经典思路总结

1， LinkedList slow and fast pointers

应用：

  • 找middle： ListNode *findMid(ListNode *head){ ListNode *slow = head; ListNode *fast = head->next; while(fast != NULL && fast->next != NULL){ slow = slow->next; fast = fast->next->next; } return slow; }
Lintcode 99. Reorder List，106. Convert Sorted List to Binary Search Tree
223. Palindrome Linked List
2，LinkedList reverse

     ListNode *reverse(ListNode *head){
        ListNode *pre = NULL; 
        while(head != NULL){
            ListNode *temp = head->next; 
            head->next = pre; //转换            pre = head; //更新
            head = temp; 
        }
        return pre; 
    }
3，two pointer 模板 （例子，找距离target最近的sum2）
int start = 0; int end = sizeN - 1; while(start < end){ int sumVal = numbers[start] + numbers[end]; if(abs(sumVal - target) < abs(res - target)){ res = sumVal; } if(sumVal > target){ end--; } else{ start++; } }
4,dummy node 在linkedlist中的使用，（452. Remove Linked List Elements）
ListNode * removeElements(ListNode * head, int val) {
// write your code here ListNode *dummy = new ListNode(0); dummy->next = head; ListNode *pre = dummy; while(head!= NULL){ if(head->val == val){ //ListNode *temp = head->next; pre->next = head->next; head = head->next; } else{ head = head->next; pre = pre->next; } } return dummy->next; }

 5, merge linked lists (1->4->3 and 5->6->7 output: 1-5-4-6-3-7)

 ListNode *merge(ListNode *l1, ListNode *l2){
        ListNode *dummy = new ListNode(0); 
        ListNode *copy = dummy; 
        while(l1 != NULL && l2 != NULL){
            dummy->next = l1;
            ListNode *temp = l1->next; //注意这里把l1->next现场保护，下一步会把l1->next
覆盖了
           
            dummy->next->next = l2; 
            dummy = l2; 
            l1 = temp; 
            l2 = l2->next; 
        }
        if(l1 != NULL){
            dummy->next = l1; 
        }
        if(l2 != NULL){
            dummy->next = l2; 
        }
        return copy->next; 

    }
6，单调栈，找右边出现的第一个比当前大的数，用单调递减栈，所有的操作都在栈pop时，iterate遇到的当前
值，把比当前值小的都pop出来，这样被pop出来的值对应的第一个比他们大的就是当前值。
push进stack的可以是index，也可以是index对应的值。
题目：510. Maximal Rectangle 122. Largest Rectangle in Histogram
1255. Remove K Digits

 stack<int> stk; int res = 0; for(int i = 0; i < sizeH + 1; i++){ while(!stk.empty() && height[stk.top()] >= height[i]){ //单独递增，也就是前面有比当前大的都pop出去 int idx = stk.top(); stk.pop();
//操作，其他是模板 int width = stk.empty() ? i : i - stk.top() - 1; //关键点2，注意是stk.top(),不是idx，因为原数组idx前面也存在着比idx对应数字大的。 res = max(res, width * height[idx]); } stk.push(i); }





7, BFS：在matrix中找最短路径: 663. Walls and Gates，573. Build Post Office II



803. Shortest Distance from All Buildings








模板           const vector<int> dx = {-1, 1, 0, 0};



               const vector<int> dy = {0, 0, -1, 1};                 queue<node> q; 



初始加入q的元素，根据实际问题，一个个加入一个个处理（处理sum类型，803. Shortest Distance from All Buildings）



，或把满足条



件的都一次加入（处理min类型, 663. Walls and Gates,974. 01 Matrix,）



有时把路径的destination加入queue (1367. Police Distance，

663. Walls and Gates,974. 01 Matrix.这三道题本质一模一样

















803. Shortest Distance from All Buildings),比较容易解题。



有时把开始位置加入（663. Walls and Gates）。



               while(!q.empty()){
                        int sizeQ = q.size();
                        for(int i = 0; i < sizeQ; i++){
                            node temp = q.front();
                            q.pop(); 
                            int oldX = node.x;
                            int oldY = node.y; 
                            for(int i = 0; i < 4; i++){
                                int newX = oldX + dx[i];
                                int newY = oldY + dy[i]; 
                                if(newX < 0 || newX >= m || newY < 0 || newY >= n || rooms[newX][newY] == -1 || rooms[newX][newY] < INT_MAX){
                                    continue; //根据具体问题和记忆状态，设置跳过的条件: visited/障碍物
                                }
                                rooms[newX][newY] = rooms[oldX][oldY] + 1; //更新状态
                                q.push(newX * n + newY); 
                            }
                        }
                    }





8，在一个string中split by the separators such as ','  '/' ..

        while(i < adjData.size()){
            // get the value 
            string sElem; 
            int j = i; 
            while(j < adjData.size() && adjData[j] != ','){ 



// while 里一定要先判断是否溢出
                j++; 
            }
            sElem = adjData.substr(i, j - i); 

            i = j + 1;  //split by ','的经典用法



  } 







9，BFS在search island类型的应用。在search时，把相同一块区域里满足条件的都重置。



这样后面search时不会再count这个区域。题目：897. Island City，433. Number of Islands



BFS:




for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){ //满足条件的
                    res++; 
                    std::queue<node> q;
                    q.push(node(i, j)); 
                    while(!q.empty()){
                        node temp = q.front();
                        q.pop(); 
                        for(int k = 0; k < 4; k++){
                            int newX = temp.x + dx[k];
                            int newY = temp.y + dy[k]; 
                            if(newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] == 0){
                                continue; 
                            }
                            q.push(node(newX, newY)); 
                            grid[newX][newY] = 0; //相同区域满足条件的重置
                        }
                    }
                }
            }
        }






