Monday, December 31, 2012

[LeetCode] Roman To Integer 解题报告


Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
» Solve this problem

[解题思路]

从前往后扫描,用一个临时变量记录分段数字。
  • 如果当前比前一个大,说明这一段的值应该是当前这个值减去上一个值。比如IV = 5 – 1
  • 否则,将当前值加入到结果中,然后开始下一段记录。比如VI = 5 + 1, II=1+1



[Code]
1:    inline int c2n(char c) {  
2:      switch(c) {  
3:        case 'I': return 1;  
4:        case 'V': return 5;  
5:        case 'X': return 10;  
6:        case 'L': return 50;  
7:        case 'C': return 100;  
8:        case 'D': return 500;  
9:        case 'M': return 1000;  
10:        default: return 0;  
11:      }  
12:    }  
13:    int romanToInt(string s) {  
14:      // Start typing your C/C++ solution below  
15:      // DO NOT write int main() function  
16:      int result=0;  
17:      for(int i =0; i< s.size(); i++)  
18:      {  
19:        if(i>0&& c2n(s[i]) > c2n(s[i-1]))  
20:        {  
21:          result +=(c2n(s[i]) - 2*c2n(s[i-1]));  
22:        }  
23:        else  
24:        {  
25:          result += c2n(s[i]);  
26:        }  
27:      }  
28:      return result;  
29:    }  


关联题:
http://fisherlei.blogspot.com/2012/12/leetcode-integer-to-roman.html



[LeetCode] Reverse Nodes in k-Group 解题报告


Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
» Solve this problem

[解题思路]
同上一题,每K个元素,翻转一次。最后一次如果不到K,再翻转回来即可。代码中链表翻转的code可以拆分成单独函数,这里懒得再refactor了。

[Code]
1:      ListNode *reverseKGroup(ListNode *head, int k) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      ListNode* safeG = new ListNode(-1);  
5:         safeG->next = head;            
6:            if(head == NULL || k==1) return head;  
7:            ListNode* pre = safeG, *cur = head, *post = head->next;  
8:            while(cur!=NULL)  
9:            {  
10:                 post = cur->next;  
11:                 int i =0;  
12:                 while(i<k-1 && post!=NULL)  
13:                 {  
14:                      ListNode *temp = post->next;  
15:                      post->next = cur;  
16:                      cur = post;  
17:                      post = temp;  
18:                      i++;  
19:                 }  
20:                 if(i!=k-1)                 
21:                 {  
22:                      int k =0;  
23:                      ListNode * temp = post;  
24:                      post = cur;  
25:                      cur = temp;  
26:                      while(k<i)  
27:                      {  
28:                           temp = post->next;  
29:                           post->next = cur;  
30:                           cur = post;  
31:                           post = temp;  
32:                           k++;  
33:                      }  
34:                      break;  
35:                 }  
36:                 ListNode* temp = pre->next;  
37:                 pre->next = cur;  
38:                 temp->next = post;  
39:                 pre = temp;  
40:                 cur = pre->next;  
41:            }  
42:            head = safeG->next;  
43:            delete safeG;  
44:            return head;  
45:    }  

[LeetCode] Reverse Linked List II 解题报告

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m  n ≤ length of list.
» Solve this problem

[解题思路]
分三步走
1. 找到m节点的前一个指针pre(加个safe guard可避免头指针的问题)
2. 从m节点开始往后reverse N个节点(双指针,cur,post)
3. 合并pre链表,cur链表及post链表。

这题难就难在繁琐上,要考虑各种边界条件,比如
{1,2,3}, 3,3
{1,2,3}, 1,1
{1,2,3}, 1,3
所以,code中需要添加一些边界检查条件。这题15分钟以内bug free我是做不到。

