LeetCode刷题笔记

LeetCode刷题笔记，记录一些非常值得记录的算法题…..

寻找输入流的中位数

LeetCode 295. Find Median from Data Stream
剑指Offer

使用两个堆：一个大顶堆，一个小顶堆。其中，大顶堆用于存放输入流中较小的一半数，小顶堆存放输入流中较大的一半数。约定，大顶堆中的数最多比小顶堆中的数多一个。那么，输入流中的中位数要么是大顶堆的头部元素（输入流中数字个数为奇），要么是两个堆顶元素和的平均值（输入流中数字个数为偶）。

class MedianFinder {

    private PriorityQueue<Integer> prioritySmall;
    private PriorityQueue<Integer> priorityBig;
    
    /** initialize your data structure here. */
    public MedianFinder() {
        prioritySmall = new PriorityQueue<>((a, b) -> {return b - a;});
        priorityBig = new PriorityQueue<>((a, b) -> {return a - b;});
    }
    
    public void addNum(int num) {
        
        if(prioritySmall.isEmpty() || prioritySmall.peek() >= num){
            prioritySmall.offer(num);
        }
        else{
            priorityBig.offer(num);
        }
        
        if(prioritySmall.size() > priorityBig.size() + 1){
            priorityBig.offer(prioritySmall.poll());
        }
        if(priorityBig.size() > prioritySmall.size()){
            prioritySmall.offer(priorityBig.poll());
        }     
    }
    
    public double findMedian() {
        
        if(prioritySmall.size() > priorityBig.size()){
            return prioritySmall.peek();
        }
        
        return (prioritySmall.peek() + priorityBig.peek()) / 2.0;
    }
}

乱序整数数组中缺失的第一个正整数

LeetCode 41. First Missing Positive

将数组中的正整数放到数组中的指定位置上：m放到数组中的第m个位置。之后，遍历数组，找出不符合该规律的位置。需要注意一点，由于数组中的数字可能存在重复，在swap时应该避免相同元素进行交换。

class Solution {
    public int firstMissingPositive(int[] nums) {
        
        if(nums == null){
            return -1;
        }
        
        int n = nums.length;
        int index = 0;
        
        while(index < n){
            if(nums[index] > 0 && nums[index] != index+1){
                if(nums[index] <= n && nums[nums[index]-1] != nums[index]){   // 里面存在重复数字，需要过滤
                    swap(nums, index, nums[index]-1);
                    continue;
                }
            }
            
            index++;
        }
        
        int res = 1;
        for(int m : nums){
            if(res != m){
                return res;
            }
            res++;
        }
        
        return res; 
    }
    
    public void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

统计数组中每个元素后面比自己小的元素数

LeetCode 315. Count of Smaller Numbers After Self

普通方法的时间复杂度一般是O(n^2)，使用二叉查找树，可以将时间复杂度降低到O(nlogn)。

该二叉查找树的每个节点除了value值之外，还需要维护一个变量ct，代表该节点的左子树的节点个数。这样，如果按数组逆序来构建这棵二查找树：

• 插入时如果元素比该节点的value大，则说明该节点的左子树上的节点以及该节点都比插入元素小，元素插入右子树
• 如果比该节点的value小的话，元素要插入该节点的左子树，该节点的ct需要加1
• 插入元素与节点value相等时，可以将其插入到右子树

这样，一个元素后面有多少个比其小的元素，就是在插入该元素过程中所有小于该元素的的节点ct域的和。

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        
        if(nums == null || nums.length == 0){
            return new ArrayList<>();
        }
        
        List<Integer> list = new ArrayList<>();
        int i = nums.length - 1;
        
        TreeNode root = new TreeNode(nums[i]);
        list.add(0);
        for(i = i - 1; i >= 0; i--){
            int m = insert(root, nums[i]);
            list.add(m);
        }
        
       Collections.reverse(list);
        
