八皇后问题

#include<iostream>
using namespace std;

const int N = 30;

int n , m ;
char g[N][N];
bool col[N] , dg[N] , udg[N];

void dfs(int u ){           //表示行;
    if(u == n + 1){ 
        for(int i=1; i<=n; i++){
             for(int j=1; j<=n; j++)
                printf("%c", g[i][j]);
            puts("");
        }
        puts("");
        return ;
    }
    for(int i=1; i<=n; i++){            //列搜索;
        if( !col[i] && !dg[u - i + n] && !udg[ i + u] ){        // u代表 y , i 代表 x . dg 斜线的b = u - i + n; udg 反斜线的 b = u + i; 
            col[i] = dg[u - i + n ] = udg[i + u] = true;
            g[u][i] = 'Q';                    //  u = i + b;  --- > u - i = b ;         -- > u- i + n ;
            dfs(u + 1);
            col[i] =  dg[u - i + n ] = udg[i + u] = false;
            g[u][i] = '.';
        }
    }
}
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            g[i][j] = '.';
    dfs(1);
    return 0;
}

排列数字

import java.util.Scanner;

public class Main {
    static int N = (int) 10e4 + 10;
    static int n ;
    static boolean [] st = new boolean[N];
    static int[] path = new int[N];
    static Scanner s = new Scanner(System.in);
    public static void main(String[] args) {
        n = s.nextInt();
        dfs(1);
    }
    static void dfs(int u){
        if(u == n + 1){
            for (int i = 1; i <=n ; i++) {
                System.out.print(path[i]);
            }
            System.out.println();
        }
        for (int i = 1; i <=n ; i++) {
            if(!st[i]){
                st[i] = true;
                path[u] = i;
                dfs(u + 1);
                st[i] = false;
            }
        }
    }
}

u 代表当前放的是第几个位置

if(!st[i]) 是判断这个数字是否
放过了,放过了就不能放了,如果没有
放过那么就将这个数字放在这个位置
并且标记这个数字 , 递归到下一个位置
因为默认是从1开始, 所以需要在放n + 1个位置的时候返回；
其次就是回溯并且恢复状态标记,记住啊。清空状态很重要！

约数个数

import java.util.HashMap;
import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static int N = (int) 10e4 + 10;
    static int n;
    static HashMap<Integer, Integer> primes = new HashMap<>();
    static int[] a = new int[N];
    static int mod = (int)1e9 + 7;
    static Scanner s = new Scanner(System.in);

    public static void main(String[] args) {
        n = s.nextInt();
        input(n);
        long ans = 1;
        for (Integer key : primes.keySet())
            ans =(ans * (primes.get(key) + 1)) % mod;
        System.out.println(ans );
    }

    public static void input(int n) {
        while (n-- != 0) {
            int x;
            x = s.nextInt();
            getDivisor(x);
        }
    }

    public static void getDivisor(int x) {
        for (int i = 2; i <= x / i; i++)
            while (x % i == 0) {
                x /= i;
               setValue(i);
            }
        if( x > 1) setValue(x);
    }
    public static void setValue(int i ){
        int p = primes.get(i) == null ? 0 : primes.get(i);
        primes.put(i, p + 1);                   //  求出约数i 和 指数 p + 1;
    }
}

