lilong dream


  • Home

  • Archives

  • Miscs

  • About

N Queens

Posted on 2017-05-06 | In dfs

Eight queens puzzle

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
#include <string>
using std::vector;
using std::string;
vector<bool> col;
vector<bool> diag;
vector<bool> antidiag;
void dfs(int i, int n, vector<vector<string> > &res, vector<string> &board) {
if (i == n) {
res.push_back(board);
return;
}
for (int j = 0; j < n; j++) {
if (!(col[j] && diag[i - j + n - 1] && antidiag[i + j])) {
continue;
}
board[i][j] = 'Q'; // Q stands for queen
col[j] = diag[i - j + n - 1] = antidiag[i + j] = false;
dfs(i + 1, n, res, board);
board[i][j] = '.';
col[j] = diag[i - j + n - 1] = antidiag[i + j] = true;
}
}
vector<vector<string> > solveNQueens(int n) {
vector<vector<string> > res;
col = vector<bool>(n, true);
diag = vector<bool>(2 * n - 1, true);
antidiag = vector<bool>(2 * n - 1, true);
vector<string> board(n, string(n, '.'));
dfs(0, n, res, board);
return res;
}
int main() {
int n;
std::cout << "Pls input n: " << std::endl;
std::cin >> n;
vector<vector<string> > res = solveNQueens(n);
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res[0].size(); j++) {
std::cout << res[i][j] << std::endl;
}
std::cout << "==========" << std::endl;
}
return 0;
}

LRU Cache

Posted on 2017-05-06 | In design

LRU Cache

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <list>
#include <unordered_map>
using std::list;
using std::unordered_map;
struct CacheItem {
int key;
int value;
CacheItem(int k, int val) : key(k), value(val) { }
};
class LRUCache {
public:
LRUCache(int capacity) : m_capacity(capacity) {
}
int get(int key) {
if (m_map.find(key) != m_map.end()) {
moveToHead(key);
return m_map[key]->value;
}
return -1;
}
void set(int key, int value) {
if (m_map.find(key) != m_map.end()) {
m_map[key]->value = value;
moveToHead(key);
} else {
if (m_cache.size() == m_capacity) {
m_map.erase(m_cache.back().key);
m_cache.pop_back();
}
CacheItem CacheItem(key, value);
m_cache.push_front(CacheItem);
m_map[key] = m_cache.begin();
}
}
private:
void moveToHead(int key) {
CacheItem updateCacheItem = *m_map[key];
m_cache.erase(m_map[key]);
m_cache.push_front(updateCacheItem);
m_map[key] = m_cache.begin();
}
int m_capacity;
list<CacheItem> m_cache;
unordered_map<int, list<CacheItem>::iterator> m_map;
};
int main() {
LRUCache cache(2);
cache.set(1, 11);
cache.set(2, 22);
std::cout << cache.get(1) << std::endl;
cache.set(3, 33);
std::cout << cache.get(2) << std::endl;
cache.set(4, 44);
std::cout << cache.get(1) << std::endl;
std::cout << cache.get(3) << std::endl;
std::cout << cache.get(4) << std::endl;
return 0;
}

backPack problems

Posted on 2017-05-05 | In dp

backPack

http://www.lintcode.com/zh-cn/problem/backpack/

method 1

1
2
3
4
5
6
7
8
9
10
11
12
13
int backPack(int m, vector<int> A) {
vector<int> f(m + 1, 0);
for (int i = 0; i < A.size(); i++) {
for (int j = m; j >= 0; j--) {
if (j >= A[i]) {
f[j] = max(f[j], f[j - A[i]] + A[i]);
}
}
}
return f[m];
}

method 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int backPack(int m, vector<int> A) {
vector<bool> f(m + 1, false);
f[0] = true;
for (int i = 0; i < A.size(); i++) {
for (int j = m; j >= 0; j--) {
if (j >= A[i]) {
f[j] = f[j] || f[j - A[i]];
}
}
}
for (int j = m; j >= 0; j--) {
if (f[j]) {
return j;
}
}
return 0;
}

backPackII

http://www.lintcode.com/zh-cn/problem/backpack-ii/

cpp code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int backPackII(int m, vector<int> A, vector<int> V) {
// f[i][j] = max(f[i - 1][j], f[i - 1][j - A[i] ] + V[i])
vector<int> f(m + 1, 0);
for (int i = 0; i < A.size(); i++) {
for (int j = m; j >= 0; j--) {
if (j >= A[i] && (f[j] < f[j - A[i]] + V[i])) {
f[j] = f[j - A[i]] + V[i];
}
}
}
return f[m];
}
lilong

lilong

3 posts
3 categories
1 tags
© 2017 lilong
Powered by Hexo
Theme - NexT.Mist