LeetCode-19

开始剑指Offer II了，代码随想录说实话懒得动了，不想刷了。

954 二倍数对数组

时间：2022-04-01

听说是之前周赛的题目，就这？三次通过，就这？当然时间还是拉胯了一点，我是遍历排序后的arr，这样子需要遍历的次数比较多，而且也需要将当前值set一遍，时间开销比较大。

var canReorderDoubled = function (arr) {
    const n = arr.length;
    arr.sort((a, b) => Math.abs(a) - Math.abs(b));
    const map = new Map();
    for (let i = 0; i < n; i++) {
        map.set(arr[i], (map.get(arr[i]) || 0) + 1);
    }
    for (let i = 0; i < n; i++) {
        if (map.get(arr[i]) == 0) continue;
        const num = 2 * arr[i];
        if (!map.has(num) || map.get(num) == 0) return false;
        map.set(num, map.get(num) - 1);
    }
    return true;
};

官解还是非常的不错的，排序数组不是拿原来的数组进行排序，而是将map的keys拿来排序，这样子就相当于去重过滤了，不会出现重复的情况，所以只需要将set一次就行了。

var canReorderDoubled = function (arr) {
    const n = arr.length;
    const map = new Map();
    for (let i of arr) map.set(i, (map.get(i) || 0) + 1);
    const vals = Array.from(map.keys()).sort((a, b) => Math.abs(a) - Math.abs(b));
    for (let i of vals) {
        const num = 2 * i;
        if ((map.get(num) || 0) < map.get(i)) return false;
        map.set(num, map.get(num) - map.get(i));
    }
    return true;
};

offer II 018 有效的回文

时间：2022-04-01

别说，还挺难的，直接抄袭别人的，不想用O(n)的空间，所以这个比较合适

var isPalindrome = function (s) {
    let i = 0,
        j = s.length - 1;
    // 是否是数字或字母
    const isLetterOrDigit = (code) => {
        if (
            // 大写字母
            (code >= 97 && code <= 122) ||
            // 小写字母
            (code >= 65 && code <= 90) ||
            // 数字
            (code >= 48 && code <= 57)
        ) {
            return true;
        }
        return false;
    };
    while (i < j) {
        let ch1 = s.charCodeAt(i),
            ch2 = s.charCodeAt(j);
        if (!isLetterOrDigit(ch1)) {
            i++;
        } else if (!isLetterOrDigit(ch2)) {
            j--;
        } else {
            // 两个指针所指向的内容都是字母或数字
            ch1 = s[i].toLowerCase();
            ch2 = s[j].toLowerCase();
            // 题目要求的是忽略字母的大小写
            if (ch1 != ch2) {
                return false;
            }
            i++;
            j--;
        }
    }
    return true;
};

还有一种正则表达式，真的牛皮，用match返回数字和字母组成的数字，然后翻转判断是不是相同的。

function isPalindrome(s) {
  const chars = s.toLowerCase().match(/[0-9a-z]/g) || [];
  return chars.join('') === chars.reverse().join('');
};

offer II 019 验证回文字符串 II

时间：2022-04-01

这道题虽然是简单题，但我居然没有写出来，想复杂了，只用判断两次就行了，相当于O(2n)吧，我想一次O(n)判断出来，有点困难吧，或者if条件也不少，还是这种方法省力点。

var validPalindrome = function (s) {
    i = 0,
        j = s.length - 1;
    while (i < j) {
        if (s[i] !== s[j]) {
            return isValid(s, i + 1, j) || isValid(s, i, j - 1);
        }
        i++;
        j--;
    }
    return true;
};
function isValid(s, i, j) {
    while (i < j) if (s[i++] != s[j--]) return false;
    return true;
}

offer II 025 链表中的两数相加

时间：2022-04-02

普通思想，两个数组。反转链表就不看了，还有人用栈，确实不错，但是为啥不用数组？栈还要pop，数组直接反向相加不就行了？

