消失的两个数字

面试题 17.19. 消失的两个数字

难度困难34

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1:

1
2
输入: [1]
输出: [2,3]

示例 2:

1
2
输入: [2,3]
输出: [1,4]

提示：

  • nums.length <= 30000

原地hash

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
35
36
37
38
class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length;

        int []res = new int[2];
        int cnt = 0;
        boolean n1 = false,n2 = false;
		
        // 对原数组原地hash
        for(int i=0;i<n;i++){
            int index = Math.abs(nums[i])-1;
            if(index < n){
                nums[index] = -nums[index];
            }else if(index==n){
                n1 = true;
            }else if(index==n+1){
                n2 = true;
            }
        }
		// 正数的位置的index就是消失的数字
        for(int i=0;i < n;i++){
            if(nums[i] > 0){
                res[cnt++] = i+1;
            }
        }
        // 如果消失的是大于n的数字，需要在这里处理
        if(!n1&&!n2){
            res[0] = n+1;
            res[1] = n+2;
        }else if(!n1){
            res[1] = n+1;
        }else if(!n2){
            res[1] = n+2;
        }

        return res;
    }
}

展开全文 >>

找出和为指定值的下标对

5761. 找出和为指定值的下标对

给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：

  1. 累加 ，将一个正整数加到 nums2 中指定下标对应元素上。
  2. 计数 ，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目（0 <= i < nums1.length 且 0 <= j < nums2.length）。

实现 FindSumPairs 类：

  • FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1 和 nums2 初始化 FindSumPairs 对象。
  • void add(int index, int val) 将 val 加到 nums2[index] 上，即，执行 nums2[index] += val 。
  • int count(int tot) 返回满足 nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
输出：
[null, 8, null, 2, 1, null, null, 11]

解释：
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ，下标对 (5,1), (5,5) 满足 3 + 4 = 7
findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // 返回 2 ；下标对 (5,2), (5,4) 满足 3 + 5 = 8
findSumPairs.count(4);  // 返回 1 ；下标对 (5,0) 满足 3 + 1 = 4
findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // 返回 11 ；下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 满足 2 + 5 = 7 ，下标对 (5,3), (5,5) 满足 3 + 4 = 7

提示：

  • 1 <= nums1.length <= 1000
  • 1 <= nums2.length <= 105
  • 1 <= nums1[i] <= 109
  • 1 <= nums2[i] <= 105
  • 0 <= index < nums2.length
  • 1 <= val <= 105
  • 1 <= tot <= 109
  • 最多调用 add 和 count 函数各 1000 次

两数之和

实际上是两数之和的变种，只是加入HashMap中的数字是会变化的，需要在add的时候更新HashMap，这样的话就跟两数之和没什么区别了。

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
35
36
37
38
39
40
41
42
43
44
45
46
class FindSumPairs {

    int[] nums1;
    int[] nums2;

    Map<Integer, Integer> map = new HashMap<>();
    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        for (int i = 0; i < nums2.length; i++) {
            map.put(nums2[i], map.getOrDefault(nums2[i], 0) + 1);
        }
    }

    public void add(int index, int val) {
        int key = nums2[index];
        int v = map.get(key);
        if (v > 1) {
            map.put(key, v - 1);
        } else {
            map.remove(key);
        }
        nums2[index] += val;
        int nKey = nums2[index];
        map.put(nKey, map.getOrDefault(nKey, 0) + 1);

    }

    public int count(int tot) {
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            int val = tot - nums1[i];
            if (map.containsKey(val)) {
                res += map.get(val);
            }
        }
        return res;
    }
}

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs obj = new FindSumPairs(nums1, nums2);
 * obj.add(index,val);
 * int param_2 = obj.count(tot);
 */

展开全文 >>

找出所有自己的异或总和再求和

5759. 找出所有子集的异或总和再求和

一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。

  • 例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。

给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。

注意：在本题中，元素 相同 的不同子集应 多次 计数。

数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [1,3]
输出：6
解释：[1,3] 共有 4 个子集：
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [5,1,6]
输出：28
解释：[5,1,6] 共有 8 个子集：
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 = 4 。
- [5,6] 的异或总和为 5 XOR 6 = 3 。
- [1,6] 的异或总和为 1 XOR 6 = 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3：

