A Code

1250. Third Maximum Number 1744. Increasing Order Search Tree 1189. Minesweeper 838. Subarray Sum Equals K(好精妙的一道小题，不难) 547. Intersection of Two Arrays 526. Load Balancer (vector和hash map结合来实现O(1)的插入，删除，和random pick up) 1287. Increasing Triplet Subsequence 1304. H-Index 719. Calculate Maximum Value 1393. Friends Of Appropriate Ages

1189. Minesweeper 带判断条件的，是否把节点放入queue in BFS。是否进行下一个的search，in DFS。 BFS:  class Solution { public : /** * @param board: a board * @param click: the position * @return: the new board */ const vector < int > dx = { 0 , 0 , -1 , 1 , -1 , -1 , 1 , 1 }; const vector < int > dy = { -1 , 1 , 0 , 0 , -1 , 1 , -1 , 1 }; const int dir = 8 ; vector < vector < char >> updateBoard( vector < vector < char >>& board, vector < int >& click) { // Write your code here // DFS //改写为BFS。 const int m = board.size(); vector < vector < char >> res; if (m == 0 ){ return res; } const int n = board[ 0 ].size(); //vector<vector<int>> neighbors; std :: queue < vector < int >> q; if (board[click[ 0 ]][click[ 1 ]] == 'M' ){ board...

今日电面F，代码相对顺利写出。 但run test by hand以及复杂度分析陷入黑洞，在多次提示下算是给出答案。 所以，要好好总结 1，run test case by hand，在平时刷题时要加以练习。 要学会些main()，并且打印结果！！！// 一般就是写一个 main()，然后建一个链表，调用你写出的函数求出结果，打印，让面试官看到给出了正确答案。然后再自己想一些 corner case，让面试官了解你枚举常见 corner case 的能力。 2，复杂度分析。 （复杂度分析要跳出代码的执行细节，high level宏观的来看，元素被访问了几遍，一遍是O(N),在一遍里  嵌套着又一遍，是O(N)） 以今天的题目为例。 找所有从root到leaf的path， 时间 复杂度，我开始给出的是O(2^N)，因为我想每个node都有左右两个节点。但其实忽略了N其实就是节点 的个数。 跳出来看，从high level看，binary tree里面的traverse 是每个点被遍历一次。所以，时间复杂度 是O(N)，而在每个节点上，都有for loop的操作。所以，还得乘以for loop里的遍历次数。for loop里次数是 leaf节点个数，leaf节点个数等于 2^height, 而height平均是log（n），所以leaf节点时O(N)。最终时间复杂度 是O(N^2). 这就是今天被面试官一步步引导的思维过程， 在面试时，一旦遇到需要现场推导的时候，别慌，一慌张，脑子就乱了，大脑充血。一步步去做。 不太可能，遇到的问题都是自己事先想到的。 空间 复杂度，开始我提到了recursion调用函数产生的系统stack空间，但我心里也不清楚这方面的复杂度是多少。 感觉也没说清楚，就过去了。（对于recursion，系统stack的消耗是recursion的深度，也就是最大是几层 的recursion，也就是函数call自己再call自己的深度，对于DFS就是Deapth深度，具体tree是height，matrix是 max(m,n)。） 主要还是要看所用的定义的变量，也就是在系统heap memory上占用的空间。 leaf的个数 * height。所以是，O(N*logN). 开始...