作者：mlq

题目

https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/

题解

直接用栈,和栈顶元素相同就pop出去

public String removeDuplicates(String S) {
    if (S.length() <= 1) {
        return S;
    }
    Deque<Character> stack = new ArrayDeque<>();
    stack.push(S.charAt(0));
    for (int i = 1; i < S.length(); i++) {
        if (!stack.isEmpty() && (stack.peek() == S.charAt(i))) {
            stack.pop();
        } else {
            stack.push(S.charAt(i));
        }
    }
    return revStack(stack);
}

private String revStack(Deque<Character> stack) {
    char[] array = new char[stack.size()];
    int len = array.length - 1;
    while (!stack.isEmpty()) {
        array[len] = stack.pop();
        len--;
    }
    return new String(array);
}

题目

https://leetcode-cn.com/problems/palindrome-partitioning-ii/

题解

这个想到 https://leetcode-cn.com/problems/palindrome-partitioning/ 这个题,只要path变成integer就可以,但是这么递归会超时.

所以需要优化的地方一个是判断一个子串是否是回文串,一个是通过dp来找最小值

优化回文子串判断

设定一个boolea[][] 如果s.charAt[1]==s.charAt[j] boolean[i][j] = boolean[i+1][j-1]

dp求回文子串最小值

该字符独立消耗一次分割次数。此时有 f[j] = f[j – 1] + 1
该字符不独立消耗一次分割次数，而是与前面的某个位置 i 形成回文串，[i, j] 作为整体消耗一次分割次数。此时有 f[j] = f[i – 1] + 1

public int minCut(String s) {
    char[] charArray = s.toCharArray();
    boolean[][] hArray = new boolean[charArray.length][charArray.length];
    for (int i = charArray.length - 1; i >= 0; i--) {
        for (int j = i; j < charArray.length; j++) {
            if (j - i <= 1) {
                hArray[i][j] = charArray[i] == charArray[j];
            } else {
                hArray[i][j] = hArray[i + 1][j - 1] && charArray[i] == charArray[j];
            }
        }
    }
    int[] dp = new int[s.length()];
    for (int i = 1; i < s.length(); i++) {
        if (hArray[0][i]) {
            dp[i] = 0;
        } else {
            dp[i] = dp[i - 1] + 1;
            for (int j = 1; j < i; j++) {
                if (hArray[j][i]) {
                    dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }
    }
    return dp[s.length() - 1];
}

题目

https://leetcode-cn.com/problems/palindrome-partitioning/

题解

递归调用,dfs(String s, int startIndex, int endIndex, Stack<String> path, List<List<String>> result) path存储已经分割过的路径,result存储结果,startIndex和endIndex是待分割区间,每次分割之后要把上次的path弹出,比如aab 如果切分a|ab path里面就是a ab再次切割需要吧ab弹出i+1这样就可以切割成a|a|b

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    Stack<String> path = new Stack<>();
    dfs(s, 0, s.length(), path, result);
    return result;
}

private void dfs(String s, int startIndex, int endIndex, Stack<String> path, List<List<String>> result) {
    if (startIndex == endIndex) {
        result.add(new ArrayList(path));
        return;
    }
    for (int i = startIndex; i < s.length(); i++) {
        if (!isPar(s, startIndex, i)) {
            continue;
        }
        path.push(new String(s.toCharArray(), startIndex, i + 1 - startIndex));
        dfs(s, i + 1, endIndex, path, result);
        path.pop();
    }
}

private boolean isPar(String s, int startIndex, int endIndex) {
    while (startIndex < endIndex) {
        if (s.charAt(startIndex) != s.charAt(endIndex)) {
            return false;
        }
        startIndex++;
        endIndex--;
    }
    return true;
}

题目

https://leetcode-cn.com/problems/next-greater-element-ii/

解法

暴力略（由于是循环数组，为了找循环的最大值，可以将原数组复制成2*nums.lenth长度的，或者i%nums.length）

单调栈

维护一个递减的单调栈，栈里面存放index，如果后边得数字比栈顶的大那么证明，遍历到的数字是第一个比栈顶nums[index]大的数值

public int[] nextGreaterElements(int[] nums) {
    int[] result = new int[nums.length];
    Arrays.fill(result, -1);
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < nums.length * 2; i++) {
        int num = nums[i % nums.length];
        while (!stack.isEmpty() && nums[stack.peek()] < num) {
            result[stack.pop()] = num;
        }
//只有比length小的index才可以入队列，保证length后边的数字只是遍历，不会影响栈里面的值
        if (i < nums.length) {
            stack.push(i);
        }
    }
    return result;
}

题目

https://leetcode-cn.com/problems/implement-queue-using-stacks/

题解

直接两个栈互相导就可以,栈A导入到栈B里面就是队列的正序

import java.util.Stack;
public class MyQueue {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.push(1);
        myQueue.push(2);
        myQueue.push(3);
        myQueue.push(4);
        System.out.println(myQueue.pop());
        myQueue.push(5);
        System.out.println(myQueue.pop());
        System.out.println(myQueue.pop());
        System.out.println(myQueue.pop());
        System.out.println(myQueue.pop());
    }

    Stack<Integer> stackOne;

    Stack<Integer> stackTwo;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        stackOne = new Stack<>();
        stackTwo = new Stack<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        if (stackOne.size() != 0 || (stackOne.size() == 0 && stackTwo.size() == 0)) {
            stackOne.push(x);
        } else {
            while (!stackTwo.isEmpty()) {
                stackOne.push(stackTwo.pop());
            }
            stackOne.push(x);
        }
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (stackTwo.size() != 0) {
            return stackTwo.pop();
        }
        while (!stackOne.isEmpty()) {
            stackTwo.push(stackOne.pop());
        }
        return stackTwo.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
        if (stackTwo.size() != 0) {
            return stackTwo.peek();
        }
        while (!stackOne.isEmpty()) {
            stackTwo.push(stackOne.pop());
        }
        return stackTwo.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return stackTwo.size() + stackOne.size() == 0;
    }
}

