阅读 1566

找到好工作之 LeetcodeTop100(Easy) by JavaScript

记录一下 leetcode top100

该部分只记录 easy 难度,由于为 easy 难度,故基本直接放解答

1. two sum

两数和 - 找到无序数组中和为定值的两个数,返回下标

因为需要返回下标,因此先排序后用两个指针扫(前->后, 后->前)的方式(NlogN)不行。 故选用类似 hash 的形式解; key 为数组值, value 为下标

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const map = {};
    nums.forEach((num, index) => map[num] = index);
    const len = nums.length;
    for(let i = 0; i < len; i++) {
        const otherIndex = map[target - nums[i]];
        if(otherIndex && otherIndex != i) {
            return [Math.min(i, otherIndex), Math.max(i, otherIndex)]
        }
    }
};
复制代码

20. Valid Parentheses

判断输入的字符串是不是只包含(){}[ and ]

  • 必须使用相同类型的括号关闭左括号。
  • 必须以正确的顺序关闭左括号。
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const stack = [];
    const helpMap = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    for(let i = 0; i < s.length; i++) {
        const char = s[i];
        if(char in helpMap) {
            stack.push(helpMap[char]);
        } else if(char !== stack.pop()){
            return false;
        }
    }
    return stack.length === 0;
};

复制代码

21. Merge Two Sorted Lists

合并两个已排序的链表并将其作为新链表返回。新链表应该通过拼接前两个链表的节点来完成。

  • 解法一:递归
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};
复制代码
  • 解法二:循环
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    const newList = new ListNode(null);
    let newPointer = newList;
    while (l1 && l2) {
        if (l1.val < l2.val) {
            newPointer.next = l1;
            l1 = l1.next;
        } else {
            newPointer.next = l2;
            l2 = l2.next;
        }
        newPointer = newPointer.next;
    }
    if (l1) newPointer.next = l1;
    if (l2) newPointer.next = l2;
    return newList.next;
};
复制代码

35. Search Insert Position

给定排序数组和目标值,如果找到目标,则返回索引。如果没有,请返回索引按顺序插入的索引。

类似于二分查找的变种题

平时二分查找递归的写多了,这里来个不使用递归的版本

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let start = 0, end = nums.length - 1;
    let mid = Math.ceil((end + start) / 2);
    while(nums[mid] !== target) {
        if(end <= start) {
            // 如果没有找到要看看插哪里
            return nums[end] < target ? end + 1 : end;
        }
        if(nums[mid] > target) {
            // 保护一下不要变成负的
            end = Math.max(mid - 1, 0);
        } else {
            // 保护一下不要越界
            start = Math.min(mid + 1, nums.length - 1);
        }
        mid = Math.floor((end + start) / 2);
    }
    return mid;
};
复制代码

52. Maximum Subarray

经典题:找一个数组中最大子序列和

解法:从头到尾遍历每一个数组元素,如何前面元素的和为正,则加上本元素的值继续搜索;如何前面元素的和为负,则此元素开始新的和计数。以及整个过程中要注意更新和的最大值。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let cache = 0;
    let max = -Infinity;
    nums.forEach(num => {
        cache += num;
        if(cache > max) max = cache;
        if(cache < 0) cache = 0;
    })
    return max;
};
复制代码

70. Climbing Stairs

跳台阶,经典DP

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const dp = [0, 1, 2];
    for(let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n]
};
复制代码

100. Same Tree

判断俩二叉树是不是完全相同 不好的写法:利用短路等特性把代码写在一行,注意做取值保护

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    return (p || q) ? (p || {}).val === (q || {}).val && isSameTree((p || {}).left, (q || {}).left) && isSameTree((p || {}).right, (q || {}).right) : true
};
复制代码

101. Symmetric Tree

判断一颗二叉树是不是镜像 解法一:继续一行写完

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    return childIsSymmetric((root || {}).left, (root || {}).right);
};

function childIsSymmetric (left, right) {
    return (left || right) ? (left || {}).val === (right || {}).val && childIsSymmetric((left || {}).left, (right || {}).right) && childIsSymmetric((left || {}).right, (right || {}).left) : true;
}
复制代码

