[Leetcode] Search a 2D Matrix II, Solution

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

[Thoughts]
双指针搜索。只不过因为数组的特殊排序，要从最右上角开始搜索，比如上例中的15.


[Code]

1:    bool searchMatrix(vector<vector<int>>& matrix, int target) {  
2:      int rows = matrix.size();  
3:      if(rows == 0) return false;  
4:      int cols = matrix[0].size();  
5:        
6:      int i = 0, j = cols-1;  
7:      while(j>=0 && i< rows) {  
8:        if(matrix[i][j] == target) return true;  
9:          
10:        if(matrix[i][j] < target) i++;  
11:        else j--;  
12:      }  
13:      return false;  
14:    }  

[Leetcode] Reverse Vowels of a String, Solution

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = "hello", return "holle".

Example 2:
Given s = "leetcode", return "leotcede".

Note:
The vowels does not include the letter "y".

[Thoughts]
双指针扫描。一个从头部，一个从尾部，发现vowel就swap。

[Code]

1:    string reverseVowels(string s) {  
2:      set<char> vowels{'a', 'o', 'e', 'i', 'u', 'A', 'O', 'E', 'I', 'U'};  
3:        
4:      for(int i =0, j = s.size()-1; i< j; ) {  
5:        if(vowels.find(s[i]) == vowels.end()) {  
6:          i++;   
7:          continue;  
8:        }  
9:          
10:        if(vowels.find(s[j]) == vowels.end()) {  
11:          j--;  
12:          continue;  
13:        }  
14:          
15:        swap(s[i], s[j]);  
16:        i++;  
17:        j--;  
18:      }  
19:        
20:      return s;  
21:    }  

[Leetcode] Ugly Number II, Solution

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

[Thoughts]

这就是多链表Merge Sort的一个扩展题。

对于任意一个ugly number - K, 2*K, 3*K, 和5*K都是ugly number，所以说新的ugly number都是从已有的ugly number上，通过与{2,3,5}相乘而产生的。

如果

Ugly Number:       1,         2,          3,           4,           5,           6,            8,         10,     ..............

那么                      1*2      2*2        3*2         4*2         5*2         6*2         8*2        10*2  .............. *2

                             1*3      2*3        3*3         4*3         5*3         6*3         8*3        10*3  .............. *3

                             1*5      2*5        3*5         4*5         5*5         6*5         8*5        10*5  .............. *5

都是ugly number。只要不断把新产生的ugly number通过merge sort添加到原有的ugly number数组中就可以了，直到找到第N个。

[Code] 

1:  class Solution {  
2:  public:  
3:    int nthUglyNumber(int n) {  
4:      vector<int> uglys(1, 1);  
5:      int p2 = 0, p3 = 0, p5 = 0;  
6:      while (uglys.size() < n) {  
7:        int ugly2 = uglys[p2] * 2, ugly3 = uglys[p3] * 3, ugly5 = uglys[p5] * 5;  
8:        int min_v = min(ugly2, min(ugly3, ugly5));  
9:        if (min_v == ugly2) ++p2;  
10:        if (min_v == ugly3) ++p3;  
11:        if (min_v == ugly5) ++p5;  
12:        if(min_v != uglys.back()) {  
13:          // skip duplicate  
14:          uglys.push_back(min_v);  
15:        }  
16:      }  
17:      return uglys[n-1];  
18:    }  
19:  };  

考虑到通用性，可以扩展如下，可以支持任意长度的因子数组factors。

