最大矩形 

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
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：
输入：matrix = []
输出：0

示例 3：
输入：matrix = [["0"]]
输出：0

示例 4：
输入：matrix = [["1"]]
输出：1

示例 5：
输入：matrix = [["0","0"]]
输出：0

提示：

rows == matrix.length
cols == matrix[0].length
0 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'

作者：字节校园
链接：https://leetcode-cn.com/leetbook/read/bytedance-c01/eik5p2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

枚举

  1. 使用类似与前缀和的方式计算每一行从左往右到当前位置时的宽度 $val[i][j]$
  2. 枚举整个矩阵，在第 $i$ 行第 $j$ 列时，$val[i][j]$ 即为当前行到j的矩形的宽度
  3. 此时矩形的面积是当前的宽度 $width*1$
  4. 从 $i$ 行开始枚举矩形的高度，计算该高度下最大宽度与高度的乘积（面积），并更新面积的最大值
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
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] val = new int[m][n];
        
        // 先计算矩形的宽度（类似于前缀和）
        for (int i = 0; i < m; i++) {
            val[i][0] = matrix[i][0] - '0';
        }
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') val[i][j] = val[i][j - 1] + 1;
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 当前位置时矩形的宽度
                int width = val[i][j];
                if (width == 0) continue;
                // 当高度为1时，此时的面积是1*width
                int area = width;
                // 枚举当前宽度下的高度
                for (int k = i - 1; k >= 0; k--) {
                    // 计算当前高度位置时，矩形的宽度，这个宽度是遍历到的最小的宽度
                    width = Math.min(width, val[k][j]);
                    // 计算在这个位置时，面积达的最大值
                    area = Math.max(area, width * (i - k + 1));
                }
                ret = Math.max(area, ret);
            }
        }
        return ret;
    }
}

时间复杂度：$O(m^2n)$,空间复杂度：$O(mn)$

单调栈

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
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        int[][] left = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    continue;
                }
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--) {
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, (i - k + 1) * width);
                }
                ret = Math.max(ret, area);
            }
        }
        return ret;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximal-rectangle/solution/zui-da-ju-xing-by-leetcode-solution-bjlu/
来源：力扣（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
DNA 是由 ACGT 四种核苷酸组成，例如 AAAGTCTGAC，假定自然环境下 DNA 发生异变的情况有：

基因缺失一个核苷酸
基因新增一个核苷酸
基因替换一个核苷酸
且发生概率相同。
古生物学家 Sam 得到了若干条相似 DNA 序列，Sam 认为一个 DNA 序列向另外一个 DNA 序列转变所需的最小异变情况数可以代表其物种血缘相近程度，异变情况数越少，血缘越相近，请帮助 Sam 实现获取两条 DNA 序列的最小异变情况数的算法。

输入描述:

每个样例只有一行，两个 DNA 序列字符串以英文逗号“,”分割
输出描述:
输出转变所需的最少情况数，类型是数字

测试用例:
输入
ACT,AGCT
输出
1

数据范围：

每个 DNA 序列不超过 100 个字符

作者：字节校园
链接：https://leetcode-cn.com/leetbook/read/bytedance-c01/eug83v/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

动态规划

自顶向下的动态规划的思路是：选择最后一个字符，

  • 如果两个字符串的第$i$,$j$个字符相同，继续判断第两个字符串的$i-1$，$j-1$的字符,即$dp[i][j]=dp[i-1][j-1]$
  • 如果两个字符串的第$i$,$j$个字符相同，则继续判断第$i-1$,$j$个字符或者第$i$,$j-1$个字符