解法二:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(!root) return true;
    function areMirror(left, right) {
        if(!left && !right) return true;
        if((left && !right) || (right && !left)) return false;
        if(left.val != right.val) return false;
        return areMirror(left.left, right.right) && areMirror(left.right, right.left);
    }
    return areMirror(root.left, root.right);
};
复制代码

104. Maximum Depth of Binary Tree

找二叉树深度

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root, deep = 0) {
    if(!root) return deep;
    return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
};
复制代码

121. Best Time to Buy and Sell Stock

给一个数组,其中第i个元素是第i天给定股票的价格。只能进行一次买进和卖出,求最大利润

首先设定最大利润和最低价格:

  • 如果当前这一天的股票价格比最低价格还小,那就把最低价格设置为这一天的股票价格。
  • 如果最大利润比当天价格减掉最低价格还要低,那就把最大利润设置成当天价格减去最低的价格。
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if(!prices.length) return 0;
    let minPrice = Infinity, maxProfit = -Infinity;
    prices.forEach(price => {
        if(price < minPrice) {
            minPrice = price;
        }
        if(maxProfit < (price - minPrice)) {
            maxProfit = (price - minPrice);
        }
    });
    return maxProfit;
};
复制代码

136. Single Number

经典题,一行代码异或解决

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums){
    return nums.reduce((a,b) => { return a ^ b});
}
复制代码

141. Linked List Cycle

判断链表是否有环,不能使用额外空间 解法:用两个指针,快指针每次走两步,慢指针每次走一步。这样每走一次快指针比慢指针多一步,如果有环最终能够相遇。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
    let slow = head;
    let fast = head;

    while (fast) {
        slow = slow.next;
        fast = fast.next && fast.next.next;
        if (slow === fast && fast !== null) {
            return true;
        }
    }

    return false;
};
复制代码

155. Min Stack

设计一个支持pushpoptop和在恒定时间内检索最小元素的堆栈。

  • push(x) -- 将元素x推入堆栈
  • pop() --  删除堆栈顶部的元素
  • top() -- 获取顶部元素
  • getMin() -- 检索堆栈中的最小元素

最优解 - O(1):

该题要求的是实现一个栈,栈的修改元素的操作只有 pop()push(x),因此我们可以在 push 的时候维护一个作用类似于 缓存 的,记录这个时候最小元素是什么的栈 minStack。在每次 push 的时候,更新一下我们的缓存,这个时候只需要对比一下当前入栈元素和 minStack 栈顶元素,然后取小的推入 minStack 即可,代表着这个时候最小值应该是 之前栈中最小的 和 新来的 中最小的一个元素。

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = [];
    this.minStack = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    const minStackTop = this.minStack[this.minStack.length - 1];
    this.minStack.push(Math.min(x, minStackTop === undefined ? Infinity : minStackTop));
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.stack.pop();
    this.minStack.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.minStack[this.minStack.length - 1];
};

/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = Object.create(MinStack).createNew()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */
复制代码

160. Intersection of Two Linked Lists

找到两个单链表公共开头的节点。

  • 果两个链接列表根本没有交集,则返回null
  • 函数返回后,链接列表必须保留其原始结构。
  • 可以假设整个链接结构中没有任何循环。
  • 代码在O(n)时间内运行,并且只使用O(1)内存。

image.png | left | 488x165
由上图可以得知,如果要让遍历用的指针在链表公共节点入口处相遇,即两个指针走的节点一样长,只需要在 A 链表遍历完以后换到 B 链表上(走了 a + c + b 个节点),然后 B 链表出发走完了换到 A 链表上(走了 b + c + a 个节点)即可。

同时我们还要处理两个链表没有公共节点的情况:

image.png | left | 244x161

如上图,从 A 出发的指针在走了 a + b 个节点后,从 B 出发的指针也走了 b + a 个节点,因此他们此时再走一步以后就都是 undefined, 也就是说两个链表没有公共节点的话,只要判断两个指针都是 undefined 就可以知道了。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let nodeA = headA, nodeB = headB;
    while(nodeA !== nodeB) {
        nodeA = nodeA ? nodeA.next : headB;
        nodeB = nodeB ? nodeB.next : headA;
    }
    return nodeA || null;
};
复制代码

