Monday, August 31, 2015

Leetcode second round: 8/31


这两天身体不舒服,没有按照原定计划完成,算是整理下思绪,希望能更高的效率做题把.

today's mission
1-28

leetcode 数字有关运算题汇总:这类题目在面试中还是出现频率很高的。

2 .    add two numbers
这个题目如果方法选的不好,思路不清晰,做起事是很痛苦的!!!一开始,我想着把 l1 和 l2的数加在一起然后放在l1的值里面,不加任何辅助的指针,但是这样做的坏处是,当L2 比 l1长,l1到达了NULL, l1再也不能放值了,这样的问题如果不用一个辅助指针根本无法处理啊!既然需要用到辅助指针,为什么不想Merge two sorted list那样,用两个辅助指针, dummy head + cur(TAIL), 这样可以非常方便地处理两个list不等长的结果。
时间复杂度: O(n+m)
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (l1 == NULL && l2 == NULL) return NULL;
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        int cnt = 0;
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        while (l1 != NULL || l2 != NULL) {
            if (l1 != NULL && l2 != NULL) {
                int tmp =  (l1->val + l2->val + cnt) % 10;
                cnt =  (l1->val + l2->val + cnt) / 10;
                l1->val = tmp;
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
                l2 = l2->next;
            } else if (l1 != NULL) {
                int tmp =  (l1->val + cnt) % 10;
                cnt =  (l1->val + cnt) / 10;
                l1->val = tmp;
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            } else if (l2 != NULL) {
                int tmp =  (l2->val + cnt) % 10;
                cnt =  (l2->val + cnt) / 10;
                l2->val = tmp;
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
        }
        if (cnt == 1) {
            cur->next = new ListNode(1);
        }
        return head->next;
    
    }
};


7.     reverse integer
这个题目要注意一点是, 一个数reverse过程中可能会出现overflow的情况, 对overflow的处理是, 如果是负数,返回 MIN, 如果是正数, 返回MAX,
关键是如何去判断这个数在reverse过程中是否overflow。sum的计算公式是: sum * 10 + n , 要使在计算过程中不越界, sum * 10 + n  <= INT_MAX, 所以这就是是否越界的判断公式。 
class Solution {
public:
    int reverse(int x) {
        int flag = false;
        if (x < 0 ) flag = true;
        x = abs(x);
        int sum = 0;
        while (x) {
            int n = x % 10;
            int c = x / 10;
            if (sum <= (INT_MAX - n) / 10) {
                sum *= 10;
                sum += n;
            } else {
                return 0;
            }
            x = c;
        }
        if (flag) return sum*(-1);
        return sum;
    }
};
8.     string to integer
这个题目虽然简单,但是还是属于特别容易出错的题目, 在开始做之前,应该先跟面试官弄清楚转换的规则是什么, 比如这个题目里面规定的是: 1. 从第一个非空格的char开始转换 2. 如果invalid string , 返回 0, 否则返回具体的值, 注意overflow的情况下返回INT_MIN, INT_MAX . 3. valid string是指+、-、digit, 并且要求, 只能有一个符号位,并且紧跟着数字,其他情况下都是invalid。
这个题目逻辑最清晰的写法是: 将遇到第一个+, -或者digit的情况提出来利用辅助函数 convert来进行计算第一个可能valid的string, 在convert里函数只能处理digit的字符, 其他字符,return 0;

