Category: Medium

Posted 2022-09-02Updated 2022-09-02LeetCode / Medium2 minutes read (About 228 words)

967. Numbers With Same Consecutive Differences

Question

Return all non-negative integers of length n such that the absolute difference between every two consecutive digits is k.

Note that every number in the answer must not have leading zeros. For example, 01 has one leading zero and is invalid.

You may return the answer in any order.

Solution

回溯，每次传入上一个数字和剩余的位数。
全局变量sum记录加和。
DFS搜索，每次计算下一位的可行数字并递归。
用回溯维护sum的值。
如果剩余位数为1，则将当前的sum加入结果，并清零sum。

Code

class Solution {
    List<Integer> res;
    int sum;
    public int[] numsSameConsecDiff(int n, int k) {
        res = new ArrayList<>();
        for(int i = 1; i < 10; i++){
            sum = 0;
            dfs(i, n, k);
        }
        
        int[] ret = new int[res.size()];
        for(int i = 0; i < res.size(); i++){
            ret[i] = res.get(i);
        }
        return ret;
    }
    
    private void dfs(int prev, int n, int k){
        sum += prev;
        if(n == 1){
            res.add(sum);
            return;
        }
        
        if(k == 0){
            sum *= 10;
            dfs(prev + k, n-1, k);
            sum /= 10;
            return;
        }
        if(prev + k < 10){
            sum *= 10;
            dfs(prev + k, n-1, k);
            sum /= 10;
        }
        if(prev >= k){
            sum *= 10;
            dfs(prev - k, n-1, k);
            sum /= 10;
        }
    }
}

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

1448. Count Good Nodes in Binary Tree

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-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-21Updated 2022-08-21LeetCode / Medium / 复习3 minutes read (About 466 words)

659. Split Array into Consecutive Subsequences

Question

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).

All subsequences have a length of 3** or more**.

Return true* if you can split nums according to the above conditions, or false otherwise*.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

Solution

用优先级队列储存每个可组成的列表。
优先级队列根据列表的长度排列。

用哈希表记录每个列表的尾数，和其对应的优先级队列。
遍历所有数字，如果存在当前数字num-1为尾数的队列，则获取长度最小的列表，并添加当前数字num在列表中。
然后将新的优先级队列放入哈希表中。

遍历整个哈希表中的数组，如果有数组的长度小于3，则返回false，否则返回true。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<List<Integer>>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<List<Integer>> last = map.getOrDefault(num - 1, null);
            PriorityQueue<List<Integer>> curr = map.getOrDefault(num, new PriorityQueue<List<Integer>>((a,b) -> a.size() - b.size()));

            if(last == null || last.size() == 0){
                List<Integer> arr = new ArrayList<>();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
            else{
                List<Integer> arr = last.poll();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(List<Integer> arr : map.get(last)){
                if(arr.size() < 3) return false;
            }
        }
        return true;
        
    }
}

Solution 2

不需要保存整个列表，只需要保存对应末尾数字的列表长度即可。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<Integer> last = map.getOrDefault(num - 1, null);
            PriorityQueue<Integer> curr = map.getOrDefault(num, new PriorityQueue<Integer>());

            if(last == null || last.size() == 0){
                curr.add(1);
                map.put(num, curr);
            }
            else{
                int min = last.poll();
                curr.add(min+1);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(int len : map.get(last)){
                if(len < 3) return false;
            }
        }
        return true;

    }
}

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

823. Binary Trees With Factors

Question

Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node’s value should be equal to the product of the values of its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 109 + 7.

Solution

根据题意，二叉树的根是两个子节点的乘积，因此一个根节点可组成的二叉树总数，相当于其左子节点可组成的二叉树总数，乘以其右子节点可组成的二叉树总数。

因此我们可以先将数组arr排序，用dp[]数组记录以从小到大的数字作为根节点可组成的最大二叉树总数。

由于每个根节点至少可以和自身组成一个节点，因此将dp[]数组初始化为1。

动态规划

从小到大遍历dp[]数组。
在遍历时，从遍历数值i的左侧选取当前位置的子节点。（根据题意子节点一定小于根节点）
当当前位置arr[i]可以整除arr[left]时，则有可能存在另一个子节点。此时根据哈希表中获得对应的另一个子节点right。如果right存在，则dp[i]更新为dp[i]+dp[left]*dp[right]的值。

最后将dp[]数组中记录的所有数字加和并返回。