1:  class Solution {  
2:  public:  
3:    int nthUglyNumber(int n) {  
4:      vector<int> factors{ 2, 3, 5};  
5:      return nthUglyNumberGeneral(n, factors);  
6:    }  
7:    int nthUglyNumberGeneral(int n, vector<int>& factors) {  
8:      vector<int> uglys(1,1);  
9:      vector<int> indexes(factors.size(), 0);  
10:      while(uglys.size() < n) {  
11:        int min_v = INT_MAX;  
12:        int min_index = 0;  
13:        for(int k =0; k< factors.size(); k++) {  
14:          int temp = uglys[indexes[k]] * factors[k];  
15:          if(temp < min_v) {  
16:            min_v = temp;  
17:            min_index = k;  
18:          }  
19:        }  
20:        indexes[min_index]++;  
21:        // need to avoid duplicate ugly number  
22:        if(uglys[uglys.size()-1] != min_v) {  
23:          uglys.push_back(min_v);  
24:         }  
25:      }  
26:      return uglys[n-1];  
27:    }  
28:  };  

从空间的优化来说，没有必要用一个uglys的数组保存所有的ugly number，尤其是当n是个非常大的数字。对于indexes指针扫过的ugly number，都可以丢掉了。不过，懒得写了。

[Leetcode] Move Zeroes, Solution

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

[Thoughts]

典型的双指针问题。使用两个指针遍历数组，一个指向数值为0的元素，另一个指向数值不为0的元素，在遍历的过程中，不断交换两个指针的值。

例如，

比较简单的一道题。

[Code]

1:  class Solution {  
2:  public:  
3:    void moveZeroes(vector<int>& nums) {  
4:      for(int zero_index = 0, none_zero_index = 0;  
5:        none_zero_index < nums.size() && zero_index < nums.size();   
6:      ) {  
7:        if(nums[zero_index] != 0) {  
8:          zero_index++;  
9:          none_zero_index = zero_index;  
10:          continue;  
11:        }   
12:        if(nums[none_zero_index] == 0) {  
13:          none_zero_index++;  
14:          continue;  
15:        }  
16:        int temp = nums[zero_index];  
17:        nums[zero_index] = nums[none_zero_index];  
18:        nums[none_zero_index] = temp;  
19:        zero_index++;  
20:        none_zero_index++;  
21:      }  
22:    }  
23:  };  

git: https://github.com/codingtmd/leetcode/blob/master/src/Move_Zeroes.cpp

[LeetCode] Reorder List, Solution

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

[Thoughts]

目前想到的解法是，分三步来做：

1. 找出中间节点

2. 把中间节点之后的后半部分链表反序

3. 把前半部分链表及后半部分链表合并

 

[Code]

三步走解法

 1     void reorderList(ListNode *head) {
 2         if(head == NULL) return;
 3         // find the median node
 4         ListNode* fast = head;
 5         ListNode* slow = head;
 6         while(true)
 7         {
 8             fast = fast->next;
 9             if(fast == NULL)
10                 break;
11             fast = fast->next;
12             if(fast == NULL)
13                 break;
14             slow = slow->next;
15         }
16         
17         if(slow == NULL) return;
18         
19         // reverse second half of link list
20         ListNode* cur = slow;
21         ListNode* pre = slow->next;
22         cur->next = NULL;
23         while(pre!=NULL)
24         {
25             ListNode* temp = pre->next;
26             pre->next = cur;
27             cur = pre;
28             pre = temp;
29         }
30         
31         // merge two lists
32         ListNode* first = head;
33         ListNode* second = cur;
34         
35         while(second!= NULL&& first!=NULL && first!=second)
36         {
37             ListNode* temp = second->next;
38             second->next = first->next;
39             first->next = second;
40             first = second->next;
41             second = temp;
42         }
43     }

应该有更漂亮的解法，还在思考中。

[LeetCode] Remove Duplicates from Sorted List II, Solution

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

» Solve this problem

[Thoughts]
实现题。前面加一个Safeguard，这样可以避免处理头结点的复杂。

[Code]

