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 224 words)

784. Letter Case Permutation

答案
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output 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
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    List<String> ans;
    String _s;
    public List<String> letterCasePermutation(String s) {
        ans = new ArrayList();
        _s = s;
        
        backTrack(new StringBuilder(),0);
        return ans;
        
    }
    
    private void backTrack(StringBuilder sb, int i){
        if(i == _s.length()){
            ans.add(sb.toString());
            return;
        }
        char curr = _s.charAt(i);
        if ( isNums(curr) ){
            sb.append(curr);
            backTrack(sb, i+1);
        }
        else{
            StringBuilder sb2 = new StringBuilder(sb);
            sb.append(Character.toLowerCase(curr));
            backTrack(sb, i+1);
            sb2.append(Character.toUpperCase(curr));
            backTrack(sb2, i+1);
        }
    }
    
    private boolean isNums(char c){
        if ( (int)c >= (int)'0' && (int)c <= (int)'9' ){
            return true;
        }
        return false;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 181 words)

46. Permutations

问题
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

回溯，建立搜索树。
每次遍历nums中的元素。
如果未遍历过该元素，则向链表及set中添加。
向下递归，链表长度达到nums的长度时返回。
然后从set和链表中移除上一个值，回溯到上一个节点。

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
class Solution {
    List<List<Integer>> ans;
    HashSet<Integer> set;
    public List<List<Integer>> permute(int[] nums) {
        ans = new ArrayList();
        set = new HashSet();
        backTrack(new LinkedList(), nums, nums.length, nums.length);
        return ans;
    }
    
    private void backTrack(LinkedList<Integer> list,int[] nums, int n, int k){
        if(k == 0){
            ans.add(new ArrayList(list));
            return;
        }
        for(int i = 0; i < n ; i++){
            if(!set.contains(nums[i])){
                list.add(nums[i]);
                set.add(nums[i]);
                backTrack(list, nums , n, k-1);
                set.remove(nums[i]);
                list.removeLast();
            }
        }
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 235 words)

567. Permutation in String

问题
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

将要查找的组合加入数组，数值为字符出现的次数。
滑动窗口，入窗口对应的元素数值-1，出窗口对应的元素数值+1。
每次移动窗口都检验一次数组的数值是否全部为0，如果是真，则返回真。
小技巧：直接用数组来记录字符出现的次数，用字符减去与’a’的差作为下标。

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 boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()){
            return false;
        }
        
        int[] dic = new int[26];
        for (int i = 0; i < s1.length(); i++){
            dic[s1.charAt(i)-'a']++;
            dic[s2.charAt(i)-'a']--;
        }
 
        int i = 0;
        int j = s1.length();
        
        while( j < s2.length() ){
            if ( allZero(dic) ){
                return true;
            }
            dic[s2.charAt(i)-'a']++;
            dic[s2.charAt(j)-'a']--;
            i++;
            j++;
        }
        return allZero(dic);
    }
    
    private boolean allZero(int[] dic){
        for (int num : dic){
            if ( num != 0 ){
                return false;
            }
        }
        return true;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 388 words)

31. Next Permutation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

从数组末尾开始遍历第i个元素。
如果后一项小于前一项，则排序关系正确。
反之则将i与遍历过的部分中比i大的第一个数字交换。
然后对已遍历的部分排序。

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
class Solution {
    public void nextPermutation(int[] nums) {
        int flag = 0;   //标记，如果没有下一个排列时，排序数组。
        if (nums.length != 1){
            int i = nums.length -2;
            while (i >= 0){
                if (nums[i + 1] <= nums[i]) {   //从尾部开始，比较元素是否是大到小
                    i--;
                    continue;
                }
                else {  //排序关系不正确时
                    for (int j = nums.length-1;j>i;j--){
                        if (nums[j] <= nums[i]){
                            continue;
                        }
                        int temp = nums[j]; //将i元素和遍历过的元素中第一个比nums[i]大的交换。
                        nums[j] = nums[i];
                        nums[i] = temp;
                        Arrays.sort(nums,i+1,nums.length);  //排序i之后的数组。
                        flag = 1;
                        break;
                    }
                    break;
                }
            }
            if (flag == 0 ){    //如果全部从大到小，则排序整个数组。
                Arrays.sort(nums);
            }  
        }
    }
}

Follow

Recents

Archives

Links

×