Code

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        final int MOD = (int) Math.pow(10, 9) + 7;
        Arrays.sort(arr);   //from minium to maxium
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < arr.length; i++){
            map.put(arr[i], i);
        }
        
        long[] dp = new long[arr.length];
        Arrays.fill(dp, 1);
        
        for(int i = 0; i < arr.length; i++){
            for(int left = 0; left < i; left++){
                if(arr[i] % arr[left] == 0){   //make sure divisible
                    int k = arr[i] / arr[left];
                    if(map.containsKey(k)){
                        int right = map.get(k);
                        dp[i] = (dp[i] + dp[left] * dp[right]) % MOD; 
                    }
                }
            }
        }
        
        int res = 0;
        
        for(long num : dp){
            res += num;
            res %= MOD;
        }
        
        return (int) res;
    }
}

Posted 2022-08-05Updated 2022-08-05LeetCode / Medium2 minutes read (About 296 words)

377. Combination Sum IV

Question

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Solution

记忆化搜索，memo[]数组用来记录达到某个总和时的可行方案数量。
辅助方法count记录累计的总和memo[total]。

递归DFS，记忆化剪枝，如果memo[]数组不为空，则直接返回记忆内容。
当total等于target时，该组合成立，返回1。

遍历nums[]数组中的每个元素，并将总组合数相加记录到memo[total]中。
最后返回总组合数memo[total]。

*非常奇怪的是，当我使用int[]数组进行记忆化搜索时部分case会超时，推测是因为我判断int[]数组是否被记录是通过是否等于0而非是否为空导致的。

Code

class Solution {
    int[] numbers;
    Integer[] memo;
    public int combinationSum4(int[] nums, int target) {
        numbers = nums;
        memo = new Integer[target+1];
        return count(0, target);
    }
    
    private int count(int total, int target){
        if(memo[total] != null) return memo[total];
        if(total == target) return 1;
    
        int sum = 0;
        for(int i = 0; i < numbers.length; i++){
            if(total + numbers[i] <= target) sum += count(total + numbers[i], target);
        }
        memo[total] = sum;
        
        return memo[total];
    }
}

Posted 2022-08-04Updated 2022-08-04LeetCode / Medium2 minutes read (About 326 words)

858. Mirror Reflection

Question

There is a special square room with mirrors on each of the four walls. Except for the southwest corner, there are receptors on each of the remaining corners, numbered 0, 1, and 2.

The square room has walls of length p and a laser ray from the southwest corner first meets the east wall at a distance q from the 0th receptor.

Given the two integers p and q, return the number of the receptor that the ray meets first.

The test cases are guaranteed so that the ray will meet a receptor eventually.

Solution

激光在箱子里折射，可以想象成在无限延展的空间内直线发射光线。
因此三个接收器可以被视作组成了一个无限延展的矩阵。

只需要将q和p化简，然后确定坐标(q, p)所对应的接收器即可。
由于接收器是间隔的，因此只需要先化简q，p后计算两者的奇偶性即可。

如果q与p皆为奇数，则返回1号接收器。
如果q是奇数，p不是，则返回0号接收器。
如果p是奇数，q不是，则返回2号接收器。

Code

class Solution {
    public int mirrorReflection(int p, int q) {
        int gcd = gcd(p, q);
        p/=gcd;
        q/=gcd;
        boolean xIsOdd = (p & 1) == 1, yIsOdd = (q & 1) == 1;
        if(xIsOdd && yIsOdd) return 1;
        else if(xIsOdd) return 0;
        else return 2;
    }
    
    private int gcd(int a, int b){
        if(a == b) return a;
        if(a > b) return gcd(b, a-b);
        else return gcd(a, b-a);
    }
}

Posted 2022-08-03Updated 2022-08-03LeetCode / Medium / 复习2 minutes read (About 361 words)

729. My Calendar I

Question

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

MyCalendar() Initializes the calendar object.

boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Solution

有更快速的解法，需要用到TreeMap，有时间再研究。

使用一个队列记录已经预定的范围。
添加无穷大到队列中，方便后期计算。

当预定新的时间段时，遍历队列，如果上一个数组的最大值小于start和end且当前遍历数组大于start和end，则可以预定，将当前的数组插入当前位置，并返回true。
如果没有满足条件的，则返回false。

Code

class MyCalendar {
    List<int[]> arr;
    public MyCalendar() {
        arr = new ArrayList<>();
        int[] inf = new int[2];
        inf[0] = Integer.MAX_VALUE;
        inf[1] = Integer.MAX_VALUE;
        arr.add(inf);
    }
    