1:       ListNode *deleteDuplicates(ListNode *head) {  
2:            if(head == NULL) return head;  
3:            ListNode *G = new ListNode(INT_MIN);  
4:            G->next = head;  
5:            ListNode *cur = G, *pre = head;  
6:            while(pre!=NULL)  
7:            {  
8:                 bool isDup = false;  
9:                 while(pre->next!=NULL && pre->val == pre->next->val)  
10:                 {  
11:                      isDup = true;  
12:                      ListNode *temp = pre;  
13:                      pre = pre->next;  
14:                      delete temp;  
15:                 }  
16:                 if(isDup)  
17:                 {  
18:                      ListNode *temp = pre;  
19:                      pre = pre->next;  
20:                      delete temp;  
21:                      continue;  
22:                 }  
23:                 cur->next = pre;  
24:                 cur = cur->next;  
25:                 pre= pre->next;  
26:            }  
27:            cur->next = pre;  
28:            ListNode *temp = G->next;  
29:            delete G;  
30:            return temp;      
31:       }  

[LeetCode] Two Sum, Solution

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

» Solve this problem

[Thoughts]
两种解法。
解法一， hash
从左往右扫描一遍，然后将数及坐标，存到map中。然后再扫描一遍即可。时间复杂度O(n)

解法二，双指针扫描
将数组排序，然后双指针从前后往中间扫描。时间复杂度O(n*lgn)。因为是要求返回原数组的下标，所以在排序的时候还得有额外的数组来存储下标信息， 也挺麻烦。

解法三，暴力搜索
这个倒是最省事的。时间复杂度O(n*n)

解法一实现如下：

1:    vector<int> twoSum(vector<int> &numbers, int target) {  
2:      map<int, int> mapping;  
3:      vector<int> result;  
4:      for(int i =0; i< numbers.size(); i++)  
5:      {  
6:        mapping[numbers[i]]=i;  
7:      }  
8:      for(int i =0; i< numbers.size(); i++)  
9:      {  
10:        int searched = target - numbers[i];  
11:        if(mapping.find(searched) != mapping.end())  
12:        {  
13:          result.push_back(i+1);  
14:          result.push_back(mapping[searched]+1);  
15:          break;  
16:        }  
17:      }  
18:      return result;  
19:    }  

解法二

1:       struct Node  
2:       {  
3:            int val;  
4:            int index;      
5:            Node(int pVal, int pIndex):val(pVal), index(pIndex){}  
6:       };  
7:       static bool compare(const Node &left, const Node &right)  
8:       {  
9:            return left.val < right.val;  
10:       }  
11:       vector<int> twoSum(vector<int> &numbers, int target) {  
12:            vector<Node> elements;  
13:            for(int i =0; i< numbers.size(); i++)  
14:            {  
15:                 elements.push_back(Node(numbers[i], i));  
16:            }  
17:            std::sort(elements.begin(), elements.end(), compare);  
18:            int start = 0, end = numbers.size()-1;  
19:            vector<int> result;  
20:            while(start < end)  
21:            {  
22:                 int sum = elements[start].val + elements[end].val;  
23:                 if(sum == target)  
24:                 {  
25:                      result.push_back(elements[start].index+1);  
26:                      if(elements[start].index < elements[end].index)  
27:                           result.push_back(elements[end].index+1);  
28:                      else  
29:                           result.insert(result.begin(),elements[end].index+1);  
30:                      break;  
31:                 }  
32:                 else if(sum > target)  
33:                      end--;  
34:                 else  
35:                      start++;                 
36:            }  
37:            return result;  
38:       }  

解法三，两个循环嵌套搜索，不写了。

[LeetCode] Valid Palindrome, Solution

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

» Solve this problem

[Thoughts]
Two pointer. From both sides to middle.


[Code]

