给一个数组, 求返回一个数组, 是当前数字往右看到所有的数字的数量.

好吧..有点费劲, 上来能反应过来是单调栈, 然后实现发现怎么也过不了, 原来题意中定义的看到不是说小于当前数,而是问有多少递增的数字. 比如[11,2,1,12]中, 11能看到的只有2和12…..1是看不到的..被2挡住了

class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        Stack<Integer> st = new Stack<>();
        int[] res = new int[heights.length];
        for(int i = heights.length - 1; i >= 0; i--){
            int count = 0;
            while(!st.isEmpty() && st.peek() < heights[i]){
                count++;
                st.pop();
            }
            res[i] = count + (st.isEmpty() ? 0 : 1);
            st.push(heights[i]);
        }
        return res;
    }
}

给一个BST做遍历器.

这题吧, 我答案又不用额外数组的…我做了做实在难…

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
    List<Integer> l;
    int index = -1;
    public BSTIterator(TreeNode root) {
        l = convert(root);
    }
    private List<Integer> convert(TreeNode root){
        List<Integer> list = new ArrayList<Integer>();
        if(root == null)
            return list;
        list.addAll(convert(root.left));
        list.add(root.val);
        list.addAll(convert(root.right));
        return list;
    }
    
    public boolean hasNext() {
        return index < l.size() - 1;
    }
    
    public int next() {
        return l.get(++index);
    }
    
    public boolean hasPrev() {
        System.out.println(index);
        return 0 < index;
    }
    
    public int prev() {
        return l.get(--index);
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * boolean param_1 = obj.hasNext();
 * int param_2 = obj.next();
 * boolean param_3 = obj.hasPrev();
 * int param_4 = obj.prev();
 */

给一个字符串s, 求有多少种分割方法, 让分割的两个字符串的不同字符数量相同.

class Solution {
    public int numSplits(String s) {
        int res = 0;
        Map<Character, Integer> map = new HashMap<>();
        for(char c : s.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);
        Map<Character, Integer> left = new HashMap<>();
        for(char c : s.toCharArray()){
            left.put(c, left.getOrDefault(c, 0) + 1);
            map.put(c, map.get(c) - 1);
            if(map.get(c) == 0)
                map.remove(c);
            if(map.size() == left.size())
                res++;
        }
        return res;
    }
}

也是2d fenwick树.

class NumMatrix {
int[][] matrix;
    int[][] BIT;
    int n;
    int m;
      public int lowbit(int x){
        return x & (-x);
    }
    
    public void set(int r, int c, int val){
        r++;
        c++;
       for(int i = r; i <= n; i += lowbit(i)){
            for(int j = c; j <= m; j += lowbit(j)){
                BIT[i][j] += val;
            }
        }
    }
    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        this.n = matrix.length;
        this.m = matrix[0].length;
        this.BIT = new int[n + 1][m + 1];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                set(i,j,matrix[i][j]);
            }
        }
    }
       public int sum(int r, int c) {
        int s = 0;
        r++;
        c++;
        for(int i = r; i > 0; i -= lowbit(i)){
            for(int j = c; j > 0; j -= lowbit(j)){
                s += BIT[i][j];
            }
        }
        return s;
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return (sum(row2, col2) + sum(row1 - 1, col1 - 1)) - (sum(row2, col1 - 1) + sum(row1 - 1, col2));
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

2d fenwick树.

class NumMatrix {
    int[][] matrix;
    int[][] BIT;
    int n;
    int m;
    
    public int lowbit(int x){
        return x & (-x);
    }
    
    public void set(int r, int c, int val){
        r++;
        c++;
       for(int i = r; i <= n; i += lowbit(i)){
            for(int j = c; j <= m; j += lowbit(j)){
                BIT[i][j] += val;
            }
        }
    }
    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        this.n = matrix.length;
        this.m = matrix[0].length;
        this.BIT = new int[n + 1][m + 1];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                set(i,j,matrix[i][j]);
            }
        }
    }
   
    public void update(int i, int j, int val) {
        int diff = val - matrix[i][j];
        matrix[i][j] = val;
        set(i, j, diff);
    }
    
    public int sum(int r, int c) {
        int s = 0;
        r++;
        c++;
        for(int i = r; i > 0; i -= lowbit(i)){
            for(int j = c; j > 0; j -= lowbit(j)){
                s += BIT[i][j];
            }
        }
        return s;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return (sum(row2, col2) + sum(row1 - 1, col1 - 1)) - (sum(row2, col1 - 1) + sum(row1 - 1, col2));
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * obj.update(row,col,val);
 * int param_2 = obj.sumRegion(row1,col1,row2,col2);
 */

求range sum, fenwick tree.

class NumArray {
    int[] nums;
    int[] BIT;
    public int lowbit(int x) {
        return x&(-x);
    }
    
    public void set(int i, int val){
        i++;
        while(i <= nums.length){
            BIT[i] += val;
            i += lowbit(i);
        }
    }
     
    public NumArray(int[] nums) {
        this.nums = nums;
        this.BIT = new int[nums.length + 5];
        for(int i = 0; i < nums.length; i++)
            set(i, nums[i]);
    }
    
    public void update(int index, int val) {
        int diff = val - nums[index];
        nums[index] = val;
        set(index, diff);
    }
    
    public int sumRange(int left, int right) {
        return sum(right) - sum(left - 1);
    }
    
    public int sum(int i){
        int s = 0;
        i++;
        while(i > 0){
            s += BIT[i];
            i -= lowbit(i);
        }
        return s;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */

给一个平衡的括号组成的字符串, 求字符串的score.

这个我自己的code太长了, 抄个答案

class Solution {
    public int scoreOfParentheses(String s) {
        Stack<Integer> st = new Stack<>();
        st.push(0);
         for(char c : s.toCharArray()){
            if(c == '('){
                st.push(0);
            }
            else
            {
                int i = st.pop();
                int j = st.pop();
                st.push(j + Math.max((i * 2), 1));
            }
        }
        return st.peek();
    }
}

给几个数组, 求所有数字重复的, 并且排序.

class Solution {
    public List<Integer> intersection(int[][] nums) {
        Set<Integer> set = new HashSet<>();
        for(int n : nums[0])
            set.add(n);
        for(int i = 1; i < nums.length; i++) {
            Set<Integer> tmp = new HashSet<>();
            for(int j = 0; j < nums[i].length; j++) {
                tmp.add(nums[i][j]);
            }
            set.retainAll(tmp);
        }
        
        List<Integer> list = new ArrayList<>();
        for(int n : set)
            list.add(n);
        Collections.sort(list);
        return list;
    }
}

上课问题, 拓扑排序, 但是这题可以在同一时间连续上课, 然后求最优.

因为可以并行上课, 所以是一道dp问题, dp[i]= max(max(dp[i],dp[i]+time[i]), dp[j]) j is the neighbor of i.

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        int[] onto = new int[n + 1];
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int[] r : relations) {
            onto[r[1]]++;
            Set<Integer> set = map.getOrDefault(r[0], new HashSet<>());
            set.add(r[1]);
            map.put(r[0],set);
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i <= n; i++){
            if(onto[i] == 0)
                queue.add(i);
        }
        int res = 0; 
        int[] dp = new int[n + 1];
        while(!queue.isEmpty()){
            int cur = queue.poll();
            dp[cur] = dp[cur] + time[cur - 1];
            res = Math.max(dp[cur], res);
            for(int cc : map.getOrDefault(cur, new HashSet<>())){
                dp[cc] = Math.max(dp[cc], dp[cur]);
                onto[cc]--;
                if(onto[cc] == 0)
                    queue.add(cc);
            }
        }
        return res; 
    }
}

class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    
    private void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            // no need to sort
            return;
        }
        // step 1: select a pivot
        Random rand = new Random();
        int randPivot = rand.nextInt(end - start + 1);
        int pivotLocation = start + randPivot;
        int pivot = nums[pivotLocation];
        // step 2: partition
        swap(nums, pivotLocation, end);
        
        int left = start;
        int right = end - 1;
        
        while (left <= right) {
            while (left <= right && nums[left] <= pivot) {
                left++;
            }
            while (left <= right && nums[right] >= pivot) {
                right--;
            }
            if (left < right) {
                swap(nums, left, right);
            }
        }
        swap(nums, left, end);
        quickSort(nums, start, left - 1);
        quickSort(nums, left + 1, end);
        return;
        
    }
    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}