1:       ListNode *reverseBetween(ListNode *head, int m, int n) {   
2:            // Start typing your C/C++ solution below   
3:            // DO NOT write int main() function   
4:            int step = n-m;   
5:            ListNode* safeG = new ListNode(-1); //intro a safe guard to avoid handle head case  
6:            safeG->next = head;   
7:            head = safeG;   
8:            ListNode* pre = head;   
9:            while(m>1)   
10:            {   
11:                 pre=pre->next;   
12:                 m--;   
13:            }   
14:            ListNode* cur = pre->next, *post = cur->next;   
15:            if(step>=1)   
16:            {   
17:                 while(step>0 && post!=NULL)   
18:                 {   
19:                      ListNode* temp = post->next;   
20:                      post->next = cur;   
21:                      cur = post;   
22:                      post = temp;   
23:                      step--;   
24:                 }   
25:                 ListNode* temp = pre->next;   
26:                 pre->next = cur;   
27:                 temp->next = post;   
28:            }   
29:            safeG = head;   
30:            head = head->next;   
31:            delete safeG;   
32:            return head;     
33:       }   

Update: 3/19/2013. SafeG在这里没有意义。

Update 3/6/2014. 又看了一遍,SafeG还是有必要的,避免对于head的处理。

[LeetCode] Reverse Integer 解题报告

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).
» Solve this problem

[解题思路]
如果是用字符串来逆序的话,需要考虑0的特殊性,但是如果直接用一个integer来滚动生成的话,0就不是问题了。
当然,溢出的问题是存在的,所以return -1。

[Code]
1:    int reverse(int x) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int lastDigit = 0;  
5:      int result = 0;  
6:      bool isNeg = x>0? false:true;  
7:      x = abs(x);  
8:      while(x>0)  
9:      {  
10:        lastDigit = x%10;  
11:        result = result*10 + lastDigit;  
12:        x = x/10;  
13:      }  
14:      if(result<0) return -1;  
15:      if(isNeg)  
16:        result *=-1;  
17:      return result;      
18:    }  



Version 2, Refactor code, 3/5/2012
Rethink for a while. And actually, we don't need to use special logic to handle '+' and '-', because the sign can be kept during calculating. Only 8 lines can resolve this problem.
1:       int reverse(int x) {  
2:            int newN =0, left =0;  
3:            while(x != 0)  
4:            {  
5:                 left = x%10;  
6:                 newN = newN*10 + left;  
7:                 x = x/10;  
8:            }  
9:            return newN;  
10:       }  


[LeetCode] Restore IP Addresses 解题报告

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
» Solve this problem

[解题思路]
递归的将数字串分成四个部分,每个部分满足0<=p<=255。要注意一些边界case,比如010是没有意思的,“0.10.010.1”。

1:       vector<string> restoreIpAddresses(string s) {   
2:            vector<string> col;   
3:            string ip;   
4:            partitionIP(s, 0, 0, ip, col);   
5:            return col;   
6:       }   
7:       void partitionIP(string s, int startIndex, int partNum,    
8:       string resultIp, vector<string>& col)   
9:       {   
10:            //max: 3 bits per partition   
11:            if(s.size() - startIndex > (4-partNum)*3) return;   
12:            //min: 1 bit per partition   
13:            if(s.size() - startIndex < (4-partNum)) return;  
14:            if(startIndex == s.size() && partNum ==4)   
15:            {   
16:                 resultIp.resize(resultIp.size()-1);   
17:                 col.push_back(resultIp);   
18:                 return;   
19:            }   
20:            int num =0;   
21:            for(int i = startIndex; i< startIndex +3; i++)   
22:            {   
23:                 num = num*10 + (s[i]-'0');   
24:                 if(num<=255)   
25:                 {   
26:                      resultIp+=s[i];   
27:                      partitionIP(s, i+1, partNum+1, resultIp+'.', col);       
28:                 }    
29:                 if(num ==0)//0.0.0.0 valid, but need to avoid 0.1.010.01   
30:                 {   
31:                      break;   
32:                 }   
33:            }   
34:       }   



Sunday, December 30, 2012

[LeetCode] Remove Nth Node From End of List 解题报告


