颜色分类

很简单的一道题,按理来说应该给easy,无奈想不到单指针,进行两次遍历,进行交换元素

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 void sortColors(int[] nums) {
        int n = nums.length;
        int tag = 0;
        for(int i = 0; i<n; i++){
            if(nums[i]==0){
                int temp = nums[i];
                nums[i] = nums[tag];
                nums[tag] = temp;
                tag++;
            }
        }
        int tag2 = tag;
        for(int i = tag; i<n; i++){
                if(nums[i]==1){
                    int temp = nums[i];
                    nums[i] = nums[tag2];
                    nums[tag2] = temp;
                    tag2++;
                }
            }
    }
}

下一个排列

很抽象的一提,微笑,先从最右边开始,找到第一个左边小于右边的数,然后从最右边开始,找到第一个大于这个数的数,然后交换这两个数,最后将这个数后面的数进行翻转,因为后面的数是降序的,所以翻转后就是最小的排列了

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
class Solution {
    public void nextPermutation(int[] nums) {
        int k = nums.length - 2;
        // 从右往左找到第一个递增的位置
        while (k >= 0 && nums[k] >= nums[k + 1]) {
            k--;
        }
        // 如果k < 0，说明整个序列是降序的，直接反转即可
        if (k < 0) {
            reverse(nums, 0, nums.length - 1);
            return;
        }
        // 从右往左找到第一个比nums[k]大的位置
        int l = nums.length - 1;
        while (l > k && nums[l] <= nums[k]) {
            l--;
        }
        // 交换nums[k]和nums[l]
        swap(nums, k, l);
        // 反转nums[k+1]到nums[nums.length-1]
        reverse(nums, k + 1, nums.length - 1);
    }

    // 交换数组中两个元素的位置
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 反转数组中一段元素的顺序
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

螺旋矩阵

形象的去想,进行对于四个顶点去卡着,遍历有点想法

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 {
    public List<Integer> spiralOrder(int[][] matrix) {
        int left = 0 , right = matrix[0].length-1;
        int top = 0 , below = matrix.length-1;
        List<Integer> ans = new ArrayList<>();
        while(true){
            for(int i = left; i<right; i++){
                ans.add(asList(matrix[top][i]));
            }
            if(++top>below) break;
            for(int i = top; i<below; i++){
                ans.add(asList(matrix[i][right]));
            }
            if(++top>below) break;
            for(int i = right; i>left; i++){
                ans.add(asList(matrix[below][i]));
            }
            if(top>--below) break;
            for(int i = below; i>top; i++){
                ans.add(asList(matrix[i][left]));
            }
            if(++left>right) break;
        }
        return ans;
    }
}