1:       bool isPalindrome(string s) {  
2:            int start = 0;  
3:            int end = s.size()-1;  
4:            std::transform(s.begin(), s.end(), s.begin(), ::tolower);  
5:            while(start<end)  
6:            {  
7:                 while(start< end && !isAlpha(s[start])) start++;  //filter non-alpha char
8:                 while(start< end && !isAlpha(s[end])) end--;  //filter non-alpha char
9:                 if(s[start]!=s[end]) break;        
10:                 start++;  
11:                 end--;  
12:            }  
13:            if(start >= end)  
14:                 return true;  
15:            else  
16:                 return false;        
17:       }  
18:       bool isAlpha(char c)  
19:       {  
20:            if(c>='a' && c<='z') return true;     
21:            if(c>='0' && c<='9') return true;  
22:            return false;  
23:       }  

[LeetCode] 3 Sum, Solution

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

» Solve this problem

[Thoughts]
Two-pointer scan.

[Code]

1:    vector<vector<int> > threeSum(vector<int> &num) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      std::sort(num.begin(), num.end());  
5:      vector<vector<int> > result;  
6:      int len = num.size();  
7:      for(int i =0; i< len; i++)  
8:      {  
9:        int target = 0-num[i];  
10:        int start = i+1, end =len-1;  
11:        while(start<end)  
12:        {  
13:          if(num[start] + num[end] == target)  
14:          {  
15:            vector<int> solution;  
16:            solution.push_back(num[i]);  
17:            solution.push_back(num[start]);  
18:            solution.push_back(num[end]);  
19:            result.push_back(solution);  
20:            start++; end--;  
21:            while(start<end && num[start] == num[start-1]) start++;  
22:            while(start<end && num[end] == num[end+1]) end--;  
23:          }  
24:          else if(num[start] + num[end] < target)  
25:          {  
26:            start++;  
27:          }  
28:          else  
29:          {  
30:            end--;  
31:          }  
32:        }  
33:        if(i<len-1)  
34:        {  
35:          while(num[i] == num[i+1]) i++;  
36:        }  
37:      }  
38:      return result;  
39:    }  

[Some tricks]
1. Line 21 and Line 22.
    filter the duplicate during two-pointer scan. For example [-2, 0, 0, 2,2], the expected output should be [-2,0,2]. If no filter here, the output will be duplicate as [-2,0,2] and [-2,0,2]
2. Line 35
   filter the duplicate for outside iteration. For example [-2, -2, -2, 0,2].

[LeetCode] Sort Colors 解题报告

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

» Solve this problem

[解题思路]
一开始想到的就是计数排序，但是计数排序需要两边扫描，第一遍统计红，白，蓝的数目，第二遍生成新数组。

考虑到题目要求one pass。这就意味着类似于链表的双指针问题，这里也要track两个index，一个是red的index，一个是blue的index，两边往中间走。

i从0到blue index扫描，
遇到0，放在red index位置，red index后移；
遇到2，放在blue index位置，blue index前移；
遇到1，i后移。
扫描一遍得到排好序的数组。时间O(n)，空间O(1)，

[Code]
two-pass solution, Counting sort solution

1:       void sortColors(int A[], int n) {   
2:            // Start typing your C/C++ solution below   
3:            // DO NOT write int main() function   
4:            int red=0, white =0, blue=0;   
5:            for(int i =0; i < n; i++)   
6:            {   
7:                 switch(A[i])   
8:                 {   
9:                 case 0:   
10:                      red++;break;   
11:                 case 1:    
12:                      white++;break;   
13:                 case 2:   
14:                      blue++;break;   
15:                 }   
16:            }   
17:            for(int i =0; i<n; i++)   
18:            {   
19:                 if(red>0)   
20:                 {   
21:                      A[i]=0;   
22:                      red--;   
23:                      continue;   
24:                 }   
25:                 if(white>0)   
26:                 {   
27:                      A[i] =1;   
28:                      white--;   
29:                      continue;   
30:                 }   
31:                 A[i]=2;   
32:            }   
33:       }   

one-pass, two pointers solution