1
2
3
输入：nums = [3,4,5,6,7,8]
输出：480
解释：每个子集的全部异或总和值之和为 480 。

提示：

  • 1 <= nums.length <= 12
  • 1 <= nums[i] <= 20

子集

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
class Solution {
    public int subsetXORSum(int[] nums) {
        subsets(nums);
        int res = 0;
        for (List<Integer> list : ans) {
            int v = 0;
            for (int val : list) {
                v = v ^ val;
            }
            res += v;
        }
        return res;
    }

    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        // 子集的总个数是2^n,所以1左移n位就可以了
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            // 对于每个数字如果当前数字的index与当前的mask相与不为0,那么添加当前的数字
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}

展开全文 >>

构成交替字符串需要的最小交换次数

5760. 构成交替字符串需要的最小交换次数

难度中等0

给你一个二进制字符串 s ，现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数，如果无法完成转化，返回 -1 。

交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100" 不是。

任意两个字符都可以进行交换，不必相邻 。

示例 1：

1
2
3
输入：s = "111000"
输出：1
解释：交换位置 1 和 4："111000" -> "101010" ，字符串变为交替字符串。

示例 2：

1
2
3
输入：s = "010"
输出：0
解释：字符串已经是交替字符串了，不需要交换。

示例 3：

1
2
输入：s = "1110"
输出：-1

提示：

  • 1 <= s.length <= 1000
  • s[i] 的值为 '0' 或 '1'

奇偶性+找规律

  • 当字符串的长度是偶数的时候:

    1. 统计当前字符串中不满足 偶数位置为1,奇数位置为0的字符的数量n1
    2. 统计当前字符串中不满足 偶数位置为0，奇数位置为1的字符的数量n2
    3. 答案就是Math.min(n1,n2)/2

  • 当字符的长度是奇数的时候(数量多的那个数字一定是字符串的第一个字符):

    • 当1的数量多于0的数量的时候(此时第一个数字应当是1，此时偶数位置为1,奇数位置为0)

      • 统计当前字符串中不满足偶数位置为1，偶数位置为0的字符的数量，答案就是该数量除以2

    • 当0的数量多于1的数量的时候(此时第一个数字应当是0，此时偶数位置为0，奇数位置为1)

      • 统计当前字符串中不满足偶数位置为0,奇数位置为1的字符的数量,答案就是该数量除以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
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int minSwaps(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int zeroCnt = 0;
        int oneCnt = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == '0') {
                zeroCnt++;
            } else {
                oneCnt++;
            }
        }
        if (Math.abs(oneCnt - zeroCnt) > 1) return -1;
        int cnt1 = 0, cnt2 = 0;
        int res = Integer.MAX_VALUE;
        
        if (zeroCnt <= oneCnt) {
            for (int i = 0; i < n; i++) {
                // 第一个字符是‘1’,此时偶数位置为1,奇数位置为0
                // 统计当前字符串中不满足偶数位置为1，奇数位置为0的字符的数量
                if (i % 2 == arr[i] - '0') {
                    cnt1++;
                }
            }
            res = Math.min(res, cnt1 / 2);
        }
        
        if (zeroCnt >= oneCnt) {
            for (int i = 0; i < n; i++) {
                // 第一个字符是'0'，此时偶数位置为0，奇数位置为1
                // 不满足偶数位置为0,奇数位置为1的字符的数量
                if (i % 2 != arr[i] - '0') {
                    cnt2++;
                }
            }
            res = Math.min(res, cnt2 / 2);
        }
        return res;
    }
}

展开全文 >>

数组中两个数的最大异或值

421. 数组中两个数的最大异或值

难度中等262

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

进阶：你可以在 O(n) 的时间解决这个问题吗？

示例 1：

1
2
3
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：

1
2
输入：nums = [0]
输出：0

示例 3：

1
2
输入：nums = [2,4]
输出：6

示例 4：

1
2
输入：nums = [8,10,2]
输出：10

示例 5：

1
2
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