169. Majority Element

找出数组中出现次数超过 `⌊ n/2 ⌋ 的数 这个题比较有意思一点,给出如下几种方案:

  • 由于多于一半,因此可以直接排序后看中间位置上的数
  • Moore voting algorithm:`每次都找出一对不同的元素,从数组中删掉,直到数组为空或只有一种元素
  • Boyer-Moore Algorithm(多数投票算法):记录一个当前过半数变量 A 及其个数 numA ,在遍历过程中,如果当前元素和记录元素 A 相等,则 numA 加 1;如果不相等,则 numA 减 1。如果 numA 为零,则更新 A 和重置 numA 。本质是:在遍历数组时,如果numA为0,表示当前并没有候选元素,也就是说之前的遍历过程中并没有找到超过半数的元素。那么,如果超过半数的元素A存在,那么A在剩下的子数组中,出现次数也一定超过半数。因此我们可以将原始问题转化为它的子问题。这里有一个可视化的流程
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let result, count = 0
    nums.forEach(num => {
        if(result !== num) {
            if(count === 0) {
                count = 1;
                result = num;
            } else {
                count--;
            }
        } else {
            count++
        }
    });
    return result;
};
复制代码

198. House Robber

你是一名专业强盗,计划沿着一条街打家劫舍。每间房屋都储存有一定数量的金钱,唯一能阻止你打劫的约束条件是:由于房屋之间有安全系统相连,如果同一个晚上有两间相邻的房屋被闯入,它们就会自动联络警察,因此不可以打劫相邻的房屋。给定一列非负整数,代表每间房屋的金钱数,计算出在不惊动警察的前提下一晚上最多可以打劫到的金钱数。

DP:对于第i个房间我们的选择是偷和不偷

  • 如果决定是偷,则第 i-1 个房间必须不偷,那么这一步的就是 dp[i] = nums[i-1] + dp[i -2] , 假设dp[i]表示打劫到第 i 间房屋时累计取得的金钱最大值
  • 如果是不偷, 那么上一步就无所谓是不是已经偷过, dp[i] = dp[i -1]
  • 因此 dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1] )
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if(!nums.length) return 0;
    const dp = [nums[0]];
    for(let i = 1; i < nums.length; i++){
        dp[i] = Math.max(dp[i - 1], (dp[i - 2] || 0) + nums[i]);
    }
    return dp[nums.length - 1];
};
复制代码

206. Reverse Linked List

反转链表

可以老老实实的循环/递归:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    if (!head) return head;
    let start = head;
    let end = head
    while (end.next) {
        const node = end.next;
        end.next = node.next;
        node.next = start;
        start = node;
    }
    return start;
}
复制代码

也可以骚操作一下:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head, pre) {
    if(!head) return head
    const next = head.next;
    head.next = pre || null
    return next ? reverseList(next, head) : head;
};
复制代码

226. Invert Binary Tree

反转二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(!root) return [];
    [root.left, root.right] = [root.right, root.left];
    invertTree(root.left);
    invertTree(root.right);
    return root
};
复制代码

234. Palindrome Linked List

判断一个链表是不是回文,要求 O(n) 时间, O(1) 空间

本题暴力解法就是遍历完链表后转为字符串,然后看是不是回文,符合时间复杂度要求,但是不符合空间复杂度要求

要求 O(1) 的空间,那就只能从链表本身动手了。首先判断回文无非就是从两边到中间或者从中间到两边。由于我们可以对链表本身动手,那就考虑让链表能够倒着访问(因为要求O(1)空间,所以不能直接改造为双向链表)。由于我们只能让链表顺着一个方向走,所以可以想到选择从中间到两边的方式,左边的向前(pre),右边的向后(next)。

那么我们如何找到中间的节点呢 - 中间节点即为链表的一半,那我们使用一个快指针一次走两步,一个慢指针一次走一步,那么快指针走到尾时,慢指针应该走到链表中间。同时要注意区分链表长度是奇数还是偶数:如果是奇数的话,正中间的节点不需要做判断,应该用它前后两个节点开始比较。

