Posted Updated LeetCode / Medium / 复习2 minutes read (About 255 words)

47. Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

首先排序，对于有重复数据的数组，排序可以方便剪枝。
回溯，每次遍历数组内的元素。
创建一个数组记录元素是否已被遍历。
遍历时如果数组已经被记录，或者当前元素与数组中的上一个元素相等，且上一个数组未被选择，则跳过。
（如果上一个同样的数字没被选择，则放弃这个排列。即在元素相同时，优先选择前面的元素进行排列）

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
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int[] visited = new int[nums.length];
        backtracking(ret, new ArrayList<>(), visited , nums);
 
        return ret;
    }

    private void backtracking(List<List<Integer>> ret, List<Integer> arr, int[] visited, int[] nums){
        if(arr.size() == nums.length){
            ret.add(new LinkedList<>(arr));
            return;
        }
        
        for(int i = 0; i < nums.length; i++){
            if(visited[i] == 1) continue;
            if(i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0) continue;
            arr.add(nums[i]);
            visited[i] = 1;
            backtracking(ret, arr, visited, nums);
            visited[i] = 0;
            arr.remove(arr.size()-1);
        }
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 214 words)

90. Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

首先对数组进行排序，这样重复的元素将排列在一起。
接下来对每一个层级进行回溯。
进入每一个层级都根据上一级传递来的列表创建新列表。
然后对层级下的所有元素进行回溯。
剪枝，当遍历节点和上一个节点相等时，则跳过。
回溯，从列表中去掉最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        backtrack(ret, new LinkedList<Integer>(), nums, 0);
        return ret;
    }
    
    private void backtrack(List<List<Integer>> ret, List<Integer> arr, int[] nums, int level){
        ret.add(new LinkedList<>(arr));
        
        for(int i = level; i < nums.length; i++){
            if(i != level && nums[i] == nums[i-1]) continue;
            arr.add(nums[i]);
            backtrack(ret, arr, nums, i+1);
            arr.remove(arr.size()-1);
        }
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 351 words)

187. Repeated DNA Sequences

The DNA sequence is composed of a series of nucleotides abbreviated as ‘A’, ‘C’, ‘G’, and ‘T’.

  • For example, “ACGAATTCCG” is a DNA sequence.
    When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

哈希表 + 滑动窗口 + 位操作。
将四个字符映射到四个二进制字符上。这样字符串就可以用20bit表示。
这样就可以用一个整数来表示这四个字符。
然后采用哈希表记录出现次数。

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
class Solution {
    static final int L = 10;
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<String>();
        if(s.length() < L) return ret;
        HashMap<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int right = 10;
        
        int[] bin = new int[26];
        bin['A'-'A'] = 0;
        bin['T'-'A'] = 1;
        bin['C'-'A'] = 2;
        bin['G'-'A'] = 3;
        
        int x = 0;
        for(int i = 0; i < L-1; i++){
            x = (x << 2) | bin[s.charAt(i)-'A'];
        }
        
        for(int i = 0; i <= s.length() - L; i++){
            x = ((x << 2) | bin[s.charAt(i + L -1)-'A']) & ((1 << L * 2) - 1);
            map.put(x, map.getOrDefault(x, 0)+1);
            if(map.get(x) == 2) ret.add(s.substring(i, i+L)); 
        }
        return ret;
    }
}

遍历将字字符串加入哈希表并记录出现次数，然后返回出现次数大于1的字符串。
注意在循环时就可以直接添加结果到列表，这样可以减少操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<String>();
        HashMap<String, Integer> map = new HashMap<>();
        int left = 0;
        int right = 10;
        
        while(right <= s.length()){
            String sub = s.substring(left, right);
            map.put(sub, map.getOrDefault(sub, 0)+1);
            if(map.get(sub) == 2) ret.add(sub); 
            left++;
            right++;
        }
        return ret;
    }
}
5. Longest Palindromic Substring
Posted Updated LeetCode / Medium / 复习8 minutes read (About 1136 words)

5. Longest Palindromic Substring

Question

Given a string s, return the longest palindromic substring in s.

Solution

马拉车算法，专门用于计算最大回文子字符串长度。

预处理

首先需要对字符串进行预处理，将每两个字符之间（包括两端）加上一个符号’#’。
然后在字符串的前后加入任意两个不同的符号。（防止中心扩展时继续搜索）

这个操作使得偶数项的回文字符串变为奇数项的回文字符串，便于接下来进行统一的中心扩展操作。

Manacher算法

参考资料：一文让你彻底明白马拉车算法

用一个数组p[]记录处理后字符串位置的中心展开长度。