    public boolean book(int start, int end) {
        int[] last = new int[2];
        for(int i = 0; i < arr.size(); i++){
            int[] curr = arr.get(i);
            if(last[1] < end && last[1] <= start && curr[0] >= end && curr[0] > start){
                int[] n = new int[2];
                n[0] = start;
                n[1] = end;
                arr.add(i, n);
                return true;
            }
            last = curr;
        }
        return false;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */

Posted 2022-07-29Updated 2022-08-03LeetCode / Medium2 minutes read (About 323 words)

890. Find and Replace Pattern

Question

Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.

Solution

遍历words，对pattern和words中的字符建立映射。
used[]数组记录访问状况。

如未建立映射关系，且word中的字符已建立映射，则不在结果中添加当前字符串。
如未建立映射，则建立新的word与pattern的映射关系。
如果当前已经建立映射，但是当前字符违反了映射关系，则不在结果中添加当前字符串。

Code

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ret = new ArrayList<>();
        for(String word : words){
            HashMap<Character, Character> map = new HashMap<>();    //map characters from pattern and words
            boolean isSamePattern = true;
            int[] used = new int[26];
            
            for(int i = 0; i < word.length(); i++){
                char pc = pattern.charAt(i), wc = word.charAt(i);
                if( !map.containsKey(pc) ){
                    if(used[wc-'a'] == 0){  //add new map if there is no map between characters and the character in word is not used
                        map.put( pc, wc );
                        used[wc-'a']++;
                    }
                    else{
                        isSamePattern = false;
                        break;
                    }
                }
                else if( map.get(pc) != wc ){   //drop the word if not follow the pattern
                    isSamePattern = false;
                    break;
                }
            }
            if(isSamePattern) ret.add(word);
        }
        return ret;
    }
}

Posted 2022-07-27Updated 2022-07-27LeetCode / Medium / 复习2 minutes read (About 343 words)

114. Flatten Binary Tree to Linked List

Question

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

The “linked list” should be in the same order as a pre-order** traversal** of the binary tree.

Solution

全局变量prev，初始化为null，用来记录上一个访问的节点。

由于最后要达到先序遍历（根节点-左子节点-右子节点）的数据结构顺序，因此在进行访问时需要与先序遍历的操作相反，首先递归右子节点，然后递归左子节点，最后修改当前节点。

先遍历当前节点的右侧节点，再遍历当前节点的左侧节点。
最后处理当前节点，将左子节点设置为null，右子节点设置为prev。
最后将当前节点保存在prev上。

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 {
    TreeNode prev = null;
    public void flatten(TreeNode root) {
        if(root == null) return;
        flatten(root.right);    //traverse right nodes first
        flatten(root.left); //traverse left nodes
        root.left = null;   //set current node's left child node to null
        root.right = prev;  //set current node's right child node to previous node
        prev = root;    //update previous node
    }
}

Posted 2022-07-24Updated 2022-07-24LeetCode / Mediuma minute read (About 155 words)

34. Find the Element in Sorted Array

Question

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Solution

二分搜索，首先搜索target。如果搜索到结果为负数，则返回[-1, -1]。
如果搜索到target，则记录index。
然后从index向两边搜索，直到找到界限并返回。

Code

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        int index = 0;
        index = Arrays.binarySearch(nums, target);
        if(index < 0){
            ret[0] = -1;
            ret[1] = -1;
            return ret;
        }
        int less = index, more = index;
        while(less >= 0 && nums[less] == target) less--;
        while(more < nums.length && nums[more] == target) more++;
        
        ret[0] = less + 1;
        ret[1] = more - 1;
        return ret;
    }
}

Posted 2022-07-22Updated 2022-07-22LeetCode / Medium3 minutes read (About 442 words)

86. Partition List

Question

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Solution 1

生成前后两个部分的dummy链表头。
遍历原链表，当当前值小于x时则将当前节点添加到第一个链表头后。
当当前值大于x时则将当前节点添加到第二个链表头后。

遍历完成后将第二个链表头的下一个节点添加到第一个链表的下一个节点上。然后将第二个链表的尾部指向null。

返回第一个dummy链表节点的下一个节点即可。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(), dummy2 = new ListNode();
        ListNode hd1 = dummy1, hd2 = dummy2;
        while(head != null){
            if(head.val < x){
                dummy1.next = head;
                dummy1 = dummy1.next;
            }
            else{
                dummy2.next = head;
                dummy2 = dummy2.next;
            }
            head = head.next;
        }
        dummy1.next = hd2.next;
        dummy2.next = null;
        
        return hd1.next;
    }
}