优化

我们每次push都维护了一个全局的正序,所以没次push和pop的时候如果stackTwo有值我们会把two的在放回到one中,保持一个全局的一致性,但是其实可以不这么做,push的时候只需要直接push one即可,pop也直接two的,如果two没有值了,在将one的导入到two中,因为one里面的数据一定在pop的后边,所以并不需要没次push的时候都清空two所以push方法,只需要直接push到one里面即可

题目

https://leetcode-cn.com/problems/russian-doll-envelopes/

题解

这个题可以看成是求最长递增子序列的变题，一旦把（x,y）的x先做排序之后，剩下的问题就是如何求y的最大递增子序列，并且递增子序列中x不可以相等

如何求一个一维数组的递增子序列

d[i]表示以i结尾的最长子序列，所以只要能找到d[0~i-1]之间的k,d[k]<d[i]并且d[k]是max(d[0~i-1]),那么d[i] = d[k]+1

public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        }
    });
    int max = 0;
    int dp[] = new int[envelopes.length];
    dp[0] = 1;
    for (int i = 1; i < envelopes.length; i++) {
        int tmpMax = 1;
        for (int j = i - 1; j >= 0; j--) {
            if (envelopes[i][1] > envelopes[j][1] && envelopes[i][0] > envelopes[j][0]) {
                tmpMax = Math.max(tmpMax, dp[j] + 1);
            }
        }
        dp[i] = tmpMax;
        max = Math.max(tmpMax, max);
    }
    return max;
}

题目

https://leetcode-cn.com/problems/counting-bits/

题解

递归,如果是偶数f(n) = f(n/2), 如果是奇数f(n) = f(n-1)+1

public int[] countBits(int num) {
    int[] result = new int[num + 1];
    // 如果是偶数f(n) = f(n/2)
    // 如果是奇数f(n) = f(n-1)+1
    result[0] = 0;
    for (int i = 1; i <= num; i++) {
        if (i % 2 == 1) {
            result[i] = result[i - 1] + 1;
        } else {
            result[i] = result[i / 2];
        }
    }
    return result;
}

题目

https://leetcode-cn.com/problems/range-sum-query-2d-immutable/

题解

1。利用一维数组前缀和

我们以前做过求任意一个一维数组的子序列和，这次变成二维的了，可以先求一维数组的和，然后每一行遍历累加matrix为原数组，subResult为一维数组的前缀和数组

public NumMatrix(int[][] matrix) {
    if(matrix.length==0){
        return;
    }
    this.matrix = matrix;
    subResult = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < subResult.length; i++) {
        int result = 0;
        for (int j = 0; j < subResult[0].length; j++) {
            result += matrix[i][j];
            subResult[i][j] = result;
        }
    }
}

public int sumRegion(int row1, int col1, int row2, int col2) {
    int result = 0;
    for (int i = row1; i <= row2; i++) {
        result += subResult[i][col2] - subResult[i][col1] + matrix[i][col1];
    }
    return result;
}

2。 二维数组前缀和

https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/ru-he-qiu-er-wei-de-qian-zhui-he-yi-ji-y-6c21/

其中有个小技巧和我们求一维数组子序列和一样，可以对subResult数组行和列多加1，可以减少一些if边界判断。

题目

https://leetcode-cn.com/problems/range-sum-query-immutable/

题解

1.循环直接求解

2.求出每一个的前缀和,如果那么subSum[i,j] = sums[j]-sums[i-1]

class NumArray {

    int[] sums;
    public NumArray(int[] nums) {
        sums = new int[nums.length];
        if (sums.length > 0) {
            sums[0] = nums[0];
        }
        for (int i = 1; i < nums.length; i++) {
            sums[i] = nums[i] + sums[i - 1];
        }
    }
    
    public int sumRange(int i, int j) {
        if(i==0){
            return sums[j];
        }
        return sums[j]-sums[i-1];
    }
}
其中因为if判断beginIndex i是否为0也是消耗时间的所以可以将sums[0]先设置成0,然后从1开始记录,这样就不会数组越界,减少判断

题目

https://leetcode-cn.com/problems/monotonic-array/

题解

先遍历一边看下第一不相同的地方是递增还是递减，然后在遍历如果不符合上边的规律返回false否则就是true，这里第二次遍历可以不从0开始，可以从第一次的返回的坐标开始

public boolean isMonotonic(int[] A) {
    int i = 0;
    int sun = 0;
    for (; i < A.length - 1; i++) {
        if (A[i] == A[i + 1]) {
            continue;
        }
        sun = A[i] < A[i + 1] ? 1 : 0;
        break;
    }
    for (; i < A.length - 1; i++) {
        if (sun == 0 && A[i] > A[i + 1]) {
            return false;
        }
        if (sun == 1 && A[i] < A[i + 1]) {
            return false;
        }
    }
    return true;
}

还有一种方法记录sun的值，可以有两个变量记录递增或者递减的情况，比如A[i]<A[i+1] a=1,A[i]>A[i+1] b=1,一旦最后a+b=2,则不是递增/减序列