最后的代码如下:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    if(!head) return true;
    if(!head.next) return true;
    let fast = head.next, slow = head;
    let pair = null;
    while(fast != null && fast.next != null) {
        slow.next.pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    if(!fast || fast.next) {
        // 奇数
        pair = slow.next;
        slow = slow.pre;
    } else {
        // 偶数
        pair = slow.next;
    }
    while(pair) {
        if(pair.val !== slow.val) return false;
        pair = pair.next;
        slow = slow.pre;
    }
    return true;
};
复制代码

283. Move Zeroes

给定一个数组nums,写一个函数将所有0移动到它的末尾,同时保持非零元素的相对顺序。 额外要求:

  • 您必须在不制作数组副本的情况下就地执行此操作
  • 最小化操作总数。 思路:
  • 最小化操作:遍历一遍的过程中操作完,且不需要额外移动操作
  • 记 zero 的个数为 zeroesNums ,然后将每一个非零的数向前移动 zeroesNums ,最后在数组末尾填上 zero
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let zeroesNums = 0;
    nums.forEach((num, index) => {
        if(num === 0) {
            zeroesNums++;
        } else {
            nums[index - zeroesNums] = num;
        }
    });
    for(let i = nums.length - 1; zeroesNums > 0; i--) {
        nums[i] = 0;
        zeroesNums--;
    }
};
复制代码

437. Path Sum III

给一颗每个节点都是整数(可正可负)的二叉树,求有多少条路径加起来等于一个给定值。注意,路径不需要在根或叶子处开始或结束,但必须向下(即仅从父节点行进到子节点)。

解法一: 暴力解,使用 BFS 和递归来搜索符合条件的路径。需要注意的是这种方法没有利用任何缓存,即计算每条路径和的时候都重新遍历了所有路径节点。时间复杂度为 O(n²)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    if(!root) return 0;
    let result = 0;
    const queue = [root];
    while(stack.length) {
        const node = queue.shift();
        result += reslove(node, sum);
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
    return result
};

function reslove(root, sum) {
    if(!root) return 0;
    let result = 0;
    if(sum === root.val) result++;
    return result + reslove(root.left, sum - root.val) + reslove(root.right, sum - root.val);
}
复制代码

解法二: 如果不想用 queue,那也可以直接用递归来做搜索

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    if(!root) return 0;
    return reslove(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
};

function reslove(root, sum) {
    if(!root) return 0;
    return ((sum === root.val) ? 1 : 0) + reslove(root.left, sum - root.val) + reslove(root.right, sum - root.val);
}
复制代码

解法三(O(n)): 在前两种解法中,我们自顶而下重复遍历了每层节点(第一层被遍历一次,第二层被遍历两次,……)。这个时候我们就该想办法利用缓存来减少遍历次数。

因此便有了如下 O(n) 复杂度的解法(思路写在了注释中了)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    // 缓存
    const hashMap = {};
    let currentSum = 0;
    return pathSumRecursive(root, currentSum, hashMap, sum);
};

function pathSumRecursive(node, currentSum, hashMap, target) {
    if (!node) {
        return 0;
    }

    const newCurrentSum = currentSum + node.val;
    // 看一看能不能利用之前的缓存,巧妙的在一次遍历中算出了所有线段
    // 当前路径和 - 目标值 —— 本质是看 中间有没有一段路径和 等于 目标值
    // 比如 2 - 5 - 3 的路径, 目标为 8,那么在 3 这个节点时,路径和为 10 , 减去目标值8 后为 2, 之前路径上有1条路线和为 2,因此中间有一段和为目标值 8
    let totalPaths = hashMap[newCurrentSum - target] || 0;
    
    if (newCurrentSum === target) {
        totalPaths++;
    }
    // 更新一下缓存
    if (hashMap[newCurrentSum]) {
        hashMap[newCurrentSum]++;
    } else {
        hashMap[newCurrentSum] = 1;
    }

    totalPaths += pathSumRecursive(node.left, newCurrentSum, hashMap, target);
    totalPaths += pathSumRecursive(node.right, newCurrentSum, hashMap, target);
    
    // 由于是共用一个缓存,因此遍历完后续节点后,要在退回上一层的时候把自身从缓存中删掉,来保证缓存数据的正确性(只应该有之前路径的)
    hashMap[newCurrentSum]--;
    return totalPaths;
}
复制代码

