题目一 猫狗队列

实现一种狗猫队列的结构，要求如下:

  • 用户可以调用add方法将cat类或dog类的实例放入队列中;
  • 用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出;
  • 用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出;
  • 用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出;
  • 用户可以调用isEmpty方法，检查队列中是否还有dog或cat 的实例;
  • 用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例;
  • 用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。

要求以上所有方法时间复杂度都是0(1)的

题目二 最小栈

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
要求:

  1. pop、push、getMin操作的时间复杂度都是O(1) ;
  2. 设计的栈类型可以使用现成的栈结构

leetcode155 最小栈

解

准备2个栈，一个数据栈，一个最小栈；入栈时数据栈直接入，最小栈查看栈顶元素是否比当前数小，小就继续压入最小的数，否则压入当前数。

题目三 队列和栈

如何仅用队列结构实现栈结构?

leetcode 225. 用队列实现栈

使用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
public class P0302Stack {

    private Queue<Integer> queue;

    public P0302Stack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        queue.add(x);
        int size = queue.size();
        while (size-- > 1){
            queue.add(queue.poll());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

如何仅用栈结构实现队列结构?

leetcode 232. 用栈实现队列

队列为先进先出，栈为先进后出，使用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
42
public class P0301Queue {

    private final Stack<Integer> inStack;
    private final Stack<Integer> outStack;

    public P0301Queue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public void convert(){
        if (outStack.empty()){
            while (!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
    }

    public int pop() {
        if (empty()){
            throw new RuntimeException("Queue is empty");
        }
        convert();
        return outStack.pop();
    }

    public int peek() {
        if (empty()){
            throw new RuntimeException("Queue is empty");
        }
        convert();
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.empty() && outStack.empty();
    }
}

题目四 动态规划的空间压缩技巧 最小路径和

给你一个二维数组matrix,其中每个数都是正数，要求从左上角走到右下角。每一步只能向右或者向下，沿途经过的数字要累加起来。最后请返回最小的路径和。

leetcode 64 最小路径和

递归

最小的路径取左边和右边的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    return process(grid, m - 1, n - 1);
}

private int process(int[][] grid, int m, int n) {
    // 不能走
    if (m == 0 && n == 0) {
        return grid[0][0];
    }

    if (m < 0 || n < 0) {
        return Integer.MAX_VALUE;
    }

    return Math.min(process(grid, m - 1, m), process(grid, m, n - 1)) + grid[m][n];
}

动态规划

每个位置只与左边和上边的元素有关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 动态规划
public int minPathSum2(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] dp = new int[m][n];
    dp[0][0] = grid[0][0];
    for (int i = 1; i < n; i++) {
        dp[0][i] = dp[0][i - 1] + grid[0][i];
    }
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    return dp[m - 1][n - 1];
}

动态规划空间压缩

对于第一行的数据只依赖于左边的数据

对于第二行的数据，依赖于它右边的数据和上边的数据，而最右边的数据只依赖于上边的数据。那么可以把二维dp表优化为一维dp表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int minPathSum3(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[] dp = new int[n];
    dp[0] = grid[0][0];
    for (int i = 1; i < n; i++) {
        dp[i] = dp[i - 1] + grid[0][i];
    }

    for (int i = 1; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (j == 0){
                dp[j] = dp[j] + grid[i][j];
                continue;
            }
            dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }

    return dp[n - 1];
}

压缩思路

1
2
a b c d e
f g h i j

h依赖于b,c这么更新，如果一个值依赖于上一行左边的几个值， 用一维数组就需要从右向左更新，因为更新时数组中值还没有发生变化，还是上一行的值。

如果h依赖于b,c,g，左边的值，左上角的值，上边的值，对于f来说，a->f没有问题，此时再申请一个变量记住a的值，对于g来说就有了a,b,f的值了，同理h也是。

题目五 装水的容器

给定一个数组arr,已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水
比如，arr = {3, 1, 2, 5，2, 4}，根据值画出的直方图就是容器形状，该容器可以装下5格水
再比如，arr = {4, 5, 1, 3, 2}，该容器可以装下2格水

解

容器可以装下几格水，从每个位置看左侧最大值和右侧最大值，较小的一个和当前位置的差值就是当前位置的最大值，对得到的每个位置求最大值就是可以装的几格水。

如果需要优化时间复杂度，采用双指针的办法，左指针从左边第二个位置开始，右指针从右边第二个开始，左侧最大值小先算左侧，右侧最大值小先算右侧

1
2
3
4
5
10 8 12 5 2 4 11 3 7 

max左侧为10 max右为7
此时右侧最大值小 求解右侧位置的水 7-3=4 右边左移
此时左侧最大值小 求解左侧位置的水 10-8=2 值不变 左边右移
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int getTheMaxOfWater(int[] arr) {

    if (arr == null || arr.length <= 2) {
        return 0;
    }
    int R = arr.length - 2;
    int L = 1;
    int leftMax = arr[0];
    int rightMax = arr[arr.length - 1];
    int water = 0;
    while (L <= R) {
        if (leftMax <= rightMax){
            water += Math.max(0, leftMax - arr[L]);
            leftMax = Math.max(leftMax, arr[L++]);
        }else {
            water += Math.max(0, rightMax - arr[R]);
            rightMax = Math.max(rightMax, arr[R--]);
        }
    }
    return water;
}

题目六 左右最值最大差

给定一个数组arr长度为N，你可以把任意长度大于0且小于N的前缀作为左部分，剩下的作为右部分。但是每种划分下都有左部分的最大值和右部分的最大值，请返回最大的，左部分最大值减去右部分最大值的绝对值。

解

贪心算法，O(n)先找到整体的max值，然后有2种情况

  1. max被划分到左部分, 右部分无论这么切，都会包含位置为N-1的数（小于这个位置的数不会统计，大于这个位置的数会降低结果）。max-arr[N-1]
  2. 同理max被划分到右部分，左部分无论这么切，都会包含位置为0的数（小于这个位置的数不会统计，大于这个位置的数会降低结果）。max-arr[0]

最后得出的2个数求最大值既是结果。

1
2
3
4
5
6
7
8
9
10
11
12
public int getLeftRightMax(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }

    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }

    return Math.max(Math.abs(max - arr[0]), Math.abs(max - arr[arr.length - 1]));
}

题目七 旋转字符串

如果一一个字符串为str，把字符串str前面任意的部分挪到后面形成的字符串叫作str的旋转词。比如str=” 12345”，str 的旋转有”12345”、”23451”、”34512”、”45123”和”51234”。 给定两个字符串a和b，请判断a和b是否互为旋转词。
比如:

1
2
3
a="cdab"，b="abcd"，返回true。
a="1ab2"，b="ab12"，返回false。 
a="2ab1"，b="ab12"，返回true。

解

有以下几个判断标准

  1. a和b的长度是否一样
  2. a+a,判断b是否是其子串
1
2
3
4
5
6
7
8
public boolean rotateString(String s, String goal) {
    if (s.length() != goal.length()){
        return false;
    }

    String doubleS = s + s;
    return doubleS.contains(goal);
}

题目八 咖啡杯问题

给定一个数组arr,已知其中所有的值都是非负的，一个数代表一台咖啡机运行时间，有n个人要喝咖啡，每个人只喝一杯，只有一台洗咖啡杯的机器，时间为a，一次一杯，咖啡杯不洗自然干净的时间为b,问n个人从喝咖啡开始，到咖啡杯洗干净需要多少时间。

解

贪心+动态规划

这个问题分为2个部分，首先计算出每个人喝完咖啡的时间，然后根据每个人的结束时间计算洗杯子的时间。

  1. 每个人喝咖啡的时间计算，使用贪心算法，总是使用最先结束的，如果同一时间结束的有多个杯子，就使用运行时间最短的一个机器，算出每个人的结束时间。采用最小堆的方式（优先级队列）。

  2. 得到每个人的结束时间后，每个人是选择机器洗还是自然风干，使用递归的方式，假设洗咖啡杯的机器washline才有空，就从选择等机器和选择自然风干中选择用时最短的即可

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
public static int shortestCoffeeCup(int[] coffee, int n, int a, int b) {

    // 最小堆 0位置放置结束时间， 1位置放置机器做咖啡的实际，2者相加最小的就是堆顶
    PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return (o1[0] + o1[1]) - (o2[0] + o2[1]);
        }
    });
    for (int i = 0; i < coffee.length; i++) {
        queue.add(new int[]{0, coffee[i]});
    }

    // 计算每个人的终止时间
    int[] drinks = new int[n];
    for (int i = 0; i < n; i++) {
        int[] drink = queue.poll();
        drink[0] += drink[1];
        drinks[i] = drink[0];
        queue.add(drink);
    }

    // 递归计算最小值
    // return process(drinks, a, b, 0, 0);
    return getMinTime(drinks, a, b);
}

// a洗咖啡杯时间 b自动挥发的实际 washLine洗碗机空闲空闲的时间
public static int process(int[] drinks, int a, int b, int index, int washLine) {
    if (index == drinks.length - 1) {
        return Math.min(Math.max(washLine, drinks[index]) + a, drinks[index] + b);
    }
    // 放咖啡机洗
    int wash = Math.max(washLine, drinks[index]) + a;
    // 洗完剩下的咖啡杯最早结束时间
    int next1 = process(drinks, a, b, index + 1, wash);
    int p1 = Math.max(wash, next1);

    // 自动挥发
    int dry = drinks[index] + b;
    int next2 = process(drinks, a, b, index + 1, washLine);
    int p2 = Math.max(dry, next2);
    return Math.min(p1, p2);
}

// index 0 - n-1
// washLine drinks[0] + na drinks[1] +(n-1)a  最大值 或者 最后一个时间点 + na
public static int getMinTime(int[] drinks, int a, int b) {
    int n = drinks.length;
    int[][] dp = new int[n][drinks[n - 1] + n * a];
    // basecase
    for (int i = 0; i < dp[0].length; i++) {
        // i就是washLine
        dp[n - 1][i] = Math.min(Math.max(i, drinks[n - 1]) + a, drinks[n - 1] + b);
    }
    for (int row = n - 2; row >= 0; row--) {
        int washLine = drinks[row] + (row + 1) * a;
        for (int col = 0; col < washLine; col++) {
            int wash = Math.max(col, drinks[row]) + a;
            // 2种取最优解
            dp[row][col] = Math.min(Math.max(wash, dp[row + 1][wash]), Math.max(drinks[row] + b, dp[row + 1][col]));
        }
    }
    return dp[0][0];
}