1:       void sortColors(int A[], int n) {   
2:            // Start typing your C/C++ solution below   
3:            // DO NOT write int main() function   
4:            int redSt=0, bluSt=n-1;   
5:            int i=0;   
6:            while(i<bluSt+1)   
7:            {   
8:                 if(A[i]==0)   
9:                 {   
10:                      std::swap(A[i],A[redSt]);   
11:                      redSt++;   
12:                      i++;   
13:                      continue;   
14:                 }   
15:                 if(A[i] ==2)   
16:                 {   
17:                      std::swap(A[i],A[bluSt]);   
18:                      bluSt--;    
19:                      continue;   
20:                 }   
21:                 i++;   
22:            }   
23:       }   

[LeetCode] Rotate List 解题报告

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

» Solve this problem

[解题思路]

首先从head开始跑，直到最后一个节点，这时可以得出链表长度len。然后将尾指针指向头指针，将整个圈连起来，接着往前跑len – k%len，从这里断开，就是要求的结果了。

[Code]

1:    ListNode *rotateRight(ListNode *head, int k) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      if(head == NULL || k ==0) return head;  
5:      int len =1;  
6:      ListNode* p = head,*pre;  
7:      while(p->next!=NULL)  
8:      {  
9:        p = p->next;  
10:        len++;      
11:      }  
12:      k = len-k%len;  
13:      p->next = head;  
14:      int step =0;  
15:      while(step< k)  
16:      {  
17:        p = p->next;  
18:        step++;  
19:      }  
20:      head = p->next;  
21:      p->next = NULL;  
22:      return head;  
23:    }  

[Note]
注意K大于len的可能。

[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] Remove Nth Node From End of List 解题报告

Given a linked list, remove the n^th 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] Minimum Window Substring 解题报告

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

» Solve this problem

[解题报告]
双指针，动态维护一个区间。尾指针不断往后扫，当扫到有一个窗口包含了所有T的字符后，然后再收缩头指针，直到不能再收缩为止。最后记录所有可能的情况中窗口最小的

[Code]

1:    string minWindow(string S, string T) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:         if(S.size() == 0) return "";  
5:            if(S.size() < T.size()) return "";            
6:            int appearCount[256];  
7:            int expectCount[256];  
8:            memset(appearCount, 0, 256*sizeof(appearCount[0]));  
9:            memset(expectCount, 0, 256*sizeof(appearCount[0]));  
10:            for(int i =0; i < T.size(); i++)  
11:            {  
12:                 expectCount[T[i]]++;                 
13:            }  
14:            int minV = INT_MAX, min_start = 0;  
15:            int wid_start=0;  
16:            int appeared = 0;   
17:            for(int wid_end = 0; wid_end< S.size(); wid_end++)  
18:            {  
19:                 if(expectCount[S[wid_end]] > 0)// this char is a part of T  
20:                 {  
21:                      appearCount[S[wid_end]]++;  
22:                      if(appearCount[S[wid_end]] <= expectCount[S[wid_end]])  
23:                           appeared ++;                      
24:                 }  
25:                 if(appeared == T.size())  
26:                 {                 
27:                      while(appearCount[S[wid_start]] > expectCount[S[wid_start]]   
28:                      || expectCount[S[wid_start]] == 0)  
29:                      {  
30:                           appearCount[S[wid_start]]--;  
31:                           wid_start ++;  
32:                    }                      
33:                      if(minV > (wid_end - wid_start +1))  
34:                      {  
35:                           minV = wid_end - wid_start +1;  
36:                           min_start = wid_start;  
37:                      }  
38:                 }                 
39:            }  
40:      if(minV == INT_MAX) return "";  
41:            return S.substr(min_start, minV);      
42:    }  

[已犯错误]
1. Line 8&9
不熟悉这个api，最初写成了

memset(expectCount, 0, 256);

结果老是出问题，检查了很多遍logic，也没发现有问题，最后还是放到VS下debug才发现原来是地址空间大小没有传对。正确的应该是：

memset(expectCount, 0, 256*sizeof(appearCount[0]));