Solution 2

遍历整个链表，根据各个节点的值将其保存在两个队列中。

设置一个dummy节点头，将两个队列中的节点按顺序挤出并生成新链表。
返回dummy节点头的下一个节点即可。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        Queue<ListNode> q1 = new LinkedList<>();
        Queue<ListNode> q2 = new LinkedList<>();
        while(head != null){
            if(head.val < x) q1.add(head);
            else q2.add(head);
            head = head.next;
        }
        
        ListNode dummy = new ListNode();
        ListNode res = dummy;
        
        while(!q1.isEmpty()){
            res.next = q1.poll();
            res = res.next;
        }
        
        while(!q2.isEmpty()){
            res.next = q2.poll();
            res = res.next;
        }
        res.next = null;
        return dummy.next;
    }
}

Posted 2022-07-16Updated 2022-07-16LeetCode / Medium / 复习3 minutes read (About 449 words)

576. Out of Boundary Paths

Question

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.

Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7.

Solution

DFS，记忆化搜索哦剪枝。

记忆化搜索

三维数组memo[][][]用来记录起点为startRow, startColumn，剩余距离为maxMove时的总路径数。
注意需要将memo[][][]所有数值初始化为-1。否则在进行BFS搜索时，无法对maxMove等于0的情况进行剪枝。

DFS

当当前位置越界，则为一个有效路径，返回1。
当剩余步数为0时，无法继续移动，返回0。

如果当前位置与剩余步数的状态已经被搜索并记录过，则直接返回memo[startRow][startColumn][maxMove]。
如果未搜索，则将maxMove减一，并向四周移动一格，对当前位置的四个方向进行递归。
记忆当前位置的四个方向的总路径数之和，模除后返回。

Code

class Solution {
    final int MOD = (int) Math.pow(10, 9) + 7;
    long[][][] memo;
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        memo = new long[m][n][maxMove];
       for(int i = 0; i < m; i++){
           for(int j = 0; j < n; j++){
               for(int k = 0; k < maxMove; k++){
                   memo[i][j][k] = -1;
               }
           }
       }
        return (int) dfs(m, n, maxMove, startRow, startColumn);
    }
    
    private long dfs(int m, int n, int maxMove, int startRow, int startColumn){
        if(startRow < 0 || startRow >= m || startColumn < 0 || startColumn >= n) return 1;
        if(maxMove == 0) return 0;
        
        maxMove--;
        if(memo[startRow][startColumn][maxMove] != -1) return memo[startRow][startColumn][maxMove];
        
        long left = dfs(m, n, maxMove, startRow-1, startColumn);
        long right = dfs(m, n, maxMove, startRow+1, startColumn);
        long up = dfs(m, n, maxMove, startRow, startColumn+1);
        long down = dfs(m, n, maxMove, startRow, startColumn-1);

        memo[startRow][startColumn][maxMove] = (left + right + up + down) % MOD;
        return memo[startRow][startColumn][maxMove];
    }
}

Posted 2022-07-13Updated 2022-07-16LeetCode / Medium / 复习2 minutes read (About 279 words)

473. Matchsticks to Square

Question

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Solution

回溯，用int[] edges记录边长。

先计算所有火柴棍的长度之和是否能被4整除，如果不能则返回false。
将所有火柴排序，以减少回溯时的计算量。

Backtracking 回溯

当遍历越界时（传入index为-1），则返回true。

每次将当前火柴matchsticks[index]添加到一个edges[i]中。
当edges[i] <= sum / 4，且向前回溯前一个位置index-1返回结果为真，则返回true。
然后将当前火柴从edges[i]中取出。

Code

class Solution {
    int[] edges;
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for(int i = 0; i < matchsticks.length; i++) sum += matchsticks[i];
        if(sum % 4 != 0) return false;
        
        edges = new int[4];
        Arrays.sort(matchsticks);
        return backtracking(matchsticks, matchsticks.length-1, sum/4);
    }
    
    public boolean backtracking(int[] matchsticks, int index, int len){
        if(index == -1) return true;

        for(int i = 0; i < 4; i++){
            edges[i] += matchsticks[index];
            if(edges[i] <= len && backtracking(matchsticks, index - 1, len)) return true;
            edges[i] -= matchsticks[index];
        }
        return false;
    }
}

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

动态规划

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

记忆化搜索

DFS

Code

Question

Solution

Backtracking 回溯

Code

Recents

Archives

Links