var addTwoNumbers = function (l1, l2) {
    const arr1 = [];
    while (l1) {
        arr1.push(l1.val);
        l1 = l1.next;
    }
    const arr2 = [];
    while (l2) {
        arr2.push(l2.val);
        l2 = l2.next;
    }
    let n1 = arr1.length - 1,
        n2 = arr2.length - 1,
        arr = [],
        add = 0;
    while (n1 >= 0 || n2 >= 0) {
        const x = n1 >= 0 ? arr1[n1] : 0;
        const y = n2 >= 0 ? arr2[n2] : 0;
        const res = x + y + add;
        arr.push(res % 10);
        add = Math.floor(res / 10);
        n1--;
        n2--;
    }
    if (add == 1) arr.push(1);
    const prev = new ListNode(-1);
    let cur = prev;
    for (let i = arr.length - 1; i >= 0; i--) {
        cur.next = new ListNode(arr[i]);
        cur = cur.next;
    }
    return prev.next;
};

offer II 027 回文链表

时间：2022-04-02

先快慢指针找到中间的，然后翻转后面的，然后再判断两个是不是相同的，判断的时候需要注意是奇偶数的问题

var isPalindrome = function (head) {
    let mid = middleNode(head);
    let last = reverseList(mid.next);
    mid.next = null;
    return isSame(head, last);
};

const middleNode = function (head) {
    let slow = new ListNode(-1, head);
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

const reverseList = function (head) {
    let prev = null;
    let cur = head;
    while (cur != null) {
        const next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
};

const isSame = function (headA, headB) {
    while (headA && headB) {
        if (headA.val !== headB.val) return false;
        headA = headA.next;
        headB = headB.next;
    }
    if (!headA && !headB) return true;
    else if ((headA && !headA.next) || (headB && !headB.next)) return true;
    else return false;
};

直接数组，还管这么多？

var isPalindrome = function(head) {
    const vals = [];
    while (head !== null) {
        vals.push(head.val);
        head = head.next;
    }
    for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
        if (vals[i] !== vals[j]) {
            return false;
        }
    }
    return true;
};

offer II 028 展平多级双向链表

时间：2022-04-02

谢邀，这道题看起来很唬人，但是还行吧，只要想到了栈，剩下的就是好好处理细节问题就行了。

var flatten = function (head) {
    if (!head) return null;
    const st = [];
    let prev = head;
    let cur = head;
    while (cur || st.length) {
        if (cur) {
            prev = cur;
            if (cur.child) {
                cur.next && st.push(cur.next);
                cur.next = cur.child;
                cur.next.prev = cur;
                cur.child = null;
            }
        }
        else if (st.length) {
            const node = st.pop();
            cur = prev;
            cur.next = node;
            node.prev = cur;
        }
        cur = cur.next;
    }
    return head;
};

offer II 029 排序的循环链表

时间：2022-04-02

正确率20%，拉了，先找到最大值，然后判断那个数字是不是比最大值和最小值边界之内，如果是之内，去找那个数字，如果不是，啥也不干，直接添加后面就完事了。

var insert = function (head, insertVal) {
    if (!head) {
        head = new Node(insertVal)
        head.next = head;
        return head;
    }
    let cur = head;
    while (cur.next.val >= cur.val) {
        if (cur.next == head) break;
        cur = cur.next;
    }
    let prev = cur;
    if (!(insertVal > cur.val || insertVal < cur.next.val)) {
        cur = cur.next;
        while (cur.val < insertVal) {
            prev = cur;
            cur = cur.next;
        }
    }
    const node = new Node(insertVal);
    node.next = prev.next;
    prev.next = node;
    return head;
};

744 寻找比目标字母大的最小字母

时间：2022-04-03

二分法，紧急在手机上刷的，因为去玩了。

var nextGreatestLetter = function (letters, target) {
    const length = letters.length;
    if (target >= letters[length - 1]) {
        return letters[0];
    }
    let low = 0,
        high = length - 1;
    while (low < high) {
        const mid = Math.floor((high - low) / 2) + low;
        if (letters[mid] > target) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return letters[low];
};

307 区域和检索-数组可修改

时间：2022-04-04

树状数组经典用法，可惜我不会，直接copy过来，也不是很想学吧

var NumArray = function (nums) {
    this.tree = new Array(nums.length + 1).fill(0);
    this.nums = nums;
    for (let i = 0; i < nums.length; i++) {
        this.add(i + 1, nums[i]);
    }
};

NumArray.prototype.update = function (index, val) {
    this.add(index + 1, val - this.nums[index]);
    this.nums[index] = val;
};

NumArray.prototype.sumRange = function (left, right) {
    return this.prefixSum(right + 1) - this.prefixSum(left);
};

NumArray.prototype.lowBit = function (x) {
    return x & -x;
};

NumArray.prototype.add = function (index, val) {
    while (index < this.tree.length) {
        this.tree[index] += val;
        index += this.lowBit(index);
    }
};

NumArray.prototype.prefixSum = function (index) {
    let sum = 0;
    while (index > 0) {
        sum += this.tree[index];
        index -= this.lowBit(index);
    }
    return sum;
};

offer II 030 插入、删除和随机访问都是 O(1) 的容器

直接抄袭，用两个保存，一个是map，保存值和下标，另一个就是普通数组，删除的时候，需要把最后一个数顶到目前的值，因为题目没有说获取到下标，所以直接这样子比较合适。之所以不纯用哈希表，是因为还有个随机返回现有集合中的一项，需要使用O(1)的时候，哈希map倒是可以遍历，但是不能通过O(1)的方法直接返回吧。

/**
 * Initialize your data structure here.
 */
var RandomizedSet = function () {
    // numToLocation存储了每个数值及其在数组nums中的下标
    this.numToLocation = new Map();
    // 数值保存在动态数组nums中
    this.nums = [];
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
    // 如果数据集中之前已经包含该数值，则不能添加
    if (this.numToLocation.has(val)) {
        return false;
    }
    // 如果之前没有该数值，则把它添加到数组nums的尾部，并把它和它在数组中的下标添加到哈希表中
    this.numToLocation.set(val, this.nums.length);
    this.nums.push(val);
    return true;
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
    // 数据集中是否已经包含该数值，如果没有包含则不能删除
    if (!this.numToLocation.has(val)) {
        return false;
    }
    // 从哈希表中删除一个元素是O(1),
    let location = this.numToLocation.get(val);
    this.numToLocation.set(this.nums[this.nums.length - 1], location);
    this.numToLocation.delete(val);
    // 数组删除对应，这里是把数据最末位的元素覆盖要删除的元素，再把数组长度减1，通过这种技巧来达到时间复杂度为O(1)
    this.nums[location] = this.nums[this.nums.length - 1];
    this.nums.length--;
    return true;
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
    // 随机生成0到this.nums.length范围内的一个整数
    let p = parseInt(Math.random() * this.nums.length);
    return this.nums[p];
};

offer II 031 最近最少使用缓存

时间：2022-04-04

仅使用Js的map特性，就很牛逼，因为js的map是有添加的顺序的，遍历是从添加顺序的，所以获取的时候，先删除，再添加，相当于添加到最后了，然后put的时候，也这样子做，如果没有的情况下，那么容量就等于map的size，那么就先删除第一个，再添加到最后一个。

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.map = new Map();
    this.capacity = capacity;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val);
    return val;
};
/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    if (this.map.has(key)) {
        this.map.delete(key);
    }
    if (this.capacity == this.map.size) {
        for (let m of this.map) {
            this.map.delete(m[0]);
            break;
        }
    }
    this.map.set(key, value);
};