这么多方法 其实真正有用的就是一个方法
for (int i = 2; i <= x / i; i++)
while (x % i == 0) {
x /= i;
setValue(i);
}
if( x > 1) setValue(x);
getDivisor 方法 是一个很重要的
其实呢 就是一个分解质因数的过程 , 上一个题搞懂了
这一个题就没难度 , 重要的就是求出约数个数的公式
这个公式是怎么推出来的呢？
我们可以一起来探讨一下:
N = p1^a1 * p2^a2 * p3^a3 * …… * pk ^ ak;
对于任意一个 d = q1^b1 * q2^b2 * …… * qk^ bk;
我们可以知道对于 任意 约数 d来说 它的每个乘积
都是来自 N 的乘积数, 决定不同的约数d因素是 每个乘积的
次数的取法 , 我们可以知道每个质因数都有 a次方 ,对于任意
的一个约数d只需要取到唯一的乘积指数组合即可;
n那么一共有多少种组合呢？
第一个乘积数(质因数)的次数有(a1+1)种取法 从 0 到 a 嘛。
那么 n 个数可以取到 (a1 + 1)*(a2 + 1) ……(an + 1)种取法;
如果实在不理解其实也可以这样想 , 一共有 n 个位置 ,每个位置
只能放一个数 , 且每个位置 只能在 [0 , a) (每个质因数范围不一样)
中取一个,你说一共有多少种取法;
for (Integer key : primes.keySet())
ans =(ans * (primes.get(key) + 1)) % mod;
这就是这段代码的由来.

快速排序

时间复杂度 O(nlogn)

#include<iostream>

using namespace std;

const int N = 1000010;

int n ,m;
int a[N];

void  sort(int l , int r){
    if(l >= r) return ;

    int tem = a[l + r >> 1 ] , i = l -1 , j = r + 1;
    while(i < j ){
        do i++ ; while(tem > a[i]);
        do j-- ; while(tem < a[j]);
        if(i < j){
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    sort(l, j);
    sort(j + 1 , r);
}
int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++)     scanf("%d", a + i);
    sort(1 , n);
    for(int i=1; i<=n; i++) printf("%d ", a[i]);
    return 0;
}

本质就是让基准数归位

保证基准数左区间严格小于等于基准数
基准数右区间严格大于等于基准数
记得要将双指针做成开区间的！！！

约数个数

时间复杂度O(nsqrt(n))

import java.util.Scanner;
import java.util.Arrays;
public class Main {
    static int  N = (int)10e4 + 10;
    static int n ;
    static Scanner s = new Scanner(System.in);
    public static void main(String [] arsg) {
        n = s.nextInt();
        input(n);
    }
    public static void input(int n){
        while(n -- != 0) {
            int x ;
            x = s.nextInt();
            fun(x);
        }
    }
    public static void fun(int n) {
        int [] a = new int [N] ;
        int cnt = 0;
        for(int i= 1; i<= n / i; i++ ) {
            if(n % i == 0) {
                a[++cnt] = i;
                if(i != n / i) a[++cnt] = n /i ;
            }
        }
        Arrays.sort(a , 1, cnt + 1);
        for(int i=1; i<=cnt; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
}

这里最重要的方法是 fun() 方法

 枚举 1 到 sqrt(n) 之间所有的数;
 原理还是利用较小的约数得到较大的约数
 但是需要注意的是 因为约数是成对出现的
 当 i = 根号下n 时 另外一个约数 也是 根号n
 你得到的约数其实是一个 , 所以你需要单判;

线性筛

时间复杂度O(n)

import java.util.Arrays;
import java.util.Scanner;

public  class  Main {
    static int N = (int) 10e7 + 10;
    static int n, cnt ;
    static int[] primes = new int[N];
    static boolean[] st = new boolean[N];

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        n = s.nextInt();
        isPrimes();
        int [] a  = new int[N];
        Arrays.sort(a , 1  , 3);
        System.out.println(cnt);               
    }

    static void isPrimes() {
        for (int i = 2; i <= n; i++) {
            if (!st[i]) primes[++cnt] = i;
            for (int j = 1; primes[j] <= n / i; j++) {          
                st[primes[j] * i] = true;          
                if (i % primes[j] == 0) break;            
            }
        }
    }

}

主要思路 筛出区间所有质数 , 直接查表; 所以是O(n)的时间复杂度;