class Solution {
private:
    int convert(string str, int idx, bool positive) {
        int rst = 0;
        for (int i = idx; i < str.size(); i++) {
            if (isdigit(str[i])) {
                if (rst <= (INT_MAX - (str[i] - '0')) / 10) {
                    rst *= 10;
                    rst += str[i] - '0';
                } else {
                    rst = INT_MAX;
                    return positive ? rst : INT_MIN;
                }
            } else {
               break;
            }
        }
        return positive ? rst : -rst;
    }
public:
    int myAtoi(string str) {
        if (str.size() == 0) return 0;
        int rst = 0;
        bool positive = true;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == ' ') {   //trim space
                continue;
            } else if (str[i] == '+') {
                positive = true;
                rst = convert(str, i+1, positive);
                break;
            } else if (str[i] == '-') {
                positive = false;
                rst = convert(str, i+1, positive);
                break;
            } else if (isdigit(str[i])) {
                rst = convert(str, i, positive);
                break;
            } else {
                break;
            }
        }
        return rst;
    }
};
9.     palindrome number
这个题目也是依据palindrome number的思想, 对数的首尾数字进行判断, 唯一一个需要注意的地方是, 在计算过程中count可能溢出,因为count在后面 count = count/10的操作, 可能会造成溢出, eg: x = 1000000001, 10位数,*10, 11位数,就溢出了。一般机器能handle的最大int值 2147483647,10位, 11位的数就直接溢出了。
class Solution {
private:
    bool helper(int x, long count) {
        while (count > 1) {
            int last = x % 10;
            int first = x/count;
            if (last != first) return false;
            x = (x % count)/10;
            count = count/100;
        }
        return true;
    }
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        long count = 1;
        int tmp = x;
        while (tmp) {
            tmp = tmp/10;
            count = count * 10;
        }
        count /= 10;
        return helper(x, count);
    }
};

12.   Interger to Roman

13. Roman to Integer

29: divide two integers
这个题目的算法还是记住比较好,用的其实是 a/b -> a = b * 2 ^n + b * 2^(n-1) +.....+ b* 2^0;
每次通过移位操作计算n, 但是要注意INT_MIN如果直接利用abs转换成负数的话,会造成溢出,所以我们需要先把INT_MIN --> long long的范围内再进行转换成正数。还要注意corner case的判断: 当 dividend 是INT_MIN, divisor 是 -1的时候, 会造成溢出,直接返回INT_MAX;

43.  multiply strings

每次做这种大数乘的题目就很慌张,有点怕,不太会做这种数学题,但是大数乘的题目在面试中还是经常考到的,不会做也要学会多做做就不怕了。
这个题目由于数字都是用string表示的,所以最好先把这些string都reverse一下,然后需要一个额外的空间来存储乘法相对应位的累加结果,然后在对这些累加的结果进行处理,比如需要往前进位啥的,最后由于一开始开辟的是最大的可能空间,如果最后不需要那么多的话,会有前导0的出现, 所以最后我们需要去掉前导0。 用到了string erase的函数。

class Solution {
public:
    string multiply(string num1, string num2) {
        string rst = "";
        if (num1.size() == 0 || num2.size() == 0) return rst;
        //reverse two strings
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        //get sum in each position
        int M[num1.size() + num2.size()] = {0};
        for (int i = 0; i < num1.size(); i++) {
            for (int j = 0; j < num2.size(); j++) {
                M[i+j] += (num1[i] - '0') * (num2[j]-'0');
            }
        }
        //dealing with these sums
        for (int i = 0; i < num1.size() + num2.size(); i++) {
            int digit = M[i] % 10;
            int cnt = M[i]/10;
            if (i+1 < num1.size()+num2.size()) {
                M[i+1] += cnt;
            }
            char tmp = (digit + '0');
            rst += tmp;
        }
        reverse(rst.begin(), rst.end());
        int i = 0;
        while (i < rst.size()-1 && rst[i] == '0') i++;
        rst.erase(0,i);
        return rst;
    }
};

67. add  binary

1. 2 SUM

2sum 有很多变形的,比如: 有的题目要求找出一对具体的两个元素,有的题目要求找出一对Index, 有的题目要求找出所有的配对的元素,有的题目要求找出所有配对的Index, 
如果要求找出所有配对的Index, 最好是不要对之前的元素排序,直接用hashmap的方法来做, 因为排了序之后Index的顺序都改变了。 如果是要求找出具体的元素,两种方法都是可以做的,看面试官要求是什么。

15.  3 SUM
3sum 这个题目还是有很多陷阱,两种方法:hashmap/sort
sort : 因为题目里面是有duplicates elements的,所以在每一步移动一个index的时候,都必须要先看新的index指向的元素是否与之前的元素相等。在去duplicate的时候要注意,先移动index,再去处理duplicate, 防止没有duplicate的时候,没有移动任何Index, 造成死循环。
hashmap: 因为这个题目里面含有重复元素, 所以利用hashmap不太好处理duplicate, 而且不管用hashmap还是sort,时间复杂度最高还是O(n^2), 排序不会影响时间复杂度。
所以 对于含有duplicates的题目,还是用sort的方法比较好。

