MJ [49] Upsampling

Question:

you have an img data as an array, output the data for upsampling. For example, 
[1, 2, 3, 4, 5, 6] as width 3(2 rows) ==> upsample 2 times would be [1 1 2 2 3 3 1 1 2 2 3 3 4 4 5 5 6 6 4 4 5 5 6 6]
================
================
Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33110511.html

LeetCode [316] Remove Duplicate Letters

 316. Remove Duplicate Letters

Medium

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

 

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: string removeDuplicateLetters(string s) { if(s.empty()) return s; string ret; while(!s.empty()){ int cnts[26] = {0}; for(char c:s) cnts[c-'a']++; int pos = 0, n = s.size(); for(int i=0; i<n; ++i){ if(s[i]<s[pos]) pos = i; cnts[s[i]-'a']--; //find who's the first to disappear if(cnts[s[i]-'a']==0) break; } ret += s[pos]; string next; for(int i=pos+1; i<n; ++i){ if(s[i]!=s[pos]) next += s[i]; } s = next; } return ret; } };

LeetCode [289] Game of Life

Note: state 1->3 if this cell will die in next step
          state 0->2 if this cell will live in next step
Ref
[1] https://leetcode.com/problems/game-of-life/

LeetCode [283] Move Zeroes

283. Move Zeroes

Easy

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.

Example:

Input: [0,1,0,3,12]
Output: [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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public: void moveZeroes(vector<int>& nums) { int n = nums.size(), i = 0, j = 0; while(j<n){ while(j<n && nums[j]==0) j++; if(j<n) nums[i++] = nums[j++]; } while(i<n){ nums[i++] = 0; } } }; class Solution { public: void moveZeroes(vector<int>& nums) { int n = nums.size(); int i = 0, j = 0; while(j<n){ while(j<n && nums[j]==0){ j++; } while(j<n && nums[j]!=0){ nums[i++] = nums[j++]; } } fill(nums.begin()+i, nums.end(), 0); } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public void moveZeroes(int[] nums) { int n = nums.length; int i = 0, j = 0; while(i<n){ if(nums[i]==0){ i++; }else{ nums[j] = nums[i]; i++; j++; } } while(j<n){ nums[j] = 0; j++; } } }

LeetCode [277] Find the Celebrity

=============

• Line 8-13 computes c, which is the only possible celebrity
• Proof:
• if c=0, c does not know any one in [1...n-1]. [c+1...n-1] are not celebrities.
• if c=1, 0 knows 1. Thus 0 is not celebrity and [c+1...n-1] are not celebrities.
• if c=2, there are 2 cases. In both cases 0 and 1 are not celebrities. Also, [c+1...n-1] are not celebrities.
1. 0 knows 1 and 1 knows 2. 
2. 0 does not know 1 but 0 knows 2. 
• if c=i, [0, i-1] and [i+1, n-1] are not celebrities.

Ref
[1] https://leetcode.com/problems/find-the-celebrity/
[2] http://www.geeksforgeeks.org/the-celebrity-problem/

MJ [24] Union and Intersection of two sorted arrays

Ref
[1] http://www.geeksforgeeks.org/union-and-intersection-of-two-sorted-arrays-2/
Question

MJ [4]

Question: Give a set of coins denoted by an integer array a. a[i] is the value of the i-th coin which can be any integer. Find the minimal number of missing coins (whose value can be any integer) such that we can get any exact change from 1 to N by choosing from the new set of coins.

Example: If a = [1, 5] N=10, the missing coins in a are 2 and 4 because a subset of  [1, 2, 4, 5] can be summed to any integer from 1 to 10. Thus, the answer is 2.

===========

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33021821.html

LeetCode [245] Shortest Word Distance III

Ref
[1] https://leetcode.com/problems/shortest-word-distance-iii/
OJ

LeetCode [243] Shortest Word Distance

 243. Shortest Word Distance

Easy

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “coding”, word2 = “practice”
Output: 3

Input: word1 = "makes", word2 = "coding"
Output: 1

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: int shortestDistance(vector<string>& words, string word1, string word2) { int n = words.size(); int p1 = -1, p2 = -1, dist = INT_MAX; for(int i=0; i<n; ++i){ if(words[i]==word1) p1 = i; if(words[i]==word2) p2 = i; if(p1>=0 && p2>=0) dist = min(dist, abs(p1-p2)); } return dist; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public int shortestDistance(String[] words, String word1, String word2) { int n = words.length, i1 = -1, i2 = -1; int minD = n; for(int i=0; i<n; ++i){ if(words[i].equals(word1)) i1 = i; if(words[i].equals(word2)) i2 = i; if(i1>=0 && i2>=0){ minD = Math.min(Math.abs(i1-i2), minD); } } return minD; } }

LeetCode [238] Product of Array Except Self

238. Product of Array Except Self

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int prod = 1, n = nums.size(), tmp = 1; vector<int> output(n,1); for(int i=1; i<n; ++i) { output[i] = tmp * nums[i-1]; tmp = output[i]; } tmp = 1; for(int i=n-2; i>=0; --i) { output[i] *= (tmp*nums[i+1]); tmp *= nums[i+1]; } return output; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] output = new int[n]; for(int i=0; i<n; ++i){ if(i==0) output[i] = 1; else output[i] = output[i-1]*nums[i-1]; } int p = nums[n-1]; for(int i=n-2; i>=0; --i){ if(i==0) output[i] = p; else output[i] = output[i]*p; p *= nums[i]; } return output; } }