提示：

  • 1 <= nums.length <= 2 * 104
  • 0 <= nums[i] <= 2^31 - 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    // 最高位的二进制位编号为 30
    static final int HIGH_BIT = 30;

    public int findMaximumXOR(int[] nums) {
        int x = 0;
        for (int k = HIGH_BIT; k >= 0; --k) {
            Set<Integer> seen = new HashSet<Integer>();
            // 将所有的 pre^k(a_j) 放入哈希表中
            for (int num : nums) {
                // 如果只想保留从最高位开始到第 k 个二进制位为止的部分
                // 只需将其右移 k 位
                seen.add(num >> k);
            }

            // 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
            // 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1
            int xNext = x * 2 + 1;
            boolean found = false;
            
            // 枚举 i
            for (int num : nums) {
                if (seen.contains(xNext ^ (num >> k))) {
                    found = true;
                    break;
                }
            }

            if (found) {
                x = xNext;
            } else {
                // 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0
                // 即为 x = x*2
                x = xNext - 1;
            }
        }
        return x;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/solution/shu-zu-zhong-liang-ge-shu-de-zui-da-yi-h-n9m9/
来源：力扣（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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
    // 字典树的根节点
    Trie root = new Trie();
    // 最高位的二进制位编号为 30
    static final int HIGH_BIT = 30;

    public int findMaximumXOR(int[] nums) {
        int n = nums.length;
        int x = 0;
        for (int i = 1; i < n; ++i) {
            // 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
            add(nums[i - 1]);
            // 将 nums[i] 看作 ai，找出最大的 x 更新答案
            x = Math.max(x, check(nums[i]));
        }
        return x;
    }

    public void add(int num) {
        Trie cur = root;
        for (int k = HIGH_BIT; k >= 0; --k) {
            int bit = (num >> k) & 1;
            if (bit == 0) {
                if (cur.left == null) {
                    cur.left = new Trie();
                }
                cur = cur.left;
            }
            else {
                if (cur.right == null) {
                    cur.right = new Trie();
                }
                cur = cur.right;
            }
        }
    }

    public int check(int num) {
        Trie cur = root;
        int x = 0;
        for (int k = HIGH_BIT; k >= 0; --k) {
            int bit = (num >> k) & 1;
            if (bit == 0) {
                // a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
                if (cur.right != null) {
                    cur = cur.right;
                    x = x * 2 + 1;
                } else {
                    cur = cur.left;
                    x = x * 2;
                }
            } else {
                // a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
                if (cur.left != null) {
                    cur = cur.left;
                    x = x * 2 + 1;
                } else {
                    cur = cur.right;
                    x = x * 2;
                }
            }
        }
        return x;
    }
}

class Trie {
    // 左子树指向表示 0 的子节点
    Trie left = null;
    // 右子树指向表示 1 的子节点
    Trie right = null;
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/solution/shu-zu-zhong-liang-ge-shu-de-zui-da-yi-h-n9m9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

旋转盒子

5744. 旋转盒子

给你一个 m x n 的字符矩阵 box ，它表示一个箱子的侧视图。箱子的每一个格子可能为：

  • '#' 表示石头
  • '*' 表示固定的障碍物
  • '.' 表示空位置

这个箱子被 顺时针旋转 90 度 ，由于重力原因，部分石头的位置会发生改变。每个石头会垂直掉落，直到它遇到障碍物，另一个石头或者箱子的底部。重力 不会 影响障碍物的位置，同时箱子旋转不会产生惯性 ，也就是说石头的水平位置不会发生改变。

题目保证初始时 box 中的石头要么在一个障碍物上，要么在另一个石头上，要么在箱子的底部。

请你返回一个 n x m的矩阵，表示按照上述旋转后，箱子内的结果。

示例 1：

img

1
2
3
4
输入：box = [["#",".","#"]]
输出：[["."],
      ["#"],
      ["#"]]

示例 2：

img

1
2
3
4
5
6
输入：box = [["#",".","*","."],
            ["#","#","*","."]]
输出：[["#","."],
      ["#","#"],
      ["*","*"],
      [".","."]]

示例 3：

img

1
2
3
4
5
6
7
8
9
输入：box = [["#","#","*",".","*","."],
            ["#","#","#","*",".","."],
            ["#","#","#",".","#","."]]
输出：[[".","#","#"],
      [".","#","#"],
      ["#","#","*"],
      ["#","*","."],
      ["#",".","*"],
      ["#",".","."]]

提示：

