Elements of Programming Interviews 白班编程记录，求挑刺求反馈

大木虫

LC 73. Set Matrix Zeroes
我这道题用的是bit mask，但是bit mask的问题是会出现overflow。
看了LC答案，答案的思路是把O(M+N)的方法变成in-place，之所以可以这样做是因为这样正好巧妙地绕过了cell-influence-other-cell的题目trick。不错。
take away：比较累的时候会出现比较多的差错，这点还需要训练，以及要放慢速度，耐心写题。

class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
      for(int i = 0; i < matrix.size(); ++i){
         for(int j = 0; j < matrix[0].size(); ++j){
            if(matrix[i][j] > 0){
                  matrix[i][j] *= 2;
                  matrix[i][j] += 1;
            }
         }
      }

      for(int i = 0; i < matrix.size(); ++i){
         for(int j = 0; j < matrix[0].size(); ++j){
            if(matrix[i][j] == 0){
                  SetRowTwo(&matrix, i);
                  break;
            }
         }
      }

      for(int j = 0; j < matrix[0].size(); ++j){
         for(int i = 0; i < matrix.size(); ++i){
            if(matrix[i][j] == 0){
                  SetColTwo(&matrix, j);
                  break;
            }
         }
      }

      for(int i = 0; i < matrix.size(); ++i){
         for(int j = 0; j < matrix[0].size(); ++j){
            if(matrix[i][j] == 2)matrix[i][j] = 0;
            else matrix[i][j] = (matrix[i][j]-1)/2;
         }
      }
}

void SetRowTwo(vector<vector<int> > * matrix, int i){
      for(int j = 0; j < (*matrix)[i].size(); ++j){
        if((*matrix)[i][j] == 0)continue;
         (*matrix)[i][j] = 2;
      }
}

void SetColTwo(vector<vector<int> > * matrix, int j){
      for(int i = 0; i < matrix->size(); ++i){
        if((*matrix)[i][j] == 0)continue;
         (*matrix)[i][j] = 2;
      }
}
};

补充内容 (2018-11-1 03:34):
【i】又被网页省掉了。。。
这里的matrix[j] 其实都是matrix【i】【j】

大木虫

LC 64. Minimum Path Sum
这道题没有上白板，直接在OJ写的，典型DP，7分钟bug free完成

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
      /* 0. MISC */
      if(grid.size() == 0 || grid[0].size() == 0)return 0;

      /* 1. prep */
      vector<int> costRow;

      int cost = 0;
      for(int num : grid[0]){
         cost += num;
         costRow.emplace_back(cost);
      }

      /* 2. key algo */
      for(int i = 1; i < grid.size(); ++i){
         vector<int> newRow = {grid[i][0] + costRow[0]};
         for(int j = 1; j < grid[0].size(); ++j){
            newRow.emplace_back(min(costRow[j], newRow[j-1]) + grid[i][j]);
         }
         costRow = move(newRow);
      }

      /* 3. answer */
      return costRow.back();
}
};

补充内容 (2018-11-1 03:48):
take away：写的速度控制在想的速度之下，稍微慢一点，让思考领着手写，下手前，思路先过一遍可能的坑以及未来几步，这样写出的代码错误少。这点tips可以用于比较累的情况和general情况。

爱丽丝和鲍勃

lz 你可以在高级模式里面找到这个图标 “ <> ”

然后贴代码

// comment

复制代码

大木虫

爱丽丝和鲍勃发表于 2018-11-1 03:51
lz 你可以在高级模式里面找到这个图标 “ ”

然后贴代码

我知道有那个选项，可是那样没法高亮错误行

大木虫

LC 272. Closest Binary Search Tree Value II
旧题重新练习，50分钟，白板110行代码，难度还是比较大的。

take away: pointer syntax consistency是个很容易出问题的地方，解决办法是全部写完之后统一检查。
take away：continue不能在loop外使用
改使用代码显示，唯一问题是没法高亮出错的地方，所以使用comment标注出错的地方。

/**
* 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:
vector<int> closestKValues(TreeNode* root, double target, int k) {
/* 0. MISC */
if(k < 1)return {};
/* 1. prep */
stack<TreeNode*> path;
vector<int> answer;
/* 2. key algo */
/* find closest */
FindClosest(root, target, &path);
stack<TreeNode*> prevPath(path), nextPath(path);
answer.emplace_back(path.top()->val);
/* get k - 1 additional closest nodes */
Next(&nextPath); Prev(&prevPath);
while(--k > 0){
if(nextPath.empty()){
answer.emplace_back(prevPath.top()->val);
Prev(&prevPath);
}else if(prevPath.empty()){
answer.emplace_back(nextPath.top()->val);
Next(&nextPath);
}else{
int nextVal = nextPath.top()->val;
int prevVal = prevPath.top()->val;
if(nextVal-target < target - prevVal){
answer.emplace_back(nextVal);
Next(&nextPath);
}else{
answer.emplace_back(prevVal);
Prev(&prevPath);
}
}
}
/* 3. answer */
return answer;
}
void Next(stack<TreeNode*> * path){
TreeNode* current = path->top();
if(current->right){
current = current->right;
path->emplace(current);
while(current->left){
current = current->left;
path->emplace(current);
}
}else{
path->pop();
while(!path->empty() && path->top()->right == current){
current = path->top();
path->pop();
}
}
}
void Prev(stack<TreeNode*> * path){
TreeNode* current = path->top();
if(current->left){
current = current->left;
path->emplace(current);
while(current->right){
current = current->right;
path->emplace(current);
}
}else{
path->pop();
while(!path->empty() && path->top()->left == current){
current = path->top();
path->pop();
}
}
}
void FindClosest(TreeNode * root, double target, stack<TreeNode*> * path){
/* 0. MISC */
if(!root)return;
/* 1. prep */
while(!path->empty())path->pop();
TreeNode* current = root;
/* 2. key algo */
while(current){
path->emplace(current);
if(current->val > target){
current = current->left;
}else if(current->val < target){
current = current->right;
}else current = NULL;
}
int val = path->top()->val;
stack<TreeNode*> copyPath(*path);
if(val > target){
Prev(&copyPath);
/* problem line here */
if(!copyPath.empty() && target - copyPath.top()->val < val - target){
*path = move(copyPath);
}
}else if(val < target){
Next(&copyPath);
/* problem line here */
if(!copyPath.empty() && copyPath.top()->val - target < target - val){
*path = move(copyPath);
}
}
}
};

