1.回文字符串

​ 给定一个字符串str，每次可以对其中的一个字符进行修改，统计将其变为回文字符串至少要修改几次。

​ 非常简单，前后两指针进行比较，统计不同的字符数即可。

2.颜色填充

题目：

​ m*n的矩阵，对其中的每个格子进行填充，有以下规则：

​ 1.每个格子必须填充

​ 2.相邻格子颜色不同

​ 3.每种颜色的格子数相同

​ 求，至少需要多少中颜色。

思路：
  • 其实两种颜色就能实现填充m*n格子，且相邻格子的颜色不同
  • 为了使所有颜色的格子数相同，我们要找m*n的最小因子

3.数组中最大子数组的最小长度

给定一个数组nums, 找出其所有具有最大值的子数组的最短长度。其中，数组的值定义如下： 

1
数组[a1, a2, a3]的值 = a1 | a2 | a3

数据范围：

1
2
nums.length() <= 10^6
数组内容全为正整数
分析：
  • 根据数据范围，算法复杂度必须小于O(n^2)
  • 数组的最大值，就是所有元素或的结果
  • 需要map进行记录，前面的状态（记录最近的，让第j位变成1的位置i）
  • 题型类似Leetcode325：这类题都是找最大、最小的子数组，只不过条件不同。
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

public int getMinLength(int[] nums){

    int n = nums.length;
    int max = 0;   // 所有子数组中的最大值
    for(int m : nums){
        max |= m;
    }

    int res = n;   // 原数组肯定具有最大值
    Map<Integer, Integer> map = new HashMap<>();  // 记录第j位最近出现的位置i

    for(int i = 0; i < n; i++){
        int m = nums[i];

        // 最大值为max，将其与m的每一位进行比较，若m对应该位的值不同(肯定为0)，
        // 就通过map找到最近的可以使该位为1的数的下标
        // 则以m为结尾的具有最大值的最小数组为，找出的所有下标的最小值
        int curLen = 1;   // 以m为结尾数组初始长度
        int j;
        for(j = 0; j < 32; j++){   // 遍历每一位
            if(((max>>j)&1) != ((m>>j)&1)){   // 第j位不同
                if(map.containsKey(j)){   // 前面具有可以使该位为1的数
                    curLen = Math.max(curLen, i - map.get(j) + 1);   // 更新长度
                }
                else{   // 前面没有，跳出循环，以m为结尾无法组成最大值数组
                    break;
                }
            }
        }
        if(j == 32){   // 更新比较，符合条件子数组的长度
            res = Math.min(res, curLen);
        }

        // 记录最近每一位成为1的位置
        for(j = 0; j < 32; j++){
            if(((m>>j)&1) != 0){
                map.put(j, i);
            }
        }
    }

    return res;
}

非常可惜，当时没有做出来。

4.图的最大生成树

n个城市，m条道路，每条道路具有一定的客流量。现在要去掉几条道路，使得城市之间是可达的，且剩余道路的总客流量最大。若无法可达，则输出-1，否则输出总客流量对10^9+7取余

1
a b c d

代表城市a和b之间的客流量为：
$$
C_c^d
$$

1
n<=10^3
分析：
  • dfs方法，会遍历所有的边，指数级增长，肯定会超时
  • 这道题本质是求图的最大生成树
  • 图的相关算法需要总结，太陌生了

使用普利姆算法，贪心的求最大生成树，只能通过40%: