1642. Furthest Building You Can Reach
Posted Updated LeetCode / Medium / 复习2 minutes read (About 341 words)

1642. Furthest Building You Can Reach

Question

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

  • If the current building’s height is greater than or equal to the next building’s height, you do not need a ladder or bricks.

  • If the current building’s height is less than the next building’s height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Solution

贪心算法+优先级队列。

从第二栋楼开始遍历当前位置，下一栋楼与当前位置的高度差为h。
如果h小于0，则无成本前进。
否则如果剩余砖块，则优先使用砖块，并将使用砖块的个数加入大根堆中。
如果剩余砖块不足，且有梯子剩余时，用梯子替换掉小号最多砖块的位置，增加剩余砖块的数量。
如果剩余砖块和梯子都不足，则返回上一个位置。

如果遍历到最后，则返回最后一个建筑物的位置。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 1; i < heights.length; i++){
            int h = heights[i] - heights[i-1];
            if(h > 0){
                pq.add(h);
                bricks-=h;
                if(bricks < 0){
                    if(ladders > 0){
                        ladders--;
                        bricks += pq.poll();
                    }
                    else{
                        return i-1;
                    }
                }
            }
        }
        return heights.length - 1;
    }
}
820. Short Encoding of Words
Posted Updated LeetCode / Medium4 minutes read (About 596 words)

820. Short Encoding of Words

Question

A valid encoding of an array of words is any reference string s and array of indices indices such that:

  • words.length == indices.length
  • The reference string s ends with the '#' character.
  • For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i].

Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.

Solution 1

LeetCode这几天的每日一题时不让我学会字典树势不罢休啊……

字典树，参数isLeaf记录每个TireNode节点是否为叶子节点。
将单词倒序组建字典树，并维护isLeaf的属性。

计算从根节点到达每个叶子节点的长度再加一的和即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        boolean isLeaf;
    }
    TrieNode root;
    int count;
    
    public int minimumLengthEncoding(String[] words) {        
        count = 0;
        root = new TrieNode();
        
        for(String word : words){
            add(word);
        }
        countLeaves(root, 0);
        return count;
    }
    
    private void add(String word){
        TrieNode curr = root;
        for(int i = word.length()-1; i >= 0; i--){
            int index = word.charAt(i) - 'a';
            if(curr.next[index] == null){
                curr.isLeaf = false;
                curr.next[index] = new TrieNode();
                curr.next[index].isLeaf = true;
            }
            curr = curr.next[index];
        }
    }
    
    private void countLeaves(TrieNode root, int length){
        if(root.isLeaf){
            count += length + 1;
        } 
        else{
            for(int i = 0; i < 26; i++){
                if(root.next[i] != null) countLeaves(root.next[i], length+1);
            }
        }
    }
}

Solution 2

排序，将数组words根据单词倒序排序。
倒序构成字典树，如果展开新的字典树分支（创建新的TrieNode节点）则将count加入根节点到新节点的距离。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        boolean end;
    }
    TrieNode root;
    int count;
    
    public int minimumLengthEncoding(String[] words) {
        Arrays.sort(words, new Comparator<String>(){
            public int compare(String a, String b){
                int i = a.length()-1, j = b.length()-1;
                while(i >= 0 && j >= 0){
                    int index = a.charAt(i) - b.charAt(j);
                    if(index == 0){
                        i--;
                        j--;
                    }
                    else{
                        return index;
                    }
                }
                return j - i;
            }
        });
        
        count = 0;
        root = new TrieNode();
        
        for(String word : words){
            add(word);
        }
        
        return count;
    }
    
    private void add(String word){
        TrieNode curr = root;
        int length = 1;
        boolean newTrieNode = false;
        for(int i = word.length()-1; i >= 0; i--){
            int index = word.charAt(i) - 'a';
            if(curr.next[index] == null){
                curr.next[index] = new TrieNode();
                newTrieNode = true;
            }
            curr = curr.next[index];
            length++;
        }
        curr.end = true;
        if(newTrieNode) count += length;
    }
}

Solution 3

倒序重组字符串并记录到reversedWords[]数组，然后根据字典顺序排序。
如果数组的上一个字符串不是下一个字符串的前缀，则加入上一个字符串的长度加一。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {    
    public int minimumLengthEncoding(String[] words) {
        String[] reversedWords = new String[words.length];
        int count = 0, index = 0;
        for(String word : words){
            reversedWords[index] = new StringBuffer(word).reverse().toString();
            index++;
        }
        
        Arrays.sort(reversedWords);
        for(int i = 0; i < words.length-1; i++){
            if(!reversedWords[i+1].startsWith(reversedWords[i])) count += reversedWords[i].length()+1;
        }
        count += reversedWords[words.length-1].length()+1;
        return count;
    }
}
1268. Search Suggestions System
Posted Updated LeetCode / Medium / 复习2 minutes read (About 366 words)

1268. Search Suggestions System

Question

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Solution

字典树+优先级队列。
在TrieNode节点中保存PriorityQueue，以记录该节点下的三个单词。
注意PriorityQueue中的String需要按倒序排列，以保证维护时可以直接poll掉字符顺序较后的单词。

add()方法

创建并添加TrieNode节点，同时在移动当前节点位置时，需要维护PriorityQueue，当长度大于3时，则挤出字典顺序排列较后的单词。

search()方法

在查找前缀时，将每个TrieNode节点上的PriorityQueue倒序加入List。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    class TrieNode{
        boolean end;
        TrieNode[] children = new TrieNode[26];
        PriorityQueue<String> q = new PriorityQueue<>((a, b) -> b.compareTo(a));
    }
    
    TrieNode root;
    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ret = new ArrayList<>();
        root = new TrieNode();
        for(String word : products){
            add(word);
        }
        return search(searchWord);
    }
    
    private void add(String word){
        TrieNode curr = root;
        for(char c : word.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
            curr.q.add(word);
            if(curr.q.size() > 3) curr.q.poll();
        }
        curr.end = true;
    }
    
    private List<List<String>> search(String prefix){
        List<List<String>> ret = new ArrayList<>();
        TrieNode curr = root;
        for(char c : prefix.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
            List<String> temp = new ArrayList<>();
            while(!curr.q.isEmpty()){
                temp.add(curr.q.poll());
            }
            Collections.reverse(temp);
            ret.add(temp);
        }
        return ret;
    }
}
1048. Longest String Chain
Posted Updated LeetCode / Medium3 minutes read (About 477 words)

1048. Longest String Chain

Question

You are given an array of words where each word consists of lowercase English letters.

word<sub>A</sub> is a predecessor of word<sub>B</sub> if and only if we can insert exactly one letter anywhere in word<sub>A</sub> without changing the order of the other characters to make it equal to word<sub>B</sub>.

  • For example, "abc" is a predecessor of "ab<u>a</u>c", while "cba" is not a predecessor of "bcad".

A word chain* *is a sequence of words [word<sub>1</sub>, word<sub>2</sub>, ..., word<sub>k</sub>] with k >= 1, where word<sub>1</sub> is a predecessor of word<sub>2</sub>, word<sub>2</sub> is a predecessor of word<sub>3</sub>, and so on. A single word is trivially a word chain with k == 1.

Return *the length of the longest possible word chain with words chosen from the given list of *words.

Solution

排序+动态规划。
采用一个一维动态规划数组记录到某个word的最大字符串链长度。

排序

每个predecessor必定比next少1，因此首先将数组根据word的长度排序。

动态规划

数组dp[i]记录到i位置时的最大长度。
双重遍历i和j，其中j>i。如果words[i-1]是words[j-1]的predecessor，则更新dp[j]为dp[j]与dp[i]+1的较大值。

辅助方法 isValid()