10, prefix sum 数组, 适用于range （745. Palindromic Ranges；1399. Take Coins），


subarray，


subsequence等。思想是先统计出在每个元素之前所有符合条件的元素个数,prefixSum[j] -


prefixSum[i],是index i + 1 ~ j 区间内的个数。




11，判断一个数n是否palindrome，对称性。745. Palindromic Ranges。两种方法：


1是转换成string, 使用to_string(),然后


int s = to_string(n); 


for(int i = 0; i < s.size()/2; i++){


   if(s[i] != s[s.size() - 1 -i]{


      return false; 


   }


}


return true; 



另一种办法: 



int copy = n; 



int newN = 0; 



while(n != 0){



newN = newN * 10 + n%10; 



n /= 10; 



}



return newN == copy; //两种方法都要注意数的正负。




12，binary search的适用范围很广:找target，找比target小的数中的最大值，找比target大的数


中的最小值，找距离target最接近的数，凡是找数的都先想想用binary search。1272. Kth Smallest Element in a Sorted Matrix。


heaters题目 1297. Count of Smaller Numbers After Self










13, Interval 类型的，开始和结束，组成一个区间。有很多个区间.题目有merge


区间或判断是否有重叠（156. Merge Intervals，920. Meeting Rooms），找有重叠的区间个数


（919. Meeting Rooms II）


Merge区间


    static bool cmp(const Interval &a, const Interval &b){
        return a.start < b.start; //关键一步 注意这里 <
    }
    vector<Interval> merge(vector<Interval> &intervals) {
        // write your code here
        vector<Interval> res; 
        if(intervals.empty()){
            return res; 
        }
        sort(intervals.begin(), intervals.end(), cmp); //先以第一个元素排序
        res.push_back(intervals[0]); //定义一个新的数组，写入merge后元素
        for(int i = 1; i < intervals.size(); i++){
            if(res.back().end >= intervals[i].start){ //注意这里 >=，判断是否重叠
                res.back().end = max(res.back().end, intervals[i].end); 
            }
            else{
                res.push_back(intervals[i]); 
            }
        }
        return res; 
    }






14，扫描线sweep line, 解决有重叠的区间个数，919. Meeting Rooms II. 391. Number of Airplanes in the Sky


start，和end 分别排序，组成两个sorted array. 遍历start array, 如果start比end小了，


结果++, 否则end++.思想就是 start保持领先，end是前面一个区间的end，如果后面区间的start < 前面


区间的end，重叠次数就要++。 


test case: [1,3] [2,5] [6,8], [7,9],starts[1,2,6,7],ends[3,5,8,9]第一次start=1


,end=3, 1 < 3, 结果1;第二次start=2,end=3,结果2；第三次start = 6,end=3,更新end到下一个


8；第四次start = 9，end = 8，结果3


int minMeetingRooms(vector<Interval> &intervals) {
        // Write your code here
        //找重复的个数，sweep line？就是把开始，结束两点分别排序。
        //遍历如果start < end结果就++，否则，end挪至下一个
        vector<int> starts, ends;
        int res = 0, endpos = 0;
        for (auto a : intervals) {
            starts.push_back(a.start);
            ends.push_back(a.end);
        }
        sort(starts.begin(), starts.end());//两个都要排序
        sort(ends.begin(), ends.end());
        for (int i = 0; i < intervals.size(); ++i) {
            if (starts[i] < ends[endpos]) { //后面的start比前面的end小
               ++res;
            }
            else{ 
               ++endpos;
            }
        }
        return res;
    }






15， 有一种matrix元素以行和列排序，然后search，可实现O(m + n)复杂度。这种类型从


左下角，或右上角开始，然后用while












比如：每行，每列都是由小到大排序。
    [
      [1, 3, 5, 7],
      [2, 4, 7, 8],
      [3, 5, 9, 10]
    ]
    target = 3
Output:2











这道题如果不能想到从左下角，或右上角开始，就没法实现O(m + n).






















l另外，如果要实现O(m +n),就要用while了






class Solution {
public:
    /**
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    int searchMatrix(vector<vector<int>> &matrix, int target) {
        // write your code here
        int rowN = matrix.size();
        if(rowN == 0){
            return 0; 
        }
        int colN = matrix[0].size();
        
        int i = rowN - 1; //左下角
        int j = 0; 
        int count = 0; 
        while(i >= 0 && j < colN){ //用while
            if(matrix[i][j] == target){
                count++;
                i--; 
                j++; 
            }
            else if(matrix[i][j] > target){
                i--; 
            }
            else{
                j++; 
            }
        }
        return count; 
    }
};








16，combination 和permutation类型，组合和排列。DFS解决。



题目：152. Combinations 

990. Beautiful Arrangement

   /**
     * @param n: Given the range of numbers
     * @param k: Given the numbers of combinations
     * @return: All the combinations of k numbers out of 1..n
     */
    vector<vector<int>> combine(int n, int k) {
        // write your code here
        vector<vector<int>> res; 
        if(k > n){
          return res; 
        }
        vector<int> resElem; 
        dfs(n, k, 1, res, resElem);
        return res; 
    }
    void dfs(int n, int k, int start, vector<vector<int>> &res, vector<int> &resElem){
        if(resElem.size() == k){
            res.push_back(resElem);
            return; //DFS出口
        }
        for(int i = start; i <= n; i++){ 

            //这里根据具体问题，会需要一个判断条件是否执行recursion。比如去重，visited等
            resElem.push_back(i);
            dfs(n, k, i + 1, res, resElem); 
            resElem.pop_back();
        }
    }








17,判断一个string是否是另一个string的subsequence。1191. Longest Uncommon Subsequence II


              看s是否是hSet的subsequence


               int l = 0;
                string s = strs[i]; 
                int k; 
                for(k = 0; k < hSet.size(); k++){
                    if(s[l] == hSet[k]){
                        l++; 
                    }
                    if(l == s.size()) break; 
                }
                if(l == s.size()){
                    return true; 
                }


                else {


                     return false; 


                } 




18, string转换成int 函数, stoi()


19,凡是有对应关系的就用hashMap.


20，判断一个string是否另外一个的substring。strstr


题目 718. Repeat String



int repeatedString(string &A, string &B) {
        // write your code here
        //非常有意思的一道题 
        //str的比较 比较 模板，注意substring和subsequence的区别。



        //substring 是所有的元素的连续的；subsequence是元素的前后顺序是一定的，中间可以有几个



元素不存在
        int m = A.size(), n = B.size();
        for(int i = 0; i < m; i++){
            int j = 0; 
            while(j < n && A[(i + j) % m] == B[j]){
                j++; 
            }
            if(j == n){
                return (i + j - 1) / m + 1; 
            }
        }
        return -1; 
    }

2019年07月21日11:44:19


21， inteval 类型的，判断是否两个interval重叠，四种可能[（）], ([]),[(]),([)].


这四种情况可以简化为：


if（intervalA.start <= intervalB.end && intervalA.end >= intervalB.start）


记住就好了（题目：30. Insert Interval）






22， prefix trie 记住数据结构 node的数据结构

struct node {

         node *child[26];

         bool isWord;

         node() {

              for(int i = 0; i < 26; i++){

                    child[i] = NULL;

               }

              isWord = false;

        }

};











































Comments











Post a Comment























Popular posts from this blog









Amazon OA 763. Partition Labels





















class Solution {  public:      vector<int> partitionLabels(string S) {          // 这是个好题          unordered_map<char, int> mp;          vector<int> res;          const int size = S.size();          if(size == 0){              return res;          }          for(int i = 0; i < size; i++){              mp[S[i]] = i;          }          int start = 0, end = 0;          for(int i = 0; i < size; i++){              end = max(end, mp[S[i]]);              if(i == end){                  res.push_back(i - start + 1);                  start = end + 1;      ...








Read more










1427. Split Array into Fibonacci Sequence





















       Description   中文 English      Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].   Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:   0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type); F.length >= 3; and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2. Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.   Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.          1 <= S.length <= 200  S contains only digits.         Have you met this question in a real interview?    Yes   Problem Correction      Example     Example 1:  Input: "123456579" Output: [123,456,579]  Example 2:  Input: "11235813" Output: [1,1,2,3,5,8,13]  Example 3:  Input: "112358130" Output: [] Ex...








Read more










1464. The K-th Combination





















    很巧妙的办法，   还有一个求 组合数目的方法   Code ( Language :C++)     Edit       class  Solution  {  public :     /**      * @param n: The integer n      * @param k: The integer k      * @return: Return the combination      */      vector < int > getCombination( int  n, int  k) {          vector < vector < int >> C(n+ 1 , vector < int >(n+ 1 , 0 ));         for  ( int  i = 0 ; i <= n; ++i) {             C[i][ 0 ] = C[i][i] = 1 ;         }         // Compute C(m, n) using C(m, n) = C(m-1, n-1)+C(m-1, n).          for  ( int  i = 1 ; i <= n; ++i) {             for  ( int  j = 1 ; j < i; ++j) {                 C[i][j] = C[i -1 ][j -1 ] + C[i -1 ][j];             }         }                  vector < int > ans;         int  curr_index = 1 ;         for  ( int  i = 1 ; i <= n/ 2 ; ++i) {             int  base = C[n-curr_index][n/ 2 -i];             // Search for next digit in ans.              while  (k > base) {                 curr_index++;                 b...








Read more