力扣热题5-接雨水

---

按照leetcode刷一遍：leetcode hot

42. 接雨水

左右最高峰

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        // 当前最高峰
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        leftMax[0] = height[0];
        rightMax[n-1] = height[n-1];
        for(int i=1;i<n;i++) {
            leftMax[i] = Math.max(height[i],leftMax[i-1]);
        }
        for(int i=n-2;i>=0;i--) {
            rightMax[i] = Math.max(rightMax[i+1],height[i]);
        }
        int result = 0;
        for(int i=1;i<n-1;i++) {
            result+=Math.max(Math.min(rightMax[i+1],leftMax[i-1])-height[i],0);
        }
        return result;
    }
}

单调队列

并没有前一个方法好理解。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int result = 0;
        // 单调递减队列的index
        Deque<Integer> deque = new LinkedList<>();
        deque.addLast(0);
        for(int i=1;i<n;i++) {
            if(deque.isEmpty()||height[i]<height[deque.peekLast()]) {
                deque.addLast(i);
            } else {
                int cur;
                while(!deque.isEmpty()) {
                    cur = deque.peekLast();
                    if(height[cur]<=height[i]) {
                        deque.removeLast();
                        if(deque.isEmpty()) {
                            break;
                        }
                        result += (Math.min(height[i],height[deque.peekLast()])-height[cur])*(i-deque.peekLast()-1);
                    } else {
                        break;
                    }
                }
                deque.addLast(i);
            }
        }
        return result;
    }
}

46. 全排列

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        permuteHelper(nums,deque,result,visited);
        return result;
    }

    private void permuteHelper(int[] nums,Deque<Integer> deque,List<List<Integer>> result,Set<Integer> visited) {
        if(deque.size()==nums.length) {
            result.add(new ArrayList(deque));
            return;
        }
        for(int i=0;i<nums.length;i++) {
            if(visited.contains(nums[i])) {
                continue;
            }
            deque.addLast(nums[i]);
            visited.add(nums[i]);
            permuteHelper(nums,deque,result,visited);
            deque.pollLast();
            visited.remove(nums[i]);
        }
    }
}

48. 旋转图像

直接模拟即可。

class Solution {
    public void rotate(int[][] matrix) {
        int cur;
        int n = matrix.length;
        for(int i=0;i<n/2;i++) {
            for(int j=i;j<n-1-i;j++) {
                cur = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[n-1-(n-1-j)][n-1-i];
                matrix[n-1-(n-1-j)][n-1-i] = cur;
            }
        }
    }
}

49. 字母异位词分组

我用的map sorted，也可以map的键用字母出现次数的hash。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        String sortedStr;
        for(String str:strs) {
            char[] chrs = str.toCharArray();
            Arrays.sort(chrs);
            sortedStr = new String(chrs);
            if(!map.containsKey(sortedStr)) {
                map.put(sortedStr,new ArrayList<>());
            }
            map.get(sortedStr).add(str);
        }

        List<List<String>> result = new ArrayList<>();
        for(String k:map.keySet()) {
            result.add(map.get(k));
        }
        return result;
    }
}