16. 3SUM closest
这个题目和3 sum的解法是相同,不同的是每次每次移动任何一个指针,都要计算一下当前的差值,并且维护一个最小差值,最后那个最小差值对应的sum就是结果。
要想提高程序的运行速度,我们需要把重复的运算和操作合并,使其只运行一次。

18. 4 SUM  --> K SUM
如果4 SUM继续利用3 SUM的方法进行的话, 时间复杂度是O(n^3)
但是联想从2SUM --> K SUM的推广的方法,我们是可以利用2SUM来解的, 我们可以先得到所有2 SUMpair, 并且存在hashmap中,然后再进行2 sum, 时间复杂度是O(n^2), 算法的思想很简单,但是由于可能有重复的pair出现,所以有很多的case 需要考虑。

3. longest substring without repeating character
这个题目是string里面 sliding window + contain duplicates的结合, 一开始想到 用 unordered_set 来处理发现duplicates的情况,后来有注意到unordered_set作用的对象是char, 对于 256 ASCII字符来说可以使用 256 size的array 来代替 set。这样可以提高set里面erase的复杂度。 时间复杂度: O(n * 2)
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0) return 0;
        //unordered_set<char> iset;
        int iset[256] = {0};
        int left = 0;
        int right = 0;
        int gmax = 0;
        for (; right < s.size(); right++) {
            if (iset[s[right]] == 0) {
                iset[s[right]]++;
                gmax = max(gmax, right-left+1);
            } else {
                while (s[left] != s[right]) {
                    iset[s[left]] = 0;
                    left++;
                }
                left++;
            }
        }
        return gmax;
    }
};
4. median of two sorted array

5. longest palindrome substring
M1: use 2D dp, check if palindrome and update the maximum length
只是这种简单的dp每次都没有一次性写对,而且每次都是把j == i+1 写成了 j = i+1, 每次还看半天都不能发现的bug !!!!
class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() == 0) return s;
        bool M[s.size()][s.size()];
        int gmax = 0;
        int left = 0;
        for (int i = s.size()-1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if ((j == i) || ((s[i] == s[j]) && (j == i+1 || M[i+1][j-1]))) {
                    M[i][j] = true;
                    if (gmax < j-i+1) {
                        gmax = j - i +1;
                        left = i;
                    }
                } else {
                    M[i][j] = false;
                }
            }
        }
        return s.substr(left, gmax);
    }
};
时间复杂度: O(n^2) 空间复杂度: O(n^2)
M2:专门解决 longest palindrome string 问题的一个算法是 : Manacher's algorithm, 时间复杂度O(n), 非常巧妙的一个算法,

6. zigzag conversion
纯粹的数学题


10.  regular expression matching



11. container with most water
这个题目感觉是简化版的trapping rain water, 以线作为板子,只需要找到两根线和x轴组成的区域面积最大, 也是histogram 板子,短板原理, 两个pointer, 分别指向首尾两端, 谁短移动谁,并且维护最大面积, 这个题目这样其实就是每次都计算出每块短板能组成的最大面积。

follow up:  42. trapping rain water
trapping rain water 比 container with most water处理上要难一些,但是两题的思路是相同的,都是利用两个指针指向两端,然后移动短板,这个题目在移动短板的时候进行的处理操作是, 对每一个短板计算能储存水的量, 这个短板能储存水的量 = maxLeft - height[left] or  maxRight - height[right], 需要维护三个值,一个是左边板子的最大高度, 右边板子的最大高度, 以及sum。


14: longest common prefix

这个题目求公共前缀, 以第一个string为基准,一个字符一个字符地比较其他字符串相应位置的字符,如果都相同,那么说明找到了一个common char, 加在 rst的尾部。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string rst = "";
        if (strs.size() == 0) return rst;
        if (strs.size() == 1) return strs[0];
        for (int i = 0; i < strs[0].size(); i++) {
            for (int j = 1; j < strs.size(); j++) {
                if (i >= strs[j].size() || strs[0][i] != strs[j][i]) return rst;
            }
            rst += strs[0][i];
        }
        return rst;
    }
};


