Sol 1 (C++): state machine
0 Comments
Sol 1 (C++): scan & center growing, distinguish odd/even cases (e.g., 'a' & 'aa' can both be the center)
Sol 2: DP
1. Define: dp[i][j]: s[i…j] is/is not palindrome 2. Initialize: all i>j: dp[i][j] = false all i=j: dp[i][j] = true all i+1=j: if s[i] == s[j], then dp[i][j] = true, else dp[i][j] = false 3. Update rule: if s[i]==s[j] && dp[i+1][j-1] == true, then dp[i][j] == true, else dp[i][j] == false Sol 1: use solution to Problem 84 ...
Skipped
Sol 2 (Python): naive dynamic programming (a nice double DP formulation, TLE though...)
Sol 1 (Python): dynamic programming
Sol 1 (python): dynamic programming
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) == 0: return 0 maxSum = float('-inf') dp = 0 for i in range(0, len(nums)): dp = max(dp+nums[i], nums[i]) maxSum = max(dp, maxSum) return maxSum |
Sol 1 (python): merge two sorted array
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ m = len(nums1) n = len(nums2) idx1 = 0 idx2 = 0 idxm = 0 isEven = (m+n)%2 == 0 currM = 0 prevM = 0 while idx1 < m or idx2 < n: if idx1 == m: prevM = currM currM = nums2[idx2] idx2 = idx2+1 idxm = idxm+1 elif idx2 == n: prevM = currM currM = nums1[idx1] idx1 = idx1+1 idxm = idxm+1 else: if nums1[idx1] <= nums2[idx2]: prevM = currM currM = nums1[idx1] idx1 = idx1+1 idxm = idxm+1 else: prevM = currM currM = nums2[idx2] idx2 = idx2+1 idxm = idxm+1 if isEven and (int)((m+n)/2) == idxm-1: return (prevM + currM) / 2.0 elif not isEven and (int)((m+n)/2) == idxm-1: return currM |
Sol 2: find kth smallest number --> binary search
The following blog provided a very good analysis: http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html
Sol 1 (C++): hash table (set) + two pointers
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 |
int lengthOfLongestSubstring(string s) { if(s.length() == 0) return 0; int idx0 = 0; int idxf = 1; int maxLength = 1; unordered_set<char> set; set.insert(s[idx0]); while(idxf<s.length()) { if( set.find(s[idxf]) != set.end() ) { idxf--; set.erase(s[idx0]); idx0++; } else { set.insert(s[idxf]); maxLength = max(maxLength, idxf-idx0+1); } idxf++; } return maxLength; } |
Sol 2 (Python): hash table (map)
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 |
def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ strLength = len(s) tmp = [] charMap = dict(tmp) idx0 = 0 idxf = 0 maxLength = 0 while idxf < strLength: charCurr = s[idxf] if charCurr in charMap: # remove the characters from idx0 to idxStop idxStop = charMap[charCurr] for id in range(idx0, idxStop+1): if s[id] in charMap: del charMap[s[id]] charMap[charCurr] = idxf idx0 = idxStop + 1 else: charMap[charCurr] = idxf maxLength = max( maxLength, idxf-idx0+1 ) idxf+=1 return maxLength |
Copyright © [Tianyu Gu] [2016]. All rights reserved.
Sol 1 (C++): math, linked list, carry
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 32 33 34 35 36 37 38 39 40 41 42 43 44 |
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { ListNode* ansRoot = NULL; ListNode* ansCurr = NULL; bool firstTime = true; int carry = 0; while( l1 != NULL || l2 != NULL || carry != 0 ) { int val1 = (l1!=NULL) ? l1->val : 0; int val2 = (l2!=NULL) ? l2->val : 0; ListNode* newNode = NULL; int tmpVal = val1 + val2 + carry; if( tmpVal > 9 ) { carry = 1; newNode = new ListNode(tmpVal - 10); } else { carry = 0; newNode = new ListNode(tmpVal); } if(firstTime) { firstTime = false; ansRoot = newNode; ansCurr = ansRoot; } else { ansCurr->next = newNode; ansCurr = ansCurr->next; } l1 = (l1!=NULL) ? l1->next : l1; l2 = (l2!=NULL) ? l2->next : l2; } return ansRoot; } |
Copyright © [Tianyu Gu] [2016]. All rights reserved.
Sol 1 (Python): sort + two pointers
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 |
def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ numIdxPairs = [] for idx in range(0, len(nums)): numIdxPairs.append( (nums[idx], idx) ) def getKey(item): return item[0] numIdxPairs.sort( key=getKey ) idx0 = 0 idxf = len(nums)-1 ans = [] while idx0 != idxf: if numIdxPairs[idx0][0] + numIdxPairs[idxf][0] == target: ans = [numIdxPairs[idx0][1]+1, numIdxPairs[idxf][1]+1] ans.sort() break elif numIdxPairs[idx0][0] + numIdxPairs[idxf][0] < target: idx0 = idx0 + 1 else: idxf = idxf - 1 return ans |
Sol 2 (C++): hash table
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
vector<int> twoSum(vector<int> &numbers, int target) { std::map<int, int> map; for(int i=0; i<numbers.size(); i++) { map.insert(std::make_pair(numbers[i],i) ); } for(int i=0; i<numbers.size(); i++) { std::map<int,int>::iterator iter = map.find(target-numbers[i]); if( iter != map.end() && i != iter->second ) { vector<int> answer; if( i<iter->second ) { answer.push_back( i + 1 ); answer.push_back( iter->second + 1 ); } else { answer.push_back( iter->second + 1 ); answer.push_back( i + 1 ); } return answer; } } } |
Copyright © [Tianyu Gu] [2016]. All rights reserved.