$\mathrm{d}[\mathrm{i}, \mathrm{j}] \rightarrow\left{\begin{array}{ll}
0 & \mathrm{i}=0, \mathrm{j}=0 \
\mathrm{j} & \mathrm{i}=0, \mathrm{j}>0 \
\mathrm{i} & \mathrm{j}>0, \mathrm{i}=0 \
\mathrm{d}[\mathrm{i}-1, \mathrm{j}-1] & \mathrm{S}_1(\mathrm{i})=\mathrm{S}_2(\mathrm{j}) \
\min (\mathrm{d}[\mathrm{i}, \mathrm{j}-1]+1, \mathrm{d}[\mathrm{i}-1, \mathrm{j}]+1, \mathrm{d}[\mathrm{i}-1, \mathrm{j}-1]+1) & \mathrm{S}_1(\mathrm{i}) \neq \mathrm{S}_2(\mathrm{j})
\end{array}\right.$

分析

定义：$S_1$、$S_2$表示两个字符串，$S_1(i)$表示$S_1$的第一个字符，$d[i, j]$表示$S_1$的第$i$个前缀到$S_2$的第$j$个前缀（例如:$S_1 = ”abc”,S_2 = ”def”$,求解$S_1$到$S_2$的编辑距离为$d[3, 3]$）。

  1. 若$S_1 = ”abc”, S_2 = ”dec”$，此时它们的编辑距离为$d[3, 3] = 2$，观察两个字符串的最后一个字符是相同的，也就是说$S_1(3) = S_2(3)$不需要做任何变换，故$S_1 = ”abc”, S_2 = ”dec”$ <=>$S_1’ = ”ab”, S_2’ = ”de”$，即当$S_1[i] = S[j]$时，$d[i, j] = d[i-1,j -1]$。得到公式：$d[i, j] = d[i - 1, j - 1] (S_1[i] = S_2[j])$

  2. 上面一条得出了当$S_1[i] = S_2[j]$的计算公式，显然还有另一种情况就是$S_1[i] ≠ S_2[j]$，$若S_1 = ”abc”, S_2 = ”def”$。$S_1$变换到$S_2$的过程可以“修改”，但还可以通过“插入”、“删除”使得$S_1$变换为$S_2$。

    • 在$S_1$字符串末位插入字符$“f”$，此时$S_1 = ”abcf”，S_2 = ”def”$,此时即$S_1[i] = S_2[j]$的情况，$S_1$变换为$S_2$的编辑距离为$d[4, 3] = d[3, 2]$。所以得出$d[i, j]=d[i, j - 1] + 1$。（$+1$是因为$S_1$新增了$”f”$）

    • 在$S_2$字符串末位插入字符$“c”$，此时$S_1 = ”abc”，S_2 = ”defc”$，此时即$S_1[i] = S[j]$的情况，$S_1$变换为$S_2$的编辑距离为$d[3, 4] = d[2, 3]$。所以得出$d[i, j]=d[i - 1, j] + 1$，实际上这是对$S_1$做了删除。（$+1$是因为$S_2$新增了$”c”）$

    • 将$S_1$字符串末位字符修改为$”f”$，此时$S_1 = ”abf”，S_2 = ”def”$，此时即$S_1[i] = S[j]$的情况，$S_1$变换为$S_2$的编辑距离为$d[3, 3] = d[2, 2]$。所以得出$d[i, j] = d[i – 1, j - 1] + 1$。（$+1$是因为$S_1$修改了$“c”$）

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
import java.util.Scanner;
class Solution{
    public static void main(String[] args){
        Solution s=new Solution();
        Scanner scan = new Scanner(System.in);
        String input = "";
        if (scan.hasNext()) {
            input = scan.nextLine();
        }
        scan.close();
        String[] array = input.split(",");
        System.out.println(s.dnaDiffer(array[0] , array[1]));
    }

    public int dnaDiffer(String d1, String d2) {
        int m = d1.length();
        int n = d2.length();
        if (m == 0) return n;
        if (n == 0) return m;

        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= m; i++) {
            char c1 = d1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = d2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

参考文献

动态规划（1）——字符串的编辑距离

展开全文 >>

替换后的最长重复字符 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意：字符串长度 和 k 不会超过 104。

示例 1：
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
通过次数22,885提交次数44,806

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

滑动窗口+哈希表

利用滑动窗口维护最大值，利用哈希表统计在滑动窗口内的字母的种类和数量

左边界 $l$ 不动滑动窗口一直扩展右边界 $r$ 直至

  • 如果滑动窗口中的出现次数最多元素的数量 $num_{mode}$,使得$num_{mode}+k<r-l$，需要左边界向右移动一个位置；
  • 否则继续右移右边界 $r$
  • 在窗口变化的过程中保证窗口的大小不缩小，最终窗口的大小就是结果
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
class Solution {
    public int characterReplacement(String s, int k) {
        int l = 0, r = 0;           // 滑动窗口的左右边界
        int[] hash = new int[26];   // 统计在滑动窗口内的字母的种类和数量

        int max = 0;
        int n = s.length();

        while (r < n) {
            // 一直扩张右边界，将右边界的值加入滑动窗口中
            int rIndex = s.charAt(r) - 'A';
            hash[rIndex]++;
            // 计算当前窗口中最右边元素的数量，判断是否大于最大数量
            max = Math.max(max, hash[rIndex]);
            // 如果窗口的大小减去窗口中的最多元素的数量大于k，那么不能继续扩大窗口了，需要左边界右移
            if (r - l + 1 - max > k) {
                int lIndex = s.charAt(l) - 'A';
                // 左边界右移时，删除窗口中左边界的元素
                hash[lIndex]--;
                // 左边界右移一个
                l++;
            }
            // 右边界始终右移
            r++;
        }
        // 因为左右边界考虑了k所以直接返回左边界的位置-左边界的位置
        return r - l;
    }
}

参考文献

官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int characterReplacement(String s, int k) {
        int[] num = new int[26];
        int n = s.length();
        int maxn = 0;
        int left = 0, right = 0;
        while (right < n) {
            num[s.charAt(right) - 'A']++;
            maxn = Math.max(maxn, num[s.charAt(right) - 'A']);
            if (right - left + 1 - maxn > k) {
                num[s.charAt(left) - 'A']--;
                left++;
            }
            right++;
        }
        return right - left;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/ti-huan-hou-de-zui-chang-zhong-fu-zi-fu-n6aza/
来源：力扣（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
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

示例 1：
输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

示例 2：
输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

提示：
1 <= n <= 104
nums.length == 2 * n
-104 <= nums[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/array-partition-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }
}

计数排序

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
public class Solution {
    public int arrayPairSum(int[] nums) {
        int[] arr = new int[20001];
        int lim = 10000;
        for (int num: nums)
            arr[num + lim]++;
        int d = 0, sum = 0;
        for (int i = -10000; i <= 10000; i++) {
            sum += (arr[i + lim] + 1 - d) / 2 * i;
            d = (2 + arr[i + lim] - d) % 2;
        }
        return sum;
    }
} 
作者：LeetCode
链接：https://leetcode-cn.com/problems/array-partition-i/solution/shu-zu-chai-fen-i-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
for(int i = -10000; i <= 10000; i++ ){
  int count = arr[i + lim];
  if(count != 0){
      //count + 1是为了让奇数在/2时能向上取整
      //如果d是1, 也就说明这个数的个数被上一次分配占用了一个, 对偶数没有影响
      //但是对奇数, 因为少了一个, 所以还剩偶数个, 所以需要再-d, 实质就是-1, 否则会多分配一对
      sum += (count + 1 - d) / 2 * i;
      //d就是用来说明这次分配有没有占用下个数的个数, 如果有, 则置1
      //要-d是因为要考虑上次分配有没有占用这次的个数, 如果占用了, 那就-1, 也就是-d
      //+2是因为  防止count == 1 || count == 0
      d = (count - d + 2) & 1;
  }
}

参考文献

ibuyan的评论

展开全文 >>

生成平衡数组的方案数 

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
给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。

比方说，如果 nums = [6,1,7,4,1] ，那么：

选择删除下标 1 ，剩下的数组为 nums = [6,7,4,1] 。
选择删除下标 2 ，剩下的数组为 nums = [6,1,4,1] 。
选择删除下标 4 ，剩下的数组为 nums = [6,1,7,4] 。
如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。

请你返回删除操作后，剩下的数组 nums 是 平衡数组 的 方案数 。

示例 1：
输入：nums = [2,1,6,4]
输出：1
解释：
删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。
删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。
删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。
删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。

示例 2：
输入：nums = [1,1,1]
输出：3
解释：你可以删除任意元素，剩余数组都是平衡数组。

示例 3：
输入：nums = [1,2,3]
输出：0
解释：不管删除哪个元素，剩下数组都不是平衡数组。
 
提示：

1 <= nums.length <= 105
1 <= nums[i] <= 104

前缀和

  1. 分别计算计数的前缀和偶数的前缀和
  2. 枚举要删除的数字$i$
  3. $i$之前的前缀和是原先是奇数的（偶数的）删除后还是奇数的（偶数的）前缀和，$i$之后的前缀和原先是奇数的（偶数）要变成偶数（奇数）。
  4. 判断删除后重新组合的前缀和是否相等

本题目难度最大的地方在于边界条件的处理，奇数的前缀和只计算奇数$index$的和，偶数位置要怎么处理？

本题解中使用重复的方法，计算奇数前缀和的时候偶数位置值使用奇数的前缀和填充

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 {
    public int waysToMakeFair(int[] nums) {
        int n = nums.length;
        int[] odd = new int[n + 1];
        int[] even = new int[n + 1];

        for (int i = 1; i <= nums.length; i++) {
            if (i % 2 == 1) {
                odd[i] = odd[i - 1] + nums[i - 1];
            } else {
                odd[i] = odd[i - 1];
            }
        }

        for (int i = 1; i <= nums.length; i++) {
            if (i % 2 == 0) {
                even[i] = even[i - 1] + nums[i - 1];
                if (i - 1 > 0) even[i - 1] = even[i];
            } else {
                even[i] = even[i - 1];
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                int oddSum = odd[i] + even[n] - even[i];
                int evenSum = odd[n] - odd[i] + even[i] - nums[i];
                if (oddSum == evenSum) res++;
            } else {
                int oddSum = odd[i] + even[n] - even[i - 1] - nums[i];
                int evenSum = odd[n] - odd[i] + even[i - 1];
                if (oddSum == evenSum) res++;
            }

        }
        return res;
    }
}

时间复杂度$O(n)$,空间复杂度$O(n)$

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 waysToMakeFair(int[] nums) {
        
        int n = nums.length;
        int sumOdd = 0;//奇数下标元素和
        int sumEven = 0;//偶数下标元素和
        for(int i=0;i<nums.length;i++){
            if(i%2==0){//偶数
                sumEven+=nums[i];
            }else{//奇数
                sumOdd+=nums[i];
            }
        }
        
        int count = 0;
        
        for(int i=n-1;i>=0;i--){
            if((i)%2==0){//偶数下标
                sumEven-=nums[i];
                if(sumEven==sumOdd) count++;
                sumOdd+=nums[i];
            }else{
                sumOdd-=nums[i];
                if(sumOdd==sumEven) count++;
                sumEven+=nums[i];
            }
        }
        
        return count++;
    }
}

作者：zhe-zhi-shi-ta-bu-jin-nao-zi-8
链接：https://leetcode-cn.com/problems/ways-to-make-a-fair-array/solution/liang-ci-bian-li-qiu-jie-by-zhe-zhi-shi-ta-bu-jin-/
来源：力扣（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
小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。

字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。

给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。

注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：

x 是 y 的一个前缀；
如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。

示例 1：
输入：n = 3, k = 27
输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。

示例 2：
输入：n = 5, k = 73
输出："aaszz"

提示：

1 <= n <= 10^5
n <= k <= 26 * n

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

这个题目的主要意思是实现使用n个数凑出k这个值，n个数的取值范围是[1,26]，选择每个数字时，数字应该尽量小。

贪心算法

  1. 如果剩余的 $n$ 的数量大于 $k/26+1$（向上取整）,那么说明有 $n-(k/26+1)$个数字的选择是受限制的，可以任意选择，那么直接就选择 $1$，选择的字符也就是 $a$
  2. 如果剩余的 $n$的数量不大于 $k/26+1$（向上取整）, 那么说明剩余数字的选择是受限制的。此时先从剩余的 $n$ 中选择第一个，为了保证选择的数字是最小的，第一个被选择的数字应该是 $k-((n-1)*26)$，接下来每一个数字都按照 2 这种选择方法选择

需要注意的是 $a$ 是 $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
class Solution {
    public String getSmallestString(int n, int k) {
        StringBuilder bd = new StringBuilder();
        char[] res = new char[n];
        int index=0;
        while (n > (k / 26 + 1)) {
            res[index++]='a';
            n--;// 消耗一个可用数字
            k--;// 因为选择的是a，所以减去1
        }

        while (n > 0) {
            // 要选择的第一个最小的数字
            int left = k - ((n - 1) * 26);
            // 处理边界条件（a的值是1而不是0）
            if (left > 0) left--;
            // 还原字符
            char c = (char) (left + 'a');
            res[index++]=c;
            // 消耗了一个数字
            n--;
            // 计算剩余的k
            k -= c - 'a' + 1;
        }
        return String.valueOf(res);
    }
}

时间复杂度$O(n)$，空间复杂度$O(n)$

展开全文 >>

检查两个字符串数组是否相等 

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
给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同，返回 true ；否则，返回 false 。

数组表示的字符串 是由数组中的所有元素 按顺序 连接形成的字符串。

示例 1：

输入：word1 = ["ab", "c"], word2 = ["a", "bc"]
输出：true
解释：
word1 表示的字符串为 "ab" + "c" -> "abc"
word2 表示的字符串为 "a" + "bc" -> "abc"
两个字符串相同，返回 true
示例 2：

输入：word1 = ["a", "cb"], word2 = ["ab", "c"]
输出：false
示例 3：

输入：word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
输出：true
 

提示：

1 <= word1.length, word2.length <= 103
1 <= word1[i].length, word2[i].length <= 103
1 <= sum(word1[i].length), sum(word2[i].length) <= 103
word1[i] 和 word2[i] 由小写字母组成

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

直接拼接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        StringBuilder bd1 = new StringBuilder();
        StringBuilder bd2 = new StringBuilder();

        for (int i = 0; i < word1.length; i++) {
            bd1.append(word1[i]);
        }

        for (int i = 0; i < word2.length; i++) {
            bd2.append(word2[i]);
        }

        return bd1.toString().equals(bd2.toString());
    }
}