初始化一个回文中心的下标位置i，和当前回文中心的右侧范围r。
在进行算法时维护这两个参数。

遍历字符串中除了首尾两个字符以外的位置。

  • 初始化i位置关于c的镜像位置m为2*c-i。
    由于回文字符串的对称特性，此时p[i]的中心拓展长度应等于p[m]。
  • 有几种特例情况，p[i]不等于p[m]：
  1. 如果p[m] + m的和大于r，则以m为中心扩展的范围超过当前c的中心扩展范围的右界。
    此时p[i]无法保证等于p[m]。但是可以确保p[i]至少可以扩展到r，因此将p[i]更新为r-i。
  2. 如果i的位置等于r，则可扩展距离为0。
  3. 如果m的位置为原字符串的左边界，则此时将p[i]赋值为1是不正确的。
    因为p[m]的计算是遇到了边界停止的，而p[i]则没有遇到边界，接下来对i位置从i+p[i]与i-p[i]开始继续进行中心扩展即可。

中心扩展

奇数项的回文字符串由中心扩展，只需要保证i+p[i]+1与i-p[i]-1（两个位置分别表示当前中心扩展的边缘再前进1）的字符相同，则可以继续向下扩展，将p[i]++。

c与r的更新

由于要保证i在r的范围之内，当从i出发的中心扩展范围大于c的中心扩展范围r，需要更新c与r。

时间复杂度

在进行扩展时，每次访问过的位置不会进入中心扩展算法。（比较从中心扩展的边缘开始，即i+p[i]+1与i-p[i]-1）
因此总的时间复杂度为O(n)。

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
class Solution {
    int n;
    int[] p;
    String newString;
    public String longestPalindrome(String s) {
        n = s.length();
        StringBuffer sb = new StringBuffer();
        if(n == 0) {   //对字符串进行处理
            sb.append("^$");
        }
        else{
            sb.append("^");
            for(int i = 0; i < s.length(); i++){
                sb.append('#');
                sb.append(s.charAt(i));
            }
            sb.append("#$");
        }
        p = new int[sb.length()];
        newString = sb.toString();
        manacher();
        
        int c = 0;
        for(int i = 0; i < sb.length(); i++){
            if(p[i] > p[c]) c = i;
        }
        return s.substring( (c-p[c])/2, (c-p[c])/2+p[c] );
    }
    
    private void manacher(){
        int c = 0, r = 0;
        for(int i = 1; i < p.length - 1; i++){
            int m = 2 * c - i;
            if(i < r){  //当i在r的范围内时，p[i]的值与p[m]相等。
                p[i] = Math.min(r-i, p[m]); //当p[m] + i超过了r时(当前中心拓展边界)，p[i]至少可以取值到r-i
            }
            else{
                p[i] = 0; //当i等于r时，该位置拓展距离为0
            }
            
            while (newString.charAt(i+p[i]+1) == newString.charAt(i-p[i]-1)) {  //中心拓展算法，当两个位置相等时则可拓展距离+1
                p[i]++;
            }
            
            if(i + p[i] > r){   //当当前位置的右侧边界大于现有边界时，更新位置r
                c = i;
                r = i + p[i]; //新的右侧边界为新的中心+拓展长度p[i]
            }
        }
    }
}

Solution 2

getLength方法，计算每一个字符位置的回文长度。（将left填成i+1，right填成i则可以搜索偶数回文的长度。）
如果出现更长的回文，则根据返回的长度，和当前的i计算出字符串的范围。

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
class Solution {
    public String longestPalindrome(String s) {
        int best = 0;
        int left = 0;
        int right = 0;
        for(int i = 0; i < s.length(); i++){
            int length = Math.max(getLength(s,i,i), getLength(s,i+1,i));
            if(best < length){
                left = i-((length-1)/2-1);
                right = i+(length/2);
                best = length;
            }
        }
        return s.substring(left,right);
    }
    