判断predecessor是否有效。
初始化一个flag为false记录不同字符是否已出现。
如果两者长度差不为1直接返回false。
双指针分别指向两个字符串，如果两个当前字符相等，则两个指针共同前进。
如果不相等且flag为true则i指针前进，并且将flag改为false。否则返回false。
如果循环结束返回true。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int longestStrChain(String[] words) {
        int max = 0;
        Arrays.sort(words, (a,b) -> a.length() - b.length());
        int[] dp = new int[words.length+1];
        for(int i = 1; i <= words.length; i++){
            for(int j = i + 1; j <= words.length; j++){
                if(isValid(words[i-1], words[j-1])){
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                    max = Math.max(max, dp[j]);
                }
            }
        }
        return max + 1;
    }
    
    private boolean isValid(String predecessor, String next){
        if(predecessor.length() + 1 != next.length()) return false;
        boolean flag = true;
        int i = 0, j = 0;
        while(i < next.length() && j < predecessor.length()){
            if(next.charAt(i) == predecessor.charAt(j)){
                i++;
                j++;
            }
            else if(flag){
                i++;
                flag = false;
            }
            else{
                return false;
            }
        }
        return true;
    }
}
1695. Maximum Erasure Value
Posted Updated LeetCode / Mediuma minute read (About 217 words)

1695. Maximum Erasure Value

Question

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

Solution

滑动窗口+数组统计。

用sum记录窗口内的和，max记录和的最大值。
当新滑入的右侧指针不为0时，从左侧滑出元素并将滑出的元素改为0。
然后将右侧指针指针对应的数组统计改为1并更新当前的和max。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        int[] bin = new int[10001];
        int left = 0, max = 0, sum = 0;
        
        for(int right = 0; right < nums.length; right++){
            sum += nums[right];
            while(bin[nums[right]] != 0){
                bin[nums[left]] = 0;
                sum -= nums[left];
                left++;
            }
            bin[nums[right]] = 1;
            max = Math.max(max, sum);
        }
        return max;
    }
}
Posted Updated LeetCode / Hard3 minutes read (About 380 words)

2302. Count Subarrays With Score Less Than K

Question

The score of an array is defined as the product of its sum and its length.

  • For example, the score of [1, 2, 3, 4, 5] is (1 + 2 + 3 + 4 + 5) * 5 = 75.

Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.

A subarray is a contiguous sequence of elements within an array.

Solution

第一次在contest中做出hard题目，而且还是超过100%，庆祝一下！（不过因为前一道题做的太久没提交上去……

滑动窗口

数组内全部为正整数，当选择的子数组的尺寸增加时，其乘积是单调递增的。因此可以采用滑动窗口，在循环时维护窗口内数字的和sum和当前的乘积product。

每次将一个新的右侧元素滑入窗口，更新窗口内的sum值，并计算product值。当当前product大于k时，则将左侧的元素滑出窗口，并更新sum和product值。

调整完窗口尺寸后，由于新的right位置可以和前面的每一个子数组组成一个新的数组，因此将count加上当前的left到right的个数即可。

循环结束后返回count。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public long countSubarrays(int[] nums, long k) {
        long count = 0, sum = 0;
        int left = 0, right = 0;
        
        while(right < nums.length){
            sum += nums[right]; //右侧滑入窗口
            long product = sum * (right - left + 1);
            
            while(product >= k){    //当乘积大于k时，左侧滑出窗口
                sum -= nums[left];
                left++;
                product = sum * (right - left + 1);
            }
            count += right - left + 1;  //计算新的right位置可组成的新组合
            right++;
        }
        return count;
    }
}
Posted Updated LeetCode / Medium / 复习4 minutes read (About 574 words)

2300. Successful Pairs of Spells and Potions

Question

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the i<sup>th</sup> spell and potions[j] represents the strength of the j<sup>th</sup> potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the i<sup>th</sup> spell.

Solution 1

排序+二分搜索。同时记录success与spells[i]的比值来减小计算量。

排序

首先对potions[]进行排序，这样可以使用二分搜索查找分界值。
数组scales[]记录success与spells[i]的比值，以此为界大于等于scales[i]的位置都可以计入ret[]数组。

二分搜索

这里有一些tricky。

由于Arrays.binarySearch()方法无法返回重复的数字，因此在搜索时我们将查找值scale减去一个小值，保证在搜索时一定返回负值。（查找值的插入位置的负数-1）
将ret[i]记录为potions[]的总数减去正确的插入位置即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] ret = new int[spells.length];
        
        Arrays.sort(potions);
        double[] scales = new double[potions.length];
        
        for(int i = 0; i < potions.length; i++){
            scales[i] = (double) potions[i];
        }
        
        for(int i = 0; i < spells.length; i++){
            double scale = (double) success / spells[i] - 0.000001;   //确保浮点数不在scale中出现，binarySearch方法返回的结果必定为上一个插入位置
            int index = Arrays.binarySearch(scales, scale);
            ret[i] = potions.length + (index + 1);
        }
        return ret;
    }
}