17: letter combinations of a phone number
这个题目一看输出所有的结果,肯定是dfs来解题, dfs注意树的层数, 每一层什么含义和每一层的分支。
eg: 23 :
position0 :               a    b    c
                                /|\   /|\   /|\
position 1:             def  def......

19. remove nth node from linked list
这个题目很简单,但是还是写了两遍才写对。 要注意两点,首先这个题目可能head会被remove, 所以保险起见,我们加一个dummy node, 其次, 当找到了要删的节点位置后, pre->next = slow->next, 这个是逻辑公式,每次写都认为是 pre->next = fast, 其实这个逻辑式一看就是错的,因为fast并不是就是在slow之后啊, 很简单的例子,比如 n= 5, 那么fast 和 slow 相隔就是5个node的距离了。
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == NULL) return NULL;
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        while (n > 0) {
            n--;
            fast =fast->next;
        }
        while (fast) {
            fast = fast->next;
            pre = slow;
            slow = slow->next;
        }
        pre->next = slow->next;
        return dummy->next;
    }
};

20: valid parentheses
这个题目判断括号对是否匹配, 用一个stack去匹配。
对这个stack进行push, pop只有两种情况, 当 stack不为空, 并且stack的 top 和 char c 可以匹配的时候,可以从stack里pop出一个元素,其他情况下,都把元素push到stack中。

21. merge two sorted list
23.  merge k sorted list
merge two sorted list 现在可以很熟练地写出来,但是merge k sorted list 才是重点, 这个题目从 2 -->k的扩展,体现了两种基本的思想: M1 : use  priority_queue to handle k object, sort, initial states and expand rules and do it in a breadth first search way.  M2: divide and conquer, iteratively apply 2 way method to get the k way method. you need to think the rules to get k. (DIVIDE AND CONQUER is generally used in k way questions and always works).
time complexity: O(n * k * logn) because every list node is pushed and popped from priority_queue , space complexity: M1:O(n*k) M2: O(1)

22. generate parentheses
利用dfs 就可以解决, 很简单。
24. swap nodes in pair
这个题目属于比较复杂的list里面的指针操作了,在进行比较复杂的指针操作的时候要注意, 必要的时候一定要记得断掉已经不存在的链接,或者无效的链接,否则,list会进入一个cycle, 比如这个题目里面每次 pre->next = NULL, cur node 和 next node之间的这个链接应该不再存在。要注意区分偶数个和奇数个nodes的情况。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        ListNode* cur = head;
        while (cur && cur->next) {
            ListNode* next = cur->next;
            ListNode* nnext = next->next;
            next->next = cur;
            pre->next = next;
            pre = cur;
            pre->next = NULL;
            cur = nnext;
        }
        if (cur) {
            pre->next = cur;
        }
        return dummy->next;
    }
};
25. reverse nodes in k-group

这个题目是上一个的2 --> k的拓展, 对于这个题目采取的做法是在2上进行修改, 其实整体上指针的操作逻辑是没有改变的,1. 指针操作还是需要小心,可以避免区别奇数和偶数的情况,可以统一处理。 2. tail 在
这个题目还是有很多细节要注意,一遍不容易写对。

26. remove duplicates in sorted array
27.  remove element
这两个题目都是属于array的操作,也可以应该在string 的操作上,
28. implement strStr()





Sunday, August 30, 2015

questions other than leetcode

Q1: check if a tree is a complete binary tree
利用 BFS breadth first search, 标记第一个lack of child 的node, 如果已经发现了一个lack of child的node, 那么在这个node之后是不能再lack of child的。逻辑还是很清晰的·。
这里是不能利用DFS来遍历tree的,因为DFS遍历node的顺序不能帮助我们解决这个问题。
complete binary tree用BFS遍历之后可以获得一个array, 这个array就能代表一些问题。