 *  is_Primes 方法的核心思路就是利用较小的质数作为合数最小质因子筛掉 ,
 * 将不是质数的合数作为下标直接映射到 boolean 数组中 , 所以质数都可以直接查表;
 * 最关键的就是筛质数 , 重在分析循环 for(int i=1; primes[j] * i <= n; i++)
 *判断部分也可以写成       *primes[j] <= n / i ;
 * 其实意思是一样的 , 就是想要筛掉1 - n 直接所有的合数;
 * 这个循环退出有两种可能
 * 1、i % primes[j] != 0 时 那么 primes[j] 是 primes[j] * i 
 * 的最小质因数;
 *      i % primes[j] == 0 是 primes[j] 是 i 的最小质因数 , 
 * 也是 primes[j] * i 的最小质因数;
 * 2、primes[j] <= n / i 这样保证了 primes[j] 
 *只会是属于 0 - n 之间的数; 因为 0 < primes[j] * i && primes[j] * i <= n;
 * 这就是线性筛的基本思路.

以后质数题只用它！

时间复杂度O(n)

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Scanner;

public class Main {
    static int N = 1000010;
    static int n;
    static Scanner s = new Scanner(System.in);

    public static void main(String[] args) {
        n = s.nextInt();
        while (n-- != 0) {
            int t = s.nextInt();
            primesFactor(t);
        }
    }

    static void primesFactor(int t) {
        LinkedHashMap<Integer , Integer> primes = new LinkedHashMap<>();
        for (int i = 2; i <= t / i; i++)
            while (t % i == 0) {
                t /= i;
                set( i , primes);
            }
        if (t > 1)
            set(t , primes);
        for (Integer key : primes.keySet())
            System.out.println(key + " " + primes.get(key));
        System.out.println();
    }
    public static  void set(int i , HashMap<Integer , Integer> primes){
        int p = primes.get(i) == null ? 0  : primes.get(i);
        primes.put(i , p + 1);
    }
}

拿Java写算法一个字难受！

但是有些题还是能拿捏的 , 尽力就好！

说正事 , 我们如何理解这题并求出分解出质因数以及对应次方的;
首先我们需要了解一个数论里面的公式 N = P^a1 * P^a2 * P^a3 ………… * P^an;
这个公式的意思就是 任何一个合数都可以分解成
质数的指数乘积的形式;

由此我们可以知道 找到一个数的质因数只需要找到将这个数进行拆解成以上形式即可;
我们这里都是对合数进行分解质因数 , 质数的质因数就是它自己 和 1;
for (int i = 2; i <= t / i; i++)
while (t % i == 0) {
t /= i;
set( i , primes);
}
这段代码是我们需要好好分析的 , 从 2开始枚举 , 枚举到 sqrt(t);
我们用较小的质因数去除这个数 ,如果能整除那么整除这个数一定是质数!
为什么一定是质数呢？
因为我们枚举 2 的时候 如果能被 2整除 , 2 是质数
然后将这个数不断取模看看能否整除 , 可以就整除;
我们可以发现 , 这个数此时去除了所有能与2 整除的因数
比如 4 肯定跟剩下的这个商肯定不能整除了;
以此类比3 , 5 , 6 , ……到 我们需要拆分这个数之间所有的
能与2 、3 、5整除的数都被整除除掉了, 变成了 质数 和指数
的形式。

所以我们确定 t % i == 0 这个条件成立 t 一定是质数!

为什么我们除的范围 是 2 到 sqrt( t )呢?
首先 1 是所有数的质因数 , 不需要考虑
而且如果从 1 开始 while会死循环
1 和任何数都能整除!
其次为什么不需要除到 t ;
因为我用较小的质因数除剩下的如果大于 sqrt(t)
那么我们就可以做一个单独判断一下加入到集合中即可
为什么需要单独判断大于 1 呢 , 因为 1 作为约数
而且有个细节忘记了 1 不是质数！不是质数! 不是质数！

最后就是学Java的小伙伴 , 记得用LinkedHashMap因为
数组开太大内存会爆 , 开小了 , 无法映射到所有的值;
为什么一定用 LinkedHashMapn呢 因为ArrayList也是数组
会下标越界 , 其次就是 不能用 HashMap 因为不能有序取出
它会hash到相对随机(其实是由规律的)位置,不能按存储顺序
取出 , 所以我们要用LinkedHahsMap
因为它维护hash表 还维护了 双向链表 可以按存储顺序取出
所以 用它！用它 ！用它！

时间复杂度 O(n)

import java.util.Scanner;

public class Main{
    static int N = 100010;
    static int n , top , x;
    static int [] st = new int[N];
    static Scanner s = new Scanner(System.in);
    public static void main(String [] args){
        n = s.nextInt();
        while(n -- != 0){
            x = s.nextInt();
            while(top != 0 && st[top] >= x) top --;
            if(top > 0) System.out.print(st[top] +" ");
            else System.out.print(-1 + " ");
            st[++top] = x;
        }
    }
}

单调栈 , 弹出元素要满足两个条件
1、Ax >= Ay
2、x < y
利用这两个条件 , 保持栈内满足单调递增的性质;
这两条件因为是线性扫描由前向后 , x < y 这个条件自然满足;
只需要看后进来的元素是否是大于等于 栈顶元素即可;

我们来看这样设计线性处理合理性;
如果 第 i 个元素 小于等于栈顶元素 ,
那么后面的元素绝对不会以栈顶元素作为答案,
因为我们知道第 i 个元素是后进来的元素
满足 x < y 的下标性质;
同时又满足 Ax >= Ay 的性质 ,
所以后面的元素要找左边的第一个最小值 , 当前栈顶元素绝对不是答案;

我们再来看 第 i 个元素是否会找到自己答案呢？
因为此时 栈顶元素绝对是大于 元素 i 的所以 ,而且栈顶元素
又不是可能后面元素的答案, 所以直接删除;
往前找 , 一直找到 一个元素 是 小于第 i 个元素的
这时就找到了左边第一个小于 i 的元素;
再让 第 i 个元素入栈;
后面的元素是同样的推理;

写的有点啰嗦 , 但是都是自己的理解;

时间复杂度

O(sqrt(n))  因为最多只要枚举到 sqrt(n) 所以 对于一个晒一个来说只需要sqrt(n);

import java.util.Scanner;

public class Main {
    static int  n , m ;
    static Scanner s = new Scanner(System.in);