Solution 2

由于Arrays.binarySearch()无法正确的搜索有重复元素的数组，因此采用辅助方法binarySearch()来搜索最左侧的下标。

直接在binarySearch()方法中查找target，比较的对象为spell和potions[i]的乘积。

为了搜寻重复的第一个元素，当遇到target时不直接返回，而是继续修改right的位置，直到left等于right。

如果未搜索到，则返回数组的总长度。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] ret = new int[spells.length];
        Arrays.sort(potions);
        for(int i = 0; i < spells.length; i++){
            int index = binarySearch(potions, spells[i], success);
            ret[i] = potions.length - index;
        }
        return ret;
    }
    
    private int binarySearch(int[] potions, long spell, long target){
        int left = 0, right = potions.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(potions[mid] * spell < target) left = mid + 1;
            else right = mid;
        }
        return potions[left] * spell < target ? potions.length : left;
    }
}
Posted Updated LeetCode / Easy2 minutes read (About 255 words)

2299. Strong Password Checker II

Question

A password is said to be strong if it satisfies all the following criteria:

  • It has at least 8 characters.

  • It contains at least one lowercase letter.

  • It contains at least one uppercase letter.

  • It contains at least one digit.

  • It contains at least one special character. The special characters are the characters in the following string: "!@#$%^&*()-+".

  • It does not contain 2 of the same character in adjacent positions (i.e., "aab" violates this condition, but "aba" does not).

Given a string password, return true* if it is a strong password*. Otherwise, return false.

Solution

直接遍历，记录四个真值对应四个符号，初始化为false，和上一个字符last。
每次遍历检查当前字符，如果等于上个字符则直接返回false。
根据字符范围来改变四个真值，最后返回四个真值的和运算。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean strongPasswordCheckerII(String password) {
        if(password.length() < 8) return false;
        char last = ' ';
        boolean hasLower = false, hasUpper = false, hasDigit = false, hasSpecial = false;
        char[] word = password.toCharArray();
        
        for(int i = 0; i < password.length(); i++){
            char cur = word[i];
            if(last == cur) return false;
            if(cur >= 'a' && cur <= 'z') hasLower = true;
            else if(cur >= 'A' && cur <= 'Z') hasUpper = true;
            else if(cur >= '0' && cur <= '9') hasDigit = true;
            else hasSpecial = true;
            last = cur;
        }
        
        return hasLower && hasUpper && hasDigit && hasSpecial;
    }
}
1658. Minimum Operations to Reduce X to Zero
Posted Updated LeetCode / Medium / 复习2 minutes read (About 367 words)

1658. Minimum Operations to Reduce X to Zero

Question

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return *the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return *-1.

Solution

将原有问题的从两边减去一定的值，寻找加和为x的问题转换为寻找滑动窗口中的总和为total - x的新问题。

滑动窗口

初始化当前窗口内的sum，左侧指针left与右侧指针right。
每次将一个新的元素nums[right]加入窗口范围。

当当前的sum大于寻找的target，则将nums[left]滑出窗口，更新left与sum的值。