438. Find All Anagrams in a String

在字符串中寻找同构体:给定一个字符串s和一个非空字符串p,找到s中p的同构体的所有起始索引。什么是同构体:两个字符串字母一样,字母在字符串中的顺序可能不一样,比如 ab 和 ba 是同构的

解法一:

对于这个首先想到的是利用缓存来提高效率,这里我们先才用 Map 的形式做映射。同时使用滑动窗口 - 两个指针(下标)来指向当前子串。然后从前往后扫,来通过 Map 看是不是匹配。如果

  • 当前字符在我们的 Map 中有,但是已经被匹配完了,则需要把指向开头的指针向后扫,直到遇见同样的字符。
  • 当前字符在我们的 Map 中根本没有,则意味着到这个字符为止都不会有符合条件的字串,因此需要将 Map 恢复后,从当前字符的下一个开始重新寻找
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    const targetMap = {};
    // 构建map
    for(let char of p) {
        if(targetMap[char]) {
            targetMap[char]++;
        } else {
            targetMap[char] = 1;
        }
    }
    let start = 0;
    let cacheLen = p.length;
    const result = [];
    for(let i = 0; i < s.length; i++) {
        const char = s[i];
        // 如果 char 还有
        if(targetMap[char]) {
            targetMap[char]--;
            cacheLen--;
            // 如果都匹配上了
            if(cacheLen === 0) {
                result.push(start); // 推进去
                // 所有的向前移动一位
                targetMap[s[start]]++; 
                start++;
                cacheLen++;
            }
        } else if(targetMap[char] === 0) {
            // char 有,但是超过个数了,就要向前走把char去掉一个
            while(s[start] !== char) {
                targetMap[s[start]]++;
                start++;
                cacheLen++;
            }
            start++;
        } else {
            // char 根本没有,就跳过之前这段
            while(start < i) {
                targetMap[s[start]]++;
                start++;
            }
            start++;
            cacheLen = p.length;
        }
    }
    return result;
};
复制代码

解法二: 上图中用 Obj 做 Mapping,我们也可以用数组结合字符下标来做 Mapping

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s2, s1) {
    const map = Array(128).fill(0);
    let start = 0,
        end = 0,
        counter = s1.length;
    const res = [];
    for (let i = 0; i < s1.length; ++i) {
        map[s1.charCodeAt(i)]++;
    }
    while (end < s2.length) {
        if (map[s2.charCodeAt(end)] > 0) {
            counter--;
        }
        map[s2.charCodeAt(end)]--;
        end++;
        while (counter == 0) {
            if (end - start == s1.length) {
                res.push(start);
            }
            if (map[s2.charCodeAt(start)] == 0) {
                counter++;
            }
            map[s2.charCodeAt(start)]++;
            start++;
        }
    }
    return res;
};
复制代码

448. Find All Numbers Disappeared in an Array

常规解法:因为题目上给出条件说数组里的数字都在 [1, n],且要求不适用额外空间,因此可以想到该题为套路题:对原位置上的数字移动/加减/位运算等解法。 此题常规可以选用反转对应位置上数字的方法:把出现的数字的对应位上的数字变为负数,然后遍历找出那些正数,其下标+1则为没有出现过的数字

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    nums.forEach(num => {
        num = Math.abs(num);
        if(nums[num - 1] > 0) {
            nums[num - 1] = -nums[num - 1]
        }
    });
    const result = [];
    nums.forEach((num, index) => {
        if(num > 0) {
            result.push(index + 1);
        }
    });
    return result;
};
复制代码