offer II 032 有效的变位词

时间：2022-04-04

和之前那题有点不一样，就是要判断是不是完全一致的情况

var isAnagram = function (s, t) {
    if (s.length != t.length) return false;
    const arr = new Array(26).fill(0);
    let flag = false;
    for (let i = 0; i < s.length; i++) {
        arr[s.charCodeAt(i) - 97]++;
        arr[t.charCodeAt(i) - 97]--;
        if (t[i] != s[i]) flag = true;
    }
    if (!flag) return false;
    for (let i of arr) if (i != 0) return false;
    return true;
};

762 二进制表示中质数个计算置位

时间：2022-04-05

直接抄了一个没有武德的写法，确实没有武德。打表永远滴神好吧。

var countPrimeSetBits = function (left, right) {
    const isSmallPrime = (x) => {
        return x == 2 || x == 3 || x == 5 || x == 7 || x == 11 || x == 13 || x == 17 || x == 19;
    };
    const bitCount = (n) => {
        return n.toString(2).match(/1/g).length;
    };
    let res = 0;
    for (let i = left; i <= right; i++) {
        if (isSmallPrime(bitCount(i))) res++;
    }
    return res;
};

offer II 033 变位词组

时间：2022-04-05

这个题解我是福气的，直接使用Object，多用，一是作为哈希表，另一个是作为返回的结果集，key和value各有用处，很牛逼的写法。

