qypx の blog

机会是留给有准备的人的.

发表于 分类于

移动零（难度：简答）

1580888243775

问题的两个要求是：

  • 将所有 0 移动到数组末尾。
  • 所有非零元素必须保持其原始顺序。

这里很好地认识到这两个需求是相互排斥的，也就是说，你可以解决单独的子问题，然后将它们组合在一起以得到最终的解决方案。

方法：

  • 一个指针i从前到后遍历数组，每当遇到非0数时，令 nums[cur] = nums[i]; cur++;，cur是另一个指针（从0开始），记录当前位置。
  • 当i遍历完后，此时cur指向的位置到数组的末尾全赋为0即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void moveZeroes(int[] nums) {
        int cur = 0;

        for(int i = 0; i < nums.length; i++){
            if(nums[i]!=0){
                nums[cur] = nums[i];
                cur++;
            }
        }

        while(cur < nums.length){
            nums[cur] = 0;
            cur++;
        }

    }
}
1580890229187

复杂度

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。

发表于 分类于

最小覆盖子串（难度：困难）

1580195563488

方法：滑动窗口

算法

  1. 初始，left指针和right指针都指向s的第一个元素.

  2. 将 right指针右移，扩张窗口，直到得到一个可行窗口，亦即包含t的全部字母的窗口。

  3. 得到可行的窗口后，将left指针逐个右移，若得到的窗口依然可行，则更新最小窗口大小。

  4. 若窗口不再可行，则跳转至 2。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from collections import defaultdict
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        left = 0
        right = 0
        res = ""
        need = defaultdict(int)
        window = defaultdict(int)
        minLen = len(s)

        for i in t:
            need[i] += 1

        while right < len(s):
            window[s[right]] += 1
            while self.con(need,window):
                if len(s[left:right+1]) < minLen:
                    minLen = len(s[left:right+1])
                    res = s[left:right+1]
                window[s[left]] -= 1
                left += 1
            right += 1

        return res


    def con(self, need, window):
        for key in need.keys():
            if need[key] > window[key]:
                return False
        return True
复杂度
1580201292271

发表于 分类于

滑动窗口最大值（难度：困难）

1579702056767
1579702078067

方法一：暴力法

遍历每个滑动窗口，找到每个窗口的最大值。一共有 N - k + 1 个滑动窗口，每个有 k 个元素，于是算法的时间复杂度为 O(Nk)，表现较差。

代码
1
2
3
4
5
6
7
8
9
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) == 0:
            return nums
        res = []
        for i in range(0,len(nums)-(k-1)):
            j = i + k-1
            res.append(max(nums[i:j+1]))
        return res
1579666044377
复杂度
  • 时间复杂度：O(Nk)。其中 N 为数组中元素个数。
  • 空间复杂度：O(N−k+1)，用于输出数组。

方法二：递归

详细讲解见https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetcode-3/

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) <= 1:
            return nums
        
        n = len(nums)
        left = [0]*n
        right = [0]*n
        left[0] = nums[0]
        right[n-1] = nums[n-1]
        
        for i in range(1,n):
            # 从左到右
            if i % k == 0: 
                # block start
                left[i] = nums[i]
            else:
                left[i] = max(left[i-1], nums[i])
            
            # 从右到左
            j = n - i - 1
            if (j+1) % k == 0:
                # block end
                right[j] = nums[j]
            else:
                right[j] = max(right[j+1], nums[j])
        
        res = []
        for i in range(n-k+1):
            j = i+k-1
            res.append(max(right[i], left[j]))
        
        return res

1579669254322
复杂度

时间复杂度：O(N)，我们对长度为 N 的数组处理了 3次。

空间复杂度：O(N)，用于存储长度为 N 的 left 和 right 数组，以及长度为 N - k + 1的输出数组。

方法三：双端队列

1579703855488
1579703901936

思路：维护窗口，向右移动时左侧超出窗口的值弹出，因为需要的是窗口内的最大值，所以只要保证窗口内的值是递减的即可，小于新加入的值全部弹出。最左端即为窗口最大值

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        temp = []
        res = []

        for i,v in enumerate(nums): # i是索引，v是值
            # 左侧超出窗口的值弹出
            if i>=k and temp[0]<=i-k:
                temp.pop(0) # pop索引为0的数
            while temp and nums[temp[-1]] <= v:
                temp.pop() # pop最后一个数
            temp.append(i)
            if i>=k-1:
                res.append(nums[temp[0]])
        return res
1579704974700
复杂度

时间复杂度：O(N)，每个元素被处理两次- 其索引被添加到双向队列中和被双向队列删除。

空间复杂度：O(N)，输出数组使用了O(N−k+1) 空间，双向队列使用了 O(k)。

发表于 更新于 分类于

二叉树的中序遍历（难度：中等）