  • m == box.length
  • n == box[i].length
  • 1 <= m, n <= 500
  • box[i][j] 只可能是 '#' ，'*' 或者 '.' 。

暴力模拟

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
35
class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length;
        int n = box[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (box[i][j] == '#') {
                    move(box, i, j);
                }
            }
        }
        char[][] res = new char[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[j][m - i - 1] = box[i][j];
            }
        }

        return res;
    }

    public void move(char[][] box, int i, int j) {
        int col = j + 1;
        boolean flag = false;
        for (; col < box[0].length && box[i][col] == '.'; col++) {
            flag = true;
        }

        if (flag) {
            box[i][j] = '.';
            col--;
            box[i][col] = '#';
        }
    }
}

展开全文 >>

增长的内存泄漏

5743. 增长的内存泄露

显示英文描述

我的提交返回竞赛

  • 通过的用户数1725
  • 尝试过的用户数1761
  • 用户总通过次数1732
  • 用户总提交次数2200
  • 题目难度**Medium**

给你两个整数 memory1 和 memory2 分别表示两个内存条剩余可用内存的位数。现在有一个程序每秒递增的速度消耗着内存。

在第 i 秒（秒数从 1 开始），有 i 位内存被分配到 剩余内存较多 的内存条（如果两者一样多，则分配到第一个内存条）。如果两者剩余内存都不足 i 位，那么程序将 意外退出 。

请你返回一个数组，包含 [crashTime, memory1crash, memory2crash] ，其中 crashTime是程序意外退出的时间（单位为秒）， memory1crash 和 memory2crash 分别是两个内存条最后剩余内存的位数。

示例 1：

1
2
3
4
5
6
输入：memory1 = 2, memory2 = 2
输出：[3,1,0]
解释：内存分配如下：
- 第 1 秒，内存条 1 被占用 1 位内存。内存条 1 现在有 1 位剩余可用内存。
- 第 2 秒，内存条 2 被占用 2 位内存。内存条 2 现在有 0 位剩余可用内存。
- 第 3 秒，程序意外退出，两个内存条分别有 1 位和 0 位剩余可用内存。

示例 2：

1
2
3
4
5
6
7
8
9
输入：memory1 = 8, memory2 = 11
输出：[6,0,4]
解释：内存分配如下：
- 第 1 秒，内存条 2 被占用 1 位内存，内存条 2 现在有 10 位剩余可用内存。
- 第 2 秒，内存条 2 被占用 2 位内存，内存条 2 现在有 8 位剩余可用内存。
- 第 3 秒，内存条 1 被占用 3 位内存，内存条 1 现在有 5 位剩余可用内存。
- 第 4 秒，内存条 2 被占用 4 位内存，内存条 2 现在有 4 位剩余可用内存。
- 第 5 秒，内存条 1 被占用 5 位内存，内存条 1 现在有 0 位剩余可用内存。
- 第 6 秒，程序意外退出，两个内存条分别有 0 位和 4 位剩余可用内存。

提示：

  • 0 <= memory1, memory2 <= 2^31 - 1

暴力模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] memLeak(int memory1, int memory2) {
        int i = 1;
        while (i <= memory1 || i <= memory2) {
            if (memory1 >= memory2) {
                memory1 -= i;
            } else {
                memory2 -= i;
            }
            i++;
        }
        return new int[]{i, memory1, memory2};
    }
}

展开全文 >>

将句子排序

5742. 将句子排序

一个 句子 指的是一个序列的单词用单个空格连接起来，且开头和结尾没有任何空格。每个单词都只包含小写或大写英文字母。

我们可以给一个句子添加 从 1 开始的单词位置索引 ，并且将句子中所有单词 打乱顺序 。

  • 比方说，句子 "This is a sentence" 可以被打乱顺序得到 "sentence4 a3 is2 This1" 或者 "is2 sentence4 This1 a3" 。