位运算骚操作版: 首先需要简单理解几个位运算是干什么的:

  • JavaScript 中位运算将其操作数(operands)当作32位的比特序列,有符号数最左比特位为1
  • 1 << 31:变成 10000000000000000000000000000000
  • 1 << 31 - 1 则变成 01111111111111111111111111111111
  • 与1 << 31 进行 | 运算,则会把一个数(无论正负)变成负数(只修改符号位)
  • 与1 << 31 - 1 进行 & 运算,则会把一个数(无论正负)变成正数(只修改符号位) 该解法用以上方式避开对符号的判断
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    for (var i = 0; i < nums.length; i++) {
        nums[(nums[i] & ((1 << 31) - 1)) - 1] |= (1 << 31);
        //                 统一正负数运算            变成负数                               
    }
    
    ans = [];
    
    for (var i = 0; i < nums.length; i++) {
        // 如果不是负数,就推进去
        if ((nums[i] & (1 << 31)) != (1 << 31))
            ans.push(i+1);
    }
    
    return ans;
};
复制代码

461. Hamming Distance

Hamming Distance 表示两个等长字符串在对应位置上不同字符的数目,也度量了通过替换字符的方式将字符串x变成y所需要的最小的替换次数。

1.常规解法:转成二进制以后一位一位的算,需要手动补位或手动判断 undefined

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
    let binaryX = x.toString(2);
    let binaryY = y.toString(2);
    const len = Math.max(binaryX.length, binaryY.length);
    if (binaryX.length < len) {
        binaryX = binaryX.padStart(len, '0')
    } else {
        binaryY = binaryY.padStart(len, '0')
    };
    let result = 0;
    for (let i = len - 1; i >= 0; i--) {
        if (binaryX[i] !== (binaryY[i])) {
            result++
        }
    }
    return result;
};

复制代码

2.位运算:按位异或,不需要考虑补长度,更简洁

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function (x, y) {
    var res = x ^ y;
    var count = 0;
    while (res != 0) {
        if (res % 2 == 1) count++;
        res = Math.floor(res / 2); // res = res >> 1;
    }
    return count;
};
复制代码

538. Convert BST to Greater Tree

二叉搜索树上的每一个节点要加上所有大于他的节点的值:原始BST的每个 key 都更改为原始 key 加上大于BST中原始 key 的所有 key 的总和。

解法一:

  • BST的性质如下
    • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
    • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
    • 它的左、右子树也分别为二叉排序树。
  • 使用 右->中->左的顺序从大到小遍历,并利用 cacheVal 来缓存比当前节点大的值来达到 O(n) 的时间复杂度
  • 在递归中进行 cacheVal 的传递而不是在外层保存该值(麻烦一点,因为需要处理右子树最左节点:代码29行
  • 因为右子树最左节点的只是除了当前节点以外最小的,所以右子树最左节点的值为最大的(所有比当前节点大的节点加起来的值)。因此当前节点只需要加上右子树最左节点的值即可
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {
    if(root) {
        converVal(root);
        return root;
    } else {
        return [];
    }
};

function converVal(root, cacheVal = 0) {
    if(root.right) {
        cacheVal = converVal(root.right, cacheVal);
    }
    root.val += cacheVal;
    cacheVal = root.val;
    if(root.left) {
        // 处理右子树最左节点,返回给上一层递归来使用(此时右子树最左节点为上一层节点需要加的值)
        return converVal(root.left, cacheVal);
    } 
    return root.val;
}
复制代码

解法二:把解法一中的 cacheVal 提出来放在外围搞一个闭包,然后就不用每次递归传进去了,这样只需要从大到小遍历即可,简单易懂。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {
    let sum = 0;
    
    return function inner(root) {
        if (root == null) return null;
        inner(root.right);
        root.val += sum;
        sum = root.val;
        inner(root.left);
        return root;
    }(root);
};
复制代码

543. Diameter of Binary Tree

给定二叉树,计算树的直径长度 - 二叉树的直径是树中任意两个节点之间最长路径的长度。此路径可能会也可能不会通过根节点。

递归,因为是寻找一条最长的路径,因此分成两个情况考虑:

  • 寻找当前子树左子树和右子树单侧最长路径,并返回给上一层使用
  • 返回当前子树最长路径(左子树最长路径 + 当前根节点(1) + 右子树最长路径给上一层使用

最后找出这两者更大的一个即可

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    if(!root) return 0;
    // 返回一个最大的
    return Math.max(...diameterOfSubtree(root)) - 1;
};
function diameterOfSubtree(root) {
    if(!root.left && !root.right) return [1, 1];
    let left = 0, leftBig = 0, right = 0, rightBig = 0;
    if(root.left) [left, leftBig] = diameterOfSubtree(root.left);
    if(root.right) [right, rightBig] = diameterOfSubtree(root.right);
    // 当前子树最长路径
    const cacheBig = Math.max(leftBig, rightBig, left + right + 1);
    return [1 + Math.max(left, right), cacheBig];
}

复制代码

572. Subtree of Another Tree

判断一棵树是不是另一颗树的子结构

解法一:直接递归看一下是不是子树,但这样有重复遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} s
 * @param {TreeNode} t
 * @return {boolean}
 */
