2018-12-26 07:01

### 算法1

blablabla

#### C++ 代码

/**
* // This is the Master's API interface.
* // You should not implement it, or speculate about its implementation
* class Master {
*   public:
*     int guess(string word);
* };
*/
class Solution {
public:
void findSecretWord(vector<string>& wordlist, Master& master) {
int match = 0;
for (int i = 0; i < 10, match < 6; i++) {
int guess_id = rand() % wordlist.size();
match = master.guess(wordlist[guess_id]);
reduceWordList(wordlist, match, wordlist[guess_id]);

}
}
void reduceWordList(vector<string>& wordlist, int match, string cur) {
vector<string> newWordList;
for (int i = 0; i < wordlist.size(); i++) {
if (isMatch(wordlist[i], cur, match)) {
newWordList.push_back(wordlist[i]);
}
}
wordlist = newWordList;
}

bool isMatch(string a, string b, int match) {
int cnt = 0;
if (a.size() != b.size()) {
return false;
}
for (int i = 0; i < a.size(); i++) {
if (a[i] == b[i]) {
cnt++;
}
}
return cnt == match;
}
};



2018-12-02 19:46
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
// a friend remind of me that I can just do inorder traversal, I don't need to remove the nodes recursively
TreeNode* cur = root;
stack<TreeNode*> ss;
while (cur) {
ss.push(cur);
cur = cur->left;
}

while(!ss.empty()) {
// extract the first node from the stack
TreeNode* cur = ss.top();
ss.pop();
if (k == 1) {
return cur->val;
} else {
k--;
if (cur->right) {
cur = cur->right;
while (cur) {
ss.push(cur);
cur = cur->left;
}
}
}
}
}
};

// time complexity: o(k)
// space complexity: o(n);


2018-12-02 18:43
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
int projectionArea(vector<vector<int>>& grid) {
int topArea = 0, frontArea = 0, sideArea = 0;
// for frontArea, just find the biggest value in each column,
// for sideArea, just find the biggest value in each row;
for (int i = 0; i < grid.size(); i++) {
int max_row_val = INT_MIN;
int max_col_val = INT_MIN;
for (int j = 0; j < grid.size(); j++) {
if (grid[i][j] > 0) {
topArea++;
}
max_row_val = max(max_row_val, grid[i][j]);
max_col_val = max(max_col_val, grid[j][i]);

}
sideArea += max_row_val;
frontArea += max_col_val;
}
return sideArea + frontArea + topArea;
}
};


2018-12-01 19:37
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
bool isPowerOfThree(int n) {
// use recursion
// because the question remaind of me that I need to use recursion
// how to solve the case when n == 1 ?
//  我觉得这个题目一开始就不应该提醒我嘛，搞得我想不出自己的方法
// 求观世音菩萨加持
// special cases: 0 and 1;
// ordinary cases: n % 3 == 0;
// forgot about the corner case again
if (n == 0) return false;
while (n == 1 || n % 3 == 0) {
if (n == 1) {
return true;
} else {
n /= 3;
}
}
return false;

}
};


2018-12-01 18:39
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
//  这里为什么返回的是一个vector 呢，不是应该是一个整数么？
// because I hope to process the number from the lower digit,
// so I would like to reverse the array first
reverse(digits.begin(), digits.end());
int n = digits.size();
// the key thing here is when we increment the last digit by 1,
// that might lead to the next higher digit also increment by 1
int increment = 1;
for (int i = 0; i < n; i++) {
digits[i] += increment;
if (digits[i] > 9) {
digits[i] = 0;
increment = 1;
} else {
increment = 0;
break;
}
}
//  I forgot about the corner case here,
// when the case that after traversed all the digits, the increment still remains 1, then
// I need to put one more 1 in the highest digit position.
if (increment) {
digits.push_back(1);
}
reverse(digits.begin(), digits.end());
return digits;
}
};


2018-11-30 06:35

### 算法

#### C++ 代码

