头像

白小白

河北科师




离线:5个月前


活动打卡代码 AcWing 843. n-皇后问题

白小白
6个月前
import java.util.*;

public class Main{
    static String[][] path = new String[10][10];
    static boolean[] col = new boolean[20];
    static boolean[] dg = new boolean[20];
    static boolean[] udg = new boolean[20];
    static int n = 0;
    public static void main(String[] args){
        Scanner read = new Scanner(System.in);
        n = read.nextInt();
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                path[i][j] = ".";
            }
        }
        dfs(0);
    }
    public static void dfs(int k){
        if(k == n){
            for(int i = 0;i < n;i++){
                for(int j = 0;j < n;j++){
                    System.out.print(path[i][j]);

                }
                System.out.println();
            }
            System.out.println();
            return;
        }
        for(int i = 0;i < n;i++){
            if(!col[i] && !dg[i+k] && !udg[i-k+n]){
                path[i][k] = "Q";
                col[i] = dg[i+k]  = udg[i-k+n] = true;
                dfs(k+1);
                path[i][k] = ".";
                col[i] = dg[i+k]  = udg[i-k+n] = false;

            }
        }
    }
}



白小白
6个月前

n-皇后问题(八皇后)

作为一道经典的题目,那必然要用经典的dfs来做
dfs:深度优先搜索————纵向搜索符合条件的内容,走到底时回到上一个路口再走到底再回去,套娃至结束。

条件:任意一个皇后所在位置的四条线(横、纵、对角、副对角)不能放置其他皇后
横:x
纵:y
副对角:y = x
主对角:y = - x

思路:
平面坐标系中的副对角线实际上也就是二维数组中的主对角线
所以得出:
任意一条副对角线公式为
y = x + b => b = y - x + n(数组中没有负数所以平移n位)
任意一条主对角线公式为
y = - x + b => b = x + y

b 是任意一条主副对角线到(0,0)的截距

那我们就可以通过一个一维数组来表示二维数组中的每一条主副对角线

至多会有2*n条主或副对角线,所以只需要开2n的空间就可以了

下面图随便看看

代码奉上

import java.util.*;

public class Main{
    static int n = 0;
    static String[][] path = new String[10][10];
    static boolean[] col = new boolean[20];
    static boolean[] dg = new boolean[20];
    static boolean[] udg = new boolean[20];
    public static void main(String[] args){
        Scanner read = new Scanner(System.in);
        n = read.nextInt();
        for(int i = 0;i < n;i++){
                for(int j = 0;j < n;j++){
                    path[i][j] = ".";
                }
            }
        dfs(0);
    }
    public static void dfs(int k){
        if(k == n){
            for(int i = 0;i < n;i++){
                for(int j = 0;j < n;j++){
                    System.out.print(path[i][j]);
                }
                System.out.println();
            }
            System.out.println();
            return;
        }

         for(int i = 0;i < n;i++){
        if(!col[i] && !dg[k+i] && !udg[i-k+n]){
            path[k][i] = "Q";
            col[i] = dg[k+i] = udg[i-k+n] = true;
            dfs(k+1);
            path[k][i] = ".";
            col[i] = dg[k+i] = udg[i-k+n] = false;
        }
    }
    }

}

时间复杂度



活动打卡代码 AcWing 842. 排列数字

白小白
7个月前
import java.util.*;
public class Main{
    static boolean[] st = new boolean[10];
    static int[] path = new int[10];
    static int n = 0;
    public static void main(String[] args){
        Scanner read = new Scanner(System.in);
        n = read.nextInt();
        dfs(0);
    }
    public static void dfs(int u){
        if(u == n){
            for(int i = 0;i < n;i++){
                System.out.print(path[i]+" ");
            }
            System.out.println();
        }
        for(int i = 1;i <= n;i++){
            if(!st[i]){
                path[u] = i;
                st[i] = true;
                dfs(u+1);
                st[i] = false;
            }
        }
    }
}



白小白
7个月前

位运算
负数的二进制表示为:符号位置为1 其余按位(正数正常位置)取反末位加一 等于 非运算后加一

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner read = new Scanner(System.in);
        int n = read.nextInt();

        for(int i = 0;i < n;i++){
            int x = read.nextInt();
            int res = 0;
            while(x != 0){
                x -= x&-x;
                res++;
            }
            System.out.print(res+" ");
        }
    }
}