       return list; 
        
    }
    
    public int insert(TreeNode root, int num){
        
        if(num < root.val){
            // 更新ct
            root.ct++;
            if(root.left == null){
                root.left = new TreeNode(num);
                return 0;
            }
            else{
                return insert(root.left, num);
            }
            
        }
        else{
            int res = root.ct;
            if(num > root.val){
                res++;
            }
                
            if(root.right == null){
                root.right = new TreeNode(num);
                return res;
            }
            else{
                return res + insert(root.right, num);
            }
            
            
        }
        
    }
}

class TreeNode{
    int val;
    int ct;
    TreeNode left, right;
    
    TreeNode(int val){
        this.val = val;
    }
}

分式的小数形式表示

LeetCode 166. Fraction to Recurring Decimal

这道题的难点在于如何找出小数部分的循环，思路是用一个Map记录和判断，具体看代码实现。这道题还需注意一下几点：

• 分式的分子分母可能为正也可能为负
• 将负数转为正数时，当心越界（非常容易出现）

class Solution {
    public String fractionToDecimal(long numerator, long denominator) {
        
        // 考虑数字正负的情况
        boolean flag = (numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0);
        // 修改为long， 避免越界
        numerator = Math.abs(numerator);
        denominator = Math.abs(denominator);
        
        // Map记录循环
        Map<Long, Integer> map = new HashMap<>();
        // 结果的整数部分和小数部分
        String posStr = "", negStr = "";
        
        posStr = String.valueOf(numerator / denominator);
        numerator = (numerator % denominator) * 10;
        
        for(int i = 0; i < 100000; i++){
            
            if(numerator == 0){
                break;
            }
            if(map.containsKey(numerator)){
                int startIndex = map.get(numerator);
                negStr = negStr.substring(0, startIndex) + "(" + negStr.substring(startIndex, i) + ")";
                break;
            }
            map.put(numerator, i);
            negStr += String.valueOf(numerator / denominator);
            numerator = (numerator % denominator) * 10;
        }
        
        // 结果添加负号
        if(flag){
            posStr = "-" + posStr;
        }
        
        if(negStr.equals("")){
            return posStr;
        }
        
        return posStr + "." + negStr;
        
        
    }
}

去掉最小子数组，使剩余数组之和能整除P

Leetcode 1590. Make Sum Divisible by P
date: 2020.09.22
算法指数：☆☆☆☆
是否做出：是

思路类似求数组中和为target的最小子数组，只不过在这道题中求的是和%sum= m的最小子数组，其中sum是整个数组的和，m是sum%p。

class Solution {
    public int minSubarray(int[] nums, int p) {
        
        Map<Integer, Integer> map = new HashMap<>();
        int target = 0;
        for(int m : nums){
            target += m;
            target %= p;    // 遍历中取余，可以避免越界
        }
        
        if(target == 0){    // 数组天然整除p，无需减少任何元素
            return 0;
        }
        
        int res = nums.length, cur = 0;   // 初始化
        map.put(0, -1);   // important，子数组从第一个元素开始的时候
        for(int i = 0; i < nums.length; i++){
            cur += nums[i];
            cur = cur % p;
            int need = (cur - target + p) % p;
            res = Math.min(res, i - map.getOrDefault(need, -nums.length));
            map.put(cur, i);
        }
        
        return res == nums.length ? -1 : res;
    }
}

判断数组中长度为3的递增子序列

Leetcode 334. Increasing Triplet Subsequence

date: 2020.10.12

算法指数：☆☆☆

是否做出：否

此类问题一般可以通过用简单方法解决。
长度为2的递增此序列—>长度为3/的递增子序列

class Solution {
    public boolean increasingTriplet(int[] nums) {
        
        int a = Integer.MAX_VALUE;
        int b = Integer.MAX_VALUE;
        
        for(int m : nums){
            if(m <= a){
                a = m;
            }
            else if(m <= b){
                b = m;
            }
            else{
                return true;
            }
        }
        
        return false;
        
    }
}

获取随机值Set

LeetCode380. Insert Delete GetRandom O(1)

