liuchuo – 第236页 – 我不管，反正我最萌～

LeetCode 349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1;
        set<int> s2;
        for(int i = 0; i < nums1.size(); i++) {
            s1.insert(nums1[i]);
        }
        for(int i = 0; i < nums2.size(); i++) {
            if(s1.find(nums2[i]) != s1.end()) {
                s2.insert(nums2[i]);
            }
        }
        vector<int> v;
        for(set<int>::iterator it = s2.begin(); it != s2.end(); it++) {
            v.push_back(*it);
        }
        return v;
    }
};

class Solution {

public:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

set<int> s1;

set<int> s2;

for(int i = 0; i < nums1.size(); i++) {

s1.insert(nums1[i]);

}

for(int i = 0; i < nums2.size(); i++) {

if(s1.find(nums2[i]) != s1.end()) {

s2.insert(nums2[i]);

}

vector<int> v;

for(set<int>::iterator it = s2.begin(); it != s2.end(); it++) {

v.push_back(*it);

}

return v;

}

};

蓝桥杯 ADV-206 算法提高不大的数

问题描述
在当今的大数据时代，超大数的高精度计算已经成为众多领域的热门研究之一。现在T校也想在此领域有所造诣已造福于全社会，然而由于时间有限，所以短时间内难以找出大数计算的通用算法，于是学校找到了同学中的“神霸”——你来帮忙，并仅要求你能在数并不算大的时候给出结果。又出于某种特殊需要，也并不要求你给出数的全部结果，而只是要求结果的前10位（注意不是后10位），并考虑到2的幂次的特殊性和典型性，所以要你计算的数均为2的幂次。
输入格式
一个自然数n。
输出格式
2的n次幂的前10位。
样例1 输入
60
样例1 输出
1152921504
样例2 输入
60000
样例2 输出
6305794870
数据规模和约定
0<=n<=10000000
注释
=。=
分析：本来想用位运算。。后来发现做不出来。。然后换了种方法做，AC了~
1.当乘以2的次数超过或者等于34次的时候，就会超过10位数字。用一个double型变量保存要求的数，然后再最后转为long long int 型。(至于为什么要用double型，因为第二步的除以1000相当于乘以1024，为了避免失去精度使得除法运算后的结果被转为int后不精准~~)为了防止超过10位数字，这个时候可以采取除法的方式让它位数控制在double的不溢出范围之内~~
2.已知2的10次方是1024，也就是说对于每一个是10的倍数i，就相当于给要求的数增加了1024倍，这个时候可以采取除以1000的方式保证它不溢出~
3.但是因为数据规模太大了，有一千万大小，所以每一个1024/1000=1.024，当乘以1.024的个数超过97次方的时候(1.024^97 = 9.979201547674)，就会等于让要求的数乘以了10.为了保证不溢出，可以在乘以了每970个2的时候，让要求的数除以10保证不会溢出~（如果想要更精准的可以用计算器得到：1.024^97.1 = 10.00289683498）就是每乘以971个2后除以10~
4.此时用上述办法得到的数如果在数据规模大的时候可能会有10位或者11位，这时候可以统计一下这个double型数字的位数，然后进行除以10的运算把它变为前面只有10位数。
5.此时转换为long long int型输出即可~

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    double t = 1.0;
    for(int i = 1; i <= n; i++) {
        t = t * 2;
        if(i >= 34 && i % 10 == 0) {
            t = t / 1000;
        }
        if(i % 971 == 0) {
            t = t / 10;
        }
    }
    long long int temp = t;
    int sum = 0;
    while(temp) {
        temp = temp / 10;
        sum++;
    }
    while(sum > 10) {
        t = t / 10;
        sum--;
    }
    long long int d = t;
    printf("%lld", d);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

double t = 1.0;

for(int i = 1; i <= n; i++) {

t = t * 2;

if(i >= 34 && i % 10 == 0) {

t = t / 1000;

}

if(i % 971 == 0) {

t = t / 10;

}

long long int temp = t;

int sum = 0;

while(temp) {

temp = temp / 10;

sum++;

}

while(sum > 10) {

t = t / 10;

sum--;

}

long long int d = t;

printf("%lld", d);

return 0;

}

蓝桥杯 BASIC-27 基础练习 2n皇后问题

问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0

分析：和n皇后问题一样，只不过2n皇后要用两个深度优先搜索。
调用放置白皇后的递归dfs，先放置白皇后，当每一个白皇后放置成功之后，在递归的return语句之前，
新建一个棋盘，复制原来的棋盘后并把放置了白皇后的位置置为0，调用摆放黑皇后的深度优先搜索。
当黑皇后也找到相应的解法后，cnt++; 最后输出cnt的值。

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int cnt = 0;

