题目一 差值为k的去重数字对

给定一一个数组arr,，求差值为k的去重数字对。

给一个数组3,2,5,7,0,0 差值为2的有(0,2),(3,5),(5,7)

(leetcode532 数组中的 k-diff 数对)

解

使用hash表将数据放入，遍历hash表，找到当前数+k的数是否存在

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<List<Integer>> findPairs(int[] nums, int k) {
    HashSet<Integer> set = new HashSet<>();
    for (int num: nums){
        set.add(num);
    }
    List<List<Integer>> res = new ArrayList<>();
    for (Integer num : set){
        if (set.contains(num + k)){
            res.add(Arrays.asList(num, num + k));
        }
    }
    return res;
}

leetcode532的解法还需要处理k=0的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findPairs(int[] nums, int k) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int num: nums){
        map.put(num, map.get(num) != null ? map.get(num) + 1 : 1);
    }
    int res = 0;
    for (Integer num : map.keySet()){
        if (map.containsKey(num + k)){
            if (k == 0 && map.get(num) == 1){
                continue;
            }
            res ++;
        }
    }
    return res;
}

题目二 magic操作

给一个包含n个整数元素的集合a，一个包含m个整数元素的集合b。

定义magic操作为，从一个集合中取出一个元素，放到另一个集合里，且操作过后每个集合的平均值都大于操作前。

注意以下两点:

  1. 不可以把一个集合的元素取空，这样就没有平均值了

  2. 值为x的元素从集合b取出放入集合a，但集合a中已经有值为x的元素，则a的平均值不变(因为集合元素不会重复)，b的平均值可能会改变( 因为x被取出了)

问最多可以进行多少次magic操作?

解

2个集合的平均值的这几种情况

  1. 平均值一样都为n，

    1. <n的数，a平均值会上升，b平均值会下降;

    2. =n的数，a平均值和b平均值不变；

    3. >n的数，a平均值会下降，b平均值会上升；

      总结相等是不能进行magic操作。

  2. 平均值不一样分别为A，B ,A<B

    1. 从小集合a向大集合b放

      1. <A的，a平均值上升，b平均值下降；
      2. =A的，a平均值不变，b平均值下降；
      3. >A的，a平均值下降；

      不能进行magic操作。

    2. 从小集合b向大集合a放

      1. <B || >A的,两个平均值上升；
      2. =B, b的平均值不变；
      3. >B ,b平均值下降；

      只能放置b集合中<B || >A的数

根据分析，只能从集合b中找到<B || >A的数放入到集合a中，并且是在集合a中不存在的数。

那么进行多少次magic操作，就要按照一定的顺序进行放置，只能找到b集合中复合条件的数，将其按从小到大排列，依次放入a集合。

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
// arr1无重复值，arr2无重复值，arr1和arr2肯定有数字
public static int maxOps(int[] arr1, int[] arr2){
    double sum1 = 0;
    for (int num : arr1){
        sum1 +=num;
    }
    double sum2 = 0;
    for (int num : arr2){
        sum2 +=num;
    }
    double avg1 = avg(sum1, arr1.length);
    double avg2 = avg(sum2, arr2.length);
    if ( avg1==avg2 ){
        return 0;
    }
    // 平均值不想动
    int[] arrMore = null;
    int[] arrLess = null;
    double sumMore =0;
    double sumLess =0;
    if (avg1 > avg2){
        arrMore = arr1;
        sumMore = sum1;
        arrLess = arr2;
        sumLess = sum2;
    }else {
        arrMore = arr2;
        sumMore = sum2;
        arrLess = arr1;
        sumLess = sum1;
    }
    Arrays.sort(arrMore);
    HashSet<Integer> setLess = new HashSet<>();
    // 判断是否存在的set
    for (int num:arrLess){
        setLess.add(num);
    }

    // 记录个数
    int moreSize = arrMore.length;
    int lessSize = arrLess.length;
    int ops = 0;
    for(int i = 0; i < arrMore.length; i++){
        double cur = (double) arrMore[i];
        if (cur < avg(sumMore, moreSize) && cur >avg(sumLess, lessSize) && !setLess.contains(arrMore[i])){
            sumMore -=cur;
            moreSize --;
            sumLess += cur;
            lessSize ++;
            setLess.add(arrMore[i]);
            ops++;
        }
    }
    return ops;
}