var groupAnagrams = function (strs) {
    let obj = {};
    strs.forEach((word) => {
        // 将每个字符串分割成数组进行排序，然后再变成字符串
        const key = word.split('').sort().toString();
        // 对每个key都创建一个数组，用来保存key相同的字符串
        if (!(key in obj)) {
            obj[key] = [];
        }
        obj[key].push(word);
    });
    return Object.values(obj);
};

034 外星语言是否排序

时间：2022-04-05

啊这，一次性通过，也是有点牛逼的、

var isAlienSorted = function (words, order) {
    const map = {};
    for (let i = 0; i < order.length; i++) {
        map[order[i]] = i;
    }
    for (let i = 1; i < words.length; i++) {
        const left = words[i - 1];
        const right = words[i];
        const leftLen = left.length;
        const rightLen = right.length;
        let j = 0;
        for (; j < leftLen && j < rightLen; j++) {
            if (map[left[j]] > map[right[j]]) {
                return false;
            } else if (map[left[j]] < map[right[j]]) {
                break;
            }
        }
        if ((j == leftLen || j == rightLen) && leftLen > rightLen) return false;
    }
    return true;
};

别人还有一种做法，直接把他还原成原本字母的样子，不过这种我写不来。

offer II 035 最小时间差

时间：2022-04-05

按照时和分进行排序，可以再优化一下，就只要分就行了

var findMinDifference = function (timePoints) {
    const time = timePoints.map((v) => v.split(':').map((v) => parseInt(v)));
    time.sort((a, b) => {
        if (a[0] == b[0]) return a[1] - b[1];
        else return a[0] - b[0];
    });
    time.push([time[0][0] + 24, time[0][1]]);
    let min = Infinity;
    console.log(time);
    for (let i = 1; i < time.length; i++) {
        let tmp = (time[i][0] - time[i - 1][0]) * 60;
        tmp += time[i][1] - time[i - 1][1];
        if (min > tmp) min = tmp;
    }
    return min;
};

当然也没有快多少，基本上大差不差。

var findMinDifference = function (timePoints) {
    const time = timePoints.map((v) => {
        const arr = v.split(':');
        return arr[0] * 60 + parseInt(arr[1]);
    });
    time.sort((a, b) => a - b);
    time.push(60 * 24 + time[0]);
    let min = Infinity;
    let tmp = 0;
    for (let i = 1; i < time.length; i++) {
        tmp = time[i] - time[i - 1];
        if (min > tmp) min = tmp;
    }
    return min;
};

310 最小高度树

时间：2022-04-06

这个题目难啊，直接抄的题解，理解都有点困难好吧，真的不是很好理解，但是有勉强能够理解。先找到最长的路径，然后就能找到。

var findMinHeightTrees = function (n, edges) {
    const ans = [];
    if (n === 1) {
        ans.push(0);
        return ans;
    }
    const adj = new Array(n).fill(0).map(() => new Array());
    for (const edge of edges) {
        adj[edge[0]].push(edge[1]);
        adj[edge[1]].push(edge[0]);
    }

    const parent = new Array(n).fill(-1);
    /* 找到与节点 0 最远的节点 x */
    let x = findLongestNode(0, parent, adj);
    /* 找到与节点 x 最远的节点 y */
    let y = findLongestNode(x, parent, adj);
    /* 求出节点 x 到节点 y 的路径 */
    const path = [];
    parent[x] = -1;
    while (y !== -1) {
        path.push(y);
        y = parent[y];
    }
    const m = path.length;
    if (m % 2 === 0) {
        ans.push(path[Math.floor(m / 2) - 1]);
    }
    ans.push(path[Math.floor(m / 2)]);
    return ans;
};
const findLongestNode = (u, parent, adj) => {
    const n = adj.length;
    const dist = new Array(n).fill(-1);
    dist[u] = 0;

    const dfs = (u, dist, parent, adj) => {
        for (const v of adj[u]) {
            if (dist[v] < 0) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                dfs(v, dist, parent, adj);
            }
        }
    };

    dfs(u, dist, parent, adj);
    let maxdist = 0;
    let node = -1;
    for (let i = 0; i < n; i++) {
        if (dist[i] > maxdist) {
            maxdist = dist[i];
            node = i;
        }
    }
    return node;
};

offer II 037 小行星碰撞

时间：2022-04-05

自己写出来的，有点单调栈的感觉，反正就用栈就完事了。

var asteroidCollision = function (asteroids) {
    const st = [];
    for (let i of asteroids) {
        while (st.length && i < 0 && st[st.length - 1] > 0) {
            if (0 < i + st[st.length - 1]) {
                i = 0;
            } else if (0 == i + st[st.length - 1]) {
                i = 0;
                st.pop();
            } else st.pop();
        }
        if (i != 0) st.push(i);
    }
    return st;
};

offer II 040 矩阵中最大的矩形

时间：2022-04-06

这题是039的延伸版本，只要039做出来，这道题就能出来，就是每次都需要计算height，然后每次调用039的思路，求出最大的面积，height就是当前列到最上面连续的1的个数。

var maximalRectangle = function (matrix) {
    if (matrix.length == 0 || matrix[0].length == 0) return 0;
    const n = matrix[0].length;
    const height = new Array(n).fill(0);
    let res = 0;
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] == '0') height[j] = 0;
            else height[j]++;
        }
        res = Math.max(res, largestRectangleArea(height));
    }
    return res;
};

var largestRectangleArea = function (heights) {
    // 从栈顶到栈底为单调递减的
    let res = 0;
    const st = [0];
    heights = [0, ...heights, 0]; // 数组头部加入元素0 数组尾部加入元素0
    for (let i = 1; i < heights.length; i++) {
        while (st.length && heights[i] < heights[st[st.length - 1]]) {
            const mid = st.pop();
            res = Math.max(res, (i - st[st.length - 1] - 1) * heights[mid]);
        }
        st.push(i);
    }
    return res;
};

offer II 041 滑动窗口的平均值

时间：2022-04-06

不是，就这？？？这给的示例容易炸掉吧兄弟，但是居然能通过，我还搞了半天，就想这怎么会是简单题目呢，sum不会炸吗？？？

var MovingAverage = function(size) {
  this.nums = [];
  this.capacity = size;
  this.sum = 0;
};

/** 
 * @param {number} val
 * @return {number}
 */
MovingAverage.prototype.next = function(val) {
  this.nums.push(val);
  this.sum += val;
  if (this.nums.length > this.capacity) {
    this.sum -= this.nums.shift();
  }
  return this.sum / this.nums.length;
};

796 旋转字符串

时间：2022-04-07

var rotateString = function (s, goal) {
    return s.length === goal.length && (s + s).indexOf(goal) !== -1;
};

offer II 042 最近请求次数

时间：2022-04-09

没事了，简单的