$3$次循环，$3n$的时间，$2n$的空间，时间复杂度$O(n)$，空间复杂度$o(n)$

展开全文 >>

盒中小球的最大数量 

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

你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。

你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。

给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。

示例 1：

输入：lowLimit = 1, highLimit = 10
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：2 1 1 1 1 1 1 1 1 0  0  ...
编号 1 的盒子放有最多小球，小球数量为 2 。
示例 2：

输入：lowLimit = 5, highLimit = 15
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：1 1 1 1 2 2 1 1 1 0  0  ...
编号 5 和 6 的盒子放有最多小球，每个盒子中的小球数量都是 2 。
示例 3：

输入：lowLimit = 19, highLimit = 28
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 12 ...
小球数量：0 1 1 1 1 1 1 1 1 2  0  0  ...
编号 10 的盒子放有最多小球，小球数量为 2 。
 
提示：

1 <= lowLimit <= highLimit <= 105

哈希表

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
class Solution {
    public int countBalls(int lowLimit, int highLimit) {
        Map<Integer, Integer> map = new HashMap<>();

        int max = 0;
        for (int i = lowLimit; i <= highLimit; i++) {
            int sum = getSum(i);
            int count = map.getOrDefault(sum, 0) + 1;
            max = Math.max(count, max);
            map.put(sum, count);
        }
        return max;
    }

