算法--2023.1.20

1.acwing842--排列数字

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static boolean[] flag;
    public static Deque<Integer> queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        flag = new boolean[n+1];
        dfs(n);
    }
    public static void dfs(int n){
        if(queue.size() == n){
            for(int t : queue){
                System.out.print(t + " ");
            }
            System.out.println();
        }
        for(int i = 1;i<=n;i++){
            if(flag[i] == false){
                flag[i] = true;
                queue.addLast(i);
                dfs(n);
                queue.removeLast();
                flag[i] = false;
            }
        }

    }
}

2.力扣240--搜索二维矩阵2

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int i = n-1, j = 0;
        while(i>=0&&j<m){
            if(matrix[j][i]>target){
                i--;
            }else if(matrix[j][i]<target){
                j++;
            }else{
                return true;
            }
        }
        return false;
    }
}

3.力扣283--移动零

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        for(int i = 0;i<n;i++){
            boolean flag = false;
            for(int j = 1;j<n;j++){
                if(nums[j-1] == 0){
                    flag = true;
                    int temp = nums[j-1];
                    nums[j-1] = nums[j];
                    nums[j] = temp;
                }
            }
            if(flag == false){
                return;
            }
        }
        return;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        //快慢指针算法:一次遍历，快指针在前面找到不是0的元素，然后放到慢指针这里，可以保证所有非零元素按照原来顺序相邻
        int n = nums.length;
        int i = 0, j = 0;
        for(;j<n;j++){
            if(nums[j] !=0){
                nums[i++] = nums[j];
            }
        }
        for(int k = i;k<n;k++){
            nums[k] = 0;
        }

    }
}