python刷题+leetcode(第二部分)
生活随笔
收集整理的這篇文章主要介紹了
python刷题+leetcode(第二部分)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
100.?簡化路徑
思路:棧
class Solution:def simplifyPath(self, path: str) -> str:stack = []for path_ in path.split('/'):if path_ not in ['', '.', '..']:stack.append(path_)elif path_ == '..' and stack:stack.pop()return '/' + '/'.join(stack)c++實現:
class Solution { public:string simplifyPath(string path) {stringstream ss(path);vector<string> strs;strs.reserve(20);string curr;while (getline(ss, curr, '/')){cout<<"curr:"<<curr<<endl;if (!curr.empty() && curr != "." && curr != ".."){strs.push_back(curr);}else if (curr == ".." && !strs.empty()){strs.pop_back();}}if (!strs.empty()){string res;for (string str_ : strs){res.append("/");res.append(str_);}return res;}else{return "/";}} };101.重復的子字符串
思路：
?解法1.abab 變為abababab 去頭與去尾看看是否存在s 若存在s說明有重復的字符串
class Solution:def repeatedSubstringPattern(self, s: str) -> bool:new_s= s+sreturn s in new_s[1:-1]c++:
class Solution { public:bool repeatedSubstringPattern(string s) {string new_str;new_str = s + s;for(int i=1; i<new_str.size() - s.size();i++){if (new_str.substr(i, s.size()) == s){return true;}}return false;} };解法2.kmp算法
構造s+s作為主字符串，s作為模板字符串，再利用kmp即可。
102.十進制整數的反碼
思路:整數→二進制數→替換‘0’和‘1’→整數
class Solution:def bitwiseComplement(self, N: int) -> int:# res = []# for bin_i in bin(N)[2:]:# if int(bin_i):# res.append('0')# else:# res.append('1')# print(res)# print('0b'+''.join(res))# return int('0b'+''.join(res),2)return int('0b'+''.join('0' if int(bin_i) and 1 else '1' for bin_i in bin(N)[2:]), 2)103.最小移動次數使數組元素相等
思路:讓n-1個元素加1等于讓一個元素-1
代碼:
class Solution:def minMoves(self, nums: List[int]) -> int:moves = 0nums = sorted(nums)for i in range(len(nums)):moves+=nums[i]-nums[0]return moves104.階乘后的零
思路:找尾數是0也就是除于10,10可以拆成5*2,通過找規律可以知道出現2的次數比5多,也就變成了找5的個數
class Solution:def trailingZeroes(self, n: int) -> int:res= 0while n>0:n = n//5res +=nreturn res105.?整數拆分
思路:j是 拆分的第一個數字,i-j就是剩下的,求i的最大等價于求i-j的最大,故狀態轉移方程為:max(j*(i-j),j*dp[i-j])
1.dp解法
#dp[i] = max(j*(i-j),j*dp[i-j]) class Solution:def integerBreak(self, n):dp = [0 for i in range(n+1)]# print('==dp:', dp)for i in range(n+1):#value = 0for j in range(i):#循環去確定i的時候的最大值value = max(value, max(j*(i-j), j*dp[i-j]))dp[i] = value# print('==dp:', dp)return dp[-1]sol = Solution() res = sol.integerBreak(n=10) print('res:', res)2.遞歸解法
class Solution:def integerBreak(self, n):if n<=1:return 0if n == 2:return 1res = 0for i in range(2, n):res = max(res, max(i*(n-i), i*self.integerBreak(n-i)))return ressol = Solution() res = sol.integerBreak(n=35) print('res:', res)106.錯誤的集合
解法一:數學解法
class Solution:def findErrorNums(self, nums: List[int]) -> List[int]:count = sum(set(nums))return [sum(nums)-count, len(nums)*(len(nums)+1)//2 - count]解法二:位運算
def findErrorNums(nums):res = 0length = len(nums)err = sum(nums) - sum(set(nums)) # 重復print('err:', err)for n in nums:#求出非重復數之和res ^= nprint('res:', res)for i in range(1, length + 1):#求出重復數之前的值res ^= iprint('==res:', res)miss = err ^ res#求出缺失值print('===miss:', miss)return [err, miss]nums = [1, 2, 2, 4] findErrorNums(nums)107：連續數列
思路：動態規劃，找到狀態方程dp[i]=max(nums[i]+dp[i-1], nums[i])
class Solution:def maxSubArray(self, nums: List[int]) -> int:dp = [0 for i in range(len(nums))]# print('===dp', dp)dp[0] =nums[0]for i in range(1, len(nums)):dp[i] = max(nums[i], dp[i-1]+nums[i])# print('==dp:', dp)return max(dp) class Solution:def maxSubArray(self, nums: List[int]) -> int:if len(nums)==0:return []res = nums[0]for i in range(1,len(nums)):nums[i] = max(nums[i], nums[i] + nums[i-1])res = max(nums[i], res)return res class Solution:def maxSubArray(self, nums: List[int]) -> int:if len(nums)==0:return []value = nums[0]res = nums[0]for i in range(1,len(nums)):value = max(nums[i], value + nums[i])res = max(value, res)return res108：編寫一個高效的算法來搜索?m?x?n?矩陣 matrix 中的一個目標值 target。該矩陣具有以下特性：
每行的元素從左到右升序排列。
每列的元素從上到下升序排列。
思路：找到值最大的一行的左下角，如果值小就減少行，值大就增加列．
class Solution:def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""if len(matrix)<=0:return Falseif len(matrix[0])<=0:return Falseh = len(matrix)w = len(matrix[0])col, row = 0, h - 1#先找到最大值的一行 左下腳 while row >= 0 and col < w:if target>matrix[row][col]:col+=1elif target < matrix[row][col]:row-=1else:return Truereturn False109.猜數字大小
思路:二分 python
# The guess API is already defined for you. # @param num, your guess # @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 # def guess(num: int) -> int:class Solution:def guessNumber(self, n: int) -> int:left, right = 1, nwhile left < right:mid = left + (right - left) // 2if guess(mid) < 0:right = mid - 1elif guess(mid) > 0:left = mid + 1else:return midreturn leftc++實現:?
/** * Forward declaration of guess API.* @param num your guess* @return -1 if num is lower than the guess number* 1 if num is higher than the guess number* otherwise return 0* int guess(int num);*/class Solution { public:int guessNumber(int n) {int left = 1, right = n;while(left < right){int mid = left + (right - left) / 2;if(guess(mid) > 0){left = mid + 1;}else if(guess(mid) < 0){right = mid - 1;}else{return mid;}}return left;} };一百一十二.最小K個數
思路：排序 取前幾個ｋ值即可．?
class Solution:def smallestK(self, arr: List[int], k: int) -> List[int]:def quicksort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quicksort(left) + middle + quicksort(right)return quicksort(arr)[:k]python最小堆，所以用負數 時間復雜度o(nlogk)
import heapq class Solution:def smallestK(self, arr, k):nums = []heapq.heapify(nums)for i in range(k):heapq.heappush(nums, -arr[i])print('==nums:', nums)for i in range(k, len(arr)):heapq.heappush(nums, -arr[i])heapq.heappop(nums)print('=nums:', nums)res = [-num for num in nums]print('==res:', res)return resarr = [1,3,5,7,2,4,6,8] k = 4 sol = Solution() sol.smallestK(arr, k)一百一十四.加油站
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:nums_of_station = len(gas)total_ = 0curent_= 0st_station = 0for i in range (nums_of_station):total_ +=gas[i] - cost[i]curent_ +=gas[i] - cost[i]if curent_<0:st_station=i+1curent_=0return st_station if total_>=0 else -1116.避免重復字母的最小刪除成本
思路:找到相鄰的字母,對其相應的損失取最小相加,注意的是碰到小的值要進行交換,否則會拿小的值再次計算和.
class Solution:def minCost(self, s, cost):price = 0for i in range(len(s)-1):if s[i] == s[i+1]:price += min(cost[i], cost[i+1])if cost[i] > cost[i+1]:#碰到小的值進行交換 不交換的話會拿小的值再一次進行相加cost[i], cost[i+1] = cost[i+1], cost[i]# print('==price', price)return price # s = "abaac" # cost = [1, 2, 3, 4, 5] s = "aaabbbabbbb" cost = [3, 5, 10, 7, 5, 3, 5, 5, 4, 8, 1] # s = "aabaa" # cost = [1, 2, 3, 4, 1] sol = Solution() price = sol.minCost(s, cost) print('=price:', price)117.合并有序數組
思路:兩個指針分別指向兩個列表,進行值的比較,將小的值放進列表,最后在看指針有沒有走完
class Solution(object):def merge(self, nums1, m, nums2, n):""":type nums1: List[int]:type m: int:type nums2: List[int]:type n: int:rtype: None Do not return anything, modify nums1 in-place instead."""nums1_copy = nums1[:m]nums1[:] = []# 雙指針法p1 = 0p2 = 0#將小的值放進reswhile p1 < m and p2 < n:if nums1_copy[p1] < nums2[p2]:nums1.append(nums1_copy[p1])p1 += 1else:nums1.append(nums2[p2])p2 += 1# 在把剩下的元素進行添加if p1 < m:nums1[p1 + p2:] = nums1_copy[p1:]if p2 < n:nums1[p1 + p2:] = nums2[p2:]return nums1119. 上升下降字符串
思路：利用桶計數對每個字符建立桶，進行左右掃描直到都為空
方法１：
class Solution:def sortString(self, s):#構建每個字符的桶 用于計數barrel = [0]*26for i in s:barrel[ord(i)-97] += 1# print('==barrel:', barrel)res = []while True:if any([barrel[i] for i in range(26)]):#退出條件 如果所有桶的字符都為０for i in range(len(barrel)):#從小到大加字符if barrel[i]>0:barrel[i]-=1res.append(chr(i+97))# print('res:', res)# print('==barrel:', barrel)for i in range(len(barrel)-1, -1, -1):#從大到小加字符if barrel[i]>0:barrel[i]-=1res.append(chr(i+97))else:break# print('res:', res)return ''.join(res) sol = Solution() s = "aaaabbbbcccc" res = sol.sortString(s) print('res:', res)方法２：利用collections
import collections class Solution:def sortString(self, s):chars=collections.Counter(s)print(chars)ans=[]signal=0while chars:group=list(chars)print('==group:', group)group.sort(reverse=signal)print('====group:', group)ans.extend(group)print('====collections.Counter(group):',collections.Counter(group))chars-=collections.Counter(group)print('===chars:', chars)signal=1-signalreturn ''.join(ans)sol = Solution() s = "aaaabbbbcccc" res = sol.sortString(s)120.字符串壓縮
?思路:從左到右遍歷字符串,開出兩個變量,一個用于計數,一個用于更新字符
class Solution(object):def compressString(self, S):""":type S: str:rtype: str"""if len(S)==0:return ''S_start = S[0]#將字符串中的第一個字符作為開始字符串cnt = 0res = ''for i in range(len(S)):if S[i] == S_start: # 等于開始字符就進行計數cnt += 1else:res += S_start + str(cnt)#碰到不等于的字符 將字符開頭和出現次數加入結果集合S_start = S[i]#重新更新開始字符串cnt = 1#重新計數# print('res:', res)res += S_start + str(cnt)# print('res:', res)return S if len(res) >= len(S) else res121.破壞回文串
思路: 1. 回文字符串特點 奇數 偶數都只找一半即可
? ? ? ? ?2. 對于前半部分如果發現不為a的替換成a即可 否則說明前半部分都是a這個時候就將后半部分變為b即可
122.恢復空格
#思路:通過雙指針來遍歷找到是否在dictionary,開辟一個列表用于計數未識別的字符數
# 利用字典key的特性方便進行判斷
125.連續差相同的數字
思路:第一位數字有9種可能性,后面的數字分別有兩種可能性,故對于一個5位數字,有9*2^4種可能性,故直接遍歷即可
class Solution(object):def numsSameConsecDiff(self, n, k):""":type n: int:type k: int:rtype: List[int]"""""":type n: int:type k: int:rtype: List[int]"""if n == 1:return [0]res = [i for i in range(1, 10)]for i in range(n - 1):temp = []for j in res:d = j % 10if d - k >= 0:temp.append(10 * j + d - k)if d + k <= 9:temp.append(10 * j + d + k)print('==temp:', temp)res = tempreturn list(set(res))N = 3 K = 2 sol = Solution() sol.numsSameConsecDiff(N, K)126.水域大小
思路１:bfs 將為0的坐標存入隊列,在對上下左右斜等8個方向用bfs進行遍歷,需要注意的是遍歷過為0的點需要更新為-1,代表已經遍歷過了,否則會陷入無限循環
class Solution(object):def pondSizes(self, land):""":type land: List[List[int]]:rtype: List[int]"""res = []rows = len(land)columns = len(land[0])for i in range(rows):for j in range(columns):if land[i][j] == 0: # 找到水域land[i][j] = -1 # 將訪問的點標記進行標記quene = []quene.append([i, j])temp_water_num = 1while len(quene) > 0:x, y = quene.pop(0)directions = [[x, y - 1], [x, y + 1], [x - 1, y - 1], [x - 1, y],[x - 1, y + 1], [x + 1, y - 1], [x + 1, y], [x + 1, y + 1]]for new_x, new_y in directions:# print('==new_x, new_y :', new_x, new_y)if 0 <= new_x < len(land) and 0 <= new_y < len(land[0]) and land[new_x][new_y] == 0:temp_water_num += 1quene.append([new_x, new_y])land[new_x][new_y] = -1 # 將訪問的點標記進行標記res.append(temp_water_num)print('==res:', res)return sorted(res)sol = Solution() land = [[0, 2, 1, 0],[0, 1, 0, 1],[1, 1, 0, 1],[0, 1, 0, 1]] sol.pondSizes(land)思路2:遞歸 對經過的０進行更新替換 每掉一次遞歸 就用一個變量+1 記錄水域的個數
class Solution:def helper(self, i, j, h, w):if i < 0 or i >= h or j < 0 or j >= w or self.land[i][j] != 0:returnself.temp += 1self.land[i][j] = -1self.helper(i - 1, j, h, w)self.helper(i + 1, j, h, w)self.helper(i, j-1, h, w)self.helper(i, j+1, h, w)self.helper(i-1, j - 1, h, w)self.helper(i-1, j + 1, h, w)self.helper(i+1, j - 1, h, w)self.helper(i+1, j + 1, h, w)def pondSizes(self, land):self.land = landh = len(self.land)w = len(self.land[0])res = []for i in range(h):for j in range(w):if self.land[i][j] == 0:self.temp = 0self.helper(i, j, h, w)res.append(self.temp)# print(res)return sorted(res)land = [[0,2,1,0],[0,1,0,1],[1,1,0,1],[0,1,0,1] ] sol = Solution() res = sol.pondSizes(land) print('==res:', res)127.計算各個位數不同的數字個數
?思路:n=0有一位, n=1有10位,n=2 有 9*9位 n=3有9*9*8 n=4有9*9*8*7 大于10位就固定了
class Solution(object):def countNumbersWithUniqueDigits(self, n):""":type n: int:rtype: int"""# n=0有一位, n=1有10位,n=2 有 9*9位 n=3有9*9*8 n=4有9*9*8*7 大于10位就固定了if n == 0:return 1temp = 9k = 9res = 10for i in range(1, min(n, 10)):temp *= kres += tempk -= 1print('res:', res)return ressol = Solution() n = 10 sol.countNumbersWithUniqueDigits(n)128.最大整除子集
思路:一個子集中的最大數能夠被整數 這個子集中的其他數就不需要在除了 故先對數字進行排序 依次找子集 最后返回最長的子集即可 class Solution(object):def largestDivisibleSubset(self, nums):""":type nums: List[int]:rtype: List[int]"""if len(nums)==0:return []nums = sorted(nums)opt = [[num] for num in nums]for i in range(len(nums)):for j in range(i-1, -1, -1):if nums[i]%nums[j]==0:# 整數滿足除于子集中的最大值余數為0 則將整數加入子集if len(opt[j])+1>len(opt[i]):opt[i] = opt[j]+[nums[i]]# print('===opt:',opt)return max(opt, key=len)129.數值的整數次方
思路:對于偶數指數一分為2即可, 對于奇數指數一分為2 在乘以底數即可?
#思路:對于偶數指數一分為2即可, 對于奇數指數一分為2 在乘以底數即可 class Solution(object):def myPow(self, x, n):""":type x: float:type n: int:rtype: float"""# 2^5= 2^2 * 2^2 *2# 2^4= 2^2 * 2^2def get_power(x, n):# 遞歸終止條件if n == 0:return 1if x == 1:return 1# print('===r:', r)if n % 2 == 0: # 偶數的情況# 二分法的一半r = get_power(x, n / 2) # 分return r * r # 合else: # 奇數的情況r = get_power(x, (n - 1) / 2) # 分return r * r * x # 合if n > 0:res = get_power(x, n)#指數為正else:res = 1 / get_power(x, -n)#指數為負return ressol = Solution() x = 2.00000 n = 2 res = sol.myPow(x, n) print('==res:', res)131.第一個錯誤的版本
思路：其實就是查找第一個值，利用雙指針，故左指針與右指針不會相遇，對于左指針更新采用ｍｉｄｄｌｅ+1,而右指針為ｍｉｄｄｌｅ即可．?
# The isBadVersion API is already defined for you. # @param version, an integer # @return a bool # def isBadVersion(version):class Solution:def firstBadVersion(self, n):""":type n: int:rtype: int"""#二分查找left,right = 1,nwhile left<right:middle = left + (right - left)//2if isBadVersion(middle):right = middleelse:left = middle+1return left132.二分查找
思路：雙指針遍歷即可
class Solution:def search(self, nums: List[int], target: int) -> int:left,right = 0,len(nums)-1while left<=right:middle = left + (right-left)//2if nums[middle]==target:return middleelif nums[middle]<target:left = middle+1else:right = middle-1return -1133.最長上升子序列
思路：利用動態規劃存儲 上升序列的值
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if len(nums)==0:return 0dp = len(nums)*[0]dp[0] = 1for i in range(1, len(nums)):value = 0for j in range(i):if nums[i]>nums[j]:value = max(value, dp[j])dp[i] = value+1# print('==dp:',dp)return max(dp)事先先把ｄｐ存儲值為１?
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if len(nums)==0:return 0dp = len(nums) * [1]for i in range(1, len(nums)):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j]+1)# print('==dp:', dp)return max(dp)138.單詞規律
思路:
1. 當s中單詞數和pattern長度不相同時，直接可以判斷為不匹配
2. 當s中單詞數和pattern長度相同時：
# 以pattern中的單詞作為key，以str中的元素作為value。遍歷pattern,s,
# 當pattern中的單詞未出現過時，判斷其是否在字典中的key值出現過：
# 若是，則判斷其對應的value是否出現過，若沖突返回不匹配；
＃若否，判斷是否出現在字典中的value：若是，返回不匹配；若否，加入字典．
class Solution(object):def wordPattern(self, pattern, s):""":type pattern: str:type str: str:rtype: bool"""s = s.split(' ')if len(pattern)!=len(s):#s的長度與pattern不一樣就返回Falsereturn Falsedic_ = {}for i, x in enumerate(s):# print('==dic_:', dic_)if pattern[i] not in dic_:# print('==dic_.values():', dic_.values())if x in dic_.values():return Falsedic_[pattern[i]] = xelse:if x != dic_[pattern[i]]:return Falsereturn True# pattern = "abba" # s = "dog cat cat dog" pattern = "abba" s = "dog dog dog dog" sol = Solution() res = sol.wordPattern(pattern, s) print('==res:', res)144.三角形的最大周長
思路:兩邊之和大于第三邊，可以從小到大排序，盡可能選最長邊．
class Solution:def largestPerimeter(self, A: List[int]) -> int:A =sorted(A)#三角形滿足兩邊之和大于第三邊for i in range(len(A)-3, -1, -1):if A[i]+A[i+1]>A[i+2]:return A[i]+A[i+1]+A[i+2]return 0149.連續子數組的最大和
class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""opt = [0]*len(nums)opt[0] = nums[0]for i in range(1,len(nums)):opt[i] = max(opt[i-1]+nums[i],nums[i])return max(opt) class Solution:def maxSubArray(self, nums: List[int]) -> int:if len(nums)==0:return []res = nums[0]for i in range(1,len(nums)):nums[i] = max(nums[i], nums[i] + nums[i-1])res = max(nums[i], res)return res class Solution:def maxSubArray(self, nums: List[int]) -> int:if len(nums)==0:return []value = nums[0]res = nums[0]for i in range(1,len(nums)):value = max(nums[i], value + nums[i])res = max(value, res)return res155.移掉K位數字
思路:單調棧
class Solution(object):def removeKdigits(self, num, k):""":type num: str:type k: int:rtype: str"""#單調棧stack = []for digit in num:while k and stack and stack[-1]>digit:stack.pop()k -= 1stack.append(digit)# print('==stack:', stack)final_stack = stack[:-k] if k else stackreturn "".join(final_stack).lstrip('0') or "0"157.無重疊區間
思路:貪心算法得到末端最小的數?
class Solution(object):def eraseOverlapIntervals(self, intervals):""":type intervals: List[List[int]]:rtype: int"""if len(intervals)==0:return 0intervals = sorted(intervals,key=lambda x:x[-1])# print('intervals', intervals)res = [intervals[0]]for interval in intervals[1:]:if res[-1][-1] <= interval[0]:res.append(interval)else:pass# print('res:',res)return len(intervals) - len(res)158.插入區間
思路１：不斷合并更新列表即可以
class Solution:def insert(self, intervals, newInterval):intervals.append(newInterval)# print('==intervals:', intervals)intervals = sorted(intervals, key=lambda x: (x[0], x[1]))print('==intervals:', intervals)index = 0while index < len(intervals) - 1:print('==index:', index)print('==intervals:', intervals)# 合并刪除if intervals[index][1] >= intervals[index + 1][0]:intervals[index][1] = max(intervals[index][1], intervals[index + 1][1])intervals.pop(index + 1)else:index += 1return intervals# intervals = [[1, 3], [6, 9]] # newInterval = [2, 5]intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]] newInterval = [4, 8] sol = Solution() sol.insert(intervals, newInterval)思路２：開出一個新列表用于存儲滿足的即可
class Solution:def insert(self, intervals, newInterval):intervals.append(newInterval)# print('==intervals:', intervals)intervals = sorted(intervals, key=lambda x: (x[0], x[1]))print('==intervals:', intervals)merge = []for interval in intervals:if len(merge) == 0 or interval[0] > merge[-1][-1]:merge.append(interval)else:merge[-1][-1] = max(merge[-1][-1], interval[-1])print(merge)return merge# intervals = [[1, 3], [6, 9]] # newInterval = [2, 5]intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]] newInterval = [4, 8] sol = Solution() sol.insert(intervals, newInterval)161.累加數
思路：兩層for循環取出相應的值和剩下的值進行遞歸即可．?
class Solution:def backtrace(self, n1, n2, rest):sum_ = str(int(n1)+int(n2))if sum_ == rest:#找到滿足的條件return Trueif len(sum_) > len(rest) or rest[:len(sum_)] != sum_:#找到不滿足的條件return Falseelse:return self.backtrace(n2, sum_, rest[len(sum_):])def isvalid_num(self, value):"""以0開頭，例如01,065"""return len(value) > 1 and value[0] == '0'def isAdditiveNumber(self, num):if len(num) < 3:return Falsefor i in range(1, len(num)):# 找到第一個數：num[:i]for j in range(i + 1, len(num)):# 找到第二個數：num[i:j]n1, n2, rest = num[:i], num[i:j], num[j:]# 剩下的數# print('==n1, n2, rest:', n1, n2, rest)if self.isvalid_num(n1) or self.isvalid_num(n2) or self.isvalid_num(rest): # 避免0開頭的非0數continueif self.backtrace(n1, n2, rest):return Truereturn Falsenum = "112358" sol = Solution() res = sol.isAdditiveNumber(num) print('res:', res)162.克隆圖
思路：BFS遍歷每個節點
""" # Definition for a Node. class Node:def __init__(self, val = 0, neighbors = None):self.val = valself.neighbors = neighbors if neighbors is not None else [] """ class Solution:def cloneGraph(self, node: 'Node') -> 'Node':if not node:return nodevisited = {}#存儲遍歷過的節點visited[node] = Node(node.val, [])quene = [node]while quene:pop_node = quene.pop()for neighbor in pop_node.neighbors:if neighbor not in visited:#沒有遍歷過visited[neighbor] = Node(neighbor.val, [])quene.append(neighbor)# 更新當前節點的鄰居列表visited[pop_node].neighbors.append(visited[neighbor])return visited[node]163.被圍繞的區域
思路：從邊界的'O'回退，找到依次相鄰的O則不動，否則置為'X'
# 從邊界的'O'回退，找到依次相鄰的O則不動，否則置為'X' class Solution:def helper(self, i, j, h, w):if not 0 <= i < h or not 0 <= j < w or self.board[i][j] != 'O':returnself.board[i][j] = 'F'self.helper(i - 1, j, h, w)self.helper(i + 1, j, h, w)self.helper(i, j-1, h, w)self.helper(i, j+1, h, w)def solve(self, board):"""Do not return anything, modify board in-place instead."""self.board = boardh, w = len(self.board), len(self.board[0])for i in range(h):self.helper(i, 0, h, w)self.helper(i, w - 1, h, w)print('==self.board:', self.board)for j in range(1, w-1):self.helper(0, j, h, w)self.helper(h-1, j, h, w)print('==self.board:', self.board)for i in range(h):for j in range(w):if self.board[i][j] == "F":self.board[i][j] = "O"elif self.board[i][j] == "O":self.board[i][j] = "X"print('==self.board:', self.board)return self.board board = [["X", "X", "X", "X"],["X", "O", "O", "X"],["X", "X", "O", "X"],["X", "O", "X", "X"]] # board = [["X", "X", "X"], # ["X", "O", "O"], # ["X", "X", "O"], # ["X", "O", "X"]] sol = Solution() sol.solve(board)175.一和零
思路：當成 0 1背包問題來做，只不過這道題需要兩個背包一個是裝０的，一個是裝１的，求在裝滿的時候的最大字符串量
使用i為止這個字符串 j個0 k個1 能夠容納的最多字符串
dp[i][j][k] = dp[i-1][j][k] 不選這個字符串
dp[i][j][k] = dp[i-1][j-cnt[0]][k-cnt[1]] 選這個字符串 cnt[0]代表0的個數 cnt[1]代表1的個數
代碼１：需要初始化第一個字符串的dp
import numpy as np class Solution:def count(self, str_):cnt= [0, 0]for i in str_:cnt[int(i) - 0] += 1return cntdef findMaxForm(self, strs, m, n):dp = [[[0 for _ in range(n+1)] for _ in range(m+1)] for _ in range(len(strs))]print(np.array(dp).shape)cnt = self.count(strs[0])#對第一件物品進行初始化for j in range(m+1):for k in range(n+1):dp[0][j][k] = 1 if j >= cnt[0] and k >= cnt[1] else 0print(np.array(dp).shape)for i in range(1, len(strs)):# print('==strs[i]:', strs[i])cnt = self.count(strs[i])print('==cnt', cnt)for j in range(m+1):for k in range(n+1):if (j - cnt[0])<0 or (k - cnt[1])<0:dp[i][j][k] = dp[i - 1][j][k]else:dp[i][j][k] = max(dp[i-1][j][k], dp[i - 1][j - cnt[0]][k - cnt[1]]+1)print(np.array(dp))return dp[len(strs)-1][m][n]strs = ["10", "0001", "111001", "1", "0"] m = 5#0 n = 3#1 sol = Solution() res= sol.findMaxForm(strs, m, n) print('res:',res)代碼２：多生成一個字符串空間dp，就不需要初始化第一個字符串
# 使用i為止這個字符串 j個0 k個1 能夠容納的最多字符串 # dp[i][j][k] = dp[i-1][j][k] 不選這個字符串 # dp[i][j][k] = dp[i-1][j-cnt[0]][k-cnt[1]] 選這個字符串 import numpy as np class Solution:def count(self, str_):cnt= [0, 0]for i in str_:cnt[int(i) - 0] += 1return cntdef findMaxForm(self, strs, m, n):dp = [[[0 for _ in range(n+1)] for _ in range(m+1)] for _ in range(len(strs)+1)]print(np.array(dp).shape)for i in range(1, len(strs)+1):# print('==strs[i]:', strs[i])cnt = self.count(strs[i-1])print('==cnt', cnt)for j in range(m+1):for k in range(n+1):if (j - cnt[0])<0 or (k - cnt[1])<0:dp[i][j][k] = dp[i - 1][j][k]else:dp[i][j][k] = max(dp[i-1][j][k], dp[i - 1][j - cnt[0]][k - cnt[1]]+1)print(np.array(dp))return dp[len(strs)][m][n]181.兩地調度問題
１．貪心算法未優化版
# 貪心算法: #思路:對ＡＢ兩地的費用之差絕對值排序,利用貪心算法選擇最小費用的城市，當最小費用的城市人滿了以后，剩下的人就去另外一個城市 class Solution:def twocitycost(self, costs):# 對差值進行排序costs = sorted(costs, key=lambda x: abs(x[0] - x[1]), reverse=True)print('==costs:', costs)total_cost = 0toA, toB = 0, 0every_city_person = len(costs) // 2for i, cost in enumerate(costs):if toA < every_city_person and toB < every_city_person:if cost[0] < cost[-1]: # Ａ地未去滿同時Ａ地的費用最小toA = +1total_cost += cost[0]else: # B地未去滿同時B地的費用最小toB = +1total_cost += cost[-1]elif toA<every_city_person:#Ｂ地滿了toA+=1total_cost = cost[0]else:#A地滿了toB += 1total_cost = cost[-1]print('==total_cost:', total_cost)return total_cost２．貪心算法優化版
#優化版 #思路:對ＡＢ兩地的費用之差排序,自然前面的人費用最小 后面的人費用最大 class Solution:def twocitycost(self, costs):# 對差值進行排序costs = sorted(costs, key=lambda x: x[0] - x[1])print('==costs:', costs)total_cost = 0every_city_person = len(costs) // 2for i in range(every_city_person):total_cost+=costs[i][0]+costs[i+every_city_person][-1]print('==total_cost:', total_cost)return total_costcosts = [[10, 20], [30, 200], [400, 50], [30, 20]] sol = Solution() sol.twocitycost(costs)
185.合并兩個有序數組
思路:歸并排序中的并
#思路:歸并排序中的并 class Solution:def merge(self, nums1, m, nums2, n):"""Do not return anything, modify nums1 in-place instead."""l, r = 0, 0nums1_copy = nums1[:m].copy()nums1 = []while l<len(nums1_copy) and r<len(nums2):if nums1_copy[l]<nums2[r]:nums1.append(nums1_copy[l])l+=1else:nums1.append(nums2[r])r+=1nums1+=nums1_copy[l:]nums1+=nums2[r:]return nums1nums1 = [1,2,3,0,0,0] m = 3 nums2 = [2,5,6] n = 3 sol = Solution() res = sol.merge(nums1, m, nums2, n) print('==res:', res)思路2:
class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""res = []i, j = 0, 0while i < m and j < n:if nums1[i]<nums2[j]:res.append(nums1[i])i += 1else:res.append(nums2[j])j += 1for k in range(i, m):res.append(nums1[k])for k in range(j, n):res.append(nums2[k])nums1[:] = resreturn nums1188.移除無效的括號
思路:棧用來保存索引和相應的左右括號
class Solution:def minRemoveToMakeValid(self, s):stack = []for i in range(len(s)):# print('===s[i]==', s[i])# print('==i, stack:', i, stack)if s[i] == '(':stack.append((i, '('))elif s[i] == ')':if len(stack) and stack[-1][-1]=='(':stack.pop()else:stack.append((i, ')'))else:pass# print('===stack', stack)stack_index = [i[0] for i in stack]res = ''for i in range(len(s)):if i not in stack_index:res+=s[i]# print('==res:', res)return ress = "a)b(c)d" # s = "lee(t(c)o)de)" # s = "))((" sol = Solution() sol.minRemoveToMakeValid(s)189.轉置矩陣
思路1.開辟二維數組
import numpy as np class Solution:def transpose(self, A):print(np.array(A))rows = len(A)cols = len(A[0])res = [[0] * rows for _ in range(cols)]print(np.array(res))for i in range(rows):for j in range(cols):res[j][i] = A[i][j]print(np.array(res))return resA = [[1,2,3],[4,5,6]] sol = Solution() res = sol.transpose(A) print('==res:', res)思路2:用zip
class Solution:def transpose(self, A: List[List[int]]) -> List[List[int]]:return list(zip(*A))193.面試題 08.13. 堆箱子
思路:其實就是在找最長上升子序列 可以將箱子先從小到大排序 在尋找最長子序列
#dp[i] 代表以第 i 個箱子放在最底下的最大高度 class Solution:def pileBox(self, box):dp = [0]*len(box)print('==dp:', dp)box = sorted(box)# print('=box:', box)for i in range(len(box)):dp[i] = box[i][-1]for j in range(i):if box[i][0] > box[j][0] and box[i][1] > box[j][1] and box[i][-1] > box[j][-1]:dp[i] = max(dp[i], dp[j]+box[i][-1])print('==dp:', dp)return max(dp) # box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]] box = [[1, 1, 1], [2, 3, 4], [3, 4, 5],[2, 6, 7]] sol = Solution() sol.pileBox(box)198.字符串中的第一個唯一字符
思路:利用hash統計每個字符出現的個數,在判斷hash中字符個數為１的字母，即找到
class Solution:def firstUniqChar(self, s):letter_num = {}for i in s:letter_num[i] = letter_num.get(i, 0) + 1print('==letter_num:', letter_num)for i in range(len(s)):if letter_num.get(s[i]) == 1:return iprint('==res:', res)return -1s = "loveleetcode" # s = "" # s = "cc" sol = Solution() sol.firstUniqChar(s)199.分發糖果
思路:從左往右找遞增 在從右往左找遞增
class Solution:def candy(self, ratings):n = len(ratings)dp = [0] * ndp[0] = 1#每個孩子至少一顆糖 從左往右 找遞增的for i in range(1, n):if ratings[i] > ratings[i - 1]:dp[i] = dp[i - 1] + 1else:dp[i] = 1print('==dp:', dp)#在從右往左 找遞增的for i in range(n - 2, -1, -1):if ratings[i] > ratings[i + 1] and dp[i] <= dp[i+1]:#i的分比i+1高,同時i的糖還<=i+1的糖dp[i] = dp[i+1] + 1print('==dp:', dp)return sum(dp)ratings = [1, 0, 2] # ratings = [1, 3, 4, 5, 2] sol = Solution() sol.candy(ratings)ｃ++實現:
class Solution { public:int candy(vector<int>& ratings) {int n = ratings.size();vector<int> left(n, 0);left[0] = 1;int res = 0;for(int i = 1; i < n; i++){if(ratings[i] > ratings[i-1]){left[i] = left[i-1] + 1;}else{left[i] = 1;}}for(int i = n - 2; i>=0; i--){if(ratings[i] > ratings[i+1] && left[i] <= left[i+1]){left[i] = left[i+1] + 1;}res += left[i+1] ;}return res + left[0];} };總結
以上是生活随笔為你收集整理的python刷题+leetcode(第二部分)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： JavaSE——Java介绍与环境变量简
- 下一篇： OpenCV与图像处理学习十七——Ope