class Solution {
public:
int minTransfers(vector<vector<int>>& transactions) {
// 原来一个二维矩阵就可以了啊，我还用hashmap 搞得这么复杂
// DFS
// 这个题目一上来不知道怎么做啊
// 先把transaction 变成 account balance
// 然后dfs 每次drop 掉一个 account
// 每次drop 掉一个account， 这是说最多drop n-1 么， n 是一开始的账户数目
// why the answer ranked top 1 sets the res to INT_MAX?
// don't know why
// what is prev
// 我感觉我好像有点看懂这个题目了
// 每一次都找一个与当前account balance whose sign is different from the current account
// and then drop out the current account by add the current account's balance to the one that found to have
// different sign balance from the current account
// in this way, we can erase one account balance each time, in other words, make at least one account's balance equal to 0
// by doing this step by step, we can make all the accounts' balance equal to 0, if all the accounts' balance equal to 0
// which means the debts have been settled.
// during that process, each time, when we erase one account, we add 1 to the current count of the transactions that have been processed
// after all the debts have been settled, we have a transaction counter value, but that's just one way to settle all the transactions, we need to try out all the possible ways to settle the transaction, and keep track of the minimum value of the transaction counter needed to settle all the debts.
// which means we need to try out all possible ways, and each time when we finish all the transactions, in other words, make all accounts' balance equal to 0, we then need to backtrack, to try other choices.
// 好了， 我要开始写code 了
// start 是为了去重用的
// 首先 traverse 所有transactions, 把transactions 转化成 account balance
// transactions: n X 3 matrix
int max_transac = transactions.size();
unordered_map<int, int> ac2bal;
for (int i = 0; i < transactions.size(); i++) {
vector<int> cur_transaction = transactions[i];
ac2bal[cur_transaction[0]] -= cur_transaction[2];
ac2bal[cur_transaction[1]] += cur_transaction[2];
}
// 因为unordered_map 不太好traverse, 所以把这个map  转化成 vector
// 题目当中还特意提醒说index 没有关系，所以 index  是什么不重要，只要这是一个unique 的index, 可以代表这个账户就好，因此vector 的index
// 就可以代表这个账户了，或者说代表这个人了，所以其实这个人一开始的编号并不需要存下来
vector<int> account_balance;
for (auto pair : ac2bal) {
if (pair.second) {
account_balance.push_back(pair.second);
}
}
// 然后我们就需要调用dfs helper function 去把这一堆不为0 的账户一个一个清掉了
return dfs(account_balance, 0);
}
private:
//  这里来写我们的helper function
int dfs(vector<int>& account_balance, int start) {
int n = account_balance.size();
// start 就是我们当前要消除的账户， 这个账户的balance 不能为0，因为如果已经为0了还消除个啥，不用消除，直接跳过
while (start < n && account_balance[start] == 0) {
start++;
}
// 我们总是从第一个账户开始消除
// 然后我们从第一个账户的下一个账户开始找起
if (start == n) return 0;
int res = INT_MAX;

for (int i = start+1; i < n; i++) {
// 如果他们刚好账户balance 正负相反，就可以消除了
//  之所以不找正正的balance来消除，是因为明显这样消除，transaction 会越变越多的
if ( account_balance[i] * account_balance[start] < 0) {
// 满足条件了，我们来消除吧 ( 相加才是消除朋友们，debug了好久发现了这个问题)
account_balance[i] += account_balance[start];
// start 前面包括start 都是已经消除过的
res = min(res, 1 + dfs(account_balance, start+1));
account_balance[i] -= account_balance[start];
}
}
return res;
}
};


2018-11-29 07:30

### 算法

#### C++ 代码

