Algorithm
LeetCode 51. N-Queens
典型的DFS
- 簡單粗暴的實(shí)現(xiàn)
對(duì)于每一行狠毯，遍歷所有的列
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> results;
vector<int> state(n);
dfs(results, state, 0, n);
return results;
}
private:
void dfs(vector<vector<string>> &results, vector<int> &state, int k, int n) {
if (k == n) { // done
results.emplace_back(n, string(n, '.'));
vector<string> &result = results.back();
for (int j = 0; j != n; ++j) {
result[j][state[j]] = 'Q';
}
}
else {
for (int j = 0; j != n; ++j) {
state[k] = j;
if (check(state, k)) {
dfs(results, state, k + 1, n);
}
}
}
}
bool check(const vector<int> &state, int k) {
for (int i = 0; i != k; ++i) {
if (state[i] == state[k]) return false;
if (abs(state[i] - state[k]) == k - i) return false;
}
return true;
}
};
n取15時(shí)耗時(shí)30.412s
Top Hotspots
Function CPU Time
Solution::check 21.540s
Solution::dfs 7.256s
- 既然hotspot是check护糖，改成在每行的遍歷之前先算好可以選擇的列，從而消除check的調(diào)用
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> results;
vector<int> state(n);
vector<vector<char>> choices(n);
dfs(results, state, choices, 0, n);
return results;
}
private:
void dfs(vector<vector<string>> &results, vector<int> &state, vector<vector<char>> &choices, int k, int n) {
if (k == n) { // done
results.emplace_back(n, string(n, '.'));
vector<string> &result = results.back();
for (int j = 0; j != n; ++j) {
result[j][state[j]] = 'Q';
}
}
else {
auto &choice = choices[k];
choice.assign(n, true);
for (int i = 0; i != k; i++)
{
choice[state[i]] = false;
if (state[i] + k - i < n) choice[state[i] + k - i] = false;
if (state[i] + i - k >= 0) choice[state[i] + i - k] = false;
}
for (int j = 0; j != n; ++j) {
if (choice[j]) {
state[k] = j;
dfs(results, state, choices, k + 1, n);
}
}
}
}
};
耗時(shí) 15.779s 縮短了大約一半嚼松。
這里有個(gè)細(xì)節(jié)嫡良，用了vector<char>來表示bool數(shù)組锰扶，如果用vector<bool>的話耗時(shí)是25.116s。
Top Hotspots
Function CPU Time
Solution::dfs 11.660s
std::vector<char, std::allocator<char> >::_Insert_n 2.339s
- 既然在處理每一行的時(shí)候寝受，要根據(jù)之前各行的信息來計(jì)算可選的列坷牛，那是否可以在之前各行處理的時(shí)候就先算好之后各行可選的列呢
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> results;
vector<int> state(n);
vector<vector<int>> attacks(n, vector<int>(n, 0));
dfs(results, state, attacks, 0, n);
return results;
}
private:
void dfs(vector<vector<string>> &results, vector<int> &state, vector<vector<int>> &attacks, int k, int n) {
if (k == n) { // done
results.emplace_back(n, string(n, '.'));
vector<string> &result = results.back();
for (int j = 0; j != n; ++j) {
result[j][state[j]] = 'Q';
}
}
else {
for (int j = 0; j != n; ++j) {
if (attacks[k][j] == 0) {
state[k] = j;
for (int i = k + 1; i != n; i++)
{
++attacks[i][j];
if (j + i - k < n) ++attacks[i][j + i - k];
if (j + k - i >= 0) ++attacks[i][j + k - i];
}
dfs(results, state, attacks, k + 1, n);
for (int i = k + 1; i != n; i++)
{
--attacks[i][j];
if (j + i - k < n) --attacks[i][j + i - k];
if (j + k - i >= 0) --attacks[i][j + k - i];
}
}
}
}
}
};
耗時(shí) 10.974s 進(jìn)一步縮短。
Review
- 大函數(shù)分解的好處
- 雖然會(huì)產(chǎn)生一些只有一個(gè)調(diào)用者的函數(shù)很澄，但代碼復(fù)用并不是重要的因素
- 可以賦一個(gè)有意義的函數(shù)名
- 減小變量的作用域
- 減少縮進(jìn)
- 可測試性
- 策略
- 閉包可以直接變成具名函數(shù)
- 循環(huán)可以提取出來京闰，尤其是C++的break不支持多層跳出
- 函數(shù)中用空格分成多塊，每塊做一件事的甩苛，通初彘梗可以提取
- 一連串對(duì)同一個(gè)對(duì)象的操作可以提取
- 復(fù)雜的if條件
Tip
https://docs.python.org/3/reference/datamodel.html#object.__new__
- __new__用于構(gòu)造新對(duì)象，返回值為一個(gè)對(duì)象實(shí)例讯蒲。
- 也可以返回已有對(duì)象痊土，用于實(shí)現(xiàn)singleton、flyweight等模式
- __init__用戶初始化對(duì)象墨林，設(shè)置對(duì)象的字段
- __new__返回的不是本類實(shí)例時(shí)赁酝，__init__不會(huì)被調(diào)用
Share
The Most Important Software Innovations
文章列舉了最重要的軟件創(chuàng)新。
（居然沒寫λ演算萌丈。。雷则。）