    public static void main(String[] args) {
        n = s.nextInt();
        while(n -- != 0){
            m = s.nextInt();
            boolean flag = true;
            for (int i = 2; i <= m /i ; i++) {
                if(m % i == 0 && (flag = false))
                    break;
            }
            if(flag && m != 1) System.out.println("Yes");
            else System.out.println("No");
        }
    }
}

试除法 , 重点在于试除 Y总在为什么只要枚举到

    sqrt(n) 这个值应该已经说明的很清楚了, 唯一
    要注意的一点的就是 1 这个数是不会被循环筛掉
    的 , 所以一定要注意输出的时候单判一下.

时间复杂度

O(n^2) 支持的数据范围大概是 10^4 左右;

C++ 代码

#include<iostream>

using namespace std;

const int N =  10010;

int n , m ,ans;
int dp[N] , v[N] , w[N];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)     scanf("%d%d",&v[i],&w[i]);

    for(int i=1; i<=n; i++)         //  遍历物品 
        for(int j=1; j<=m; j++)     // 遍历容量; 
            if(j >= v[i])   
                dp[j] = max(dp[j-v[i]] + w[i] , dp[j]);
    for(int i=1; i<=m; i++)
        ans = max(dp[i] , ans);
    cout << ans ;
    return  0;
}

主要思路

遍历物品 , 在遍历背包容量 , 你把所有选第i件这个情况下所能选的物品最大值都取到了, 那么整体你所能取到的也一定是最大值 , 因为这种遍历方式将所有物品都挑了一遍,
在所有容量下 , 只挑到的都是最大价值 , 那么也可以解释 为什么最后的结果一定是最大价值;

其实遍历循环是可以交换的 , 因为你的当前最大值都只从左上角和正上方推到而来, 所以你交换遍历循环
也是没有任何问题的。但是背包容量的遍历顺序一定是由前往后遍历.
不然就无法重复的选择物品.