class Solution {
 public:
  bool isCompleted(TreeNode* root) {
    //sanity check
    if (root == NULL) return true;
    queue<TreeNode*> explore;
    bool flag = false;//mark the first node lack of child
    explore.push(root);
    while(!explore.empty()) {
      TreeNode* tmp = explore.front();
      explore.pop();
      //check if the node lack of child
      if (flag == true) {//one  node is lack of child
        if (tmp->left == NULL && tmp->right == NULL) {}
        else return false;//if the flag is true, there should be no any child nodes afterwards
      }else {//no node lack of child until now
        if (tmp->left == NULL && tmp->right != NULL) return false; // the node has no left child node but has right child node
        if (tmp->left == NULL || tmp->right == NULL) flag = true; //the node lack of at least one child node
        if (tmp->left != NULL) explore.push(tmp->left);
        if (tmp->right != NULL) explore.push(tmp->right);
      }
    }
    //if has traversed all of the nodes and not return false, then it's a complete binary tree
    return true;
  }
};

Q2:heap sort

Q3: 倒序遍历perfect tree

Q4: 2 sum in binary search tree
这个题目有很多种方法:
M1: 比较投机取巧: 利用一个array, inorder 遍历这个BST, 把结果存到array里面,然后do 2 sum over the array, time complexity: O (n), space complexity: O(n)
M2 :   inplace + O(n) time complexity, but change the original tree structure. use recursion to change the binary search tree into double linked list using inorder traversal. then do 2 sum over the double linked list
M3:  space complexity: O(logn) + time complexity: O(n), use 2 stack to do inorder traversal over left subtree and right subtree in iterative way, from bottom to top, find the next largest node or find the next smallest node and do two sum. 利用两个阀门, 一个控制左子树的遍历(from smallest to largest),一个控制右子树的遍历(from largest to smallest),双向inorder traversal, 找到相对应的值之后看是否为sum。
M3 的实现代码:tree的 preorder traversal 和 inorder traversal的iterative 的写法非常重要

