Leetcode Hot 100 (brush question 9) (301/45/517/407/offer62/mst08.14/)

Catalog

1.leetcode301 Remove invalid brackets

2.leetcode45 Jumping game II

3.leetcode517 Super washing machine

4.leetcode407 Rainwater collection II

5. Interview questions 08.14. Boolean operation

6. The finger of the sword Offer 62. The last number in the circle

---

1.leetcode301 Remove invalid brackets

class Solution {
    //  come from leetcode Vote for the first answer , The implementation is very good , Let's appreciate 
    public static List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<>();
        remove(s, ans, 0, 0, new char[] { '(', ')' });
        return ans;
    }
 
    // modifyIndex <= checkIndex
    //  Just check s[checkIndex....] Part of , Because the previous one must have been adjusted correctly 
    //  But how to adjust the previous part correctly , Where has it been adjusted ？ Namely modifyIndex
    //  such as ：
    // ( ( ) ( ) ) ) ...
    // 0 1 2 3 4 5 6
    //  At first, of course checkIndex = 0,modifyIndex = 0
    //  When found 6 When , It's not right ,
    //  Then you can remove 2 Location 、4 Positional  ), Fine 
    //  If you remove 2 Positional  ),  So the next step is 
    // ( ( ( ) ) ) ...
    // 0 1 2 3 4 5 6
    // checkIndex = 6 ,modifyIndex = 2
    //  If you remove 4 Positional  ),  So the next step is 
    // ( ( ) ( ) ) ...
    // 0 1 2 3 4 5 6
    // checkIndex = 6 ,modifyIndex = 4
    //  in other words ,
    // checkIndex and modifyIndex, Respectively indicates the beginning of the search   and   The beginning of the adjustment , Never mind the previous   par  (  )
    public static void remove(String s, List<String> ans, int checkIndex, int deleteIndex, char[] par) {
        for (int count = 0, i = checkIndex; i < s.length(); i++) {
            if (s.charAt(i) == par[0]) {
                count++;
            }
            if (s.charAt(i) == par[1]) {
                count--;
            }
            // i check Count <0 The first position 
            if (count < 0) {
                for (int j = deleteIndex; j <= i; ++j) {
                    //  such as 
                    if (s.charAt(j) == par[1] && (j == deleteIndex || s.charAt(j - 1) != par[1])) {
                        remove(
                                s.substring(0, j) + s.substring(j + 1, s.length()),
                                ans, i, j, par);
                    }
                }
                return;  // Delete the first illegal .  direct return
            }
        }
        String reversed = new StringBuilder(s).reverse().toString();
        if (par[0] == '(') {
            remove(reversed, ans, 0, 0, new char[] { ')', '(' });
        } else {
            ans.add(reversed);
        }
    }
}

2.leetcode45 Jumping game II

/**
    O(N)
    O(1)
 */
class Solution {
    public static int jump(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int step = 0;
        int cur = 0;
        int next = 0;
        for (int i = 0; i < arr.length; i++) {
            if (cur < i) {
                step++;
                cur = next;
            }
            next = Math.max(next, i + arr[i]);
        }
        return step;
    }
}

3.leetcode517 Super washing machine

class Solution {
      public  int findMinMoves(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int size = arr.length;
        int sum = 0;
        for (int i = 0; i < size; i++) {
            sum += arr[i];
        }
        if (sum % size != 0) {
            return -1;
        }
        int avg = sum / size;
        int leftSum = 0;
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            int leftRest = leftSum - i * avg;
            int rightRest = (sum - leftSum - arr[i]) - (size - i - 1) * avg;
            if (leftRest < 0 && rightRest < 0) {
                ans = Math.max(ans, Math.abs(leftRest) + Math.abs(rightRest));
            } else {
                ans = Math.max(ans, Math.max(Math.abs(leftRest), Math.abs(rightRest)));
            }
            leftSum += arr[i];
        }
        return ans;
    }
}

4.leetcode407 Rainwater collection II

class Solution {
    public static class Node {
        public int value;
        public int row;
        public int col;
 