bool issafe(vector<vector<int> > pic, vector<int> pos, int row) {
    for(int i = 0; i < row; i++) {
        if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))
            return false;
    }
    return true;
}

void blackdfs(vector<vector<int> > blackpic, vector<int> blackpos, int n, int blackrow) {
    if(blackrow == n) {
        cnt++;
        return ;
    }
    for(blackpos[blackrow] = 0; blackpos[blackrow] < n; blackpos[blackrow]++) {
        if(blackpic[blackrow][blackpos[blackrow]] == 1 && issafe(blackpic, blackpos, blackrow)) {
            blackdfs(blackpic, blackpos, n, blackrow + 1);
        }
    }
}


void dfs(vector<vector<int> > pic, vector<int> pos, int n, int row) {
    if(row == n) {
        vector<vector<int> > blackpic(n, vector<int>(n));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                blackpic[i][j] = pic[i][j];
            }
        }
        for(int i = 0; i < n; i++) {
            blackpic[i][pos[i]] = 0;
        }
        vector<int> blackpos(n);
        blackdfs(blackpic, blackpos, n, 0);
        return ;
    }
    for(pos[row] = 0; pos[row] < n; pos[row]++) {
        if(pic[row][pos[row]] == 1 && issafe(pic, pos, row)) {
            dfs(pic, pos, n, row + 1);
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int> > pic(n, vector<int>(n));
    vector<int> pos(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> pic[i][j];
        }
    }
    dfs(pic, pos, n, 0);
    cout << cnt;
    return 0;
}

#include <iostream>

#include <cmath>

#include <vector>

using namespace std;

int cnt = 0;

bool issafe(vector<vector<int> > pic, vector<int> pos, int row) {

for(int i = 0; i < row; i++) {

if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))

return false;

}

return true;

}

void blackdfs(vector<vector<int> > blackpic, vector<int> blackpos, int n, int blackrow) {

if(blackrow == n) {

cnt++;

return ;

}

for(blackpos[blackrow] = 0; blackpos[blackrow] < n; blackpos[blackrow]++) {

if(blackpic[blackrow][blackpos[blackrow]] == 1 && issafe(blackpic, blackpos, blackrow)) {

blackdfs(blackpic, blackpos, n, blackrow + 1);

}

void dfs(vector<vector<int> > pic, vector<int> pos, int n, int row) {

if(row == n) {

vector<vector<int> > blackpic(n, vector<int>(n));

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

blackpic[i][j] = pic[i][j];

}

for(int i = 0; i < n; i++) {

blackpic[i][pos[i]] = 0;

}

vector<int> blackpos(n);

blackdfs(blackpic, blackpos, n, 0);

return ;

}

for(pos[row] = 0; pos[row] < n; pos[row]++) {

if(pic[row][pos[row]] == 1 && issafe(pic, pos, row)) {

dfs(pic, pos, n, row + 1);

}

int main() {

int n;

cin >> n;

vector<vector<int> > pic(n, vector<int>(n));

vector<int> pos(n);

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

cin >> pic[i][j];

}

dfs(pic, pos, n, 0);

cout << cnt;

return 0;

}

蓝桥杯 ADV-203 算法提高 8皇后·改(八皇后问题)

问题描述
规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。
输入格式
一个8*8的棋盘。
输出格式
所能得到的最大数字和
样例输入
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
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
样例输出
260
数据规模和约定
棋盘上的数字范围0~99

#include <iostream>
#include <cmath>
using namespace std;
int maxvalue = 0;
int pic[8][8];

bool issafe(int pos[], int row) {
    for(int i = 0; i < row; i++) {
        if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))
            return false;
    }
    return true;
}
void dfs(int pos[], int row) {
    if(row == 8) {
        int sum = 0;
        for(int i = 0; i < 8; i++) {
            sum += pic[i][pos[i]];
        }
        maxvalue = sum > maxvalue ? sum : maxvalue;
        return ;
    }
    for(pos[row] = 0; pos[row] < 8; pos[row]++) {
        if(issafe(pos, row)) {
            dfs(pos, row + 1);
        }
    }
}

int main() {
    int pos[8];
    for(int i = 0; i < 8; i++) {
        for(int j = 0; j < 8; j++) {
            cin >> pic[i][j];
        }
    }
    dfs(pos, 0);
    cout << maxvalue;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int maxvalue = 0;

int pic[8][8];

bool issafe(int pos[], int row) {

for(int i = 0; i < row; i++) {

if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))

return false;

}