    private int getLength(String s, int left, int right){
        while(left >= 0 && right < s.length() && left < s.length()){
            if(s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            else break;
        }

        return right - left + 1;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 436 words)

1396. Design Underground System

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

  • void checkIn(int id, string stationName, int t)
    • A customer with a card ID equal to id, checks in at the station stationName at time t.
    • A customer can only be checked into one place at a time.
  • void checkOut(int id, string stationName, int t)
    • A customer with a card ID equal to id, checks out from the station stationName at time t.
  • double getAverageTime(string startStation, string endStation)
    • Returns the average time it takes to travel from startStation to endStation.
    • The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.
    • The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.
    • There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.
      You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t1 then checks out at time t2, then t1 < t2. All events happen in chronological order.

两个哈希表，第一个暂存id。第二个用来储存“站点——站点”和路线中的总用时，路线中的总人数。
最后返回总用时除以总人数。
（一开始采用的算法没有考虑id重复进站，和id出站进站不同的情况。）

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
class UndergroundSystem {
    HashMap<Integer, Pair<String, Integer>> inMap;
    HashMap<String, int[]> outMap;
    public UndergroundSystem() {
        inMap = new HashMap<Integer, Pair<String, Integer>>();
        outMap = new HashMap<String, int[]>();
    }
    
    public void checkIn(int id, String stationName, int t) {
        Pair<String, Integer> data = new Pair(stationName, t);
        inMap.put(id, data);
    }
    
    public void checkOut(int id, String stationName, int t) {
        Pair<String, Integer> data = inMap.get(id);
        String route = data.getKey() + "-" + stationName;
  
        int[] routeData = outMap.getOrDefault(route, new int[2]);
        routeData[0] += t - data.getValue();
        routeData[1]++;
    
        outMap.put(route, routeData);
    }
    
    public double getAverageTime(String startStation, String endStation) {
        String route = startStation + "-" + endStation;
        return outMap.get(route)[0] / (double) outMap.get(route)[1];
    }
}

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem obj = new UndergroundSystem();
 * obj.checkIn(id,stationName,t);
 * obj.checkOut(id,stationName,t);
 * double param_3 = obj.getAverageTime(startStation,endStation);
 */
Posted Updated LeetCode / Medium / 复习a minute read (About 214 words)

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

两个字符串的位数做乘法，每次计算进位。
当前位等于自身加上计算结果的个位（由于有之前的进位存在。），下一位等于计算结果的十位。

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
class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        if( num1.equals("0") || num2.equals("0")){
            return "0";
        }
        int[] product = new int[m+n];
        
        char[] arr1 = num1.toCharArray();
        char[] arr2 = num2.toCharArray();
        
        for(int i = m-1; i >= 0; i--){
            for(int j = n-1; j >=0; j--){
                int sum = product[i+j+1] + (arr1[i] - '0') * (arr2[j] - '0');
                int curr = sum % 10;
                int carry = sum / 10;
            
                product[i+j] += carry;
                product[i+j+1] = curr;
            }
        }
        StringBuffer sb = new StringBuffer();
        for(int k = 0; k < m+n; k++ ){
            if(k == 0 && product[k] == 0 ) continue;
            sb.append(product[k]);
        }
        return sb.toString();
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 246 words)

49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

利用JAVA中字符串会固定内存地址。（因此在进行字符串操作时是生成了新的对象。）
遍历每个单词，记录26个字母出现的次数，并映射到字符数组上。
将字符数组转换成字符串，生成一个新的字符串。

将字符串作为key放入map中，value储存原有单词。（字符串的内存地址固定，因此同样的字符串可以被搜索到。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ret = new ArrayList<>();
        HashMap<String, List<String>> map = new HashMap<>();
        
        for(String word : strs){
            char[] alphabet = new char[26];
            for(int j = 0; j < word.length(); j++){
                alphabet[word.charAt(j)-'a']++;
            }
            String s = new String(alphabet);
            List<String> str = map.getOrDefault(s, new ArrayList<String>());
            str.add(word);
            map.put(s, str);
        }
        for(String key : map.keySet()){
            ret.add(map.get(key));
        }
        return ret;   
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 519 words)

1091. Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.

由于不能重复搜索，且需要在搜索时将搜索过的位置改变，因此需要采用BFS逐一层级的搜索。
逐层级搜索并记录层级。最后返回层级+1即可。
（还有更快的优化算法A*）

整体没有改变太多，基本还是方法二那种。启发式函数改为切比雪夫距离距离。
距离计算方法有很多，常用启发式函数有这几种。选择合适的启发式函数有利于速度的提升。这题可以用好几种启发式函数，初学都可以试着都写一下。

曼哈顿距离（Manhattan Distance）
一般只能在四个方向上移动时用（右、左、上、下）

对角线距离（Diagonal Distance）：
当我们只允许向八个方向移动时用（国际象棋中的王移动方式那种）

欧几里得距离（Euclidean Distance）：
不受限制，允许向任何方向移动时。