LeetCode [229] Majority Element II

 229. Majority Element II

Medium

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Follow-up: Could you solve the problem in linear time and in O(1) space?

 

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

 

Constraints:

• 1 <= nums.length <= 5 * 104
• -109 <= nums[i] <= 109

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { public: vector<int> majorityElement(vector<int>& nums) { vector<int> ret; int n1, c1 = 0, n2, c2 = 0; for(auto n:nums){ if(c1>0 && n==n1){ c1++; }else if(c2>0 && n==n2){ c2++; }else if(c1==0){ c1++; n1 = n; }else if(c2==0){ c2++; n2 = n; }else{ c1--; c2--; } } int t1 = 0, t2 = 0, n = nums.size(); for(auto n:nums){ if(c1>0 && n==n1) t1++; if(c2>0 && n==n2) t2++; } if(t1>n/3) ret.push_back(n1); if(t2>n/3) ret.push_back(n2); return ret; } };

LeetCode [216] Combination Sum III

 216. Combination Sum III

Medium

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

 

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations. [1,2,1] is not valid because 1 is used twice.

Example 4:

Input: k = 3, n = 2
Output: []
Explanation: There are no valid combinations.

Example 5:

Input: k = 9, n = 45
Output: [[1,2,3,4,5,6,7,8,9]]
Explanation:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
​​​​​​​There are no other valid combinations.

 

Constraints:

• 2 <= k <= 9
• 1 <= n <= 60

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> res; vector<int> cur; bt(k, n, res, cur, 1, 0); return res; } void bt(int k, int n, vector<vector<int>> &res, vector<int> cur, int pos, int sum){ if(sum==n && cur.size()==k){ res.push_back(cur); }else if(sum<n && pos<=9 && cur.size()<k){ for(int i=pos; i<=9; ++i){ if(sum+i>n) return; cur.push_back(i); bt(k, n, res, cur, i+1, sum+i); cur.pop_back(); } } } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { List<List<Integer>> lists = new ArrayList<>(); public List<List<Integer>> combinationSum3(int k, int n) { helper(0, new ArrayList<>(), k, n, 1); return lists; } void helper(int sum, List<Integer> list, int k, int n, int p){ if(sum>=n){ if(sum==n && list.size()==k){ lists.add(list); } }else if(p<=9 && sum+p<=n && list.size()<k){ helper(sum, list, k, n, p+1); List<Integer> newList = new ArrayList<Integer>(list); newList.add(p); helper(sum+p, newList, k, n, p+1); } } }