Given a linked list, remove the nth node from the end of list and return its head.
For example,
   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
» Solve this problem

[解题思路]
经典题。双指针,一个指针先走n步,然后两个同步走,直到第一个走到终点,第二个指针就是需要删除的节点。唯一要注意的就是头节点的处理,比如,
1->2->NULL, n =2; 这时,要删除的就是头节点。


[Code]
1:    ListNode *removeNthFromEnd(ListNode *head, int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      assert(head);  
5:      ListNode* pre, *cur;  
6:      pre = head;cur = head;  
7:      int step = 0;  
8:      while(step< n && cur!=NULL)  
9:      {  
10:        cur = cur->next;  
11:        step++;  
12:      }  
13:      if(step ==n && cur == NULL)  
14:      {  
15:        head = head->next;  
16:        delete pre;  
17:        return head;  
18:      }  
19:      while(cur->next!=NULL)  
20:      {  
21:        pre = pre->next;  
22:        cur = cur->next;  
23:      }  
24:      ListNode* temp = pre->next;  
25:      pre->next = temp->next;  
26:      delete temp;      
27:      return head;  
28:    }  


[LeetCode] Remove Element 解题报告


Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
» Solve this problem

[解题思路]
双指针。

[Code]
1:    int removeElement(int A[], int n, int elem) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int cur = 0;  
5:      for(int i =0; i< n; i++)  
6:      {  
7:        if(A[i] == elem)  
8:          continue;  
9:        A[cur]=A[i];  
10:        cur++;  
11:      }  
12:      return cur;  
13:    }  


[LeetCode] Remove Duplicates from Sorted List 解题报告


Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
» Solve this problem

[解题思路]
同样是双指针,但是这里要注意delete不用的节点。

[Code]
1:    ListNode *deleteDuplicates(ListNode *head) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      if(head == NULL) return NULL;  
5:      ListNode * pre = head;  
6:      ListNode *p = head->next;  
7:      while(p!=NULL)  
8:      {  
9:        if(pre->val == p->val)  
10:        {  
11:          ListNode* temp = p;  
12:          p = p->next;  
13:          pre->next =p;  
14:          delete temp;  
15:          continue;  
16:        }  
17:        pre = pre->next;  
18:        p = p->next;  
19:      }  
20:      return head;  
21:    }  





[LeetCode] Remove Duplicates from Sorted Array II 解题报告


Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].
» Solve this problem


[解题思路]
加一个变量track一下字符出现次数即可,这题因为是已经排序的数组,所以一个变量即可解决。但是如果是没有排序的数组,可以引入一个hashmap来处理出现次数。

[Code]
1:    int removeDuplicates(int A[], int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      if(n<=1) return n;  
5:      int pre=1, cur =1;  
6:      int occur = 1;  
7:      while(cur<n)  
8:      {  
9:        if(A[cur] == A[cur-1])  
10:        {  
11:          if(occur >=2)  
12:          {  
13:            cur++;          
14:            continue;  
15:          }  
16:          else  
17:          {  
18:            occur++;  
19:          }  
20:        }  
21:        else  
22:        {  
23:          occur = 1;   
24:        }        
25:        A[pre] = A[cur];  
26:        pre++;  
27:        cur++;        
28:      }  
29:      return pre;  
30:    }  

Update 03/09/2014  improve readability a bit.

1:       int removeDuplicates(int A[], int n) {  
2:            if(n == 0) return 0;  
3:            int occur = 1;  
4:            int index = 0;  
5:            for(int i =1; i< n; i++)  
6:            {  
7:                 if(A[index] == A[i])  
8:                 {  
9:                      if(occur == 2)  
10:                      {  
11:                           continue;  
12:                      }  
13:                      occur++;  
14:                 }  
15:                 else  
16:                 {  
17:                      occur =1 ;  
18:                 }  
19:                 A[++index] = A[i];  
20:            }  
21:            return index+1;  
22:       }  