如果当前窗口内的sum等于寻找的target，则更新记录最小操作次数的min。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minOperations(int[] nums, int x) {
        int total = 0, min = Integer.MAX_VALUE;
        for(int num : nums){
            total += num;
        }
        int target = total - x; //将减去两侧元素并寻找和为x的结果的问题转换为用滑动窗口寻找total - x的结果。
        int sum = 0, left = 0, right = 0;
        while(right < nums.length){
            sum += nums[right]; //调整右侧范围，加入新元素到窗口
            right++;
            
            while(left < right && sum > target){ //如果窗口内的和大于目标，则调整左侧范围
                sum -= nums[left];
                left++;
            }
            if(sum == target){   //如果窗口内的和等于目标，则更新最小操作次数
                min = Math.min(min, nums.length - (right - left));
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}
1332. Remove Palindromic Subsequences
Posted Updated LeetCode / Easy2 minutes read (About 246 words)

1332. Remove Palindromic Subsequences

Question

You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.

A string is called palindrome if is one that reads the same backward as well as forward.

Solution

当字符为空时，返回0。
注意本题中的子序列不需要连续。
由于只有’a’与’b’两个字符，因此最多两步即可将字符串清空。

辅助方法判断字符串是否为回文字符串。
如果为真则返回1，只需要删除一次。

如果为假则返回2，需要先删除所有的’a’，再删除所有的’b’。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int removePalindromeSub(String s) {
        if(s.length() == 0) return 0;
        return isPalindrome(s) ? 1 : 2;
    }
    
    private boolean isPalindrome(String s){
        int i = 0, j = s.length() - 1;
        while(j > i){
            if(s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}
52. N-Queens II
Posted Updated LeetCode / Harda minute read (About 188 words)

52. N-Queens II

Question

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Solution

和昨天的题目51. N-Queens一样。
只是不需要转换并记录字符串了，递归结束时直接将res+1即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    int target;
    int res;
    int[][] operations;
    public int totalNQueens(int n) {
        target = n;
        res = 0;
        operations = new int[][]{{-1,0},{-1,1},{-1,-1}};
        backtracking(new int[n][n], 0, 0);
        return res;
    }
    
    private void backtracking(int[][] board, int i, int n){
        if(n == target){
            res++;
            return;
        }
        for(int j = 0; j < target; j++){
            if(isValid(board, i, j)){
                board[i][j] = 1;
                backtracking(board, i+1, n+1);
                board[i][j] = 0;
            }
        }
    }
    
    private boolean isValid(int[][] board, int i, int j){
        for(int[] operation : operations){
            int p = i + operation[0], q = j + operation[1];
            while(p >= 0 && p < target && q >= 0 && q < target){
                if(board[p][q] == 1) return false;
                p += operation[0];
                q += operation[1];                
            }
        }
        return true;
    }
}
51. N-Queens
Posted Updated LeetCode / Hard / 复习5 minutes read (About 749 words)

51. N-Queens

Question

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Solution

话说今天出这道题真的不是搞事情嘛？

八皇后问题，回溯+剪枝。按顺序搜索可以减少情况的重复计算。
由于棋盘的大小为n * n，要放n个皇后，因此每一行（列）上都有且只有一位皇后。
我们可以依顺序逐行回溯，对逐行的每一列进行回溯。
由于每一行的可选位置都减少1，因此时间复杂度为O(N!)。

回溯

通过一个char数组board[][]记录棋子状态。将board[][]初始化为’.’。
遍历这一行的所有列，如果该位置有效，则board[i][j]改为’Q’，将这个点设置为有棋子，并递归下一行。
回溯，将board[i][j]重新设置为’.’。

当递归次数达到n时，将char[]数组转换为字符串加入答案。

辅助方法 isValid

检测该位置是否有效。即该位置的路径上是否已经有棋子，或该位置已经有棋子。
由于我们的回溯方法是逐行确定棋子位置，因此不需要查看全部八个方向，而是查看之前已经遍历过的行即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    List<List<String>> ret;
    int size;
    int[][] operations;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        size = n;
        operations = new int[][]{{-1,-1},{-1,1},{-1,0}};
        char[][] board = new char[n][n];
        for(char[] s : board){
            Arrays.fill(s,'.');
        }
        backtracking(board,0,0);
        return ret;
    }
    
    private void backtracking(char[][] board, int n, int i){
        if(n == size){
            List<String> ans = new ArrayList<>();
            for(char[] s : board) ans.add(new String(s));
            ret.add(ans);
            return;
        }

        for(int j = 0; j < size; j++){
            if(isValid(board, i, j)){
                board[i][j] = 'Q';
                backtracking(board, n+1, i+1);
                board[i][j] = '.';
            }
        }
    }
    
    private boolean isValid(char[][] board, int i, int j){
        for(int[] operation : operations){
            int p = i + operation[0];
            int q = j + operation[1];
            while(p >= 0 && p < size && q >= 0 && q < size){
                if(board[p][q] == 'Q') return false;
                p += operation[0];
                q += operation[1];
            }
        }
        return true;
    }
}

Solution 2

简单回溯。
在回溯时搜索二维位置，因此增加了时间复杂度，正常是过不了的。
通过按顺序进行搜索（只搜索当前行之后的位置）进行剪枝。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    List<List<String>> ret;
    int size;
    int[][] operations;
    HashSet<String> set;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        size = n;
        operations = new int[][]{{1,1},{1,-1},{1,0},{0,1},{0,-1}};
        backtracking(new int[n][n],0,0);
        return ret;
    }
    
    private void backtracking(int[][] border, int n, int start){
        if(n == size){
            //print(border);
            List<String> ans = new ArrayList<>();
            for(int i = 0; i < size; i++){
                StringBuffer sb = new StringBuffer();
                for(int j = 0; j < size; j++){
                    if(border[i][j] == 1){
                        sb.append("Q");
                    }
                    else{
                        sb.append(".");
                    }
                }
                ans.add(sb.toString());
            }
            ret.add(ans);
            return;
        }
        
        for(int i = start; i < size; i++){
            for(int j = 0; j < size; j++){
                if(border[i][j] == 0){
                    border[i][j] = 1;
                    List<int[]> temp = new ArrayList<>();
                    for(int[] operation : operations){
                        int p = i, q = j;
                        while(p >= 0 && p < size && q >= 0 && q < size){
                            if(border[p][q] == 0){
                                border[p][q] = 2;
                                temp.add(new int[]{p,q});
                            }
                            p += operation[0];
                            q += operation[1];
                        }
                    }
                    backtracking(border, n+1, i+1);
                    for(int[] t : temp){
                        border[t[0]][t[1]] = 0;
                    }
                    border[i][j] = 0;
                }
            }
        }
    }
}
304. Range Sum Query 2D - Immutable
Posted Updated LeetCode / Medium3 minutes read (About 432 words)

