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

大木虫 · 2018-11-30 23:19:25

我的心理素质还是有一些不过关，等公司面试结果期间无心做题，天天老惦记着公司能不能要我，这样不是很好。我要练习move on。

大木虫 · 2018-11-30 23:20:21

Number of Islands
总结了一个近似模板的写法，DFS/BFS图类

class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
/* 0. MISC */
/* 1. prep */
int count = 0;
/* 2. key algo */
for(int i = 0; i < grid.size(); ++i){
for(int j = 0; j < grid[i].size(); ++j){
if(grid[i][j] == '1'){
++count;
BFS(grid, {i, j});
}
}
}
/* 3. answer */
return count;
}
void BFS(vector<vector<char> >& grid, const pair<int, int>& loc){
/* 0. MISC */
/* 1. prep */
queue<pair<int, int> > bfsQueue;
bfsQueue.emplace(loc);
grid[loc.first][loc.second] = 0;
vector<pair<int, int> > directions = {
pair<int, int>(-1, 0),
pair<int, int>(1, 0),
pair<int, int>(0, 1),
pair<int, int>(0, -1)
};
/* 2. key algo */
while(!bfsQueue.empty()){
auto node = bfsQueue.front();
bfsQueue.pop();
for(auto dir: directions){
pair<int, int> child(node.first + dir.first, node.second + dir.second);
if(!InRange(grid, child))continue;
if(grid[child.first][child.second] == '0')continue;
grid[child.first][child.second] = '0';
bfsQueue.emplace(move(child));
}
}
/* 3. answer */
/* no answer to return*/
}
string Encode(const pair<int, int>& loc){
return loc.first + " " + loc.second;
}
bool InRange(const vector<vector<char> >& grid, const pair<int, int>& loc){
return loc.first >= 0 && loc.first < grid.size() &&
loc.second >= 0 && loc.second < grid[loc.first].size();
}
};

复制代码

大木虫