    public int getSum(int val) {
        int sum = 0;
        while (val > 0) {
            int bit = val % 10;
            val /= 10;
            sum += bit;
        }

        return sum;
    }
}

展开全文 >>

设计前中后队列 

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
请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。

请你完成 FrontMiddleBack 类：

FrontMiddleBack() 初始化队列。
void pushFront(int val) 将 val 添加到队列的 最前面 。
void pushMiddle(int val) 将 val 添加到队列的 正中间 。
void pushBack(int val) 将 val 添加到队里的 最后面 。
int popFront() 将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popMiddle() 将 正中间 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
请注意当有 两个 中间位置的时候，选择靠前面的位置进行操作。比方说：

将 6 添加到 [1, 2, 3, 4, 5] 的中间位置，结果数组为 [1, 2, 6, 3, 4, 5] 。
从 [1, 2, 3, 4, 5, 6] 的中间位置弹出元素，返回 3 ，数组变为 [1, 2, 4, 5, 6] 。
 

示例 1：

输入：
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
输出：
[null, null, null, null, null, 1, 3, 4, 2, -1]

解释：
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // 返回 1 -> [4, 3, 2]
q.popMiddle();    // 返回 3 -> [4, 2]
q.popMiddle();    // 返回 4 -> [2]
q.popBack();      // 返回 2 -> []
q.popFront();     // 返回 -1 -> [] （队列为空）
 