[LeetCode] Remove Duplicates from Sorted Array 解题报告


Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].
» Solve this problem

[解题思路]
二指针问题。一前一后扫描。


[Code]
1:    int removeDuplicates(int A[], int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int pre, cur;  
5:      pre = 1; cur = 1;  
6:      if(n <=1) return n;  
7:      while(cur<n)  
8:      {  
9:        if(A[cur] == A[cur-1])  
10:        {  
11:          cur++;  
12:          continue;  
13:        }  
14:        A[pre] = A[cur];  
15:        pre++;  
16:        cur++;  
17:      }  
18:      return pre;  
19:    }  


Updated. 3/9/2013
1:    int removeDuplicates(int A[], int n) {  
2:      if(n ==0) return 0;  
3:      int index = 0;  
4:      for(int i =0;i<n; i++)  
5:      {  
6:        if(A[index] == A[i])  
7:        {  
8:          continue;  
9:        }  
10:        index++;  
11:        A[index] = A[i];  
12:      }  
13:      return index+1;  
14:    }  


[LeetCode] Pow(x, n) 解题报告


Implement pow(xn).
» Solve this problem


[解题思路]
二分法,注意n<0的情况。

[Code]
1:    double power(double x, int n)  
2:    {  
3:       if (n == 0)  
4:         return 1;  
5:       double v = power(x, n / 2);  
6:       if (n % 2 == 0)  
7:         return v * v;  
8:       else  
9:         return v * v * x;  
10:     }  
11:     double pow(double x, int n) {  
12:       // Start typing your C/C++ solution below  
13:       // DO NOT write int main() function  
14:       if (n < 0)  
15:         return 1.0 / power(x, -n);  
16:       else  
17:         return power(x, n);      
18:     }  





[LeetCode] Recover Binary Search Tree 解题报告


Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
» Solve this problem

[解题报告]
O(n)空间的解法比较直观,中序遍历一遍以后,重新赋值一遍即可,这个解法可以面向n个元素错位的情况。但是对于O(1)空间的解法,最开始的想法是,可以考虑采用类似最大堆的调正过程的算法,但是这样又可能会破坏树的原有结构。暂未想出来解法。

只能给个O(n)空间的解法。

[Code]
1:    void recoverTree(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<TreeNode*> list;  
5:      vector<int > vals;  
6:         InOrderTravel(root, list, vals);  
7:            sort(vals.begin(), vals.end());  
8:            for(int i =0; i< list.size(); i++)  
9:            {  
10:                 list[i]->val = vals[i];  
11:            }            
12:    }  
13:       void InOrderTravel(TreeNode* node, vector<TreeNode*>& list, vector<int>& vals)  
14:       {  
15:            if(node == NULL) return;  
16:            InOrderTravel(node->left, list, vals);  
17:            list.push_back(node);  
18:            vals.push_back(node->val);  
19:            InOrderTravel(node->right, list, vals);            
20:       }  

Updates:  3/16/2013
Searched in the web. Actually, there is a smart solution to travel the tree with two node.
The link is http://discuss.leetcode.com/questions/272/recover-binary-search-tree

1:  void Solution::recoverTree(TreeNode *h) {  
2:    TreeNode *f1=NULL, *f2=NULL;  
3:    bool found = false;  
4:    TreeNode *pre, *par = 0; // previous AND parent  
5:    while(h) { // Morris Traversal  
6:      if(h->left == 0) {  
7:        if(par && par->val > h->val) { // inorder previous is: par  
8:          if(!found) {  
9:            f1 = par;  
10:            found = true;  
11:          }  
12:          f2 = h;  
13:        }  
14:        par = h;  
15:        h = h->right;  
16:        continue;  
17:      }  
18:      pre = h->left;  
19:      while(pre->right != 0 && pre->right != h)   
20:        pre = pre->right;  
21:      if(pre->right == 0) {  
22:        pre->right = h;  
23:        h = h->left;  
24:      } else {  
25:        pre->right = 0;  
26:        if(pre->val > h->val) { // inorder previous is: pre  
27:          if(!found) {  
28:            f1 = pre;  
29:            found =true;  
30:          }  
31:          f2 = h;  
32:        }  
33:        par = h;  
34:        h = h->right;  
35:      }  
36:    }  
37:    if(found)  
38:      swap(f1->val, f2->val);  
39:  }  