297. Serialize and Deserialize Binary Tree
这次的重点是写了迭代的解法，用stack，写了一个小时左右

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
/* 0. MISC */
if(!root)return "N ";
/* 1. prep */
string answer;
stack<TreeNode*> dfsStack;
dfsStack.emplace(root);
/* 2. key algo */
while(!dfsStack.empty()){
auto node = dfsStack.top();
dfsStack.pop();
if(node){
answer += to_string(node->val) + " ";
}else answer += "N ";
if(node){
dfsStack.emplace(node->right);
dfsStack.emplace(node->left);
}
}
/* 3. answer */
return answer;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
/* 0. MISC */
if(data == "N ")return NULL;
/* 1. prep */
stack<pair<TreeNode*, int>> treeStack;
int index = 0;
TreeNode* answer = NULL;
bool start = true;
/* 2. key algo */
while(index < data.size()){
string valStr = NextVal(data, index);
TreeNode* node;
if(valStr != "N")node = new TreeNode(stoi(valStr));
else node = NULL;
if(start){
answer = node;
start = false;
}
if(!treeStack.empty()){
if(treeStack.top().second == 0){
treeStack.top().second++;
treeStack.top().first->left = node;
}else{
auto parent = treeStack.top();
(parent.first)->right = node;
treeStack.pop();
}
}
if(node)treeStack.emplace(node, 0);
}
/* 3. answer */
return answer;
}
string NextVal(const string& data, int& index){
int tmp = index;
index = data.find(" ", index);
return data.substr(tmp, index++ - tmp);
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

复制代码

大木虫

317. Shortest Distance from All Buildings (hard)
直观的BFS题目，写起来比较冗长，55分钟AC

class Solution {
public:
int shortestDistance(vector<vector<int>>& grid){
/* 0. MISC */
/* 1. prep */
vector<vector<int> > totalDistGrid(grid.size(), vector<int>(grid[0].size(), 0));
vector<vector<int> > reachableBuildings(grid.size(), vector<int>(grid[0].size(), 0));
int numBuilding = CountBuilding(grid);
/* 2. key algo */
for(int i = 0; i < grid.size(); ++i){
for(int j = 0; j < grid[i].size(); ++j){
if(grid[i][j] == 1){
UpdateGridBFS(grid, totalDistGrid, reachableBuildings, {i, j});
}
}
}
/* 3. answer */
return MinQualifiedElement(grid, totalDistGrid, reachableBuildings, numBuilding);
}
void UpdateGridBFS( const vector<vector<int>>& grid,
vector<vector<int> >& totalDistGrid,
vector<vector<int> >& reachableBuildings,
const pair<int, int>& loc){
/* 0. MISC */
/* 1. prep */
vector<vector<int> > distGrid(grid.size(), vector<int>(grid[0].size(), -1));
vector<vector<int> > visited(grid.size(), vector<int>(grid[0].size(), 0));
queue<pair<int, int> > bfsQueue;
bfsQueue.emplace(loc);
visited[loc.first][loc.second] = 1;
distGrid[loc.first][loc.second] = 0;
vector<pair<int, int> > directions =
{
pair<int, int>(-1, 0),
pair<int, int>(1, 0),
pair<int, int>(0, -1),
pair<int, int>(0, 1)
};
/* 2. key algo */
while(!bfsQueue.empty()){
auto node = bfsQueue.front();
bfsQueue.pop();
for(auto dir: directions){
pair<int, int> neighbor(node.first + dir.first, node.second + dir.second);
if(!InRange(grid, neighbor))continue;
if(grid[neighbor.first][neighbor.second] != 0)continue;
if(visited[neighbor.first][neighbor.second] != 0)continue;
visited[neighbor.first][neighbor.second] = 1;
distGrid[neighbor.first][neighbor.second] = distGrid[node.first][node.second] + 1;
bfsQueue.emplace(neighbor);
}
}
/* 3. answer */
MatrixAdd(reachableBuildings, move(visited));
MatrixAdd(totalDistGrid, move(distGrid));
}
void MatrixAdd(vector<vector<int>>& base, const vector<vector<int>>& addition){
if(base.empty() || addition.empty())return;
if(base.size() != addition.size() || base[0].size() != addition[0].size())return;
for(int i = 0; i < base.size(); ++i){
for(int j = 0; j < base[i].size(); ++j){
base[i][j] += addition[i][j];
}
}
}
int MinQualifiedElement(const vector<vector<int>>& grid,
const vector<vector<int>>& distGrid,
const vector<vector<int>>& buildingCountGrid,
int numBuilding){
int ans = -1;
for(int i = 0; i < distGrid.size(); ++i){
for(int j = 0; j < distGrid[i].size(); ++j){
if(buildingCountGrid[i][j] != numBuilding)continue;
if(grid[i][j] != 0)continue;
if(ans == -1)ans = distGrid[i][j];
else ans = min(ans, distGrid[i][j]);
}
}
return ans;
}
bool InRange(const vector<vector<int>>& grid, const pair<int, int>& loc){
return loc.first >= 0 && loc.first < grid.size() &&
loc.second >= 0 && loc.second < grid[loc.first].size();
}
int CountBuilding(const vector<vector<int>>& grid){
int ans = 0;
for(auto row: grid){
for(int n: row){
if(n == 1)++ans;
}
}
return ans;
}
void Print2DMatrix(const vector<vector<int> >& matrix){
cout << "matrix: " << endl;
for(auto row: matrix){
for(int n: row)
cout << n << " ";
cout << endl;
}
}
};

复制代码

bubblebobabee

给楼主点赞。能坚持这么久的人在战拖区其实寥寥无几……祝楼主拿到心仪的大offer！

大木虫

279. Perfect Squares
写了两种解法：DP, BFS，总共用时21分钟

DP 解法（44ms）

class Solution {
public:
int numSquares(int n) {
/* 0. MISC */
/* 1. prep */
vector<int> dpMatrix(n + 1, -1);
dpMatrix[0] = 0;
/* 2. key algo */
for(int i = 0; i < dpMatrix.size(); ++i){
for(int j = 1; i + j * j <= n; ++j){
int nextStep = i + j * j;
if(dpMatrix[nextStep] == -1)
dpMatrix[nextStep] = dpMatrix[i] + 1;
else dpMatrix[nextStep] = min(dpMatrix[nextStep], dpMatrix[i] + 1);
}
}
/* 3. answer */
return dpMatrix.back();
}
};

复制代码

BFS 解法（4ms）

class Solution {
public:
int numSquares(int n) {
/* 0. MISC */
/* 1. prep */
queue<int> bfsQueue;
vector<int> memo(n + 1, -1);
memo[0] = 0;
bfsQueue.emplace(0);
/* 2. key algo */
while(!bfsQueue.empty()){
int node = bfsQueue.front();
bfsQueue.pop();
int val = memo[node];
for(int i = 1; node + i * i <= n; ++i){
int child = node + i * i;
if(child == n)return val + 1;
if(memo[child] != -1)continue;
memo[child] = val + 1;
bfsQueue.emplace(child);
}
}
/* 3. answer */
return -1; /* error case */
}
};

复制代码

大木虫

679. 24 Game (hard)
开始佛系写题了，能写几道写几道吧
这题不难，就是繁琐

class Solution {
public:
bool judgePoint24(vector<int>& nums) {
/* 0. MISC */
/* 1. prep */
vector<float> numFloat = {nums[0], nums[1], nums[2], nums[3]};
bool answer = false;
/* 2. key algo */
Permute24(numFloat, answer, 0);
/* 3. answer */
return answer;
}
void Permute24(vector<float>& nums, bool& answer, int index){
static int count = 0;
if(answer)return;
if(index == nums.size() - 1){
answer |= Get24(nums);
return;
}
for(int i = index; i < nums.size(); ++i){
swap(nums[index], nums[i]);
Permute24(nums, answer, index + 1);
swap(nums[index], nums[i]);
}
}
bool Get24(const vector<float>& nums){
string opCollection = "+-*/";
bool ans = false;
for(char op1: opCollection){
for(char op2: opCollection){
for(char op3: opCollection){
string opStr;
opStr += op1;
opStr += op2;
opStr += op3;
ans = SetPriority24(nums, opStr);
if(ans)return ans;
}
}
}
return ans;
}
bool SetPriority24(const vector<float>& nums, string opStr){
vector<string> prioritySet = {"00", "10", "20", "01", "11", "21"};
for(string priority: prioritySet){
float result = Result(nums, opStr, priority);
if(abs(result - 24.0) < 0.00001){
return true;
}
}
return false;
}
float Result(const vector<float>& nums, string opStr, const string& priority){
vector<float> stage1, stage2;
string op1, op2;
float result;
for(int i = 0; i < nums.size(); ++i){
if(i == priority[0] - '0'){
stage1.emplace_back(Calc(nums[i], nums[i+1], opStr[i]));
opStr[i] = '0';
i++;
}
else {
stage1.emplace_back(nums[i]);
}
}
op1 = ConstructOp(opStr);
for(int i = 0; i < stage1.size(); ++i){
if(i == priority[1] - '0'){
stage2.emplace_back(Calc(stage1[i], stage1[i+1], op1[i]));
op1[i] = '0';
++i;
}
else {
stage2.emplace_back(stage1[i]);
}
}
op2 = ConstructOp(op1);
float ans = Calc(stage2[0], stage2[1], op2[0]);
return ans;
}
string ConstructOp(const string& opStr){
string ans;
for(char c: opStr){
if(c != '0')ans += c;
}
return ans;
}
float Calc(float num1, float num2, char op){
if(op == '+')return num1 + num2;
if(op == '-')return num1 - num2;
if(op == '*')return num1 * num2;
if(op == '/' && num2 != 0)return num1 / num2;
return 1;
}
template <class T>
void printVec(const vector<T>& vec){
for(T element: vec)cout << element << " ";
cout << endl;
}
};

复制代码

大木虫

295. Find Median from Data Stream
继续佛系，这题原来在EPI上写过，现在在LC上写一遍

class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
minHeap.emplace(num);
maxHeap.emplace(minHeap.top());
minHeap.pop();
if(maxHeap.size() - minHeap.size() > 1){
minHeap.emplace(maxHeap.top());
maxHeap.pop();
}
}
double findMedian() {
if(minHeap.size() == maxHeap.size())
return (minHeap.top() + maxHeap.top()) / (double)2;
else return maxHeap.top();
}
priority_queue<int, vector<int>, greater<int> > minHeap;
priority_queue<int> maxHeap;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/

复制代码

大木虫

感觉最近老在挑最水的hard写。。。然后标榜自己写了一堆hard。。。这样自我膨胀是不行的

ly_67

大木虫发表于 2018-8-3 08:54
今天给一个门卫大叔话15分钟讲明白了二分查找，给另一个门卫大哥花30分钟讲了 Leetcode Edit Distance 的 ...

太6了，这是什么骚操作

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

评分

浏览过的版块