var RecentCounter = function () {
    this.nums = [];
    this.last = 0;
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function (t) {
    const nums = this.nums;
    nums.push(t);
    while (nums[this.last] < t - 3000) {
        this.last++;
    }
    // console.log(nums.length, this.last)
    return nums.length - this.last;
};

offer II 043 往完全二叉树添加节点

时间：2022-04-09

谢邀，写出来了，用的层序遍历

/**
 * @param {TreeNode} root
 */
var CBTInserter = function (root) {
    let parent = [root];
    let child = [];
    while (parent.length) {
        const len = parent.length;
        for (let i = 0; i < len; i++) {
            const node = parent[i];
            node.left && child.push(node.left);
            node.right && child.push(node.right);
        }
        const childLen = child.length;
        if (childLen > 0 && childLen == len * 2) {
            parent = child;
            child = [];
        } else {
            for (let i = Math.floor((childLen) / 2); i > 0; i--) {
                parent.shift();
            }
            break;
        }
    }
    this.parent = parent;
    this.child = child;
    this.root = root;
};

/**
 * @param {number} v
 * @return {number}
 */
CBTInserter.prototype.insert = function (v) {
    let parent = this.parent;
    let child = this.child;

    const newChild = new TreeNode(v);
    if (!parent[0].left) {
        parent[0].left = newChild;
    } else if (!parent[0].right) {
        parent[0].right = newChild;
    } else {
        parent.shift();
        if (parent.length == 0) {
            parent = child;
            child = [];
            this.parent = parent;
            this.child = child

        }

        parent[0].left = newChild;
    }
    child.push(newChild);

    return parent[0].val
};

/**
 * @return {TreeNode}
 */
CBTInserter.prototype.get_root = function () {
    return this.root;
};

offer II 047 二叉树剪枝

时间：2022-04-09

题目和示例有点区别，一个是全零，一个是不包含1，虽然两个意思一样，但是理解不同，写出来的就不一样吧，这里采用的是全零，如果当前节点是0，并且左右也是0，那么就返回null

var pruneTree = function (root) {
    if (!root) return null;
    root.left = pruneTree(root.left);
    root.right = pruneTree(root.right)
    if (root.val == 0 && !root.left && !root.right) return null;
    return root;
};

offer II 049 从根节点到叶节点的路径数字之和

时间：2022-04-09

简单，简单的很

var sumNumbers = function (root) {
    let res = 0;
    const dfs = (root, num) => {
        const tmp = num * 10 + root.val;
        if (!root.left && !root.right) res += tmp;
        root.left && dfs(root.left, tmp);
        root.right && dfs(root.right, tmp);
    };
    dfs(root, 0)
    return res;
};

offer II 050 向下的路径节点之和

时间：2022-04-09

抄的，正常思路应该是O(n2)的方法，优化方法就是用上前缀和，树的前缀和罢了。

var pathSum = function (root, targetSum) {
    const prefix = new Map();
    prefix.set(0, 1);
    const dfs = (root, sum) => {
        if (!root) return 0;
        let res = 0;
        sum += root.val;
        res = prefix.get(sum - targetSum) || 0;
        prefix.set(sum, (prefix.get(sum) || 0) + 1);
        res += dfs(root.left, sum);
        res += dfs(root.right, sum);
        prefix.set(sum, (prefix.get(sum) || 0) - 1); //这个减0的操作大可不必
        return res;
    };
    return dfs(root, 0);
};

780 到达终点

时间：2022-04-09

一开始写的正向递归，还是炸了就应该逆向找出来，确实非常的蛋疼

var reachingPoints = function(sx, sy, tx, ty) {
    while (tx > sx && ty > sy && tx != ty) {
        if (tx > ty) {
            tx %= ty;
        } else {
            ty %= tx;
        }
    }
    if (tx === sx && ty === sy) {
        return true;
    } else if (tx === sx) {
        return ty > sy && (ty - sy) % tx === 0;
    } else if (ty === sy) {
        return tx > sx && (tx - sx) % ty === 0;
    } else {
        return false;
    }
};

991 坏了的计算器

时间：2022-04-09

这道题还行吧，是这上面那题的简单版，也是要反向一下，这个倒还简单吧。

var brokenCalc = function (startValue, target) {
    let res = 0;
    while (target > startValue) {
        if (target & 1) target++;
        else target = Math.floor(target / 2);
        res++;
    }
    return startValue - target + res;
};

397 整数替换

时间：2022-04-09

什么贪心想法，尿了，真的贪好吧。反向思路就是这题的正常思路，所以也不知道怎么解。

var integerReplacement = function(n) {
    let ans = 0;
    while (n !== 1) {
        if (n % 2 === 0) {
            ++ans;
            n = Math.floor(n / 2);
        } else if (n % 4 === 1) {
            ans += 2;
            n = Math.floor(n / 2);
        } else {
            if (n === 3) {
                ans += 2;
                n = 1;
            } else {
                ans += 2;
                n = Math.floor(n / 2) + 1;
            }
        }
    }
    return ans;
};

804 唯一摩尔斯密码词

时间：2022-04-10

简单题，简单写

var uniqueMorseRepresentations = function (words) {
    const set = new Set();
    const arr = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
    for (let word of words) {
        let tmp = [];
        for (let w of word) {
            tmp.push(arr[w.charCodeAt() - 97]);
        }
        set.add(tmp.join(''));
    }
    return set.size;
};

357 统计各位数字都不同的数字个数

时间：2022-04-12

抄的，相当于找规律，这种题我基本都是死的，直接抄就完事了。

var countNumbersWithUniqueDigits = function (n) {
    if (n === 0) return 1;
    if (n === 1) return 10;
    let res = 10,
        cur = 9;
    for (let i = 0; i < n - 1; i++) {
        cur *= 9 - i;
        res += cur;
    }
    return res;
};

或者直接打表，甚至打表都不够快，真有他的。

var countNumbersWithUniqueDigits = function (n) {
    return [1, 10, 91, 739, 5275, 32491, 168571, 712891, 2345851][n]
};

806 写字符串需要的行数

时间：2022-04-12

var numberOfLines = function (widths, s) {
    let len;
    const MAXLEN = 100;
    const res = [1, 0];
    for (let i of s) {
        len = widths[i.charCodeAt() - 97];
        if (res[1] + len <= MAXLEN) {
            res[1] += len;
        } else {
            res[1] = len;
            res[0]++;
        }
    }
    return res;
};

offer II 51 节点之和最大的路径

时间：2022-04-12

抄的，虽然是困难题，但是看完题解后没有那么难了，dfs返回的是最大贡献度，就是取左右子树的最大结果+当前节点的值，但是res是取两个子树的值加上当前值的最大值，和返回值不一样。

var maxPathSum = function (root) {
    let res = Number.MIN_SAFE_INTEGER;
    const dfs = (root) => {
        if (!root) return 0;
        const left = Math.max(dfs(root.left), 0);
        const right = Math.max(dfs(root.right), 0);
        const max = left + right + root.val
        if (max > res) res = max;
        return Math.max(left, right) + root.val
    };
    dfs(root)
    return res;
};

offer II 052 展平二叉搜索树

时间：2022-04-12

这也不算简单题吧，虽然我简单写出来了，好吧，就是简单题

var increasingBST = function (root) {
    let prev = null;
    let res = null;
    const dfs = (root) => {
        root.left && dfs(root.left);
        if (!prev) {
            prev = root;
            res = root;
        } else {
            root.left = null;
            prev.right = root;
            prev = root;
        }
        root.right && dfs(root.right);
    };
    dfs(root);
    return res;
};

offer II 053 二叉搜索树中的中序后继

时间：2022-04-12

递归写一遍先，肯定有个神仙的迭代法则，应该是非常的简单，不过我写不出来

var inorderSuccessor = function (root, p) {
    let prev = null;
    let res = null;
    const dfs = (root) => {
        root.left && dfs(root.left);
        if (prev == 1) {
            res = root;
            prev = 2
            return;
        }
        if (p == root)
            prev = 1;
        root.right && dfs(root.right);
    };
    dfs(root)
    return res;
};

果然有个，简单的很，大概理解就是，中序后续肯定比目标节点大，所以至少当前节点比目标节点大，那么就记录当前节点，反复刷新就完事了。

var inorderSuccessor = function (root, p) {
    let cur = root;
    let result = null;
    while (cur) {
        if (cur.val > p.val) {
            result = cur;
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }
    return result;
};

offer II 055 二叉搜索树迭代器

时间：2022-04-12

扁平化数组，简单

var BSTIterator = function (root) {
    let arr = [];
    const dfs = (root) => {
        root.right && dfs(root.right);
        arr.push(root.val);
        root.left && dfs(root.left);
        return root;
    };
    dfs(root);
    this.arr = arr;
};

/**
 * @return {number}
 */
BSTIterator.prototype.next = function () {
    return this.arr.pop();
};

/**
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function () {
    return this.arr.length;
};

迭代法，果然有，果然也是用栈，但这这个均摊的想法又是我没想到的，相当于只做了中序遍历的做种，栈里面保存的是左中的节点，其实就是正常的中序迭代方法吧。

var BSTIterator = function(root) {
    this.cur = root;
    this.stack = [];
};

BSTIterator.prototype.next = function() {
    while (this.cur) {
        this.stack.push(this.cur);
        this.cur = this.cur.left;
    }
    this.cur = this.stack.pop();
    const ret = this.cur.val;
    this.cur = this.cur.right;
    return ret;
};

BSTIterator.prototype.hasNext = function() {
    return this.cur !== null || this.stack.length;
};