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 / Mediuma minute read (About 217 words)

284. Peeking Iterator

Design an iterator that supports the peek operation on an existing iterator in addition to the hasNext and the next operations.

Implement the PeekingIterator class:

  • PeekingIterator(Iterator nums) Initializes the object with the given integer iterator iterator.
  • int next() Returns the next element in the array and moves the pointer to the next element.
  • boolean hasNext() Returns true if there are still elements in the array.
  • int peek() Returns the next element in the array without moving the pointer.

Note: Each language may have a different implementation of the constructor and Iterator, but they all support the int next() and boolean hasNext() functions.

使用队列储存迭代器里的数据，根据需要返回队列里的数据。

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
// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {
    Queue<Integer> q;
	public PeekingIterator(Iterator<Integer> iterator) {
	    // initialize any member here.
	    q = new LinkedList<>();
        while(iterator.hasNext()){
            q.add(iterator.next());
        }
	}
	
    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
        return q.peek();
	}
	
	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
	    return q.poll();
	}
	
	@Override
	public boolean hasNext() {
	    return !q.isEmpty();
	}
}
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;
    }
}
Follow

Recents

Archives

Links

×