切比雪夫距离（Chebyshev Distance）：
可参考：[https://leetcode-cn.com/problems/minimum-time-visiting-all-points/solution/fang-wen-suo-you-dian-de-zui-xiao-shi-jian-by-le-2/](LeetCode 1266)

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
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid[0].length;
        int m = grid.length;
        
        Queue<Integer> q = new LinkedList<>();
        int count = 0;
        q.add(0);
        int size = q.size();
        
        while(!q.isEmpty()){
            for(int k = 0; k < size; k++){
                int curr = q.poll();
                int i = curr / n;
                int j = curr % n;

                if(grid[i][j] ==1) continue;                
                if(i == m-1 && j == n-1 && grid[i][j] == 0) return count+1;
            
                if(grid[i][j] == 0){
                    grid[i][j] = 1;
                    if(i+1<n && j+1<n) q.add((i+1) * n + (j+1));
                    if(i+1<n && j-1>=0) q.add((i+1) * n + (j-1));
                    if(i+1<n) q.add((i+1) * n + j);
                    if(i-1>=0 && j-1>=0) q.add((i-1) * n + (j-1));
                    if(i-1>=0 && j+1<n) q.add((i-1) * n + (j+1));
                    if(j+1<n) q.add(i * n + (j+1));
                    if(j-1>=0) q.add(i * n + (j-1));
                    if(i-1>=0) q.add((i-1) * n + j);
                }
            }
            size = q.size();
            count++;
        }
        return -1;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 194 words)

547. Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

DFS搜索，当map[i][i] = 1时加入搜索。
搜索时将map[i][i]设为0。遍历并递归其数列。
当map[i][i]等于0时，返回。

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
class Solution {
    int[][] map;
    public int findCircleNum(int[][] isConnected) {
        map = isConnected;
        int count = 0;
        
        for(int i = 0; i < isConnected.length; i++){
            if(map[i][i] == 1){
                count++;
                dfs(i);
            }
        }
        return count;
    }
    
