[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] 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] Container With Most Water, Solution

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

» Solve this problem

[Thoughts]
For any container, its volume depends on the shortest board.
Two-pointer scan. And always move with shorter board index.


[Code]

1:    int maxArea(vector<int> &height) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int start =0;  
5:      int end = height.size()-1;  
6:      int maxV = INT_MIN;  
7:      while(start<end)  
8:      {  
9:        int contain = min(height[end], height[start]) * (end-start);  
10:        maxV = max(maxV, contain);  
11:        if(height[start]<= height[end])  
12:        {  
13:          start++;  
14:        }  
15:        else  
16:        {  
17:          end--;  
18:        }  
19:      }  
20:      return maxV;  
21:    }  

[LeetCode] 3Sum Closest, Solution

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

» Solve this problem

[Thoughts]
Similar as 3Sum. Only need to add a new variable to track the minimum history.

[Code]

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

[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].