classSolution(object): defmaxProfit(self, prices): """ :type prices: List[int] :rtype: int """ p = 0 for i inrange(1,len(prices)): tmp = prices[i] - prices[i-1] if tmp > 0: p += tmp return p
classSolution(object): defisPalindrome(self, s): """ :type s: str :rtype: bool """ ifnot s: returnTrue left = 0 right = len(s)-1 while left < right: while left < right andnot s[left].isalnum(): left += 1 while left < right andnot s[right].isalnum(): right -= 1 if s[left].lower() != s[right].lower(): returnFalse left += 1 right -= 1 returnTrue
classSolution(object): deffindLadders(self, beginWord, endWord, wordList): """ :type beginWord: str :type endWord: str :type wordList: List[str] :rtype: List[List[str]] """ wordList = set(wordList) res = [] from collections import defaultdict next_word_dict = defaultdict(list) distance = {} distance[beginWord] = 0 defnext_word(word): ans = [] for i inrange(len(word)): for j inrange(97,123): tmp = word[:i] + chr(j) + word[i+1:] if tmp != word and tmp in wordList: ans.append(tmp) return ans defbfs(): step = 0 flag = False cur = [beginWord] while cur: step += 1 next_time = [] for word in cur: for nw in next_word(word): next_word_dict[word].append(nw) if nw == endWord: flag = True if nw notin distance: distance[nw] = step next_time.append(nw) if flag: break cur = next_time defdfs(tmp,step): if tmp[-1] == endWord: res.append(tmp) return for word in next_word_dict[tmp[-1]]: if distance[word] == step + 1: dfs(tmp + [word],step + 1) bfs() dfs([beginWord],0) return res
classSolution(object): deffindLadders(self, beginWord, endWord, wordList): """ :type beginWord: str :type endWord: str :type wordList: List[str] :rtype: List[List[str]] """ defbacktrack(res,routine,path,endWord): iflen(routine[endWord]) == 0: res.append([endWord] + path) else: for pre in routine[endWord]: backtrack(res,routine,[endWord] + path,pre) lookup = set(wordList) | set([beginWord]) res,cur,routine = [],set([beginWord]),{word:[] for word in lookup} while cur and endWord notin cur: next_queue = set() for word in cur: lookup.remove(word) for word in cur: for i inrange(len(word)): for j inrange(97,123): tmp = word[:i] + chr(j) + word[i+1:] if tmp in lookup: next_queue.add(tmp) routine[tmp].append(word) cur = next_queue if cur: backtrack(res,routine,[],endWord) return res
classSolution(object): defladderLength(self, beginWord, endWord, wordList): """ :type beginWord: str :type endWord: str :type wordList: List[str] :rtype: int """ res = 1 cur = [beginWord] if endWord notin wordList: return0 wordList = set(wordList) while cur: next_time = [] if endWord in cur: return res for word in cur: if word in wordList: wordList.remove(word) for i inrange(len(word)): for j inrange(97,123): tmp = word[:i] + chr(j) + word[i+1:] if tmp != word and tmp in wordList: next_time.append(tmp) cur = next_time res += 1 return0
classSolution(object): deflongestConsecutive(self, nums): """ :type nums: List[int] :rtype: int """ nums = set(nums) res = 0 for x in nums: if x-1notin nums: y = x + 1 while y in nums: y += 1 res = max(res,y-x) return res
classSolution(object): defsolve(self, board): """ :type board: List[List[str]] :rtype: None Do not return anything, modify board in-place instead. """ ifnot board ornot board[0]: return row = len(board) col = len(board[0]) defdfs(i,j): board[i][j] == 'B' for x,y in [(-1,0),(1,0),(0,1),(0,-1)]: tmp_i = i + x tmp_j = j + y if1 <= tmp_i < row and1 <= tmp_j < col and board[tmp_i][tmp_j] =='O': dfs(tmp_i,tmp_j) for j inrange(col): if board[0][j] == 'O': dfs(0,j) if board[row-1][j] == 'O': dfs(row-1,j) for i inrange(row): if board[i][0] == 'O': dfs(i,0) if board[i][col-1] == 'O': dfs(i,col-1) for i inrange(row): for j inrange(col): if board[i][j] == 'O': board[i][j] == 'X' if board[i][j] == 'B': board[i][j] == 'O'
11. 分割回文串(Medium)
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
1 2 3 4 5 6
输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
解答：
思路：
很标准的回溯法，针对可能的每一个分割点，如果前面是回文，则递归判断后面。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution(object): defpartition(self, s): """ :type s: str :rtype: List[List[str]] """ res = [] defhelper(s,tmp): ifnot s: res.append(tmp) for i inrange(1,len(s)+1): if s[:i] == s[:i][::-1]: helper(s[i:],tmp + [s[:i]]) helper(s,[]) return res
12. 分割回文串2(Hard)
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
1 2 3
输入: "aab" 输出: 1 解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
解答：
思路：
如果还是用上一题的思路，结果超时。
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution(object): defminCut(self, s): """ :type s: str :rtype: int """ ans = float('inf') if s == s[::-1]: return0 for i inrange(1,len(s)+1): if s[:i] == s[:i][::-1]: ans = min(self.minCut(s[i:])+1,ans) return ans
所以，使用动态规划。
很容易理解。
如果s[j:i]是回文，那么cut[i] =min(cut[i],cut[j-1]+1)
怎么判断回文，用DP数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution(object): defminCut(self, s): """ :type s: str :rtype: int """ cut = list(range(len(s))) dp = [[False] * len(s) for _ inrange(len(s))] for i inrange(len(s)): for j inrange(i+1): if s[i] == s[j] and(i-j<2or dp[j+1][i-1]): dp[j][i] = True if j == 0: cut[i] = 0 else: cut[i] = min(cut[i],cut[j-1]+1) return cut[-1]
从上一次重置的加油站到当前加油站的任意一个加油站出发，到达当前加油站之前， cur 也一定会比 0 小
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution(object): defcanCompleteCircuit(self, gas, cost): """ :type gas: List[int] :type cost: List[int] :rtype: int """ total = cur = 0 start = 0 for i inrange(len(gas)): total += gas[i] - cost[i] cur += gas[i] - cost[i] if cur < 0: start = i+1 cur = 0 return start if total>=0else -1
classSolution(object): defcandy(self, ratings): """ :type ratings: List[int] :rtype: int """ n = len(ratings) res = [1] * n for i inrange(1,n): if ratings[i] > ratings[i-1]: res[i] = res[i-1]+1 for i inrange(n-2,-1,-1): if ratings[i] > ratings[i+1]: res[i] = max(res[i],res[i+1]+1) returnsum(res)
classSolution(object): defcandy(self, ratings): """ :type ratings: List[int] :rtype: int """ ifnot ratings: return0 res = 1 pre = 1 des = 0 for i inrange(1,len(ratings)): if ratings[i] >= ratings[i-1]: if des > 0: res += (1 + des) * des/2 if pre <= des: res += des-pre+1 des=0 pre=1 if ratings[i] == ratings[i-1]: pre = 1 else: pre += 1 res += pre else: des += 1 if des > 0: res += (1 + des) * des/2 if pre <= des: res += des-pre + 1 return res
classSolution(object): defsingleNumber(self, nums): """ :type nums: List[int] :rtype: int """ one,two = 0,0 for i in nums: one = (one^i)&~two two = (two^i)&~one return one
classSolution(object): defwordBreak(self, s, wordDict): """ :type s: str :type wordDict: List[str] :rtype: List[str] """ res = [] defdfs(idx,tmp): if idx == len(s): res.append(tmp[:-1]) for i inrange(idx+1,len(s)+1): if s[idx:i] in wordDict: dfs(i,tmp+s[idx:i]+' ') dfs(0,'') return res
classSolution(object): defwordBreak(self, s, wordDict): """ :type s: str :type wordDict: List[str] :rtype: List[str] """ defhelper(s,wordDict,memo): if s in memo: return memo[s] ifnot s: return [] res = [] for word in wordDict: ifnot s.startswith(word): continue iflen(s) == len(word): res.append(word) else: re = helper(s[len(word):],wordDict,memo) for item in re: item = word + ' ' + item res.append(item) memo[s] = res return res return helper(s,wordDict,{})
