DFS

leetcode 46 全排列

原题链接:
https://leetcode.cn/problems/permutations/description/

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 {
    List<List<Integer>> ans = new ArrayList<>();
    int [] q;
    int n; 
    public List<List<Integer>> permute(int[] nums) {
        q = nums;
        n = q.length;
        dfs(0,new ArrayList<>());
        return ans;
    }

    private void dfs(int u,List<Integer> list){
        if(n == list.size()){
            ans.add(new ArrayList<Integer>(list));
        }

        for(int i = 0 ; i < n ; i++){
            // 相当于使用了一个used数组
            if(list.contains(q[i])){
                continue;
            }
            list.add(q[i]);
            dfs(i + 1,list);
            list.remove(list.size() - 1);
        }
    }
}

排序

leetcode 283 移动零点

原题链接:
https://leetcode.cn/problems/move-zeroes/description/

最优解是快排思想 当然两次遍历交换也可以做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int j = 0;
        // 快排思想
        for(int i = 0 ; i < nums.length ; i++){
            if(nums[i] != 0){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }
    }
}