class Solution:
# @return a tuple, (index1, index2)
def twoSum(self, num, target):
#dictionary O(n)
dict = {}
for i in range(len(num)):
if num[i] not in dict:
dict[targetnum[i]] = i
else:
return (dict[num[i]]+1, i+1)
return (1, 1)
X
xiaoying10101
@xiaoying10101
190
Reputation
88
Posts
311
Profile views
0
Followers
0
Following
Posts made by xiaoying10101

Sharing accepted Python O(n) solution using hash

Sharing my accepted Python solution with explanation
# Definition for singlylinked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param head, a ListNode # @return a list node def detectCycle(self, head): #first get the crossing node X when a fast and slow pointer came across #start from X and head, then the crossing node Y is the cycle begins #trick: Xing node Y to beginning of cycle == headnode to beginning of cycle # 2vtvt = n*cycle => vt = n*cycle and vt = head_to_cycle_start + cycle_start_to_X + m*cycle # => head_to_cycle_start = (nm)*cycle  cycle_start_to_X # = (nm1)*(cycle_start_to_X + X_to_cycle_start) + X_to_cycle_start #thus, starting from cycle_start_to_X, walk head_to_cycle_start nodes, must arrive at the starting node of cycle if head is None or head.next is None: return None slow, fast = head.next, head.next.next while slow != fast: if fast is None or fast.next is None: return None slow = slow.next fast = fast.next.next crossing = slow ptr = head while crossing != ptr: crossing = crossing.next ptr = ptr.next return crossing

Sharing accepted Python solution
class Solution: # @param s, a string # @return an integer def longestValidParentheses(self, s): #(()) is valid(wellformed) #dp[i] = continuous valid substring till s[i] #if s[i] == "(": dp[i] = 0 #if s[i] == ")":j=idp[i1]1, if j >= 0 and s[j] == "(", dp[i] = 2+dp[i1] # if j1 >= 0, dp[i] += dp[j1] # else dp[i] = 0 since no open parentheses can be found to be paired with s[i] # dp = [0 for x in range(len(s)+1)] for i in range(len(s)): if s[i] == "(": continue else: #s[i] == ")" j = idp[i]1 #dp[0] => length of s is 0 if j >= 0 and s[j] == "(": dp[i+1] = 2+dp[i] if j1 >= 0: dp[i+1] += dp[j] else: dp[i+1] = 0 return max(dp)

Accepted Python DP solution
class Solution: # @param dungeon, a list of lists of integers # @return a integer def calculateMinimumHP(self, dungeon): #If at any point his health point drops to 0 or below, he dies immediately. #have to make sure at any point health is > 0 #dp[i][j] is minimum health needed when arriving at this grid #dp[i][j] = min(max(1, dp[right]right_grid_value), max(1, dp[down]down_grid_value)) row, col = len(dungeon), len(dungeon[0]) dp = [[0 for x in range(col)] for x in range(row)] dp[row1][col1] = 1 for i in range(row2, 1, 1): dp[i][col1] = max(1, dp[i+1][col1]dungeon[i+1][col1]) for i in range(col2, 1, 1): dp[row1][i] = max(1, dp[row1][i+1]dungeon[row1][i+1]) for i in range(row2, 1, 1): for j in range(col2, 1, 1): right = max(1, dp[i][j+1]dungeon[i][j+1]) down = max(1, dp[i+1][j]dungeon[i+1][j]) dp[i][j] = min(right, down) return max(1, dp[0][0]dungeon[0][0])

DP python solution with memoization
class Solution: # @return a boolean def __init__(self): self.cache = {} def isMatch(self, s, p): #If the next character of p is NOT ‘*’, then it must match the current character of s. Continue pattern matching with the next character of both s and p. #If the next character of p is ‘*’, then we do a brute force exhaustive matching of 0, 1, or more repeats of current character of p… Until we could not match any more characters. if (s, p) in self.cache: return self.cache[(s,p)] if p == "": self.cache[(s,p)] = s == "" return s == "" #next char is not "*", must match current char if len(p) == 1 or p[1] != "*": self.cache[(s,p)] = s != "" and (p[0] == s[0] or p[0] == ".") and self.isMatch(s[1:], p[1:]) return self.cache[(s,p)] #next char is "*", take current char into consideration i = 0 while i < len(s) and (p[0] == s[i] or p[0] == "."): if self.isMatch(s[i:], p[2:]): self.cache[(s,p)] = True return True i += 1 self.cache[(s,p)] = self.isMatch(s[i:], p[2:]) return self.cache[(s,p)]