        public Node(int v, int r, int c) {
            value = v;
            row = r;
            col = c;
        }
 
    }
    public static int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0 || heightMap[0] == null || heightMap[0].length == 0) {
            return 0;
        }
        int N = heightMap.length;
        int M = heightMap[0].length;
        boolean[][] isEnter = new boolean[N][M];
        PriorityQueue<Node> heap = new PriorityQueue<>((a, b) -> a.value - b.value);
        for (int col = 0; col < M - 1; col++) {
            isEnter[0][col] = true;
            heap.add(new Node(heightMap[0][col], 0, col));
        }
        for (int row = 0; row < N - 1; row++) {
            isEnter[row][M - 1] = true;
            heap.add(new Node(heightMap[row][M - 1], row, M - 1));
        }
        for (int col = M - 1; col > 0; col--) {
            isEnter[N - 1][col] = true;
            heap.add(new Node(heightMap[N - 1][col], N - 1, col));
        }
        for (int row = N - 1; row > 0; row--) {
            isEnter[row][0] = true;
            heap.add(new Node(heightMap[row][0], row, 0));
        }
        int water = 0;
        int max = 0;
        while (!heap.isEmpty()) {
            Node cur = heap.poll();
            max = Math.max(max, cur.value);
            int r = cur.row;
            int c = cur.col;
            //    On 
            if (r > 0 && !isEnter[r - 1][c]) {
                water += Math.max(0, max - heightMap[r - 1][c]);
                isEnter[r - 1][c] = true;
                heap.add(new Node(heightMap[r - 1][c], r - 1, c));
            }
            //   Next 
            if (r < N - 1 && !isEnter[r + 1][c]) {
                water += Math.max(0, max - heightMap[r + 1][c]);
                isEnter[r + 1][c] = true;
                heap.add(new Node(heightMap[r + 1][c], r + 1, c));
            }
            //  Left 
            if (c > 0 && !isEnter[r][c - 1]) {
                water += Math.max(0, max - heightMap[r][c - 1]);
                isEnter[r][c - 1] = true;
                heap.add(new Node(heightMap[r][c - 1], r, c - 1));
            }
            //  Right 
            if (c < M - 1 && !isEnter[r][c + 1]) {
                water += Math.max(0, max - heightMap[r][c + 1]);
                isEnter[r][c + 1] = true;
                heap.add(new Node(heightMap[r][c + 1], r, c + 1));
            }
        }
        return water;
    }
}

5. Interview questions 08.14. Boolean operation

class Solution {
    public  int countEval(String express, int desired) {
        if (express == null || express.equals("")) {
            return 0;
        }
        char[] exp = express.toCharArray();
        int N = exp.length;
        Info[][] dp = new Info[N][N];
        Info allInfo = func(exp, 0, exp.length - 1, dp);
        return desired == 1 ? allInfo.t : allInfo.f;
    }
 
 
    public  class Info {
        public int t;   // by true The number of ways 
        public int f;   // by false The number of ways 
 
        public Info(int tr, int fa) {
            t = tr;
            f = fa;
        }
    }
 
    //  Limit :
    // L...R On , There must be an odd number of characters 
    // L The character of the position and R The character of position , Not 0 namely 1, Cannot be a logical symbol ！
    //  return str[L...R] This is a piece of , by true The number of ways , and false The number of ways 
    public  Info func(char[] str, int L, int R, Info[][] dp) {
        if (dp[L][R] != null) {
            return dp[L][R];
        }
        int t = 0;
        int f = 0;
        if (L == R) {
            t = str[L] == '1' ? 1 : 0;
            f = str[L] == '0' ? 1 : 0;
        } else { // L..R >=3
            //  Every logical symbol ,split Enumerating things 
            //  Try the final combination 
            for (int split = L + 1; split < R; split += 2) {
                Info leftInfo = func(str, L, split - 1, dp);
                Info rightInfo = func(str, split + 1, R, dp);
                int a = leftInfo.t;
                int b = leftInfo.f;
                int c = rightInfo.t;
                int d = rightInfo.f;
                switch (str[split]) {
                    case '&':
                        t += a * c;
                        f += b * c + b * d + a * d;
                        break;
                    case '|':
                        t += a * c + a * d + b * c;
                        f += b * d;
                        break;
                    case '^':
                        t += a * d + b * c;
                        f += a * c + b * d;
                        break;
                }
            }
 
        }
        dp[L][R] = new Info(t, f);
        return dp[L][R];
    }
}

6. The finger of the sword Offer 62. The last number in the circle

/**
      The formula ：   front  = （ after  + m - 1） % i + 1 
*/
    //  Submit directly through 
    //  The given number is 0~n-1 Under the circumstances , Count to m Just kill 
    //  Return to who will live ？
    public int lastRemaining1(int n, int m) {
        return getLive(n, m) - 1;
    }
 
    //  The setting of the topic in class is , The given number is 1~n Under the circumstances , Count to m Just kill 
    //  Return to who will live ？
    public static int getLive(int n, int m) {
        if (n == 1) {
            return 1;
        }
        // The formula ： front  = （ after  + m - 1） % i + 1 ;
        return (getLive(n - 1, m) + m - 1) % n + 1;
    }




class Solution {
    public int lastRemaining(int n, int m) {
        int ans = 1;
        int r = 1;
        while (r <= n) {
            ans = (ans + m - 1) % (r++) + 1;
        }
        return ans - 1;
    }
}