var isSubtree = function (s, t) {
    return !!(subtree(s, t) || 
            (s.left && isSubtree(s.left, t)) || 
            (s.right && isSubtree(s.right, t)));
};
function subtree(s, t) {
    if (!s && !t) return true;
    return ((s || {}).val === (t || {}).val) && 
            subtree(s.left, t.left) && 
            subtree(s.right, t.right);
}
复制代码

解法二:前序遍历树,存成字符串,然后看看 source 里面是不是包含 target 即可

var isSubtree = function(s, t) {
  let string1 = {str: ""};
  let string2 = {str: ""};
  treeString(s, string1);
  treeString(t, string2);

  return string1.str.includes(string2.str);
}

function treeString(root, string) {
  if (!root) {
    string.str += "X";
    return;
  }
  string.str += `,${root.val},`
  treeString(root.left, string);
  treeString(root.right, string);
}
复制代码

581. Shortest Unsorted Continuous Subarray

最短未排序连续子数组:给定一个整数数组,您需要找到一个最短的连续的子数组,要求是如果序对此子数组进行升序排序后,整个数组也将按升序排序。

第一种简单的方法是把数组进行排序,那么原数组和新数组不一样的个数即为界限,但是这种的复杂度为 O(nlgn) (排序后遍历)

或者我们可以用两个指针,一个从前向后,一个从后向前

  • 从前向后的寻找最后一个不为最大值的索引
  • 从后向前的寻找第一个不为最小值的索引

然后就能得出哪一段是没有按照升序排序的了

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
    let last = 0, first = -1, max = -Infinity, min = Infinity;
    for(let i = 0, j = nums.length - 1; j >= 0; j--, i++){
        max = Math.max(max, nums[i]);
        if(nums[i] !== max) first = i;
        
        min = Math.min(min, nums[j]);
        if(nums[j] !== min) last = j;
    }
    return first - last + 1;
};
复制代码

617. Merge Two Binary Trees

该题有疑似有恶性 bug - testcase:

Input: [] []
Expected: []
Output: null
复制代码

递归:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}
 */
var mergeTrees = function(t1, t2) {
  if (!t1) {
    return t2;
  }
  if (!t2) {
    return t1;
  }
  t1.val += t2.val;
  t1.left = mergeTrees(t1.left, t2.left);
  t1.right = mergeTrees(t1.right, t2.right);
  return t1;
};
复制代码

非递归:利用栈加树的层次遍历写法

var mergeTrees = function (t1, t2) {
    if (t1 === null) {
        return t2;
    }
    const stack = [];
    stack.push([t1, t2]);
    while (stack.length !== 0) {
        const t = stack.pop();
        if (t[0] === null || t[1] === null) {
            continue;
        }
        t[0].val += t[1].val;
        if (t[0].left === null) {
            t[0].left = t[1].left;
        } else {
            stack.push([t[0].left, t[1].left]);
        }
        if (t[0].right === null) {
            t[0].right = t[1].right;
        } else {
            stack.push([t[0].right, t[1].right]);
        }
    }
    return t1;
};
复制代码
关注下面的标签,发现更多相似文章
评论