1579622453083

中序遍历：左-中-右

方法一：递归

定义一个辅助函数来实现递归。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        helper(root, res);
        return res;
    }

    public void helper(TreeNode root, List < Integer > res) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, res);
            }
            res.add(root.val);
            if (root.right != null) {
                helper(root.right, res);
            }
        }
    }
}

复杂度

时间复杂度：O(n)。递归函数 T(n) = 2 T(n/2)+1。 空间复杂度：最坏情况下需要空间O(n)，平均情况为O(logn)。

方法二：迭代

颜色标记法：

作者：hzhu212 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/ 来源：力扣（LeetCode）

其核心思想如下：

  • 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
  • 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
  • 如果遇到的节点为灰色，则将节点的值输出。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node == None:
                continue
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res

如要实现前序、后序遍历，只需要调整左右子节点的入栈顺序即可。

另一种写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack:
                return res
            root = stack.pop()
            res.append(root.val)
            root = root.right
1579622422214
复杂度

时间复杂度：O(n)。

空间复杂度：O(n)。

算法 执行用时 内存消耗 语言
方法二：迭代（另一种写法） 28 ms 13 MB Python3
方法二：迭代（颜色标价法） 36 ms 12.7 MB Python3
方法一：递归 0 ms 34.6 MB Java

发表于 更新于 分类于

二叉搜索树中第K小的元素（难度：中等）

1579620616705
1579620662544

此题与二叉树的中序遍历（难度：中等）类似，只需稍加变化。

方法一：递归

通过构造 BST 的中序遍历序列，则第 k-1 个元素就是第 k 小的元素。

7dc3fe454519e27105c5aaf57d20b26137bd77c56bb0289830bf18116627de12-file_1579413216156
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> arr = new ArrayList<>();
        inorder(root,arr);
        return arr.get(k-1);
    }

    public void inorder(TreeNode root, List arr){
        if(root!=null){
            if(root.left!=null)
                inorder(root.left, arr);
            arr.add(root.val);
            if(root.right!=null)
                inorder(root.right, arr);
        }
    }
}
1579620513520
复杂度

时间复杂度：O(N)，遍历了整个树。

空间复杂度：O(N)，用了一个数组存储中序序列。

方法二：迭代

在栈的帮助下，可以将方法一的递归转换为迭代，这样可以加快速度，因为这样可以不用遍历整个树，可以在找到答案后停止。

25159a5137867644b75f203ee1917645d2cd454d8f4871e371d7edfa67bef083-file_1579413216176
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

1579621550313
复杂度

时间复杂度：O(H+k)，其中 H指的是树的高度，由于我们开始遍历之前，要先向下达到叶，当树是一个平衡树时：复杂度为O(logN+k)。当树是一个不平衡树时：复杂度为 O(N+k)，此时所有的节点都在左子树。

空间复杂度：O(H+k)。当树是一个平衡树时：O(logN+k)。当树是一个非平衡树时：O(N+k)。

发表于 分类于

最长连续序列（难度：困难）

1579513410172

方法：哈希表（HashSet）

因为一个序列可能在 nums 数组的任意一个数字开始，我们可以枚举每个数字作为序列的第一个数字，搜索所有的可能性 （暴力法）。优化：将数组中的数字用HashSet保存，实现O(1)的时间查询，同时，我们只对 当前数字 - 1 不在哈希表里的数字，作为连续序列的第一个数字去找对应的最长序列，这是因为其他数字一定已经出现在了某个序列里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length <= 1)
            return nums.length;
            
        HashSet<Integer> hashSet = new HashSet<>();
        for(int num:nums)
            hashSet.add(num);
        
        int maxLen = 1;

        for(int i = 1; i < nums.length; i++){
            int curLen = 1;
            if(!hashSet.contains(nums[i]-1)){
                int curNum = nums[i];
                while(hashSet.contains(curNum+1)){
                    curLen++;
                    curNum++;
                }
            }
            maxLen = Math.max(maxLen,curLen);
            
        }
        return maxLen;        
    }
}
复杂度

时间复杂度：O(n)。尽管在 for 循环中嵌套了一个 while 循环，时间复杂度看起来像是二次方级别的。但其实它是线性的算法。因为只有当 curNum 遇到了一个序列的开始， while 循环才会被执行（也就是 curNum-1 不在数组 nums 里）， while 循环在整个运行过程中只会被迭代 n 次。这意味着尽管看起来时间复杂度为 O(n⋅n) ，实际这个嵌套循环只会运行O(n+n)=O(n) 次。所有的计算都是线性时间的，所以总的时间复杂度是 O(n)的。

空间复杂度：O(n)。为了实现 O(1)的查询，我们对哈希表分配线性空间，以保存 nums 数组中的 O(n)个数字。

0%