白小白
7个月前

O(n+m)
i指针从前到后
j指针从后到前
因为两个数组都是升序的
所以在满足(a[i]+b[j] >= x)时移动j指针,最后保证b[j]是满足 a[i]+b[j] >= x 的最小值
当j循环一遍时必定会有解

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner read = new Scanner(System.in);
        int n = read.nextInt();
        int m = read.nextInt();
        int x = read.nextInt();
        int[] a = new int[100010];
        int[] b = new int[100010];
        for(int i = 0;i < n;i++){
            a[i] = read.nextInt();
        }
        for(int i = 0;i < m;i++){
            b[i] = read.nextInt();
        }
        int j = m-1;
        for(int i = 0;i < n;i++){
            while(j >= 0 && a[i] + b[j] >= x){
                if(a[i] + b[j] == x)System.out.print(i+" "+j);
                j--;

            }
        }
    }
}



白小白
7个月前
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner read = new Scanner(System.in);
        int n = read.nextInt();
        int[] num = new int[100010];
        int[] s = new int[100010];
        int j = 0;
        int res = 0;
        for(int i = 0;i < n;i++){
            num[i] = read.nextInt();
        }
        for(int i = 0;i < n;i++){
            s[num[i]]++;
            while(s[num[i]] > 1){
                s[num[j]]--;
                j++;
            }
            res = Math.max(res,i-j+1);
        }
        System.out.print(res);
    }
}


活动打卡代码 AcWing 797. 差分

白小白
7个月前
import java.util.*;

public class Main{
    static Scanner read = new Scanner(System.in);
    static int[] b = new int[100010];

    public static void main(String[] args){
        int n = jin();
        int m = jin();
        int[] a = new int[100010];
        for(int i = 1;i <= n;i++){
            a[i] = jin();
        }
        for(int i = 1;i <= n;i++){
            b[i] = a[i] - a[i-1];
            // insert(i,i,a[i]);
        }
        while(m-- != 0){
            int l = jin();
            int r = jin();
            int c = jin();
            insert(l,r,c);
        }
        for(int i = 1;i <= n;i++){
            a[i] = a[i-1] + b[i];
        }
        for(int i = 1;i <= n;i++){
            System.out.print(a[i] + " ");
        }

    }
    public static void insert(int l,int r,int c){
        b[l] += c;
        b[r+1] -= c; 
    }
    public static int jin(){
        int temp = read.nextInt();
        return temp;
    }
}


活动打卡代码 AcWing 796. 子矩阵的和

白小白
7个月前
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner read = new Scanner(System.in);
        int n = read.nextInt();
        int m = read.nextInt();
        int q = read.nextInt();
        int[][] num = new int[1010][1010];
        int[][] sum = new int[1010][1010];
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
                num[i][j] = read.nextInt();
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + num[i][j];
        while(q-- != 0){
            int x1,y1,x2,y2;
            x1 = read.nextInt();
            y1 = read.nextInt();
            x2 = read.nextInt();
            y2 = read.nextInt();
            System.out.println(sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]);
        }
    }
}


活动打卡代码 AcWing 795. 前缀和

白小白
7个月前
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner read = new Scanner(System.in);
        int n = read.nextInt();
        int m = read.nextInt();
        int[] num = new int[100010];
        int[] sum = new int[100010];
        sum[0] = 0;
        for(int i = 1;i <= n;i++){
            num[i] = read.nextInt();
            sum[i] = num[i]+sum[i-1];
        }
        while(m-- != 0){
            int l = read.nextInt();
            int r = read.nextInt();
            System.out.println(sum[r] - sum[l-1]);
        }

    }
}


活动打卡代码 AcWing 790. 数的三次方根

白小白
7个月前
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner read = new Scanner(System.in);
        double n = read.nextDouble();
        double l = -10000,r = 10000;
        while(r-l > 10e-8){
            double mid = (l+r)/2;
            if(mid*mid*mid >= n)r = mid;
            else l = mid;
        }
        System.out.printf("%f",l);
    }
}