return true;

}

void dfs(int pos[], int row) {

if(row == 8) {

int sum = 0;

for(int i = 0; i < 8; i++) {

sum += pic[i][pos[i]];

}

maxvalue = sum > maxvalue ? sum : maxvalue;

return ;

}

for(pos[row] = 0; pos[row] < 8; pos[row]++) {

if(issafe(pos, row)) {

dfs(pos, row + 1);

}

int main() {

int pos[8];

for(int i = 0; i < 8; i++) {

for(int j = 0; j < 8; j++) {

cin >> pic[i][j];

}

dfs(pos, 0);

cout << maxvalue;

return 0;

}

LeetCode 52. N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

分析：和LeetCode 51. N-Queens一样，只需改动几行代码即可~

class Solution {
    int cnt = 0;
public:
    int totalNQueens(int n) {
        vector<int> pos(n);
        dfs(pos, n, 0);
        return cnt;
    }
private:
    void dfs(vector<int> &pos, int n, int row) {
        if(row == n) {
            cnt++;
            return ;
        }
        for(pos[row] = 0; pos[row] < n; pos[row]++) {
            if(issafe(pos, n, row)) {
                dfs(pos, n, row + 1);
            }
        }
    }
    
    bool issafe(vector<int> &pos, int n, int row) {
        for(int i = 0; i < row; i++)
            if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))
                return false;
        return true;
    }
};

class Solution {

int cnt = 0;

public:

int totalNQueens(int n) {

vector<int> pos(n);

dfs(pos, n, 0);

return cnt;

}

private:

void dfs(vector<int> &pos, int n, int row) {

if(row == n) {

cnt++;

return ;

}

for(pos[row] = 0; pos[row] < n; pos[row]++) {

if(issafe(pos, n, row)) {

dfs(pos, n, row + 1);

}

bool issafe(vector<int> &pos, int n, int row) {

for(int i = 0; i < row; i++)

if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))

return false;

return true;

}

};

LeetCode 51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[“.Q..”, // Solution 1
“…Q”,
“Q…”,
“..Q.”],

[“..Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]

分析：pos[i]存放的是第i行的皇后所在的位置，递归以行的形式递归，每次放置的皇后要判断是否与前面已经放置的皇后冲突。从pos[row] = 0开始一直到n-1，判断是否安全如果安全就进行下一行的摆放，每次递归到row==n的时候表示当前所有n个皇后已经摆放完成，此时将当前完成的结果保存在string类型的temp数组里面，先将数组置为’…..’，后根据pos[i]存放i行皇后的位置的特性将temp数组里面temp[i][pos[i]]置为’Q’。然后将temp压入v数组中，return。这样递归结束就能找到所有的摆放方法。这是一个深度优先的过程，从在第一行放在第一个位置开始，摆放第二行、第三行…直到最后一行。然后pos[row]++,表示将第一行放在第二个位置…然后摆放第二行、第三行…直到最后一行……直到所有的情况深度优先搜索完成～

class Solution {
    vector<vector<string> > v;
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<int> pos(n);
        dfs(pos, n, 0);
        return v;
    }
private:
    void dfs(vector<int> &pos, int n, int row) {
        if(row == n) {
            vector<string> temp(n, string(n, '.'));
            for(int i = 0; i < n; i++) {
                temp[i][pos[i]] = 'Q';
            }
            v.push_back(temp);
            return ;
        }
        for(pos[row] = 0; pos[row] < n; pos[row]++) {
            if(issafe(pos, n, row)) {
                dfs(pos, n, row + 1);
            }
        }
    }
    
    bool issafe(vector<int> &pos, int n, int row) {
        for(int i = 0; i < row; i++)
            if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))
                return false;
        return true;
    }
};

class Solution {

vector<vector<string> > v;

public:

vector<vector<string>> solveNQueens(int n) {

vector<int> pos(n);

dfs(pos, n, 0);

return v;

}

private:

void dfs(vector<int> &pos, int n, int row) {

if(row == n) {

vector<string> temp(n, string(n, '.'));

for(int i = 0; i < n; i++) {

temp[i][pos[i]] = 'Q';

}

v.push_back(temp);

return ;

}

for(pos[row] = 0; pos[row] < n; pos[row]++) {

if(issafe(pos, n, row)) {

dfs(pos, n, row + 1);

}

bool issafe(vector<int> &pos, int n, int row) {

for(int i = 0; i < row; i++)

if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))

return false;

return true;

}

};