## 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

[解题思路]

[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);
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:            }
43:            delete safeG;
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

``````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
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:            }
31:            delete safeG;
33:       }
``````

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

### [LeetCode] Reverse Integer 解题报告

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
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

[解题思路]

[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

[解题思路]

``````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

[解题思路]

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
5:      ListNode* pre, *cur;
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:      {
16:        delete pre;
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;
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

[解题思路]

[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;
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:      }
21:    }
``````

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

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

[解题思路]

[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

[解题思路]

[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)空间的解法，最开始的想法是，可以考虑采用类似最大堆的调正过程的算法，但是这样又可能会破坏树的原有结构。暂未想出来解法。

[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:       }
``````

Searched in the web. Actually, there is a smart solution to travel the tree with two node.

``````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.

```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;
}

[Code]

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);
}