304. Range Sum Query 2D - Immutable

Question

Given a 2D matrix matrix, handle multiple queries of the following type:

  • Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

  • NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
  • int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Solution

前缀和/动态规划，用一个dp[][]数组记录到matrix[0][0]到matrix[i][j]区域的和。

计算两个点之间形成的总数只需用外侧的位置的前缀和加上内侧位置的前缀和，然后减去两者交换长宽位置的前缀和即可。

递推公式

计算dp[][]数组时，需要将其上侧与左侧所有数字加和，并加上matrix[][]上该位置对应的元素。
用dp[i][j-1] - dp[i-1][j-1]计算出左侧所有数字之和，dp[i-1][j]则是上侧所有数字之和。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumMatrix {
    int[][] dp;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        dp = new int[m+1][n+1];
        
        for(int i = 1; i <= matrix.length; i++){
            for(int j = 1; j <= matrix[0].length; j++){
                dp[i][j] = dp[i][j-1] - dp[i-1][j-1] + dp[i-1][j] + matrix[i-1][j-1];
            }
        };
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row1][col1] + dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1];
    }
}

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

Solution 2

暴力搜索，直接计算从row1, col1到row2, col2的元素加和。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class NumMatrix {
    int[][] mat;
    public NumMatrix(int[][] matrix) {
        mat = matrix;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for(int i = row1; i <= row2; i++){
            for(int j = col1; j <= col2; j++){
                sum += mat[i][j];
            }
        }
        return sum;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
867. Transpose Matrix
Posted Updated LeetCode / Easya few seconds read (About 107 words)

867. Transpose Matrix

Question

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix’s row and column indices.

Solution

记录一个新数组res[][]。

双重循环，交换下标将matrix[i][j]复制到res[j][i]，最后返回。

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[][] transpose(int[][] matrix) {
        int[][] res = new int[matrix[0].length][matrix.length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                res[j][i] = matrix[i][j];
            }
        }
        return res;
    }
}
1480. Running Sum of 1d Array
Posted Updated LeetCode / Easya few seconds read (About 85 words)

1480. Running Sum of 1d Array

Question

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Solution

类似动态规划，遍历数组，并将当前位置的元素和上一个位置的元素进行加和。

Code

1
2
3
4
5
6
7
8
class Solution {
    public int[] runningSum(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            nums[i] += nums[i-1];
        }
        return nums;
    }
}
Follow

Recents

Archives

Links

×