找出最具竞争力的子序列 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。

数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。

在子序列 a 和子序列 b 第一个不相同的位置上，如果 a 中的数字小于 b 中对应的数字，那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。 例如，[1,3,4] 比 [1,3,5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， 4 小于 5 。

示例 1：
输入：nums = [3,5,2,6], k = 2
输出：[2,6]
解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。

示例 2：
输入：nums = [2,4,3,3,5,4,9,6], k = 4
输出：[2,3,3,4]
 
提示：
1 <= nums.length <= 105
0 <= nums[i] <= 109
1 <= k <= nums.length


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-most-competitive-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

维护一个单调栈（如果当前的元素小于栈顶元素，则将栈中大于当前元素的所有元素出栈，将当前元素入栈）

这里需要对单调栈进行一下修改，因为最多只能删除n-k个元素，要剩下至少k个元素，如果当前队列中的元素已经删除了n-k个，那么往后就不能出栈，只能入栈元素。

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
class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[]{};
        Deque<Integer> stack = new LinkedList<>();

        int n = nums.length;

        int maxDelete = n - k;
        stack.push(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            while (maxDelete > 0 && !stack.isEmpty() && stack.peek() > nums[i]) {
                stack.pop();
                maxDelete--;
            }
            stack.push(nums[i]);
        }

        int index = k - 1;
        int[] res = new int[k];

        int size = stack.size();
        for (int i = 0; i < size - k; i++) stack.pop();
        while (!stack.isEmpty()) {
            res[index--] = stack.pop();
        }
        return res;
    }
}

展开全文 >>

java字符串拼接

对于 Java来说，由于字符串是不可变的，因此在连接时首先为新字符串分配足够的空间，复制旧字符串中的内容并附加到新字符串。

因此，总时间复杂度将是：

$5+5×2+5×3+…+5×n=5×(1+2+3+…+n)=5×n×(n+1)/2 即O(N^2)。$

针对 Java 中出现的此问题，我们提供了以下解决方案：

如果你确实希望你的字符串是可变的，则可以使用 toCharArray 将其转换为字符数组。
如果你经常必须连接字符串，最好使用一些其他的数据结构，如 StringBuilder 。

1
2
3
4
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/array-and-string/c9lnm/
来源：力扣（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
在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

（请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。

返回区域的数目。

示例 1：
输入：
[
  " /",
  "/ "
]
输出：2
解释：2x2 网格如下：

示例 2：
输入：
[
  " /",
  "  "
]
输出：1
解释：2x2 网格如下：

示例 3：
输入：
[
  "\\/",
  "/\\"
]
输出：4
解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
2x2 网格如下：

示例 4：
输入：
[
  "/\\",
  "\\/"
]
输出：5
解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
2x2 网格如下：

示例 5：
输入：
[
  "//",
  "/ "
]
输出：3
解释：2x2 网格如下：

提示：

1 <= grid.length == grid[0].length <= 30
grid[i][j] 是 '/'、'\'、或 ' '。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regions-cut-by-slashes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

并查集

avatar

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
class Solution {
    public int regionsBySlashes(String[] grid) {
        int n = grid.length;
        father = new int[n * n * 4];
        for (int i = 0; i < n * n * 4; i++) {
            father[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int idx = i * n + j;
                if (i < n - 1) {
                    int bottom = idx + n;
                    union(idx * 4 + 2, bottom * 4);
                }
                if (j < n - 1) {
                    int right = idx + 1;
                    union(idx * 4 + 1, right * 4 + 3);
                }
                if (grid[i].charAt(j) == '/') {
                    union(idx * 4, idx * 4 + 3);
                    union(idx * 4 + 1, idx * 4 + 2);
                } else if (grid[i].charAt(j) == '\\') {
                    union(idx * 4, idx * 4 + 1);
                    union(idx * 4 + 2, idx * 4 + 3);
                } else {
                    union(idx * 4, idx * 4 + 1);
                    union(idx * 4 + 1, idx * 4 + 2);
                    union(idx * 4 + 2, idx * 4 + 3);
                }
            }
        }

        Set<Integer> fSet = new HashSet<Integer>();
        for (int i = 0; i < n * n * 4; i++) {
            int fa = find(i);
            fSet.add(fa);
        }
        return fSet.size();
    }


    int[] father;

    public int find(int x) {
        int a = x;
        while (x != father[x]) x = father[x];
        while (a != father[a]) {
            int z = a;
            a = father[a];
            father[z] = x;
        }
        return x;
    }

    public void union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa != fb) father[fa] = fb;
    }
}