提示：

1 <= val <= 109
最多调用 1000 次 pushFront， pushMiddle， pushBack， popFront， popMiddle 和 popBack 。

数组模拟队列使用LinkedList

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
class FrontMiddleBackQueue {

    List<Integer> list = null;

    public FrontMiddleBackQueue() {
        list = new LinkedList<>();
    }

    public void pushFront(int val) {
        list.add(0, val);
    }

    public void pushMiddle(int val) {
        int size = list.size();
        int index = size / 2;
        list.add(index, val);
    }

    public void pushBack(int val) {
        list.add(val);
    }

    public int popFront() {
        if (list.size() > 0) return list.remove(0);
        else return -1;
    }

    public int popMiddle() {
        int size = list.size();
        int index = 0;
        if (size % 2 == 0) index = size / 2 - 1;
        else index = size / 2;
        if (list.size() > 0) return list.remove(index);
        else return -1;
    }

    public int popBack() {
        if (list.size() > 0) return list.remove(list.size() - 1);
        else return -1;
    }
}

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * FrontMiddleBackQueue obj = new FrontMiddleBackQueue();
 * obj.pushFront(val);
 * obj.pushMiddle(val);
 * obj.pushBack(val);
 * int param_4 = obj.popFront();
 * int param_5 = obj.popMiddle();
 * int param_6 = obj.popBack();
 */

展开全文 >>

合并两个链表 

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
给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中第 a 个节点到第 b 个节点删除，并将list2 接在被删除节点的位置。

下图中蓝色边和节点展示了操作后的结果：


请你返回结果链表的头指针。

示例 1：

输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中第三和第四个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
示例 2：


输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释：上图中蓝色的边和节点为答案链表。
 

提示：

3 <= list1.length <= 104
1 <= a <= b < list1.length - 1
1 <= list2.length <= 104

链表遍历

先定位到要替换的节点的前一个节点，直接替换

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode temp1 = list1;
        ListNode temp2 = list1;

        ListNode p1 = list1;
        ListNode p2 = list2;

        ListNode temp4 = list2;//list2 tail

        while (p2 != null) {
            temp4 = p2;
            p2 = p2.next;
        }

        int count = 0;
        while (p1 != null) {
            count++;
            if (count == a) {
                temp1 = p1;
            } else if (count == b+1) {
                temp2 = p1;
            }
            p1 = p1.next;
        }

        temp1.next = list2;
        temp4.next = temp2.next;

        return list1;
    }
}

展开全文 >>

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>希望有一天被领走