给你一个 打乱顺序 的句子 s ，它包含的单词不超过 9 个，请你重新构造并得到原本顺序的句子。

示例 1：

1
2
3
输入：s = "is2 sentence4 This1 a3"
输出："This is a sentence"
解释：将 s 中的单词按照初始位置排序，得到 "This1 is2 a3 sentence4" ，然后删除数字。

示例 2：

1
2
3
输入：s = "Myself2 Me1 I4 and3"
输出："Me Myself and I"
解释：将 s 中的单词按照初始位置排序，得到 "Me1 Myself2 and3 I4" ，然后删除数字。

提示：

  • 2 <= s.length <= 200
  • s 只包含小写和大写英文字母、空格以及从 1 到 9 的数字。
  • s 中单词数目为 1 到 9 个。
  • s 中的单词由单个空格分隔。
  • s 不包含任何前导或者后缀空格。

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String sortSentence(String s) {
        String[] arr = s.split("\\s+");
        
        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.charAt(o1.length() - 1) - o2.charAt(o2.length() - 1);
            }
        });
        int n = arr.length;
        StringBuilder bd = new StringBuilder();
        for (int i = 0; i < n; i++) {
            bd.append(arr[i].substring(0, arr[i].length() - 1));
            bd.append(" ");
        }

        if (bd.length() > 0) bd.deleteCharAt(bd.length() - 1);
        return bd.toString();
    }
}

展开全文 >>

存在重复元素2

219. 存在重复元素 II

难度简单267

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:

1
2
输入: nums = [1,2,3,1], k = 3
输出: true

示例 2:

1
2
输入: nums = [1,0,1,1], k = 1
输出: true

示例 3:

1
2
输入: nums = [1,2,3,1,2,3], k = 2
输出: false

哈希表

  • 巧妙之处在于一直加入数字，如果当前的set的size() > k说明最后一个加入元素的index与第一个元素加入的index差值大于k了，此时要把第一个加入的元素删掉

  • 如果某次查找时当前元素在set里面说明有一个元素与当前元素的index差值不超过k,此时满足条件,跳出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();

        for(int i=0;i<n;i++){
            if(set.contains(nums[i])) return true;
            // 巧妙之处在于一直加入数字，如果当前的set的size() > k说明最后一个加入元素的index与第一个元素加入的index差值大于k了，此时要把第一个加入的元素删掉
            // 如果某次查找时当前元素在set里面说明有一个元素与当前元素的index差值不超过k,此时满足条件,跳出
            set.add(nums[i]);
            if(set.size() > k){
                set.remove(nums[i-k]);
            }
        }
        return false; 
    }
}

展开全文 >>

最长连续序列

128. 最长连续序列

难度困难764

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

示例 1：

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1
2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

  • 0 <= nums.length <= 104
  • -10^9 <= nums[i] <= 10^9

哈希表加速

使用哈希表来做visited，然后向前向后统计数量

  • 如果visited==1,那么就不再遍历了。
  • 如果visisted==0那么就向前向后遍历统计数量。
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
35
class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        int n = nums.length;
        for(int i = 0;i < n; i++){
            map.put(nums[i],0);
        }
        
        int max = 0;
        for(int i=0;i<n;i++){
            // 如果数字没有被遍历过,那么就去遍历并计算长度
            if(map.get(nums[i]) == 0){
                // 记录从这个数字开始遍历的最大长度
                max = Math.max(dfs(nums[i],map),max);
            }
        }
        return max;
    }
    // 找到一个数字向前向后找其他数字，遍历过就置1
    public int dfs(int val,Map<Integer,Integer> map){
        int max = val;
        int min = val;
        while(map.containsKey(max)){
            map.put(max,1);
            if(map.containsKey(max+1)) max++;
            else break;
        }
        while(map.containsKey(min)){
            map.put(min,1);
            if(map.containsKey(min-1)) min--;
            else break;
        }
        return max - min + 1;
    }
}

HashSet加速

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
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            // 巧妙之处在于这里，只从最小的数字开始遍历，其余的数字跳过
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/zui-chang-lian-xu-xu-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走