public static double avg(double sum, int size){
    return sum / (double) (size);
}

题目三 字符串转化

将给定的数转换为字符串，原则如下: 1对应a,2对应b，…26对应z，例如12258可以转换为”abbeh”，”aveh”，”abyh”， “Ibeh” and “Iyh”， 个数为5，编写一个函数，给出可以转换的不同字符串的个数。

（leetcode91解码方法）

解法

这是一个依次获取结果的动态规划问题，有一下几种情况

  1. [i] == '0',这种情况没有办法进行转换 dp[i] = 0
  2. [i] == 1, 这种情况有可能是2位数也有可能是2位数 dp[i] = dp[i+1] + dp[i+2]
  3. [i] == 2,这种情况一定有dp[i+1],有没有dp[i+2]需要判断[i+1]<=6
  4. [i]为其他值dp[i] = dp[i+1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int decodeStr(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[n] = 1;
    dp[n - 1] = s.charAt(n - 1) == '0' ? 0 : 1;
    for (int i = n - 2; i >= 0; i--) {
        if (s.charAt(i) != '0') {
            dp[i] = dp[i + 1];
            if ((s.charAt(i) - '0') * 10 + s.charAt(i + 1) - '0' < 27) {
                dp[i] += dp[i + 2];
            }
        }
    }
    return dp[0];
}

题目四 合法的括号匹配序列

一个合法的括号匹配序列有以下定义:

  1. 空串""是一个合法的括号匹配序列
  2. 如果"X"和"Y"都是合法的括号匹配序列, “XY”也是一个合法的括号匹配序列
  3. 如果”X”是一个合法的括号匹配序列，那么”(X)”也是一个合法的括号匹配序列
  4. 每个合法的括号序列都可以由以上规则生成。

例如: "", "()","() ()", "((()))"都是合法的括号序列

对于一个合法的括号序列我们又有以下定义它的深度:

  1. 空串””的深度是0
  2. 如果字符串”X”的深度是x,字符串”Y”的深度是y,那么字符串”XY”的深度为max(x,y)
  3. 如果”X” 的深度是x,那么字符串” (X) “的深度是x+1

例如: “() () ()“的深度是1, “((()))“的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

leetcode1614 括号的最大嵌套深度

解

定义一个变量count的，遍历字符串，遇到左括号count++,遇到右括号count–,count达到的最大值就是其最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxDepth(String s) {
    char[] chr = s.toCharArray();
    int count = 0;
    int maxCount =0;
    for (int i =0;i<s.length();i++){
        if (chr[i] == '('){
            count++;
            maxCount = Math.max(maxCount, count);
        }else if (chr[i] == ')'){
            count--;
        }
    }
    return maxCount;
}

要求得到最长的有效子串 动态规划

题目与上一道类似，只是要求得到最长的有效子串动态规划

leetcode32 最长有效括号

解法

dp[i]表示子串必须以i位置结尾，最长的有效子串是多大

求整个字符串的有效括号，就求一每个位置i为结尾，求当前最长的有效长度，有以下情况：

  1. i='(', dp[i]=0,因为以(结尾，必不可能是有效的
  2. i=')',这是需要获取dp[i-1]位置上最长有效距离，并且获取这一段前的字符记为P是否为(如果是dp[i-1]+2,并且获取dp[P-1]位置上的最长有效距离，因为中间断开了，前面可能还有一段距离，并且不需要继续向前获取，因为在dp[P-1]位置上已经向前获取过了。
1
2
3
4
(()())()()
0123456789
002046080
求最后一位时前面是( 所有+2，并且+8 因为前面这一位已经把前面最大的计算过了

题目五 对栈里面数据进行排序

请编写一个程序，对一个栈里的整型数据，按升序进行排序( 即排序前，栈里的数据是无序的，排序后最大元素位于栈顶)，要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。

解

使用另外的一个栈，在这个栈中让数据保持从小到大，栈顶为最小，从数据栈中弹出一个元素，如果比排序栈中栈顶元素小直接放入，否则排序栈一直弹出元素到数据栈中，知道可以把数据放入。

1
2
3
4
5
6
7
8
9
10
11
public static Stack<Integer> sortStack(Stack<Integer> stack){
    Stack<Integer> helpStack = new Stack<>();
    while (!stack.isEmpty()){
        Integer pop = stack.pop();
        while (!helpStack.isEmpty() && pop < helpStack.peek()){
            stack.push(helpStack.pop());
        }
        helpStack.push(pop);
    }
    return helpStack;
}

题目六 涂色的最少方案

牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后，每个红色R都比每个绿色G距离最左侧近。牛牛想知道他最少需要涂染几个正方形。
如样例所示: s = RGRGR
我们涂染之后变成RRRGG满足要求了，涂染的个数为2,没有比这个更好的涂染方案。

解法一

从左向右遍历数组，L范围[0，N]。 L左侧全变为R，L右侧全变为G

  1. L == 0 ，统计[0，N-1]上一共有多少个R全部染成G。
  2. L == N，统计[0，N-1]上一共有多少个G全部染成R。
  3. 统计arr[0,L]有多少个G，全部染成R + 统计arr[L+1,N-1]有多少个G，全部染成R

3个情况下变化最少的情况就是我们所需要的结果。

时间复杂度O(n*n)

解法二-预处理

在每次遍历时都需要统计多少个G，多少个R，这时我们可以引入两个辅助数组保存这个结果,arr1这个数组保存着 0-i范围上有几个R，arr2保存着i-n-1上有几个G。这样在遍历时直接去数组中获取答案即可，时间复杂度为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
// RGRGR -> RRRGG
public static int minPaint(String s) {
    if (s == null || s.length() < 2) {
        return 0;
    }
    char[] chs = s.toCharArray();
    int[] right = new int[chs.length];
    right[chs.length - 1] = chs[chs.length - 1] == 'R' ? 1 : 0;
    // 辅助数组的计算
    for (int i = chs.length - 2; i >= 0; i--) {
        right[i] = right[i + 1] + (chs[i] == 'R' ? 1 : 0);
    }
    // 初始为 把数组全变为G的代价
    int res = right[0];
    int left = 0;
    for (int i = 0; i < chs.length - 1; i++) {
        left += chs[i] == 'G' ? 1 : 0; // 计算左侧几个G染成R
        // 左侧的变为R的个数 + 右侧变为G的个数
        res = Math.min(res, left + right[i + 1]);
    }

    // 把数组全部变为R的代价 统计数组有几个G
    res = Math.min(res, left + (chs[chs.length - 1] == 'G' ? 1 : 0));
    return res;
}

题目七 二叉树的最大权值

二叉树每个结点都有一-个int型权值，给定一棵二叉树，要求计算出从根结点到叶结点的所有路径中，权值和最大的值为多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 全局变量
public static int maxSum = Integer.MIN_VALUE;

public static int maxPath(TreeNode head) {
    p(head, 0);
    return maxSum;
}

public static void p(TreeNode x, int pre) {
    if (x.left == null && x.right == null) {
        maxSum = Math.max(maxSum, pre + x.val);
    }
    if (x.left != null){
        p(x.left, pre+x.val);
    }
    if (x.right != null){
        p(x.right, pre+x.val);
    }
}