    private void dfs(int i){
        if(map[i][i] == 0){
            return;
        }
        map[i][i] = 0;
        for(int j = 0; j < map[0].length; j++){
            if(map[i][j] == 1){
                dfs(j);
            }
        }
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 150 words)

713. Subarray Product Less Than K

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

滑动窗口，维护一个窗口内的乘积。
当乘积小于目标值时，窗口右侧向右移动。每加入一个新数值，可以增加(j-i+1)个组合。
当乘积大于目标时，窗口左侧向右移动。

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 numSubarrayProductLessThanK(int[] nums, int k) {
        int i = 0;
        int j = 0;
        int product = nums[0];
        int count = 0;
        
        while(i < nums.length && j < nums.length){
            if(product < k){
                count += (j - i) + 1;
                j++;
                if(j < nums.length ) product *= nums[j];
            }
            else{
                product /= nums[i];
                i++;
            }   
        }
        return count;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 451 words)

209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

滑动窗口，先取最左侧数字。记录窗口的最小值。
如果小于目标值，则右侧窗口向右移动，扩大窗口。更新窗口内的值。
如果大于等于目标值，则左侧窗口向右移动，缩小窗口。更新窗口内的值。
同时如果窗口大小小于最小值则更新窗口最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int sum = nums[0];
        while(right < nums.length){
            if(sum >= target){
                min = Math.min(min, right - left + 1);
                sum -= nums[left];
                left++;
            }
            else{
                right++;
                if(right < nums.length) sum += nums[right];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

计算前缀和。
前缀和[j]与前缀和的[i]的差就是i+1到j的和。
因此需要找到sum[j] - sum[i] >= k。
暴力枚举的话需要O(n^2^)的时间复杂度。

由于前缀和是有序的，因此我们可以采用二分搜索。
寻找sum[j] - k >= sum[i]。
Arrays.binarySearch方法可以返回查找到的目录。
如果没有该值，方法会返回一个负数，其取反（x取反相当于[-(x+1)]）的值就是应该插入的目录。
将ans设置为无限大，如果(index - i)小于最小值则更新到ans。

时间复杂度O(nlogn)。

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 minSubArrayLen(int target, int[] nums) {
        int[] sum = new int[nums.length+1];
        for(int i = 1; i <= nums.length; i++){
            sum[i] = sum[i-1] + nums[i-1];
        }
        
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < sum.length; i++){
            int search = sum[i] + target;
            int index = Arrays.binarySearch(sum, search);
            if(index < 0){
                index = ~index;
            }
            if(index < sum.length){
                ans = Math.min(ans, index - i);
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 243 words)

560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

对于数组中每个数字，计算其前缀的和。
前缀[i]减去前缀[j]的差，等于[j]-[i]之间数字的和。（类似一种DP，数组可以用一个变量代替。）

因此，原题目等于寻找找 前缀[i]-前缀[j] = k。
用哈希表储存已经遍历过的前缀和出现的次数。
每次遍历时先查看哈希表内是否有当前[前缀和-k]的键在。
如果有则加入到count中。
（哈希表中需要提前放入一个0键，值等于1，为了计算[前缀和-k]等于0的情况。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int subarraySum(int[] nums, int k) {
        
        int[] sum = new int[nums.length + 1];
        HashMap<Integer, Integer> map = new HashMap();
        int count = 0;
        map.put(0, 1);
        
        for(int i = 1; i <= nums.length; i++){
            sum[i] = sum[i-1] + nums[i-1];
            count += map.getOrDefault(sum[i]-k, 0);
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
        }
        
        return count;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 258 words)

238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

当前数字之外的积等于左边所有数字的积乘以右边所有数字的积。
因此可以维护两个数组，分别计算从左到右的乘积，和从右到左的乘积。

由于返回答案不算占用空间，因此可以将左侧乘积的数组保存在答案数组上。
然后在遍历时，从右至左遍历，使用一个变量储存右边的乘积，直接将两者的乘积更新在答案数组上。
此时空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        ans[0] = 1;
        
        for(int i = 1; i < nums.length; i++){
            ans[i] = ans[i-1] * nums[i-1];
        }
        
        int rightProduct = 1;
        
        for(int j = nums.length-1; j >=0; j--){
            ans[j] = ans[j] * rightProduct;
            rightProduct *= nums[j];
        }
        return ans;   
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 307 words)

438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

滑动窗口。采用两个数组分别计算两个字符串中字符出现的数量。

滑动窗口时，维护数组中字符串中字符出现的次数。
循环，判断两个字符串是否相等，如果相等，则将当前的左指针添加进答案。
移动窗口的左右指针，在数组中减少前一项出现的次数，增加后一项出现的次数。

通过维护一个表示两个字符串中字符差值的数组，可以将算法优化算法，而不必进行两个数组的比较。

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 List<Integer> findAnagrams(String s, String p) {        
        List<Integer> ans = new ArrayList();
        if(p.length()>s.length()){
            return ans;
        }
        
        int[] alphabet = new int[26];
        int[] window = new int[26];
        
        for(int i = 0; i < p.length(); i++){
            alphabet[p.charAt(i) - 'a']++;
            window[s.charAt(i) - 'a']++;
        }
        
        int i = 0;
        int j = p.length();
        
        while(j < s.length()){
            if(Arrays.equals(alphabet, window)){
                ans.add(i);
            }
            window[s.charAt(i) - 'a']--;
            window[s.charAt(j) - 'a']++;
            i++;
            j++;
        }
        
        if(Arrays.equals(alphabet, window)){
            ans.add(i);
        }
        
        return ans;
        
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 511 words)

334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

贪心算法。
将first与second初始化为最大值。
first保存遍历过的最小值。
second保存遍历过的大于之前最小值的最小值。

遍历数组。
条件一：如果数字小于现在第一个值，则更新第一个值。
（此时一定不满足条件二，因此可以安全地更新更小的数字。）
条件二：如果数字大于第一个值，且小于第二个值，则更新第二个值。
（此时第一个值已经被更新过了，满足第一个值小于第二个值。）
条件三：如果数字大于第二个值，则返回true。
（此时两个值一定都被更新过了，满足第一个值小于第二个值小于第三个值。）

注意：
更新first后，second不会更新，但是second的存在可以确保曾经存在first小于second。
如果此时数字大于second，则数组中存在Triplet Subsequence。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;
        
        for(int num : nums){
            if(num < first){
                first = num;
            }
            else if(num > first && num < second){
                second = num;
            }
            else if(num > second){
                return true;
            }   
        }
        return false;
    }
}

双向遍历，逐渐收紧搜索窗口。设置i，k两个指针分别在头尾。
当nums[j] <= nums[i]，则更新i指针为j。
当nums[j] >= nums[k]，则更新k指针为j。
如果找到符合条件的nums[i] < nums[j] < nums[k]则返回。

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
class Solution {
    public boolean increasingTriplet(int[] nums) {
        boolean flag = true;
        int i = 0;
        int k = nums.length -1 ;
        int j;
        int count = 1;
        
        while(i < k && i + count < k){
            if(flag){
                j = i + count;
                if(nums[i] >= nums[j]){
                    i = j;
                    count = 1;
                    flag = true;
                    continue;
                }
                else if(nums[j] < nums[k]){
                    return true;
                }
                flag = !flag;
            }
            else{
                j = k - count;
                if(nums[k] <= nums[j]){
                    k = j;
                    count = 1;
                    flag = true;
                    continue;
                }
                else if(nums[j] > nums[i]){
                    return true;
                }
                else{
                    count++;
                }
                flag = !flag;
            }
        }
        return false;
    }
}
Follow

Recents

Archives

Links

×