bool 2sumBST(TreeNode* root) {

stack<TreeNode*> lstack;
stack<TreeNode*> rstack;

bool openl = false;
bool openr = false;

TreeNode* cur1 = root;
TreeNode* cur2 = root;

int val1 = 0;
int val2 = 0;
while (true) {

while (openl == false) {
if (cur1 != NULL) {
lstack.push(cur1;
cur1 = cur1->left;
} else {
if (lstack.empty()) {
openl = true;
} else {
TreeNode* tmp = lstack.pop();
val1 = tmp->val;
cur1 = tmp->right;
openl = true;
}
}
}

while (openr ==  false) {
if (cur2 != NULL) {
rstack.push(cur);
cur2 = cur2->right;
} else {
if (rstack.empty()) {
openr = true;
} else {
TreeNode* tmp = rstack.pop();
val2 = tmp->val;
cur2 = tmp->left;
openr = true;
}
}

}

//check 2 sum
if (val1 != val2 && val1 + val2 == target) {
return true;
} else  if (val1 + val2 < target) {
openl = false; //go the left subtree
} else if (val1 + val2 > target) {
openr = false;  //go the right subtree
} else if (val1 >= val2) {
return false;
}
}

}
时间复杂度: O(n) bloomberg onsite 原题!

Q4: BST, 给定一个区间,删除所有区间 之外的node, 返回modify 这个树的root
How to do a  BST related problems.
需要在BST里面找出所有在区间之外的node, 并删除(delete nodes in BST), BST的题目要充分利用BST的性质,分析每个node的可能情况,对于不同的情况,怎么去处理这个node, 思维逻辑要清晰。  比如这个题目:一个node可能有两种情况:
case1: the node value is in the interval, we do nothing
case2: the node is not in the interval, if the node is smaller than min, then the left subtree of the node can be all deleted; if the node is larger than max, then the right subtree of the node can be all deleted
we can bottom-up recursion to solve this problem.
TreeNode* remove(TreeNode* root, int min, int max) {
         if (root == NULL) return NULL;
         //bottom-up recursion
        //get modified left subtree and modified right subtree
        root->left = remove(root->left, min, max);
        root->right = remove(root->right, min, max);
        // Current node do what in current level
       // case2:delete all the left subtree
       if (root->val < min)   {
              TreeNode* tmp = root->right;
               delete root;
              return tmp;
      }
      //case3: delete all the right subtree
     if (root->val > max) {
             TreeNode* tmp = root->left;
             delete root;
             return tmp;
    }
    return root;
}


Q5: 垂直遍历
这个题目主要是需要知道在同一个vertical 线上node有哪些,我们需要知道每个Node 距离原点horizontal的距离,这个可以通过go left -1, go right +1来获得,将同一个vertical上的nodes存在一个map里面,最后输出即可。

Friday, August 28, 2015

Leetcode second round 8/27

today's mission: 93-75

93: restore IP addresses

92: reverse linked list II
这个题目翻转链表指定范围内的nodes,并且要求O(N), O(1)空间,这个题目一看就感觉会有很多辅助指针,先找到m所在位置,然后开始翻转链表操作,直到n,最后再对链表进行一些修改,这个题目也是一个dummy node使用的一个例子,因为在这个过程中,链表的头结点可能被修改,所以需要用一个辅助头指针来进行corner case的处理。 这个题目大致算法不难,但是对于指针的 操作还是要小心处理,防止NULL指针的不合理操作。

91: decode way
看到这个题目求 求解方案有多少个,就感觉用一维dp来做,分析后发现和claimbing stairs差不多,一般情况下induction rule = M[i-1] + M[i-2], 但是有很多条件限制
case1: 第一位不能为'0'
case2: 当前字符如果为'0',最后那个字符不能decode, 所以此时M[i] 最多 = M[i-2], 否则, M[i] = M[i-1];
case3: 当前字符的前一个字符不为'0', 并且最后两个字符组成的int <= 26 && >= 0, M[i] += M[i-2]
这个题目这里用到一个技巧,对于string的dp,我们通常把DP数组声明成length+1,这样就更方便处理。

78: subset
90: subsetII
这两个问题都属于dfs, 第二个问题是第一个问题的follow up, 如果存在duplicates的话怎么去处理。这个问题还需要注意的一点是题目要求结果是按照升序排序的,所以我们在做之前,需要对这个数组进行sort才能得到正确的结果。
subset的DFS树,其实就是二叉树,分别代表加当前数字和不加当前数字,所以在每一层,call 两次DFS.
对于如果有duplicates的处理,也可以从DFS树看出来, 在不加当前数字那个分叉,如果当前数字 == 后面那个数字,就没有下面那个不加数字的那个分支了,直到出现新的数字为止。所以只需要在原来的基础上添加一个条件判断就可以了。
要注意是在当前层看后面那个元素,来决定当前层是否往右边那个不加元素的分支走,而不是在当前层往前看。

89: grey code
感觉这个题目还是很难发现规律,需要找到递归式推出由n-1 --> n的grey的表示方法。
n的grey表达式 = n-1的grey表达式逆向 + (1 《  (n-1)), 并且n的grey表达式的前半部分是不需要改变的。每次直接往rst里面push函数就可以了。
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> rst;
        rst.push_back(0);
        if (n == 0) return rst;
        rst.push_back(1);
        for (int i = 2; i <= n; i++) {
            int size1 = rst.size();
            for (int j = size1-1; j >= 0; j--) {
                rst.push_back(rst[j] + (1 << (i-1)));
            }
        }
        return rst;
    }
};
87: scrambling string

86: partition list
这个题目还算是简单的,但是要注意这种对原链表进行拆分的题目,不要忘记把应该断开的地方断开,不然会形成一个循环链表,死Bug。
85:maximum rectangle
84:largest rectangle in histogram

83: remove duplicates from sorted list I
82: remove duplicates from sorted listII
第一个题目很简单,slow, fast指针的移动操作, 关键是第二题之前一直用的是含有flag的那种slow , fast指针的做法,也能做出来,但是很麻烦,而且效率不高,在网上看了下别人做的solution,确实简单明了不少啊!这里把solution贴出来,很巧妙,每次比较fast 和fast->next的值是否相同,如果相同,那么就一直找,找到一个和fast不相同的值为止,然后pre指向这个值,下次如果cur->val != cur->next->val的时候,pre先向前移动一位,说明之前那个值需要留下,也说明是只出现了一次的值。 效率高了不少。从此跟flag那种做法告别了。
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL) return NULL;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        ListNode* cur = head;
        while (cur && cur->next) {
            if (cur->val == cur->next->val) {
                while (cur->next && cur->val == cur->next->val) {
                    cur = cur->next;
                }
                pre->next = cur->next;
            } else {
                pre = cur;
            }
            cur = cur->next;
        }
        return dummy->next;
    }
};