并查集

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
class Solution {
    public int regionsBySlashes(String[] grid) {
        int n = grid.length;
        int[] f = new int[n * n * 4];
        for (int i = 0; i < n * n * 4; i++) {
            f[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int idx = i * n + j;
                if (i < n - 1) {
                    int bottom = idx + n;
                    merge(f, idx * 4 + 2, bottom * 4);
                }
                if (j < n - 1) {
                    int right = idx + 1;
                    merge(f, idx * 4 + 1, right * 4 + 3);
                }
                if (grid[i].charAt(j) == '/') {
                    merge(f, idx * 4, idx * 4 + 3);
                    merge(f, idx * 4 + 1, idx * 4 + 2);
                } else if (grid[i].charAt(j) == '\\') {
                    merge(f, idx * 4, idx * 4 + 1);
                    merge(f, idx * 4 + 2, idx * 4 + 3);
                } else {
                    merge(f, idx * 4, idx * 4 + 1);
                    merge(f, idx * 4 + 1, idx * 4 + 2);
                    merge(f, idx * 4 + 2, idx * 4 + 3);
                }
            }
        }

        Set<Integer> fathers = new HashSet<Integer>();
        for (int i = 0; i < n * n * 4; i++) {
            int fa = find(f, i);
            fathers.add(fa);
        }
        return fathers.size();
    }

    public int find(int[] f, int x) {
        if (f[x] == x) {
            return x;
        }
        int fa = find(f, f[x]);
        f[x] = fa;
        return fa;
    }

    public void merge(int[] f, int x, int y) {
        int fx = find(f, x);
        int fy = find(f, y);
        f[fx] = fy;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/you-xie-gang-hua-fen-qu-yu-by-leetcode-s-ztob/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

找出第k大的异或坐标值

1738. 找出第 K 大的异或坐标值

难度中等30收藏分享切换为英文接收动态反馈

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。

矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。

请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。

示例 1：

1
2
3
输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。

示例 2：

1
2
3
输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。

示例 3：

1
2
3
输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。

示例 4：

1
2
3
输入：matrix = [[5,2],[1,6]], k = 4
输出：0
解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 1000
  • 0 <= matrix[i][j] <= 106
  • 1 <= k <= m * n

维护一个类似于前缀和的矩阵+小根堆

矩阵中坐标为 $(i,j)$ 的数字由以 $(0，0)$ 为左上角到 $(i,j)$ 为右下角的矩形区域的所有数字异或得到的

可以通过一个数组临时保存计算结果从而加速计算过程，

1
dp(i,j)=dp(i-1,j) ^ dp(i,j-1) ^ dp(i-1,j-1) ^ maxtrix(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
36
37
class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] dp = new int[m][n];
        // 处理边界条件
        dp[0][0] = matrix[0][0];
        pq.offer(dp[0][0]);
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] ^ matrix[i][0];
            pq.offer(dp[i][0]);
        }

        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] ^ matrix[0][i];
            pq.offer(dp[0][i]);
        }
        // 状态转移
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                dp[i][j] = dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1] ^ matrix[i][j]; 
                // 因为多异或了dp[i - 1][j - 1]，消除了，所以再异或一次
                pq.offer(dp[i][j]);
            }
        }

        int res = 0;
        for (int i = 0; i < k; i++) {
            res = pq.poll();
        }

        return res;
    }
}

展开全文 >>

满足三条件之一需改变的最少字符数 

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
给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。

操作的最终目标是满足下列三个条件 之一 ：

a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。
b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。
a 和 b 都 由 同一个 字母组成。
返回达成目标所需的 最少 操作数。

示例 1：
输入：a = "aba", b = "caa"
输出：2
解释：满足每个条件的最佳方案分别是：
1) 将 b 变为 "ccc"，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母；
2) 将 a 变为 "bbb" 并将 b 变为 "aaa"，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母；
3) 将 a 变为 "aaa" 并将 b 变为 "aaa"，2 次操作，满足 a 和 b 由同一个字母组成。
最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。

示例 2：
输入：a = "dabadd", b = "cda"
输出：3
解释：满足条件 1 的最佳方案是将 b 变为 "eee" 。

提示：

1 <= a.length, b.length <= 105
a 和 b 只由小写字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  1. 使用前缀和统计字符串中小于某个字母的数字的数目

  2. 然后暴力遍历i，将a中的a+’i’左边的字母移到右边，b中a+’i’右边的字母移到左边，记录每个i需要移动的字母的数量

  3. 然后暴力遍历i，将b中的a+’i’左边的字母移到右边，a中a+’i’右边的字母移到左边，记录每个i需要移动的字母的数量

  4. 还要遍历i，将a中的字母都变成a+’i’记录最小数量

  5. 然后三个取最小

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
class Solution {
    public int minCharacters(String a, String b) {
        int m = a.length();
        int n = b.length();

        // 统计字符数量
        int[] countA = new int[26];
        int[] countB = new int[26];
        for (char c : a.toCharArray()) {
            countA[c - 'a']++;
        }
        for (char c : b.toCharArray()) {
            countB[c - 'a']++;
        }

        // 前缀和preA[i]记录字符串a中<=('a'+i)的字符数
        int[] preA = new int[26];
        for (int i = 0; i < 26; i++) {
            preA[i] = i == 0 ? countA[0] : preA[i - 1] + countA[i];
        }
        // 前缀和preB[i]记录字符串b中<=('a'+i)的字符数
        int[] preB = new int[26];
        for (int i = 0; i < 26; i++) {
            preB[i] = i == 0 ? countB[0] : preB[i - 1] + countB[i];
        }

        // 遍历“分割字符”，收集答案
        int ans = Integer.MAX_VALUE;
        for (char i = 0; i < 26; i++) {
            // 当前分割字符c = 'a'+i
            if (i != 25) {
                // a中全部变成>c, b中全部变成<=c，需要的操作次数
                ans = Math.min(ans, preA[i] + (n - preB[i]));
                // b中全部变成>c, a中全部<=c
                ans = Math.min(ans, (m - preA[i]) + preB[i]);
            }

            // 都转成字符'a'+i，需要的操作次数
            int notEq1 = m - countA[i];
            int notEq2 = n - countB[i];
            ans = Math.min(ans, notEq1 + notEq2);
        }
        return ans;
    }
}

展开全文 >>

最长连续递增序列 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

提示：

0 <= nums.length <= 104
-109 <= nums[i] <= 109

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int l = 0, r = 0;
        int n = nums.length;
        if (n == 0) return 0;
        int max = 1;

        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                r = i;
            } else {
                l = i;
            }
            max = Math.max(r - l + 1, max);
        }

        return max;
    }
}

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans = 0;
        int n = nums.length;
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] <= nums[i - 1]) {
                start = i;
            }
            ans = Math.max(ans, i - start + 1);
        }
        return ans;
    }
}

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

展开全文 >>

解码异或后的排列

1734. 解码异或后的排列

难度中等48

给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。

它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。

给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。

示例 1：

1
2
3
输入：encoded = [3,1]
输出：[1,2,3]
解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]

示例 2：

1
2
输入：encoded = [6,5,4,6]
输出：[2,4,1,5,3]

提示：

  • 3 <= n < 105
  • n 是奇数。
  • encoded.length == n - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
原始数字：a,b,c,d,e,f,g

异或过程：a^b,b^c,c^d,d^e,e^f,f^g

异或结果：A,B,C,D,E,F

a^b=A
b^c=B
c^d=C
d^e=D
e^f=E
f^g=F

b^c^d^e^f=B^D^F

因为perm是前n个整数的排列
所以
a^b^c^d^e^f=1^2^3^4^5^6


a=(a^b^c^d^e^f)^(B^D^F)

有了第一个数字就可以通过第一个与encode异或得出异或前的数字

官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int total = 0;
        for (int i = 1; i <= n; i++) {
            total ^= i;
        }
        int odd = 0;
        for (int i = 1; i < n - 1; i += 2) {
            odd ^= encoded[i];
        }
        int[] perm = new int[n];
        perm[0] = total ^ odd;
        for (int i = 0; i < n - 1; i++) {
            perm[i + 1] = perm[i] ^ encoded[i];
        }
        return perm;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/decode-xored-permutation/solution/jie-ma-yi-huo-hou-de-pai-lie-by-leetcode-9gw4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

其他解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length;
        int[] res = new int[n + 1];

        int ret = 0;
        for (int i = 1; i <= n + 1; i++) ret = ret ^ i;
        for (int i = 1; i < n; i += 2) {
            ret = ret ^ encoded[i];
        }
        res[0] = ret;
        for (int i = 1; i <= encoded.length; i++) {
            res[i] = res[i - 1] ^ encoded[i - 1];
        }

        return res;
    }
}

参考文献

灵机一动的解法，作者：MOTMlsc

展开全文 >>

找到字符串中所有字母异位词 

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
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
 示例 2:

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
class Solution {
    int[] pHash = new int[26];

    public List<Integer> findAnagrams(String s, String p) {
        for (int i = 0; i < p.length(); i++) {
            pHash[p.charAt(i) - 'a']++;
        }

        int l = 0, r = 0;
        int pLen = p.length();

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < s.length(); i++) {
            r = i;
            if (r - l + 1 >= pLen) {
                if (isSame(s.substring(l, r + 1))) list.add(l);
                l++;
            }
        }


        return list;
    }

    public boolean isSame(String s) {
        int[] hash = new int[26];

        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < 26; i++) {
            if (hash[i] != pHash[i]) return false;
        }

        return true;
    }
}

展开全文 >>

二叉树的直径 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

深度优先遍历统计每个节点的左子树和右子树的深度，并计算左子树和右子树深度的最大值

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.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        deep(root);
        return max;
    }

    public int deep(TreeNode root) {
        if (root == null) return 0;
        int left = deep(root.left);
        int right = deep(root.right);
        max = Math.max(left + right, max);
        return Math.max(left, right) + 1;
    }
}

官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    public int depth(TreeNode node) {
        if (node == null) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(node.left); // 左儿子为根的子树的深度
        int R = depth(node.right); // 右儿子为根的子树的深度
        ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans
        return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/diameter-of-binary-tree/solution/er-cha-shu-de-zhi-jing-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

和为k的子数组 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] pre = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + nums[i - 1];
        }

        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (pre[i] - pre[j] == k) res++;
            }
        }

        return res;
    }
}

前缀和+哈希表优化

因为：

$pre[i]−pre[j−1]==k$

移项

$pre[j−1]==pre[i]−k$

只需要计算pre[i]-k,然后查找哈希表中有没有pre[j-1]就可以统计出结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap < Integer, Integer > mp = new HashMap < > ();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-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>希望有一天被领走