复制代码

大木虫

LC 124. Binary Tree Maximum Path Sum
take away: 看清题目要求（a valid path should contain at least one node）
take away: 对于recursion，代码通常比较短，但是逻辑稍微复杂，所以要先想清楚，在写，不要担心写得慢，因为想清楚的recursion正确代码不需要多少时间就可以写完。

/**
* 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 maxPathSum(TreeNode* root) {
/* 0. MISC */
if(!root) return 0;
/* 1. prep */
int answer = 0, maxNode = INT_MIN;
/* 2. key algo */
MaxPathSumRec(root, &answer, &maxNode);
/* 3. answer */
if(maxNode < 0){
return maxNode;
}else return answer;
}
int MaxPathSumRec(TreeNode* node, int* curMax, int* maxNode){
/* base case */
if(!node)return 0;
/* pre-order */
*maxNode = max(*maxNode, node->val);
/* recursion */
int leftVal = MaxPathSumRec(node->left, curMax, maxNode);
int rightVal = MaxPathSumRec(node->right, curMax, maxNode);
/* post-order */
*curMax = max(*curMax, node->val + leftVal + rightVal);
return max(max(node->val, 0), node->val + max(leftVal, rightVal));
}
};

复制代码

大木虫

LC 636. Exclusive Time of Functions
新题，37分钟写码 + 8分钟example

take away: struct init need forward declaraction
take away: 写之前把问题彻底搞清楚，这样避免进入误区浪费思考时间
take away: 写每一步前彻底想清楚，然后一遍写对
take away: 看这到题是在模拟什么情景，然后用该情景的惯常做法解决，举例，本题模仿的情景是function call stack，那我们就用stack解决它
take away: 像这种simulation题目用画图来解释例子特别的直观方便。

class Solution {
public:
struct Log{
int id, stamp;
string op;
Log(string op_, int stamp_, int id_):
op(op_), stamp(stamp_), id(id_){}
};
vector<int> exclusiveTime(int n, const vector<string>& logs) {
/* 0. MISC */
/* 1. prep */
stack<int> callStack;
int prevStamp = 0;
string prevOp;
vector<int> answer(n, 0);
/* 2. key algo */
for(string logStr : logs){
Log log = ParseLog(logStr);
int id = log.id, stamp = log.stamp;
string op = log.op;
if(op == "start"){
if(!callStack.empty()){
answer[callStack.top()] += stamp - prevStamp;
if(prevOp == "end")answer[callStack.top()]--;
}
callStack.emplace(id);
}else{
answer[id] += stamp - prevStamp;
if(prevOp == "start")answer[id]++;
callStack.pop();
}
prevStamp = stamp;
prevOp = op;
}
/* 3. answer */
return answer;
}
Log ParseLog(const string & s){
int firstSep = s.find(":");
int secondSep = s.find(":", firstSep + 1);
string idStr = s.substr(0, firstSep);
string op = s.substr(firstSep + 1, secondSep - firstSep - 1);
string stampStr = s.substr(secondSep + 1, s.size() - secondSep);
return Log(op, stoi(stampStr), stoi(idStr));
}
};

复制代码

补充内容 (2018-11-2 03:14):
这是白板代码，直接原文从白板上打下来的，有三个syntax typo，修改后AC

大木虫

大木虫发表于 2018-11-2 03:12
LC 636. Exclusive Time of Functions
新题，37分钟写码 + 8分钟example

take away: 如果让自定义API，那么怎么舒服方便怎么来，比如说这里的（struct Log）

大木虫

LC 23. Merge k Sorted Lists
take away: 自定义Comparator (functor)的时候要弄清楚正反(greater对应minHeap)

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
struct Compare{
bool operator()(ListNode * l1, ListNode * l2){
if(!l1 || !l2)return false;
return l1->val > l2->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
/* 0. MISC */
if(lists.empty())return NULL;
/* 1. prep */
priority_queue<ListNode*, vector<ListNode*>, Compare> listHeap;
for(auto node : lists){
if(node)listHeap.emplace(node);
}
ListNode* dummyHead = new ListNode(0);
ListNode* current = dummyHead;
/* 2. key algo */
while(!listHeap.empty()){
ListNode* node = listHeap.top();
listHeap.pop();
current->next = node;
current = node;
if(node->next){
listHeap.emplace(node->next);
}
}
ListNode* head = dummyHead->next;
delete dummyHead;
/* 3. answer */
return head;
}
};

复制代码

补充内容 (2018-11-2 04:12):
用时15分钟（毕竟典型题目）

大木虫

LC 301. Remove Invalid Parentheses
这是一道综合题，我第一遍写的时候写了230行
如今上白板，在假设API的前提下实现了主体，43分钟完成，时间还是相对较长的。

take away: 题目细节复杂的时候先自定义几个方便的API，然后先实现主体思路，可以大大提升白板写码的效率

白板代码如下：（右边是几个自定义API）：

Elements of Programming Interviews 白班编程记录，求挑刺求反馈

浏览过的版块