date: 2020.10.17

算法指数：☆☆☆

是否做出：是

通过数组+Map实现随机访问。

class RandomizedSet {
    
    private Map<Integer, Integer> map;
    private int[] array;
    private int nextInsert;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap<>();
        array = new int[100005];
        nextInsert = 0;
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(map.containsKey(val)){
            return false;
        }
        
        array[nextInsert] = val;
        map.put(val, nextInsert++);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(map.containsKey(val)){
            int index = map.get(val);
            swap(array, index, --nextInsert);
            map.put(array[index], index);    // 更新索引
            map.remove(val);
            return true;
        }
        
        return false;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        
        int index = ((int)(Math.random() * 10000000)) % nextInsert;
        
        return array[index];
    }
    
    public void swap(int[] array, int i, int j){
        
        int m = array[i];
        array[i] = array[j];
        array[j] = m;
    }
}

最大的数字

LeetCode 179. Largest Number

date: 2020.10.17

算法指数：☆☆☆☆

是否做出：是

这道题的关键在于字符串比较部分：34和3哪个应该放前面、30和3哪个应该放前面。

class Solution {
    public String largestNumber(int[] nums) {
        
        if(nums == null || nums.length == 0){
            return "";
        }
        
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            strs[i] = String.valueOf(nums[i]);
        }
        
        Arrays.sort(strs, (s1, s2) -> {
            
            return compareString(s1, s2);
            
        });
            
        String res = "";
        for(String s : strs){
            res += s;
        }
        
        // 过滤0前缀
        int startIndex;
        for(startIndex = 0; startIndex < res.length()-1; startIndex++){
            if(res.charAt(startIndex) != '0'){
                break;
            }
        }
                
        return res.substring(startIndex);
    }
    
    public int compareString(String s1, String s2){
        
        int i = 0;
        for(; i < s1.length() && i < s2.length(); i++){
            if(s1.charAt(i) > s2.charAt(i)){
                return -1;
            }
            if(s1.charAt(i) < s2.charAt(i)){
                return 1;
            }
        }
        
        if(i < s1.length()){
            return compareString(s1.substring(i), s2);
        }
        if(i < s2.length()){
            return compareString(s1, s2.substring(i));
        }
        
        return 0;
    }
}

直方图中的最大面积

LeetCode 84. Largest Rectangle in Histogram

date: 2020.10.17

算法指数：☆☆☆☆☆

是否做出：否

单调递增栈可以实现记录当前bar在最大区间[i, j]中是最低的。用图来说明递增栈是如何解决这个问题的：

首先，高度为2的bar<0, 2>进栈(0代表该bar从位置0到当前位置是最低的，2代表该bar的高度):

然后，高度为1的bar想要进栈，但是小于栈顶高度为2的bar，所以栈中的元素要出栈。<0, 2>出栈，该bar最低的最大区间为[0, 0]，area = 2*1。此时栈为空，高度为1的bar继续进栈，此时注意进栈的是<0, 1>，因为前面出栈的bar的高度都比1高。高度为5，6的bar<2, 5>,<3, 6>依次进栈，

现在该高度为2的bar进栈了，重复前面的操作。首先<3, 6>出栈，该bar对应的区间为[3, 3]，area = 1 * 6;然后<2, 5>出栈，对应的区间为[2, 3]，area = 2 * 5。然后<2, 2>进栈，<5, 3>进栈。

最终依次出栈：<5, 3>对应区间为[5, 5],area = 1 * 3; <2, 2>对应区间为[2, 5]，area = 4 * 2; <0, 1>对应区间为[0, 5],area = 6 * 1。

