Hexo

Posted 2022-09-01Updated 2022-09-01LeetCode / Mediuma minute read (About 161 words)

Question

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Solution

DFS搜索，每次传入当前分支的最大值。
如果当前值大于等于最大值，则count+1。

Code

/**
 * 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 Solution {
    int count;
    public int goodNodes(TreeNode root) {
        count = 0;
        dfs(root, Integer.MIN_VALUE);
        return count;
    }
    
    private void dfs(TreeNode root, int max){
        if(root == null) return;
        if(root.val >= max){
            count++;
            max = root.val;
        }

        dfs(root.left, max);
        dfs(root.right, max);
    }
}

Posted 2022-08-27Updated 2022-08-27LeetCode / Medium2 minutes read (About 234 words)

1329. Sort the Matrix Diagonally

Question

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix’s end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

Solution

分别遍历数组的两条边。
按对角线顺序进行遍历，用列表记录访问过的数字。
排序列表后按对角线填入原数组。

Code

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        List<Integer> arr = new ArrayList<>();
        
        for(int t = 0; t < m; t++){
            int i = t, j = 0;
            
            while(i < m && j < n){
                arr.add(mat[i][j]);
                i++;
                j++;
            }
            
            Collections.sort(arr);
            
            i = t;
            j = 0;
            
            while(i < m && j < n){
                mat[i][j] = arr.get(j);
                i++;
                j++;
            }
            arr.clear();
        }

        for(int t = 1; t < n; t++){
            int i = 0, j = t;
            
            while(i < m && j < n){
                arr.add(mat[i][j]);
                i++;
                j++;
            }
            
            Collections.sort(arr);
            
            i = 0;
            j = t;
            
            while(i < m && j < n){
                mat[i][j] = arr.get(i);
                i++;
                j++;
            }
            arr.clear();
        }
        return mat;
    }
}

Posted 2022-08-27Updated 2022-08-27LeetCode / Hard / 复习2 minutes read (About 231 words)

363. Max Sum of Rectangle No Larger Than K

Question

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

Solution

前缀和，计算矩阵中每个位置对应的方形的和。
遍历方形的两个对角线上的点。
其面积等于大块加小块的面积减去两个长方形的面积。
如果面积有小于k的，则记录其最大值并返回。

Code

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int x = matrix.length, y = matrix[0].length, max = Integer.MIN_VALUE;
        int[][] sum = new int[x+1][y+1];
        
        for(int i = 1; i <= x; i++){
            int total = 0;
            for(int j = 1; j <= y; j++){
                total += matrix[i-1][j-1];
                sum[i][j] = sum[i-1][j] + total;
            }
        }
 
        for(int i = 0; i <= x; i++){
            for(int j = 0; j <= y; j++){
                for(int m = i + 1; m <= x; m++){
                    for(int n = j + 1; n <= y; n++){
                        int area = sum[m][n] + sum[i][j] - sum[m][j] - sum[i][n];
                        if(area <= k) max = Math.max(max, area);
                    }
                }
            }
        }
        return max;
    }
}

Posted 2022-08-26Updated 2022-08-26LeetCode / Medium / 复习3 minutes read (About 411 words)

869. Reordered Power of 2

Question

You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

Solution

打表，将所有二的指数全部计算出来，并用数组统计各个数字出现的频率。
然后同样统计n中各个数字出现的频率。

如果两者中有频率完全相同的情况，则返回true，反之返回false。

Code

class Solution {
    public boolean reorderedPowerOf2(int n) {
        int[] reorders = new int[10];
        int m = 1, digits = 0;
        for(int i = n; i > 0; i/=10){
            reorders[i % 10]++;
            digits++;
        }
        
        int size = 0;
        List<Integer[]> powerOfTwo = new ArrayList<>();
        
        while(m > 0 && size <= digits){
            size = 0;
            Integer[] bin = new Integer[10];
            Arrays.fill(bin, 0);
            for(int i = m; i > 0; i/=10){
                size++;
                bin[i % 10]++;
            }
            if(size == digits) powerOfTwo.add(bin);
            m *= 2;
        }
        
        for(Integer[] bin : powerOfTwo) if(check(bin, reorders)) return true;
        return false;
    }
    
    private boolean check(Integer[] bin, int[] reorders){
        for(int i = 0; i < bin.length; i++) if(bin[i] != reorders[i]) return false;
        return true;        
    }
}

Solution 2

回溯，遍历计算可以组成的所有数字。
打表记录所有二的指数并记录在哈希表内，如果所有组成数字中有哈希表内的数字则返回true，反之返回false。

Code

class Solution {
    HashSet<Integer> visited, set, numbers;
    List<Integer> arr, res;
    public boolean reorderedPowerOf2(int n) {
        int m = 1;
        set = new HashSet<>();
        visited = new HashSet<>();
        numbers = new HashSet<>();
        res = new ArrayList<Integer>();
        while(m > 0){
            set.add(m);
            m *= 2;
        }
        
        arr = new ArrayList<>();
        
        while(n > 0){
            arr.add(n % 10);
            n /= 10;
        }
        
        for(int i = 0; i< arr.size(); i++){
            if(arr.get(i) == 0) continue;
            visited.add(i);
            reorder(arr.get(i));
            visited.remove(i);
        }
        
        
        for(int num : res) if(set.contains(num)) return true;
        return false;
    }
    
    private void reorder(int num){
        if(visited.size() == arr.size()){
            res.add(num);
            return;
        };
        
        if(numbers.contains(num)) return;
        numbers.add(num);

        for(int i = 0; i < arr.size(); i++){
            if(visited.contains(i)) continue;
            int next = num * 10 + arr.get(i);
            visited.add(i);
            reorder(next);
            visited.remove(i);
        }
    }
}

Posted 2022-08-25Updated 2022-08-25LeetCode / Easya minute read (About 125 words)

383. Ransom Note

Question

Given two strings ransomNote and magazine, return true* if ransomNote can be constructed by using the letters from magazine and false otherwise*.

Each letter in magazine can only be used once in ransomNote.

Solution

数组统计，统计magazine内的字符。
遍历ransomNote，如果对字符数组位置为0则返回false。
每次遍历减少数组统计结果。

最后返回true。

Code

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] bin = new char[26];
        
        for(char c : magazine.toCharArray()) bin[c-'a']++;
        for(char c : ransomNote.toCharArray()){
            if(bin[c-'a'] == 0) return false;
            bin[c-'a']--;
        }
        
        return true;
    }
}

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Recents

Archives

Links