这个题目的思想应用在sorted array 去重,其实思想理解起来很简单,就是fast != fast-》next 有两种情况,这两种情况下的处理是不相同的,下面红色部分就是这两种不相同的情况下的处理方式。 每次比较当前和当前的下一个元素。 
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 1) return 1;
        int slow = -1;
        int fast = 0;
        for (; fast < nums.size(); fast++) {
            if (nums[fast] != nums[fast+1]) {
                nums[++slow] = nums[fast];
            } else {
                while (nums[fast] == nums[fast+1]) {
                    fast++;
                }
                nums[slow+1] = nums[fast+1];
            }
        }
        return slow+1;
    }
};

81:search in rotated arrayII
这个题目是含有duplicates的情况,我们需要分三种情况讨论,根据left 和 mid值的比较,容易出错的地方在于,当去判断target在不在一个范围内的时候,需要包括左右边界,即 >= left 和 <= right, 这样的话就会包含如果target就是边界数的情况.否则会出现bug.

80: remove duplicates in sorted arrayII

在sorted array里面去重, 保留两个重复字符,去重的题目有很多种类型,保留一个,保留两个,一个不留,这类题目都是可以用快慢指针来对字符串进行处理。保留两个说明一开始不管怎么样,slow可以直接放在idx = 2的位置,然后每次fast 与 slow-2位置字符进行比较。数一个不留的情况下,稍微复杂一些。

79: word search
这个题目是搜索单词,能直接想到的方法是对每一个与word的第一个char相等的位置进行DFS+back tracing, 这里用到back tracing的原因是每次回退到某一个位置,从另一个path走,之前走过的也都是unvisited的,可以再次搜索。因为这里的DFS其实是属于穷尽搜索,需要走遍所有的可能路径去搜索确定的路径。当穷尽搜索的时候,即必须走过所有可能路径的时候我们才需要用到DFS+back tracing, 如果只是一般搜索的时候,就可以用DFS+ mark visitI来做,效果类似BFS。
还要注意一点的是,结束条件要小心,比如这个题目我一开始的结束条件写成了: if (idx == word.size()) return true; 但是后面做的操作,有比较word[idx+1] == ..这样的话如果此时idx == word.size()-1,就会发生越界,所以我们的结束条件,应该是 if (idx == word.size()-1) return true;,所以在写程序的时候不能总是按惯性去写,不同的题目处理问题方式不同,代码也有所改变,要防止发生一些小bug。还有一个地方容易出错就是如果当前访问的node之前已经访问过了,是return true? false? 这个都要通过含义去判断。
这个题目我觉得比一般的DFS要难一些,因为加上了另外一个条件的判断,需要同时去匹配字符,结束条件相应多了一条,并且对于二维矩阵的DFS mark visited的做法,一般是不需要另外去开辟另一个二维矩阵来mark visited的,可以直接以一个特殊字符比如“#”来代表已经访问过,这样就节省了很多空间。

77: combination
DFS求所有解的问题,画出DFS树出来,然后就能正确地写出程序了。树的每一层代表什么含义,每一层有多个叉。DFS循环调用多少次。还有一个 cur level来记录有没有到达树的最后一层,即一条path有没有结束。

76: minimum window substring
这个题目属于sliding window里面好写的一类题,就是变长的sliding window, 由两个指针模拟窗口,先right指针走,并且同时匹配字符,如果完全匹配,此时固定right, 移动left, 每次移出的元素要在map里面还原,如果还原之后,仍然所有字符match, 那么仍然移动left,并且每次更新最小值,直到不再match,再去移动right,直至right移动到string 尾部。
时间复杂度O(2 *n),right和left指针都只是从头到尾分别遍历一遍字符串。