Share accepted Python solution
class Solution: # @return a boolean def isInterleave(self, s1, s2, s3): #dp[i][j][k] = True if s3[:k] is interleave of s1[:i] and s2[:j] #dp[i][j][k] = (dp[i1][j][k1] if s1[i] == s3[k]) or (dp[i][j1][k1] if s2[j] == s3[k]) #dp[0][0][0] = True #dp[i][j][k] = False if i+j != k Since k always = i+j, we can eliminate one dimension if len(s1)+len(s2) != len(s3): return False dp = [[False for j in range(len(s2)+1)] for i in range(len(s1)+1)] for i in range(0, len(s1)+1): for j in range(0, len(s2)+1): #k is determined if i == 0 and j == 0: dp[i][j] = True elif i == 0: #"aa", "ab", "abaa" length of s1 is 0 dp[i][j] = s2[:j] == s3[:j] elif j == 0: #length of s2 is 0 dp[i][j] = s1[:i] == s3[:i] else: dp[i][j] = (dp[i1][j] and s1[i1] == s3[i+j1]) or (dp[i][j1] and s2[j1] == s3[i+j1]) return dp[1][1]

Sharing my accepted Python solution
class Solution: # @return a string def fractionToDecimal(self, numerator, denominator):. neg = numerator != 0 and numerator >> 31 != denominator >> 31 #otherwise 0, 5 = 0 numerator = abs(numerator) denominator = abs(denominator) result = "" remainder = numerator%denominator quotient = numerator//denominator result += str(quotient)+"." #start dealing with decimalpart remainders = {} decimalpart = "" curposition = 0 while remainder not in remainders and remainder != 0: remainders[remainder] = curposition curposition += 1 numerator = remainder*10 remainder = numerator%denominator quotient = numerator//denominator decimalpart += str(quotient) if remainder == 0: result += decimalpart if result[1] == ".": #"0."case result = result[:1] else: start = remainders[remainder] result = result + decimalpart[:start] + "(" + decimalpart[start:] +")" return ""+result if neg else result
Basic idea: ONCE the remainder starts repeating, so does the divided result

Accepted Python backtracking solution
class Solution: # @param board, a list of lists of 1 length string # @param word, a string # @return a boolean def exist(self, board, word): #backtracking, recursion, dfs def search(board, word, row, col): if word == "": return True original = board[row][col] board[row][col] = "." for i in [row1, row+1]: if i < len(board) and i > 1: if board[i][col] != "." and board[i][col] == word[0]: if search(board, word[1:], i, col): return True for j in [col1, col+1]: if j < len(board[0]) and j > 1: if board[row][j] != "." and board[row][j] == word[0]: if search(board, word[1:], row, j): return True board[row][col] = original return False for row in range(len(board)): for col in range(len(board[0])): if board[row][col] == word[0]: if search(board, word[1:], row, col): return True return False

My accepted Python solution
class Solution: # @param words, a list of strings # @param L, an integer # @return a list of strings def fullJustify(self, words, L): result = [] i = 0 while i < len(words): length = len(words[i]) j = i+1 while j < len(words): if length+1+len(words[j]) > L: break length += (1+len(words[j])) j += 1 numofwords = ji if numofwords == 1: line = words[i]+" "*(Llength) elif j == len(words): #deal with last line case line = words[i] for x in range(i+1, j): line += (" "+words[x]) line += " "*(Llength) else: space = (Llength)//(numofwords1) remain = (Llength)%(numofwords1) line = words[i] for x in range(i+1, j): if remain > 0: line += (" "*(space+1+1)+words[x]) remain = 1 else: line += (" "*(space+1)+words[x]) result.append(line) i = j return result