class Solution {
    // 单调递增栈
    public int largestRectangleArea(int[] heights) {
        
        if(heights == null || heights.length == 0){
            return 0;
        }
        
        int maxArea = 0;
        Stack<int[]> stack = new Stack<>();
        for(int i = 0; i < heights.length; i++){
            int start = i;
            while(!stack.isEmpty() && stack.peek()[1] > heights[i]){
                int[] arr = stack.pop();
                int height = arr[1];
                int width = i - arr[0];
                start = arr[0];
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(new int[]{start, heights[i]});
        }
        
        while(!stack.isEmpty()){
            int[] arr = stack.pop();
            int height = arr[1];
            int width = heights.length - arr[0];
            maxArea = Math.max(maxArea, height * width);
        }
        
        return maxArea;
        
    }
}

快速幂

LeetCode 50. Pow(x, n)

date: 2020.10.19

算法指数：☆☆☆☆

是否做出：否

利用二分思想，xⁿ = x^n/2 * x^n/2 * x^{n%2==1 ? 1 : 0}

class Solution {
    // 快速幂
    public double myPow(double x, long n) {
        
        boolean isNegative = n < 0;
        n = Math.abs(n);    // 注意int负数越界
        
        double res = calculate(x, n);
        
        return isNegative ? 1/res : res;
    }
    
    public double calculate(double x, long n){
        
        if(n == 0){
            return 1;
        }
        if(n == 1){
            return x;
        }
        
        double res = calculate(x, n/2);
        res *= res;
        res *= n % 2 == 1 ? x : 1;
        
        return res;
        
    }
}

另一种方法：

​ 2¹¹ = 2⁸ * 2² * 2¹ = 2⁽¹⁰⁰⁰⁾ * 2⁽¹⁰⁾ *2⁽¹⁾

class Solution {
    public double myPow(double x, long n) {
        
        if(n == 0){
            return 1;
        }

        boolean flag = n < 0 ? true : false;
        n = Math.abs(n);

        double res = 1;
        double base = x;
        while(n != 0){
            if((n&1) == 1){
                res = res * base;
            }
            base = base * base;
            n = n>>1;
        }

        if(flag){
            return 1/res;
        }
        
        return res;

    }
}

无序数组中最长的有序序列

LeetCode 128.Longest Consecutive Sequence

date: 2020.10.19

难度：hard

算法指数：☆☆☆☆

是否做出：否

这道题目的是找最长的有序序列，那么就从所有有序序列的开始元素找起。将元素放到Set中可以快速找到每个有序序类的第一个元素。在找下一个元素时，要小心加1导致的位溢出。

class Solution {
    public int longestConsecutive(int[] nums) {
        
        if(nums == null || nums.length == 0){
            return 0;
        }
        
        Set<Integer> set = new HashSet<>();
        for(int m : nums){
            set.add(m);
        }
        
        int maxLen = 0;
        for(int m : nums){
            if(!set.contains(m-1)){
                int curCount = 0;
                int curNum = m;
                while(set.contains(curNum)){
                    curCount++;
                    if(curNum == Integer.MAX_VALUE){    // 位溢出
                        break;
                    }
                    curNum++;
                }
                maxLen = Math.max(maxLen, curCount);
            }
        }
        
        return maxLen;
        
    }
}

矩阵中最长的增长路径

LeetCode 329. Longest Increasing Path in a Matrix

date: 2020.10.23

难度：hard

算法指数：☆☆☆☆

是否做出：是

暴力遍历方法可以轻易解决这个问题，但是会超时，在搜索过程中可以有两个优化的地方：

• 使用Map记录已经搜索过的路径
• 从最小的数开始搜索

class Solution {
    
    int[][] directions = new int[][]{{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    Map<String, Integer> map;
    int m, n;
    
    public int longestIncreasingPath(int[][] matrix) {
        
        if(matrix == null || matrix.length == 0){
            return 0;
        }
        
        m = matrix.length;
        n = matrix[0].length;
        int maxLen = 0;
        boolean[][] visited = new boolean[m][n];
        map = new HashMap<>();
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(isSmallest(matrix, i, j)){
                    maxLen = Math.max(maxLen, dfs(matrix, i, j, visited));
                }
            }
        }
        
        return maxLen;
        
    }
    