75: sorted colors
这个是属于quick sort partition的变形, quick sort partition是一个挡板,一个指针,这个题目是用了两个挡板,1个指针,但是特别需要注意的是sort k colors,不能再继续用挡板法来做了,对于2->k的实现,只要利用分而治之,每次sort好首尾两个颜色,这样时间复杂度O(K/2 * N),空间复杂度为O(1)

88: merge sorted array
这个题目看似简单,但是跟之前merge不同的是,要求inplace merge, 我们不能开辟一个新的数组空间, 但是因为nums1的空间足够大, 我们可以将nums1看做是结果数组,如果从前往后进行merge的话,会出现nums2 覆盖nums1的情况,我们可以从后往前进行merge,这样的话nums1就相当于一个新的数组了。
这个图能够很好地表示这个题目中的思想。3个指针,1个指向nums1 n处, nums2的m处,最后那个指向nums1的n+m-1处。





Thursday, August 27, 2015

new questions other than leetcode(not done yet)

Q1: Robin-Karp
进行字符串匹配,Strstr, 利用对字符串进行hashing的做法,pattern : p (hash value for pattern), txt: t (hash value for txt) , hash value的计算: 基数*rst + 当前字符对应的ascII整数,这里基数是256(ascII个数),还需要一个h值,是pattern最高位的系数,方便后面移动窗口时下一个txt的计算,下一个txt的t = (d*(t - txt[i]* h) + txt[i+M])%q,  去掉上一个的最高位,剩下的往左移,再加上新的元素值。q: 取的一个prime number, 为了避免当pattern字符串很长的时候,p的值会非常大,模q的话可以保证hash值在一个范围内。 当每次window内的值p == t的时候,我们就只需要去check这个window内的每一个char是否与pattern 匹配,如果匹配就找到了一个match, 如果不匹配,就继续sliding window.

// d is the number of characters in input alphabet
#define d 256
  
/*  pat  -> pattern
    txt  -> text
    q    -> A prime number
*/
void search(char *pat, char *txt, int q)
{
    int M = strlen(pat);
    int N = strlen(txt);
    int i, j;
    int p = 0;  // hash value for pattern
    int t = 0; // hash value for txt
    int h = 1;
  
    // The value of h would be "pow(d, M-1)%q"
    for (i = 0; i < M-1; i++)
        h = (h*d)%q;
  
    // Calculate the hash value of pattern and first window of text
    for (i = 0; i < M; i++)
    {
        p = (d*p + pat[i])%q;
        t = (d*t + txt[i])%q;
    }
  
    // Slide the pattern over text one by one
    for (i = 0; i <= N - M; i++)
    {
        
        // Check the hash values of current window of text and pattern
        // If the hash values match then only check for characters on by one
        if ( p == t )
        {
            /* Check for characters one by one */
            for (j = 0; j < M; j++)
            {
                if (txt[i+j] != pat[j])
                    break;
            }
            if (j == M)  // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
            {
                printf("Pattern found at index %d \n", i);
            }
        }
         
        // Calculate hash value for next window of text: Remove leading digit,
        // add trailing digit          
        if ( i < N-M )
        {
            t = (d*(t - txt[i]*h) + txt[i+M])%q;
             
            // We might get negative value of t, converting it to positive
            if(t < 0)
              t = (t + q);
        }
    }
}
Q2: Counting sort && Radix sort

Q3: 正则表达式匹配

Q4:检查两个字符是否是rotated的,比如: abcade->cadeab true
case1: 如果这个string里面有重复字符,一个很tricky的做法是把第一个字符串copy一份放到自己的后面,然后查看第二个字符串是不是新字符串的子串。比如: abcadeabcade -> cadeab,如果是子串,那么这两个字符就是rotated的。
case2: 如果这个string里面没有重复字符,这个题目可以很巧妙地利用快慢指针来解,
abcade
s
   f     f
cadeab
i     i

Q5: design 类题目
          前缀提示器: 比如输入 “ab”, 在提示框里能够显示给定词库里所有以ab为头的词,并且支持添加,查找,删除的功能。

Q6: oodesign

建立一个10位电话号码查询类,查找每个电话对应的人名。