class Solution {
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
// 感觉就是dfs 的题目，好久没有做dfs了啊
// 感觉就是找一条从起点到终点的路啊
// 一条路一直走下去，如果走不下去的时候，就回头，回到上一次做选择的地方，再走其他的路。
// 感觉就是这样做，这道题目
// 怎么写呢，这道题目
// 这个unordered_map 不行，怎么办呢？ 用什么可以替换呢？
// 好困啊，求观世音菩萨加持，让我把这个题目想出来
unordered_map<string, double> map;
unordered_map<string, vector<string>> start2end;
// avoid loop

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

string start = equations[i].first;
string end = equations[i].second;

map[start + end] = values[i];
map[end + start] = 1.0/values[i];

start2end[start].push_back(end);
start2end[end].push_back(start);
}
// define a return vector to store the result
vector<double> res;
// map 存好了以后就可以进行dfs
for (int i = 0; i < queries.size(); i++) {
unordered_set<string> visited;
pair<string, string> curQuery = queries[i];
// 怎么进行dfs 呢？
// 首先需要 我们要找的路劲的起点和终点， 那我只需要定义一个起点和一个终点就好了啊
string start = curQuery.first;
string end = curQuery.second;
// 知道起点和终点以后，我们就可以在我们存好的　hashmap 里面进行dfs了
// 我觉得这道题目真的很好
// 一开始把query 的结果定义为没有，直到找到以后再重新赋值
double value = 1;
value = dfs(start, end, map, start2end, value, visited);
res.push_back(value);
}
return res;
// unordered_map 里面应该怎么写， 当 a 走到 b 之后， b 不能再走回 a 了。
// 要怎么才可以消环呢？

}
private:
double dfs(string start, string end, unordered_map<string, double>& map, unordered_map<string, vector<string>>& start2end, double value, unordered_set<string>& visited)  {
// the key here should be start, should not be the pair of the start and the end
// in that way, we can query the hashmap if the start point exist in this map
// however, how can I store both end point string and the double value into a single mapped value?
//   观世音菩萨加持
// 对啊，一个hashmap 存不下的时候就用两个hashmap 嘛
//  在unordered_map里面走过一个就要erase 一个

if (!start2end.count(start)) {
return -1.0;
} else {
if (start == end) {
return value;
}
// 不行我一定要自己写出来，不要看答案
// 观世音菩萨加持 感觉这里应该是multimap, 而不是 unordered_map,
vector<string> nexts = start2end[start];
visited.insert(start);
for (int i = 0; i < nexts.size(); i++) {
string next = nexts[i];
if (visited.count(next)) {
continue;
}
// 观世音菩萨加持
//pair<string, string> cur = make_pair(start, next);

double tmp = dfs(next, end, map, start2end, value*map[start+next], visited);
if (tmp > -1.0) {
return tmp;
}
visited.erase(start);
}
return -1.0;
// 求观世音菩萨加持，让我把最后一个bug de 出来

}

}
};


2018-11-26 00:02
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
// Forward declaration of isBadVersion API.

class Solution {
public:
int l = 1, r = n;
while (l < r) {
int mid = l + (r - l)/2;
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};


2018-11-25 06:18
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// 直接写感觉好绕
// 不要从前往后merge, 从后往前merge
int pos1 = m - 1, pos2 = n - 1, pos = m + n - 1;
while (pos1 >= 0 && pos2 >= 0) {
if (nums1[pos1] >= nums2[pos2]) {
nums1[pos--] = nums1[pos1--];
} else {
nums1[pos--] = nums2[pos2--];
}
}
while (pos2 >= 0) {
nums1[pos--] = nums2[pos2--];
}
}
};


2018-11-25 06:04
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// 直接写感觉好绕
// 不要从前往后merge, 从后往前merge
int pos1 = m - 1, pos2 = n - 1, pos = m + n - 1;
while (pos1 >= 0 && pos2 >= 0) {
if (nums1[pos1] >= nums2[pos2]) {
nums1[pos--] = nums1[pos1--];
} else {
nums1[pos--] = nums2[pos2--];
}
}
while (pos2 >= 0) {
nums1[pos--] = nums2[pos2--];
}
}
};