2020-06-18

题目汇总

LeetCode 739. Daily Temperatures

算法思路

单调栈

class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 典型的单调栈题目
        Stack<Integer> stack = new Stack();
        int[] res = new int[T.length];

        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && T[stack.peek()] < T[i]) {
                res[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }

        return res;
    }
}

LeetCode 274. H-Index

算法思路

274和275我觉得是很垃圾的两道题，有点像脑筋急转弯。对于274题，其实就是找出一个数x，使得数组中大于等于x的数恰好为x个。

注意，这里找到的hindex不一定是数组里的数，例如:[4,0,6,1,5]的hindex就是3。

这里有个弯需要绕一下，就是while循环那里，我们的h要从小到大去遍历，而查找citation的数量需要从后向前找，因为这是一个相遇问题而不是追击问题。需要细品一下。

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);

        // 最终的h的值一定是小于n的，看一下solution里的图就可以明白
        int n = citation.length, h = 0;
        while (h < n && citations[n - h - 1] > h) {
            h++;
        }

        return h;
    }
}

LeetCode 275. H-Index II

算法思路

和274基本一致，只是这里的array是有序的，用二分查找更方便。目标是找到一个target似的citations[i]
= n - i，如果没有这样的i，那么最终的left及其后面的数的数量就是h个。

class Solution {
  public int hIndex(int[] citations) {
    int idx = 0, n = citations.length;
    int pivot, left = 0, right = n - 1;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (citations[pivot] == n - pivot) return n - pivot;
      else if (citations[pivot] < n - pivot) left = pivot + 1;
      else right = pivot - 1;
    }
    return n - left;
  }
}

LeetCode 36. Valid Sudoku

算法思路

就是通过多个hashmap或者hashset来对每一行、每一列以及每一个box进行查找。

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 这道题只要判断数独是否合法，而不一定有解！！！
        // 分情况讨论即可

        // 检查每一行是否valid
        for (int i = 0; i < 9; i++) {
            Set<Character> dict = new HashSet(); 
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    if (dict.contains(board[i][j])) {
                        return false;
                    }
                    dict.add(board[i][j]);
                }
            }
        }

        // 检查每一列是否valid
        for (int j = 0; j < 9; j++) {
            Set<Character> dict = new HashSet(); 
            for (int i = 0; i < 9; i++) {
                if (board[i][j] != '.') {
                    if (dict.contains(board[i][j])) {
                        return false;
                    }
                    dict.add(board[i][j]);
                }
            }
        }

        // 检查每一个3x3小方框是否valid
        Set<Character>[] dicts = new HashSet[9];
        for (int i = 0; i < 9; i++) {
            dicts[i] = new HashSet<Character>();
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int id = (i / 3) * 3 + j / 3;
                if (board[i][j] != '.') {
                    if (dicts[id].contains(board[i][j])) {
                        return false;
                    }
                    dicts[id].add(board[i][j]);
                }
            }
        }

        return true;
    }
}