Update: 3/21/2013  上一个解法不容易看清楚,添加分析。
O(1)的解法就是
Inorder traverse, keep the previous tree node,
Find first misplaced node by
if ( current.val < prev.val )
   Node first = prev;

Find second by
if ( current.val < prev.val )
   Node second = current;

After traversal, swap the values of first and second node. Only need two pointers, prev and current node. O(1) space.

但是这个解法的前提是Traverse Tree without Stack. 中序遍历如何才能不使用栈。这里就要引入一个概念, Threaded Binary Tree。So, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.

1. Initialize current as root 
2. While current is not NULL
   If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as right child of the rightmost node in current's left subtree
      b) Go to this left child, i.e., current = current->left


代码如下:

/* Function to traverse binary tree without recursion and without stack */
vector<int> inorderTraversal(TreeNode *root)
{
       vector<int> result;  
       TreeNode  *current,*pre;

       if(root == NULL)
       return result;

       current = root;
       while(current != NULL)
       {                
             if(current->left == NULL)
             {
                    result.push_back(current->val);
                    current = current->right;     
             }   
             else
             {
                    /* Find the inorder predecessor of current */
                    pre = current->left;
                    while(pre->right != NULL && pre->right != current)
                           pre = pre->right;

                    /* Make current as right child of its inorder predecessor */
                    if(pre->right == NULL)
                    {
                           pre->right = current;
                           current = current->left;
                    }
                   
                    /* Revert the changes made in if part to restore the original
                 tree i.e., fix the right child of predecssor */  
                    else
                    {
                           pre->right = NULL;
                           result.push_back(current->val);
                           current = current->right;     
                    } /* End of if condition pre->right == NULL */
             } /* End of if condition current->left == NULL*/
       } /* End of while */

       return result;
}


那么,基于这个双指针遍历,可以把错置节点的判断逻辑加进去,就可以完美的在O(1)空间内,完成树的重构。

[Code]
改动代码如红字所示。增加了一个pointer -- parent来记录上一个访问节点。整个遍历过程中,使用(parent->val > current->val)来寻找违规节点,但是区别是,要获取第一次violation的parent和第二次violation的current,然后交换。

void recoverTree(TreeNode *root)
{     
       TreeNode *f1=NULL, *f2=NULL;
       TreeNode  *current,*pre, *parent=NULL;

       if(root == NULL)
             return;
       bool found = false;
       current = root;
       while(current != NULL)
       {                
             if(current->left == NULL)
             {
                    if(parent && parent->val > current->val)
                    {
                           if(!found)
                           {
                                 f1 = parent;
                                 found = true;
                           }
                           f2 = current;
                    }
                    parent = current;
                    current = current->right;     
             }   
             else
             {
                    /* Find the inorder predecessor of current */
                    pre = current->left;
                    while(pre->right != NULL && pre->right != current)
                           pre = pre->right;

                    /* Make current as right child of its inorder predecessor */
                    if(pre->right == NULL)
                    {
                           pre->right = current;
                           current = current->left;
                    }

                    /* Revert the changes made in if part to restore the original
                    tree i.e., fix the right child of predecssor */  
                    else
                    {
                           pre->right = NULL;
                           if(parent->val > current->val)
                           {
                                 if(!found)
                                 {
                                        f1 = parent;       
                                        found = true;
                                 }
                                 f2 = current;
                           }
                           parent = current;
                           current = current->right;     
                    } /* End of if condition pre->right == NULL */
             } /* End of if condition current->left == NULL*/
       } /* End of while */

       if(f1 && f2)
             swap(f1->val, f2->val);
}