    public boolean isSmallest(int[][] matrix, int i, int j){
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        if(i > 0 && matrix[i-1][j] < matrix[i][j]){
            return false;
        }
        if(i < m-1 && matrix[i+1][j] < matrix[i][j]){
            return false;
        }
        if(j > 0 && matrix[i][j-1] < matrix[i][j]){
            return false;
        }
        if(j < n-1 && matrix[i][j+1] < matrix[i][j]){
            return false;
        }
        
        return true;
    }
    
    public int dfs(int[][] matrix, int x, int y, boolean[][] visited){
        
        // has result
        String key = "(" + x + "," + y + ")";
        if(map.containsKey(key)){
            return map.get(key);
        }
        
        visited[x][y] = true;
        int maxLen = 0;
        
        for(int[] dir : directions){
            int i = x + dir[0];
            int j = y + dir[1];
            
            if(i >= 0 && i < m && j >= 0 && j < n && !visited[i][j] && matrix[i][j] > matrix[x][y]){
                maxLen = Math.max(maxLen, dfs(matrix, i, j, visited));
            }
        }
        
        visited[x][y] = false;
        map.put(key, 1+maxLen);
        
        return 1 + maxLen;
        
    }
}

可以使用数组代替Map，效率会有不错的提升，visited数组也可以不用使用：

class Solution {
    
    int[][] directions = new int[][]{{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    int[][] cache;
    int m, n;
    
    public int longestIncreasingPath(int[][] matrix) {
        
        if(matrix == null || matrix.length == 0){
            return 0;
        }
        
        m = matrix.length;
        n = matrix[0].length;
        cache = new int[m][n];
        int maxLen = 0;
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(isSmallest(matrix, i, j)){
                    maxLen = Math.max(maxLen, dfs(matrix, i, j));
                }
            }
        }
        
        return maxLen;
        
    }
    
    public boolean isSmallest(int[][] matrix, int i, int j){
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        if(i > 0 && matrix[i-1][j] < matrix[i][j]){
            return false;
        }
        if(i < m-1 && matrix[i+1][j] < matrix[i][j]){
            return false;
        }
        if(j > 0 && matrix[i][j-1] < matrix[i][j]){
            return false;
        }
        if(j < n-1 && matrix[i][j+1] < matrix[i][j]){
            return false;
        }
        
        return true;
    }
    
    public int dfs(int[][] matrix, int x, int y){
        
        // has result
        if(cache[x][y] != 0){
            return cache[x][y];
        }
        
        int maxLen = 0;
        
        for(int[] dir : directions){
            int i = x + dir[0];
            int j = y + dir[1];
            
            if(i >= 0 && i < m && j >= 0 && j < n && matrix[i][j] > matrix[x][y]){
                maxLen = Math.max(maxLen, dfs(matrix, i, j));
            }
        }
        
        cache[x][y] = maxLen + 1;
        
        return 1 + maxLen;
        
    }
}

摆动序列II

LeetCode 324. Wiggle Sort II

date: 2020.10.31

难度：Medium

算法指数：☆☆☆☆

是否做出：否

先对数组nums排序，然后分成两部分：[1, … , (n+1)/2]，[(n+1)/2 +1, …, n]，然后将两个序列分别插入到数组中。这里插入时需要倒序插入，因为正序插入的话会出现特殊情况：

如数组：[1, 2, 4, 4, 4, 6]，加粗代表较大的部分。

正序插入：[1, 4, 2, 4, 4, 6]

倒序插入：[4, 6, 2, 4, 1, 4]

class Solution {
    public void wiggleSort(int[] nums) {
        
        int n = nums.length;
        int[] copyArray = Arrays.copyOf(nums, n);
        Arrays.sort(copyArray);
        
        int mid = (n + 1) / 2;
        int s = mid-1, l = n-1;
        for(int i = 0; i < n; i+=2){
            nums[i] = copyArray[s--];
        }
        for(int i = 1; i < n; i+=2){
            nums[i] = copyArray[l--];
        }
        
        
    }
    
}