python刷题+leetcode(第一部分)
生活随笔
收集整理的這篇文章主要介紹了
python刷题+leetcode(第一部分)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
1. 設計前中后隊列
思路:python代碼直接利用list的insert特性
class FrontMiddleBackQueue:def __init__(self):self.queque = []def pushFront(self, val: int) -> None:self.queque.insert(0, val)def pushMiddle(self, val: int) -> None:self.queque.insert(len(self.queque)//2, val)def pushBack(self, val: int) -> None:self.queque.append(val)def popFront(self) -> int:if self.queque: return self.queque.pop(0)return -1def popMiddle(self) -> int:if self.queque: return self.queque.pop((len(self.queque)-1)//2)return -1def popBack(self) -> int:if self.queque: return self.queque.pop(-1)return -1# Your FrontMiddleBackQueue object will be instantiated and called as such: # obj = FrontMiddleBackQueue() # obj.pushFront(val) # obj.pushMiddle(val) # obj.pushBack(val) # param_4 = obj.popFront() # param_5 = obj.popMiddle() # param_6 = obj.popBack()ｃ++實現:利用vector特性
class FrontMiddleBackQueue { public:vector<int> queue;FrontMiddleBackQueue() {}void pushFront(int val) {queue.insert(queue.begin(), val);}void pushMiddle(int val) {int pos = queue.size() / 2;queue.insert(queue.begin() + pos, val);}void pushBack(int val) {queue.push_back(val);}int popFront() {if(queue.empty()){return -1;}int value = queue[0];queue.erase(queue.begin());return value;}int popMiddle() {if(queue.empty()){return -1;}int pos = (queue.size()-1)/2;int value = queue[pos];queue.erase(queue.begin() + pos);return value;}int popBack() {if(queue.empty()){return -1;}int value = queue[queue.size()-1];// queue.erase(queue.end()-1);queue.pop_back();return value;} };/*** Your FrontMiddleBackQueue object will be instantiated and called as such:* FrontMiddleBackQueue* obj = new FrontMiddleBackQueue();* obj->pushFront(val);* obj->pushMiddle(val);* obj->pushBack(val);* int param_4 = obj->popFront();* int param_5 = obj->popMiddle();* int param_6 = obj->popBack();*/2. 字典序的第K小數字
思路:
python代碼:
class Solution:def getNode(self, n, first, second):nums = 0while first <= n:nums += min(n+1, second) - firstfirst *= 10second *= 10return numsdef findKthNumber(self, n: int, k: int) -> int:cur = 1k -= 1while k > 0:nums = self.getNode(n, cur, cur+1)if nums <= k: #第k個數不在以cur為根節點的樹上cur += 1 #cur在字典序數組中從左往右移動k -= numselse:#在子樹中cur *= 10 #cur在字典序數組中從上往下移動k -= 1 #刨除根節點return curc++實現:
class Solution { public:int getNode(long n, long first, long second){int nums = 0;while(first <= n){nums += min(n+1, second) - first;first *= 10;second *= 10;}return nums;}int findKthNumber(int n, int k) {long cur = 1;k -= 1;while(k > 0){int nums = getNode(n, cur, cur + 1);if(nums <= k){cur += 1;k -= nums;}else{cur *= 10;k -= 1;}}return cur;} };3.復原 IP 地址
思路:遞歸+回溯
分兩種情況:如果開頭是0 需要單獨拿出來， 不是的話 在分 1位， 2位， 3位的 只是需要注意，兩位 三位需要有數字范圍限定
class Solution:def backtrace(self, s, track, count):if len(track) == 4 and count == self.length:self.res.append('.'.join(track))returnif len(track) == 4 and count != self.length:returnif count == self.length:returnn = len(s)for i in range(n):if s[i] == '0': #0要單獨拿出來 self.backtrace(s[i+1:], track + ['0'], count + 1)else:self.backtrace(s[i+1:], track + [s[i]], count + 1)#一位數的if i < n-1 and 10 <= int(s[i:i+2])<=99:self.backtrace(s[i+2:], track + [s[i:i+2]], count + 2)#兩位數的if i < n-2 and 100 <= int(s[i:i+3])<=255:self.backtrace(s[i+3:], track + [s[i:i+3]], count + 3)#三位數的def restoreIpAddresses(self, s: str) -> List[str]:self.res = []self.length = len(s)if self.length > 12:return []self.backtrace(s, [], 0)return self.resc++實現:
class Solution { public:vector<string> res;void backtrace(string s, vector<string>& track, int count, int length){if(track.size() == 4 && count == length){ string temp = "";for(int i = 0; i < 4; i++){temp += track[i];if(i != 3){temp += ".";}}res.push_back(temp);return;}if(track.size() == 4 && count != length){return;}if(count == length){return;}int n = s.size();for(int i = 0; i < n; i++){if(s[i] == '0'){track.push_back("0");backtrace(s.substr(i + 1, n - 1), track, count + 1, length);track.pop_back();}else{string temp_;temp_ = s[i];track.push_back(temp_);backtrace(s.substr(i + 1, n - 1), track, count + 1, length);track.pop_back();if(i < n-1 && 10 <= atoi(s.substr(i, 2).c_str()) && atoi(s.substr(i, 2).c_str()) <= 99){track.push_back(s.substr(i, 2));backtrace(s.substr(i + 2, n - 2), track, count + 2, length);track.pop_back();}if(i < n-2 && 100 <= atoi(s.substr(i, 3).c_str()) && atoi(s.substr(i, 3).c_str()) <= 255){track.push_back(s.substr(i, 3));backtrace(s.substr(i + 3, n - 3), track, count + 3, length);track.pop_back();}}}} vector<string> restoreIpAddresses(string s) {int length = s.size();if(length > 12){return {};}vector<string> track;backtrace(s, track, 0, length);return res;} };4.無重復字符的最長子串
思路1.暴力破解
""" 給一個字符串，找出最長的沒有重復字符的子字符串，并返回該字符串的長度 """ # class solution: def lengthOfLongestSubstring(s):max_len=0if(len(s)==1 or len(s)==0):max_len=len(s)#第一層循環從最左側到右側第二個，第二層循環從第一層緊跟的一個到最后一個，找出所有不重復的子字符串，比較長度得出最長。for i in range(0,len(s)-1):for j in range(i+1,len(s)):if s[j] in s[i:j]:if j-i>max_len:right=jleft=imax_len=right-leftarray=s[i:j]breakelif j==len(s)-1:if max_len<j-i+1:max_len=j-i+1array = s[:(j+1)]return max_len,array # # sol=solution() result,array=lengthOfLongestSubstring('abcabcbbb') print(result,array)思路２．滑動窗口
class Solution:def lengthOfLongestSubstring(self, s: str) -> int: dict_={}res = 0left,right=0,0while right<len(s):dict_[s[right]]=dict_.get(s[right],0)+1while dict_[s[right]]>1:dict_[s[left]]-=1left+=1res = max(res, right-left+1)right+=1return res思路３．利用字典，用key存儲字符 value存儲其相應的index
#hash 用key存儲字符 value存儲其相應的index class Solution:def lengthOfLongestSubstring(self, s):dict_={}max_length = 0start = 0for index,char in enumerate(s):if char in dict_ and start<=dict_[char]:start = dict_[char]+1else:max_length = max(max_length, index - start +1)dict_[char] = indexprint('==dict_:',dict_)return max_length s = 'abcdafg' sol = Solution() res = sol.lengthOfLongestSubstring(s) print('res:', res)5，給出兩個有序的數字列表，長度分別為m,n。找到這兩個列表中的中間值。
""" 給出兩個有序的數字列表，長度分別為m,n。找到這兩個列表中的中間值。 """ class solution:def findMedianSortedArrays(self,nums1,nums2):nums3=[0]*(len(nums1)+len(nums2))l_i,r_i,i=0,0,0#兩個列表進行比較，將較小值放入新的列表while(l_i<len(nums1)) and (r_i<len(nums2)):if nums1[l_i]<nums2[r_i]:nums3[i]=nums1[l_i]l_i+=1else:nums3[i]=nums2[r_i]r_i+=1i+=1#將未遍歷完的列表加入新的列表if l_i!=len(nums1):nums3[i:]=nums1[l_i:]else:nums3[i:]=nums2[r_i:]len_3=len(nums3)if len_3%2!=0:return float(nums3[(len_3-1)//2])return (nums3[len_3//2-1]+nums3[len_3//2])/2 sol=solution()num1=[1,3,5] num2=[2,4] result=sol.findMedianSortedArrays(num1,num2) print(result)6.將字符串?"PAYPALISHIRING"?以Z字形排列成給定的行數：
P A H N A P L S I I G Y I R之后從左往右，逐行讀取字符："PAHNAPLSIIGYIR"
暴力解法：
class Solution:def convert(self,s,numRows):n=numRowsres_list=[]l=len(s)if n==1:return sfor i in range(n):for j in range(l):if j%(2*n-2)==i or j%(2*n-2)==2*n-2-i:res_list.append(s[j])res=''.join(res_list)return ressol=Solution() res=sol.convert('abcdefg',3) print(res)更好的解法，不需要遍歷整個字符串長度
class Solution:def convert(self, s, numRows):str_length=len(s)node_length=2*numRows-2result=''if str_length==0 or numRows==0 or numRows==1:return s#從第一行遍歷到最后一行for i in range(numRows):#大的改進for j in range(i,str_length,node_length):#第一行和最后一行和普通行的整列數據result+=s[j]#得到斜著部分 j-2*i+node_lengthif i!=0 and i!=numRows-1 and j-2*i+node_length<str_length:result+=s[j-2*i+node_length]return resultsol=Solution() res=sol.convert('abcdefg',3) print(res)7. 丟失的數字
思路:和減去nums中的數，就是缺失的啦
class Solution:def missingNumber(self, nums: List[int]) -> int:n = len(nums)sum_ = n*(n+1)//2for num in nums:sum_ -= numreturn sum_c++實現:
class Solution { public:int missingNumber(vector<int>& nums) {int n = nums.size();int sum_ = n*(n+1)/2;for(auto num: nums){sum_ -= num;}return sum_;} };8.整數反轉
class Solution:def reverse(self, x):""":type x: int:rtype: int"""sign = [-1, 1][x > 0]res=sign*int(str(abs(x))[::-1])return res if -(2**31)<=res<=2**31-1 else 0 sol=Solution() res=sol.reverse(-123) print(res)c++實現:
class Solution { public:int reverse(int x) {//棧int res = 0;while(x != 0){int temp = x % 10;x /=10;if(res > INT_MAX/10 || (res == INT_MAX/10 && temp > 7)) return 0;if(res < INT_MIN/10 || (res == INT_MIN/10 && temp < -8)) return 0;res = res * 10 + temp;}return res;}};9.把字符串轉換成整數
'
思路:刪除首尾空格
判斷刪除空格后的第一個字符是否是+或者-
? ? ? ? ? ? ? ? ? ? ? ? 如果是+或者- 下一個字符必須是數字 否則返回0,是的話就一直合并到字母
? ? ? ? ? ? ? ? ? ? ? ? 如果是數字就一直合并到出現字母停止
10.外觀數列
思路:核心是雙指針做聚類，只不過需要聚類的字符串需要更新，外面需要套一個for循環
python代碼:
class Solution:def countAndSay(self, n: int) -> str:#雙指針外面 套一個循環n就行pre = ""res = "1"for k in range(1, n):pre = resres = ""left, right = 0, 0while right < len(pre):while right < len(pre) and pre[left] == pre[right]:right += 1res += str(right - left) + pre[left]left = rightreturn resc++代碼:
class Solution { public:string countAndSay(int n) { string res = "1";string s = "";for(int k = 1; k < n; k++){s = res;res = "";int left = 0, right = 0;while(right < s.size()){while(right < s.size() && s[left] == s[right]){right++;}res += to_string(right - left) + s[left];left = right;}}return res;} };11.只出現一次的數字 III
思路1：hash
class Solution:def singleNumber(self, nums: List[int]) -> List[int]:dict_ = {}for num in nums:if num not in dict_:dict_[num] = 1else:dict_[num] -= 1res = []for key in dict_:if dict_[key] != 0:res.append(key)return resc++:
class Solution { public:vector<int> singleNumber(vector<int>& nums) {map<int, int> dict_;for(auto num: nums){if(dict_.count(num) == 0){dict_[num] += 1;}else{dict_[num] -= 1;}}vector<int> res;map<int, int> ::iterator it;for(it = dict_.begin(); it != dict_.end(); it++){if(it->second != 0){res.push_back(it->first);}}return res;} };思路2:因為有兩個不同的數，如果能將兩個不同的數分組開，那么異或一下自然就出來了。
class Solution { public:vector<int> singleNumber(vector<int>& nums) {//div保持的是兩位要找的數的異或 ^long div = 0;int a = 0, b = 0;for(int num : nums)div ^= num;//取最低位的1，這個1表示的是在這個bit，a與b一個為0一個為1div &= -div;for(int num : nums){ if(div & num)a ^= num;else{b ^= num;}}return {a,b};} };12. 整數轉羅馬數字
思路:貪心算法
class Solution:def intToRoman(self, num: int) -> str:# 使用哈希表，按照從大到小順序排列dict_ = {1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}res = ""for key in dict_:count = num // keyif count != 0:res += count*dict_[key]num %= keyreturn res;c++實現:
class Solution { public:string intToRoman(int num) {int value[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};string str_[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};string res;for(int i = 0; i < 13; i++){while(num >= value[i]){num -= value[i];res += str_[i];}}return res;} };13.羅馬數字轉整數
思路:貪心算法
class Solution:def romanToInt(self, s: str) -> int:dict_ = {'M':1000,"CM":900,'D':500, "CD":400, 'C':100, "XC":90, 'L':50,"XL":40, 'X':10, "IX":9, 'V':5, "IV":4,'I':1}n = len(s)res = 0i= 0while i < n:if i < n-1 and s[i:i+2] in dict_:res += dict_[s[i:i+2]]i += 2else:res += dict_[s[i]]i += 1return resc++實現:?
class Solution { public:int romanToInt(string s) {int value[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};string str_[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};map<string, int> dict_;int length = sizeof(value)/sizeof(value[0]);for(int i = 0; i < length; i++){dict_[str_[i]] = value[i];}int res = 0;int i = 0;int n = s.size();while(i < n){if (i < n-1 && dict_.count(s.substr(i, 2))){res += dict_[s.substr(i, 2)];i += 2;}else{res += dict_[s.substr(i, 1)];i++;}}return res;} };14. 最長公共前綴
找最短字符串即可
class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:min_length = min([len(str_) for str_ in strs]) #最短字符串for i in range(min_length):for j in range(1, len(strs)):if strs[0][i] != strs[j][i]:return strs[0][:i]return strs[0][:min_length]c++實現:
class Solution { public:string longestCommonPrefix(vector<string>& strs) {int min_lenth = INT_MAX;int n = strs.size();for(int i = 0; i < n; i++){int temp_ = strs[i].size();if(temp_ < min_lenth){min_lenth = temp_;}} for(int i = 0; i < min_lenth; i++){for (int j = 1; j < n; j++){if(strs[0][i] != strs[j][i]){return strs[0].substr(0, i);}}}return strs[0].substr(0, min_lenth);} };14.三數之和
思路1: 固定兩數，尋找第三個數，兩層循環，最復雜解法，列表比較大時，時間會很長
class Solution:def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""result=[]nums.sort()length=len(nums)for i in range(length-1):for j in range(i+1,length):if -(nums[i]+nums[j]) in nums[j+1:]:tmp=[nums[i],nums[j],-(nums[i]+nums[j])]if tmp not in result:result.append(tmp)return result思路2: 雙指針，固定一個數，讓其余兩個數從第一個數+1和尾 向中間靠近，只需要循環一遍
# 雙指針:排好序以后，雙指針去尋找兩數之和等于第一個 class Solution:def threeSum(self, nums):nums = sorted(nums)res = []n = len(nums)print('==nums:', nums)for i in range(n):if i>0 and nums[i]==nums[i-1]:#去除相同的第一個數[-1, 0, 1, 2, -1, -4]continuestart = i + 1end = n - 1# print('==start:', start)# print('==end:', end)while start < end:if nums[i] + nums[start] + nums[end] == 0:res.append([nums[i], nums[start], nums[end]])start += 1end -= 1while start<end and nums[start]==nums[start-1]:# 首部出現連續兩個數[-2, 0, 0, 2, 2]start+=1while start<end and nums[end]==nums[end+1]:# 尾部出現連續兩個數[-2, 0, 0, 2, 2]end-=1elif (nums[i] + nums[start] + nums[end]) > 0:end -= 1else:start += 1print('==res:', res)return res# nums = [-1, 0, 1, 2, -1, -4] nums = [-2, 0, 0, 2, 2] sol = Solution() sol.threeSum(nums)十五：最接近的三數之和
固定一個數，讓其余兩個數從首，尾 向中間靠近，只需要循環一遍
class Solution:def threeSumClosest(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""nums.sort()length=len(nums)res=[]for i,num in enumerate(nums[0:-2]):l,r=i+1,length-1if num+nums[r]+nums[r-1]<target:#從右邊遍歷res.append(num+nums[r]+nums[r-1])elif num+nums[l]+nums[l+1]>target:#從左邊遍歷res.append(num + nums[l] + nums[l+1])else:while l<r:#左邊索引小于右邊時，遍歷res.append(num + nums[l] + nums[r])if num+nums[l]+nums[r]<target:l+=1elif num+nums[l]+nums[r]>target:r-=1else:return targetres.sort(key=lambda x:abs(x-target))return res[0]nums = [-1,2,1,-4] target = 1. sol=Solution() result=sol.threeSumClosest(nums,target) print(result)16.給定一個僅包含數字?2-9?的字符串，返回所有它能表示的字母組合。
給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/description/
輸入："23" 輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. class Solution:def letterCombinations(self, digits):""":type digits: str:rtype: List[str]"""if not digits: return []#建立字典table={'2':['a','b','c'],'3':['d','e','f'],'4':['g','h','i'],'5':['j','k','l'],'6':['m','n','o'],'7':['p','q','r','s'],'8':['t','u','v'],'9':['w','x','y','z']}result=['']for digit in digits:str_list=[]for char_single in table[digit]:str_list+=[x+char_single for x in result]print(str_list)#result存儲前一個數對應的字母result=str_listreturn result17.Pow(x, n)
思路:一層一層遞歸 超時
class Solution:def myPow(self, x: float, n: int) -> float:if n == 0:return 1if n == 1:return xif n > 0:return x*self.myPow(x, n-1)else:return 1/(x*self.myPow(x, abs(n)-1))思路:快速冪
class Solution:def help(self, x, n):if n == 0:return 1temp = self.myPow(x, n//2)if n % 2 == 0:return temp*tempelse:return x*(temp*temp)def myPow(self, x: float, n: int) -> float:if n > 0:return self.help(x, n)else:return 1 / self.help(x, -n)c++實現:
class Solution { public:double help(double x, long long n){if(n == 0){return 1.;}double temp = help(x, n / 2);if (n % 2){return x*(temp*temp);}else{return temp*temp;}}double myPow(double x, int n) {long long N = n;if(n > 0){return help(x, N);}else{return 1. / help(x, -N);}} };18：螺旋矩陣
思路:循環打印
class Solution:def help(self, x1, x2, y1, y2, matrix):for i in range(x1, x2 + 1):self.res.append(matrix[y1][i]) #1, 2, 3for i in range(y1 + 1, y2 + 1):self.res.append(matrix[i][x2]) #6, 9if x1 < x2 and y1 < y2:for i in range(x2 - 1, x1, -1):self.res.append(matrix[y2][i]) #8for i in range(y2, y1, -1):self.res.append(matrix[i][x1]) #7, 4def spiralOrder(self, matrix: List[List[int]]) -> List[int]:self.res = []x1, y1, x2, y2 = 0, 0, len(matrix[0]) - 1, len(matrix) - 1while(x1 <= x2 and y1 <= y2):self.help(x1, x2, y1, y2, matrix)x1 += 1y1 += 1x2 -= 1 y2 -= 1return self.resc++實現:
class Solution { public:vector<int> res;void help(int x1, int y1, int x2, int y2, vector<vector<int>>& matrix){for(int i = x1; i < x2 + 1; i++){res.push_back(matrix[y1][i]); //1, 2, 3}for(int i = y1 + 1; i < y2 + 1; i++){res.push_back(matrix[i][x2]); //6, 9}if(x2 > x1 && y2 > y1){for(int i = x2 - 1; i > x1 ; i--){res.push_back(matrix[y2][i]); //8}for(int i = y2; i > y1 ; i--){res.push_back(matrix[i][x1]); //7,4}} }vector<int> spiralOrder(vector<vector<int>>& matrix) {int x1 = 0, y1 = 0, x2 = matrix[0].size() - 1, y2 = matrix.size() - 1;while(x1 <= x2 && y1 <= y2){help(x1, y1, x2, y2, matrix);x1++;y1++;x2--;y2--;}return res;} };20-1.用棧實現隊列
思路:就是將先進后出換成先進先出，這樣的話在出隊列的時候，需要將棧A除去棧底的元素給棧B,在彈出A中元素，在把棧B給A,一直循環保持棧A只有一個元素
python代碼:
class MyQueue:def __init__(self):"""Initialize your data structure here."""self.stack_A = []self.stack_B = []def push(self, x: int) -> None:"""Push element x to the back of queue."""self.stack_A.append(x)def pop(self) -> int:"""Removes the element from in front of queue and returns that element."""while len(self.stack_A)>1:self.stack_B.append(self.stack_A.pop())value = self.stack_A.pop()while len(self.stack_B):self.stack_A.append(self.stack_B.pop())return valuedef peek(self) -> int:"""Get the front element."""if len(self.stack_A):return self.stack_A[0]else:return Nonedef empty(self) -> bool:"""Returns whether the queue is empty."""if len(self.stack_A):return Falseelse:return True# Your MyQueue object will be instantiated and called as such: # obj = MyQueue() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.peek() # param_4 = obj.empty()c++:
#include <map> #include <vector> #include <iostream> #include <string> #include <algorithm> #include <limits.h> #include <math.h> #include <stack>class MyQueue { public:stack<int> stack_A;stack<int> stack_B;/** Initialize your data structure here. */MyQueue() {} /** Push element x to the back of queue. */void push(int x) {stack_A.push(x);} /** Removes the element from in front of queue and returns that element. */int pop() {if(stack_B.empty()){while (!stack_A.empty()){stack_B.push(stack_A.top());stack_A.pop();}} int value = stack_B.top();stack_B.pop();return value;} /** Get the front element. */int peek() {int res = pop();stack_B.push(res);return res;} /** Returns whether the queue is empty. */bool empty() {return stack_A.empty() && stack_B.empty();} };int main() {MyQueue* obj = new MyQueue();int x=1;obj->push(x);x=2;obj->push(x);x=3;obj->push(x);int param_2 = obj->pop();cout<<"param_2:"<<param_2<<endl;int param_3 = obj->peek();cout<<param_3<<endl;bool param_4 = obj->empty();cout<<param_4<<endl;delete obj;obj=NULL;return 0; }20-2.用隊列實現棧
思路：就是將先進先出換成先進后出，這樣的話在出棧的時候，需要將隊列A除去隊尾的元素給隊列B,在彈出A中元素，在把隊列B給A,一直循環保持隊列A只有一個元素
python代碼：
class MyStack:def __init__(self):"""Initialize your data structure here."""self.quene_A = []self.quene_B = []def push(self, x):"""Push element x onto stack."""self.quene_A.append(x)def pop(self):"""Removes the element on top of the stack and returns that element."""if len(self.quene_A)==0:return Nonewhile len(self.quene_A)>1:self.quene_B.append(self.quene_A.pop(0))value = self.quene_A.pop()self.quene_A=self.quene_Bself.quene_B =[]return valuedef top(self):"""Get the top element."""if len(self.quene_A) == 0:return Nonereturn self.quene_A[-1]def empty(self):"""Returns whether the stack is empty."""if len(self.quene_A):return Trueelse:return False # Your MyStack object will be instantiated and called as such: obj = MyStack() obj.push(1) obj.push(2) obj.push(3) param_2 = obj.pop() print('==param_2:', param_2) param_3 = obj.top() print('==param_3:', param_3) param_4 = obj.empty() print('=param_4:', param_4)c++:
#include <map> #include <vector> #include <iostream> #include <string> #include <algorithm> #include <limits.h> #include <math.h>class MyStack { public:queue<int> queue_A;queue<int> queue_B;/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {queue_A.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int length = queue_A.size();cout<<length<<endl;while (length>1)//讓A中只有一個元素{ length--;queue_B.push(queue_A.front());queue_A.pop();}int res = queue_A.front();//彈出的A就是棧頂元素queue_A.pop();queue_A = queue_B;while (!queue_B.empty()){queue_B.pop();}return res;}/** Get the top element. */int top() {return queue_A.back();}/** Returns whether the stack is empty. */bool empty() {return queue_A.empty();} };int main() {MyStack* obj = new MyStack();int x=1;obj->push(x);x=2;obj->push(x);x=3;obj->push(x);int param_2 = obj->pop();cout<<"param_2:"<<param_2<<endl;int param_3 = obj->top();cout<<param_3<<endl;bool param_4 = obj->empty();cout<<param_4<<endl;delete obj;obj=NULL;return 0; }二十一，實現最大子列和問題
時間復雜度O(N)
class Solution:def maxSubArray(self, nums):for i in range(1,len(nums)):nums[i]+=max(nums[i-1],0)print('==nums:', nums)return max(nums) sol =Solution() # nums =[-1] nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] res = sol.maxSubArray(nums) print('res:',res)二十二，利用鏈表實現多項式加法
解題思路
存儲方式可以采用鏈表存儲和數組存儲，為了熟悉鏈式操作，所以采用鏈表存儲。其中指針定義的格式如下所示
23-1.滑動窗口中位數
#滑動窗口 雙指針 class Solution:def medianSlidingWindow(self, nums, k):left, right = 0, 0length = len(nums)res = []while right + k <= length:part_num = sorted(nums[left:right + k])print('==part_num:', part_num)if k % 2 == 1: # 奇數res.append(part_num[k // 2])else:res.append((part_num[k // 2] + part_num[k // 2 - 1]) / 2)left += 1right += 1print(res)return resnums = [1, 3, -1, -3, 5, 3, 6, 7] k = 3 sol = Solution() sol.medianSlidingWindow(nums, k)24:一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階。求該青蛙跳上一個 n?級的臺階總共有多少種跳法。
答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請返回 1。
1.?
class Solution(object):def numWays(self, n):""":type n: int:rtype: int"""if n==0:return 1if 1<=n<3:return ndp = [0]*(n+1)dp[1],dp[2] = 1,2for i in range(3, n+1):dp[i] = dp[i-1]+dp[i-2]return dp[-1]%(1000000007)2.
class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""i=1j=2for _ in range(3,n):i,j=j,i+jreturn i+j if n>2 else n24-2.使用最小花費爬樓梯
class Solution:def minCostClimbingStairs(self, cost):dp = [0]*len(cost)dp[0],dp[1] =cost[0],cost[1]for i in range(2,len(cost)):dp[i] = min(dp[i-1],dp[i-2])+cost[i]print(dp)return min(dp[-1],dp[-2])sol =Solution() cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] sol.minCostClimbingStairs(cost)c++:
class Solution { public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n, 0);dp[0] = cost[0];dp[1] = cost[1];for(int i=2; i<n; i++){dp[i] = min(dp[i-1], dp[i-2]) + cost[i];}return min(dp[n-1], dp[n-2]);} };二十五：#一個四位數，如1024，1004，打印出他們的中文形式，如果一千零二十四，一千零四
a=9002 number_key={'0':'零','1':'一','2':'二','3':'三','4':'四','5':'五','6':'六','7':'七','8':'八','9':'九'} c='' if a%1000:for i,_ in enumerate(str(a)):while(i==0):c+=number_key[str(a)[i]]+'千'breakwhile(i==1):if str(a)[i]=='0' and str(a)[i]==str(a)[i+1]:c+=number_key[str(a)[i]]breakif str(a)[i]=='0' and str(a)[i]!=str(a)[i+1]:c+=number_key[str(a)[i]]+number_key[str(a)[i+1]]+'十'breakif str(a)[i] !='0' and str(a)[i+1]=='0':c+=number_key[str(a)[i]]+'百'breakelse:c+=number_key[str(a)[i]]+'百'+number_key[str(a)[i+1]]+'十'breakwhile(i==3):if str(a)[i]=='0':breakelse:c += number_key[str(a)[i]]break else:c+=number_key[str(a)[0]]+'千' print(c)二十六：#找一串最長字符串 不含數字
#找一串最長字符串 不含數字 str1 = "abc123abcd234abcdefgha324adsdawqdasdaseqqwe345abchded"#第一種解法 #空間換時間做法 O(n) all_count=[] count='' flag=0 for i in str1:if i.isdigit():flag=1if len(count):all_count.append(count)count=''else:flag=0count+=iprint(all_count) num=[len(i) for i in all_count] print(all_count[num.index(max(num))])二十七：# 給定一行字符串，求出這行字符串中出現頻率最高的字符，字符串中含有標點符號， # 字符不區分大小寫。如果出現頻率相同時，輸出先出現在字符串中的字符。
s='AbAdefg ahigkl Mnopq rstu o v wBBBBBB!'a={s[0]:1} for i in s[1:]:if i !=' ':if i in a:a[i]+=1else:a[i]=1print(a)print(a.items()) #a.items() 將dict變成list b=sorted(a.items(),key=lambda x:x[1]) print(b) print(b[-1][0]) print(b[-1][1])二十八：#給出一個字符串，然后計算字符串中數字的和，
s=input() # s='ssddd-12jijij-12hi-12' a='' for i in s:if i.isdigit() or i=='-':a+=ielse:a+='+' print(a)if '-' in a:print(eval(a)) else:print(int(a))eval知識補充：
x = 7 print(eval( '3 * x' )) print(eval('2 +++- 2'))二十九：#有一對奶牛，從出生后的第四年開始生小牛，每次生一對小牛， # 問現在有m對小牛，在第n年后有多少奶牛？
def cal(n):if n==None:return Noneif n<=3:return 1else:return cal(n-3)+cal(n-1) #上一年的牛 + 今年出生的牛n=4 m=2 print(cal(n))三十：漁夫捕魚
# A、B、C、D、E五人在某天夜里合伙捕魚 最后疲憊不堪各自睡覺
# 第二天A第一個醒來 他將魚分為5份 扔掉多余的1條 拿走自己的一份
# B第二個醒來 也將魚分為5份 扔掉多余的1條 拿走自己的一份
# 然后C、D、E依次醒來也按同樣的方式分魚 問他們至少捕了多少條魚
total=6 while True:enough=Truesingle_fish=totalfor person in range(5):if (single_fish -1) % 5==0:print('before single_fish=', single_fish)single_fish=(single_fish-1)//5*4print('after single_fish=', single_fish)else:enough=Falsebreakif enough:print('total=', total)breaktotal+=532.刪除排序數組中的重復項
class Solution:def removeDuplicates(self, nums):# temp=0# n = len(nums)# for i in range(1,n):# if nums[i]==nums[i-1]:# temp+=1# return n-tempj = 0for i in range(1, len(nums)):if nums[i] != nums[j]:j += 1nums[j] = nums[i]print(nums)return j + 1nums = [1, 1, 2] sol = Solution() res = sol.removeDuplicates(nums) print('==res:', res)三十三.給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素最多出現兩次，返回移除后數組的新長度。給定 nums = [1,1,1,2,2,3],函數應返回新長度 length = 5, 并且原數組的前五個元素被修改為 1, 1, 2, 2,3 。
nums = [1,1,1,2,2,3,3,3,4]class Solution(object):def removeDuplicates(self, nums):""":type nums: List[int]:rtype: int"""if len(nums)<=2:return len(nums)k=2for i in range(k,len(nums)):if nums[i]!=nums[k-1] or nums[i]!=nums[k-2]:nums[k]=nums[i]k+=1return ksol=Solution() k=sol.removeDuplicates(nums) print(k) print(nums[:k])三十四:給定一個按照升序排列的整數數組?nums，和一個目標值?target。找出給定目標值在數組中的開始位置和結束位置。
nums = [5,7,7,8,8,10] target = 8 def solution(nums,target):a=[]#O(N)時間復雜度for i in range(len(nums)):if target==nums[i]:a.append(i)if len(a)==0:a=[-1,-1]return a res=solution(nums,target) print('res=',res)#O(log(N))時間復雜度 雙指針查找 def solution(nums,target):low=0high=len(nums)-1while(low<=high):if target==nums[low] and target==nums[high]:return [low,high]elif target!=nums[low]:low+=1elif target!=nums[high]:high-=1return [-1,-1] res=solution(nums,target) print('res=',res)三十五:給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。你可以假設數組中無重復元素。
示例 1:
輸入: [1,3,5,6], 5
輸出: 2
三十六.給定一個無重復元素的數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字
candidates = [2,3,6,7] target = 7 所求解集為: [[7],[2,2,3] ] # #給定一個無重復元素的數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合 candidates = [2,4,6] target = 7def combinationSum(candidates, target):results=[]for i,num in enumerate(candidates):if target==num:results.append([num])elif num<target:print('num:',num)result_son=combinationSum(candidates[i:],target-num)print('result_son:',result_son)for result in result_son:result.append(num)results.append(result)return resultsres=combinationSum(candidates,target) print('res:',res)三十七.給定一個數組?candidates?和一個目標數?target?，找出?candidates?中所有可以使數字和為?target?的組合。candidates?中的每個數字在每個組合中只能使用一次。
candidates = [8,10] target = 8 class Solution:def combinationSum2(self, candidates, target):candidates.sort()print('candidates:',candidates)res=[]self.addsort(candidates,target,res,[])return resdef addsort(self,candidates,target,res,cur):for i in range(len(candidates)):if target==candidates[i]:if cur+[candidates[i]] not in res:res.append(cur+[candidates[i]])print('res:',res)elif candidates[i]>target:returnelse:self.addsort(candidates[i+1:],target-candidates[i],res,cur+[candidates[i]])solv=Solution() res=solv.combinationSum2(candidates,target) print('res:',res)三十八.合并矩形框算法
class Solution:def merge(self, intervals,threshold):# intervals.sort(key=lambda x: x[0])# print(intervals)merged = []for interval in intervals:# print('interval:',interval)#x2減去下一個框的x1if not merged or abs(merged[-1][2]-interval[0]) <threshold :if len(merged):merged[-1][-2:] = interval[-2:]else:merged.append(interval)else:merged.append(interval)print('merged:',merged)return merged# a=[[1,3],[2,6],[12,10],[15,18]] import numpy as np import cv2 points=np.array([[0,0,20,20],[30,0,20,50],[90,0,70,20],[220,0,200,200],[240,0,220,200],[250,230,260,280]]) img=np.zeros((500,500)) #before merge for point in points:x1,y1,x2,y2=pointcv2.rectangle(img,(x1,y1),(x2,y2),color=(255,255,255),thickness=1) cv2.imwrite('img_before.jpg',img)#after merge sol=Solution() res=sol.merge(points,threshold=100) print(res) #before merge # for point in res: # x1,y1,x2,y2=point # cv2.rectangle(img,(x1,y1),(x2,y2),color=(255,255,255),thickness=1) # cv2.imwrite('img_after.jpg',img)三十九.求眾數
class Solution(object):def majorityElement(self, nums):""":type nums: List[int]:rtype: int"""res={}for num in nums:if num not in res:res[num]=1else:res[num]+=1index=sorted(res,key=lambda i:res[i])return index[-1]a=[1,1,1,2,2,3,3,3,3,3] sol=Solution() res=sol.majorityElement(a) print('res:',res)四十.缺失的第一個正數
class Solution(object):def firstMissingPositive(self, nums):""":type nums: List[int]:rtype: int"""num=1for i in range(len(nums)):if num in nums:num+=1return numa=[1,2,3,-1] sol=Solution() res=sol.firstMissingPositive(a) print('res:',res)四十二.牛頓法開跟號
class Solution(object):def mySqrt(self, a):""":type x: int:rtype: int"""x0=awhile x0*x0>a:x0=(x0*x0+a)/(2*x0)return int(x0)sol=Solution() x=5 res=sol.mySqrt(x) print('res:',res)四十三.堆棧實現加減乘除（逆波蘭表達式求值）
class Solution(object):def evalRPN(self, tokens):""":type tokens: List[str]:rtype: int"""stack = []cal = {"+" : lambda x,y :x+y, "-" : lambda x,y : x-y, "*" : lambda x,y : x*y, "/" : lambda x,y : int(x/y)}for i in tokens:print('stack:',stack)if i not in ["+","-","*","/"]:stack.append(int(i))else:b = stack.pop()a = stack.pop()stack.append(cal[i](a,b))return stack[0]a=["10","6","9","3","+","-11","*","/","*","17","+","5","+"] sol=Solution() res=sol.evalRPN(a) print('res:',res)四十五.給定一個字符串，逐個翻轉字符串中的每個單詞。
輸入: " ?hello world! ?" 輸出:?"world! hello" class Solution(object):def reverseWords(self, s):""":type s: str:rtype: str"""return " ".join(s.split()[::-1])49.給定兩個數組，編寫一個函數來計算它們的交集。
class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""inter = set(nums1) & set(nums2)res = []for i in inter:res += [i] * min(nums1.count(i), nums2.count(i))return resnums1 = [1,2,3,2,1] nums2 = [2,3,2] sol=Solution() res=sol.intersection(nums1,nums2) print('res:', res)
五十.給定一個包含紅色、白色和藍色，一共?n 個元素的數組，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列。此題中，我們使用整數 0、?1 和 2 分別表示紅色、白色和藍色
https://leetcode-cn.com/problems/sort-colors/
利用三指針，（p0, p2 和curr）來分別追蹤0的最右邊界，2的最左邊界和當前考慮的元素。
class Solution(object):def sortColors(self, nums):""":type nums: List[int]:rtype: None Do not return anything, modify nums in-place instead."""p0=0curr=0p2=len(nums)-1while curr<=p2:if nums[curr]==0:nums[p0],nums[curr]=nums[curr],nums[p0]p0+=1curr+=1elif nums[curr]==1:curr += 1else:#nums[curr]==2nums[p2],nums[curr] = nums[curr],nums[p2]p2 -= 1print(nums)return numsnums=[2,0,2,1,1,0] sol=Solution() sol.sortColors(nums)51.驗證回文字符串
解法1：雙指針
class Solution(object):def isPalindrome(self, s):""":type s: str:rtype: bool"""i = 0j = len(s)-1while i<j:while i < len(s) and not s[i].isalnum():i += 1while j>=0 and not s[j].isalnum():j-=1#多個符號時 i跳得太多if i>j:return Trueif s[i].upper()!=s[j].upper():return Falseelse:i+=1j-=1#while外面自然是i>=jreturn Trues= "" sol = Solution() res = sol.isPalindrome(s) print('res:',res)解法2：
class Solution(object):def isPalindrome(self, s):""":type s: str:rtype: bool"""s = ''.join(list(filter(str.isalnum,s))).lower()print('s:',s)return s==s[::-1]五十二,驗證回文串2，字符串只包含從 a-z 的小寫字母。字符串的最大長度是50000。
https://leetcode-cn.com/problems/valid-palindrome-ii/
class Solution(object):def validPalindrome(self, s):""":type s: str:rtype: bool"""if s==s[::-1]:return Truel=0r=len(s)-1while l<r:if s[l]==s[r]:l+=1r-=1else:part1=s[l+1:r+1]part2=s[l:r]# print('part1',part1)# print('part2',part2)return part1 == part1[::-1] or part2 == part2[::-1]s= "abca" sol = Solution() res = sol.validPalindrome(s) print('res:',res)五十三.漢諾他問題
如果只有一個A直接給C,當大與1個時,將n-1暫時給B,剩下的最大的給C,然后再將n-1給C.
def hannota(n,A,B,C):if n==1:print(A+'->'+C)else:hannota(n - 1,A,C,B)print(A + '->' + C)hannota(n - 1, B, A, C)if __name__ == '__main__':n=2A='A'B='B'C='C'hannota(n,A,B,C)五十四.有效的數獨 要求：行 ，列和3x3只能出現一個數字一次
https://leetcode-cn.com/problems/valid-sudoku/
class Solution(object):def isValidSudoku(self, board):""":type board: List[List[str]]:rtype: bool"""# init datarows = [{} for i in range(9)]columns = [{} for i in range(9)]boxes = [{} for i in range(9)]# print(rows)# print(rows[2].get(3, 0))rows[2][3]=rows[2].get(3, 0)# print(rows)for i in range(9):for j in range(9):num = board[i][j]if num != '.':num = int(num)box_index = (i // 3) * 3 + j // 3# keep the current cell valuerows[i][num] = rows[i].get(num,0) + 1columns[j][num] = columns[j].get(num,0)+1boxes[box_index][num]=boxes[box_index].get(num,0)+1if rows[i][num]>1 or columns[j][num]>1 or boxes[box_index][num]>1:return Falsereturn Trueboard=[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"] ] sol = Solution() res = sol.isValidSudoku(board) print('res:') print(res)五十五.給定一個整數數組和一個整數?k，判斷數組中是否存在兩個不同的索引?i?和?j，使得?nums [i] = nums [j]，并且 i 和 j?的差的絕對值最大為 k。
https://leetcode-cn.com/problems/contains-duplicate-ii/
class Solution:def containsNearbyDuplicate(self, nums, k):""":type nums: List[int]:type k: int:rtype: bool"""nums_len = len(nums)if nums_len <= 1:return False#key存放列表值，value存放位置索引nums_dict = {}for i in range(nums_len):print(nums_dict)if nums[i] in nums_dict:if i-nums_dict[nums[i]] <= k:return Truenums_dict[nums[i]] = ireturn Falsenums = [1,2,3,1] k = 3 sol = Solution() res = sol.containsNearbyDuplicate(nums,k) print('res:') print(res)五十六.長度最小的子數組
思路:雙指針 滑動窗口
class Solution:def minSubArrayLen(self, s, nums):i = 0j = 0ans = float('inf')while j < len(nums):# 向右滑動 直到大于sif sum(nums[i:j + 1]) < s:# Sum=sum(nums[begin:right])j += 1# 找到滑窗之和大于s的地方else:# 當前長度若是小于之前的 則更新if j - i < ans:ans = j - i + 1i += 1return 0 if ans == float('inf') else anss = 7 nums = [2,3,1,2,4,3] sol = Solution() res = sol.minSubArrayLen(s, nums) print('==res:', res)五十七.滑動窗口找到長度最長的子數組? <=4 [3,1，2，1]? 最長為[1,2,1]
class Solution(object):def minSubArrayLen(self, s, nums):""":type s: int:type nums: List[int]:rtype: int"""final_begin=0final_end=0begin=0right=0ans=0#float('inf')while right<len(nums):# print('begin:', begin)# print('right:', right)# print(nums[begin:right+1])#向右滑動 直到大于sif sum(nums[begin:right+1]) <= s:# Sum=sum(nums[begin:right])right+=1# 當前長度若是大于之前的 則更新if right-begin>ans:ans = right-begin +1final_begin=beginfinal_end=right#找到滑窗之和大于s的地方else:begin+=1print('final_begin:',final_begin)print('final_end:',final_end)print(nums[final_begin:final_end+1])return 0 if ans==float('inf') else anss = 4 nums = [3,1,2,1] # s = 3 # nums = [1,1] sol=Solution() res=sol.minSubArrayLen(s,nums) print('res:',res)五十九.將矩陣存在0的行列都置零
https://leetcode-cn.com/problems/set-matrix-zeroes
import numpy as npclass Solution(object):def setZeroes(self, matrix):""":type matrix: List[List[int]]:rtype: None Do not return anything, modify matrix in-place instead."""print(np.array(matrix))# matrix=np.array(matrix)is_col=False#記錄為0的索引，并此處的行頭和獵頭置為零for i in range(len(matrix)):if matrix[i][0]==0:is_col=Truefor j in range(1,len(matrix[0])):# print(matrix[i][j])if matrix[i][j]==0:matrix[0][j] = 0matrix[i][0] = 0# breakprint(np.array(matrix))for i in range(1,len(matrix)):for j in range(1,len(matrix[0])):if not matrix[i][0] or not matrix[0][j]:matrix[i][j]=0print(np.array(matrix))# 對第一個數存在0將這一列置為0print(np.array(matrix))if matrix[0][0] == 0:for j in range(len(matrix[0])):matrix[0][j] = 0#對第一列存在0將整列置零if is_col:for i in range(len(matrix)):matrix[i][0]=0print(np.array(matrix))return matrix# matrix = [[1,1,1], # [1,0,1], # [1,1,1]] # matrix=[[0,1,2,0], # [3,4,5,2], # [1,3,1,5]] matrix=[[1,1,1],[0,1,2]] sol=Solution() res=sol.setZeroes(matrix) print('res:',res)六十.給定一個包含?n 個整數的數組?nums?和一個目標值?target，判斷?nums?中是否存在四個元素 a，b，c?和 d?，使得?a + b + c + d?的值與?target?相等？找出所有滿足條件且不重復的四元組。
https://leetcode-cn.com/problems/4sum/
class Solution(object):def fourSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[List[int]]"""nums.sort()# print('nums:',nums)ans = set()for i in range(len(nums)-3):#第一層循環到達三個數之前for j in range(i+1,len(nums)-2):#最后兩個數需要固定left=j+1 #左指針right=len(nums)-1 #右指針while(right>left):temp=nums[i]+nums[j]+nums[left]+nums[right]if temp==target:ans.add((nums[i],nums[j],nums[left],nums[right]))left+=1right-=1elif temp>target:right-=1else:left+=1# print('ans:',ans)ans = sorted(ans)res=[]for i in ans:res.append(i)# print('res:',res)return resnums = [-3,-2,-1,0,0,1,2,3] target = 0 sol=Solution() res=sol.fourSum(nums, target) print('res:',res)61.無重復字符的最長子串
思路１滑動窗口：
class Solution:def lengthOfLongestSubstring(self, s):left, right = 0, 0dict_ = {}res = 0while right < len(s):dict_[s[right]] = dict_.get(s[right], 0) + 1while dict_[s[right]] > 1:dict_[s[left]] -= 1left += 1right += 1res = max(right - left, res)print('==res:', res)return ress = "abcabcbb" sol = Solution() sol.lengthOfLongestSubstring(s)思路2．hash
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:occ = set()n = len(s)# 右指針，初始值為 -1，相當于我們在字符串的左邊界的左側，還沒有開始移動start, ans = -1, 0for i in range(n):# print('===occ:', occ)if i != 0:# 左指針向右移動一格，移除一個字符occ.remove(s[i - 1])while start + 1 < n and s[start + 1] not in occ:# 不斷地移動右指針occ.add(s[start + 1])start += 1# 第 i 到 rk 個字符是一個極長的無重復字符子串ans = max(ans, start - i + 1)return ans六十二.串聯所有單詞的子串
給定一個字符串s和一些長度相同的單詞 words。找出 s 中恰好可以由 words 中所有單詞串聯形成的子串的起始位置。
注意子串要與 words 中的單詞完全匹配，中間不能有其他字符，但不需要考慮 words 中單詞串聯的順序。
#通過滑動去裁剪主串得到子串,然后子串與需要匹配的字符串數組去統計出現的個數,個數相等即找到 class Solution:def findSubstring(self, s, words):from collections import Counterif not s or not words:return []all_len = len(''.join(words))print('==all_len:', all_len)n = len(s)words = Counter(words)print('==words', words)res = []for i in range(0, n-all_len+1):temp = s[i:i+all_len]# print(temp)c_temp=[]for j in range(0, all_len,all_len//len(words)):c_temp.append(temp[j:j+all_len//len(words)])# print(c_temp)if Counter(c_temp)==words:res.append(i)# print('res:', res)return resif __name__ == '__main__':solution = Solution()# s = "abc"# words = ["a"]s = "barfoothefoobarman"words = ["foo", "bar"]res = solution.findSubstring(s, words)print('res:', res)六十三.給你一個字符串 S、一個字符串 T，請在字符串 S 里面找出：包含 T 所有字母的最小子串。
輸入: S = "ADOBECODEBANC", T = "ABC" 輸出: "BANC"雙指針法：
from collections import Counterdef minWindow(s, t):""":type s: str:type t: str:rtype: str"""if not t or not s:return ""dict_t = Counter(t)print('==dict_t:', dict_t)required = len(dict_t)l, r = 0, 0formed = 0window_counts = {}# ans tuple of the form (window length, left, right)ans = float("inf"), None, Nonewhile r < len(s):character = s[r]window_counts[character] = window_counts.get(character, 0) + 1print('==window_counts:', window_counts)#s = "ABAACBAB"#t = "ABC"#相等的話就加1if character in dict_t and window_counts[character] == dict_t[character]:formed += 1#找到滿足要求的 進行存儲while l <= r and formed == required:character = s[l]print('==character:', character)# Save the smallest window until now.if r - l + 1 < ans[0]:ans = (r - l + 1, l, r)#window_counts[character] -= 1#左指針向右移動 出現不符合的就減一if character in dict_t and window_counts[character] < dict_t[character]:formed -= 1#移動左指針l += 1#右指針移動r += 1return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]S = "ABAACBAB" T = "ABC" res = minWindow(S, T) print('res:', res)六十四.替換子串得到平衡字符串
有一個只含有'Q',?'W',?'E','R'四種字符，且長度為?n的字符串。假如在該字符串中，這四個字符都恰好出現n/4次，那么它就是一個「平衡字符串」。
輸入：s = "QQWE" 輸出：1 解釋：我們需要把一個 'Q' 替換成 'R'，這樣得到的 "RQWE" (或 "QRWE") 是平衡的。 import collections class Solution(object):def balancedString(self, s):"""python版本:type s: str:rtype: int"""cnt = collections.Counter(s)res = n = len(s)left, avg = 0, n//4for right, c in enumerate(s):# print('c:', c)#一直進行字符減操作cnt[c] -= 1print('cnt:', cnt)#直到n//4大于單個字符的個數 說明右邊界找到 在對左邊界進行右移 找最小的長度while left < n and all(avg >= cnt[x] for x in 'QWER'):res = min(res, right - left + 1)print('res:', res)cnt[s[left]] += 1print('==cnt:', cnt)left += 1print('res:', res)return ressol = Solution()s = 'WQWRQQQW' sol.balancedString(s)六十八.不鄰接植花
圖著色問題?
# 1、構建鄰接矩陣; # 2、將1的顏色置為1，從2開始遍歷鄰接矩陣； # 3、每一次遍歷，新建一個顏色集合（[1,2,3,4]），取出key對應的花園代號，遍歷代號。 # 如果該代號花園已經有顏色了，取出其顏色，從顏色集合中去掉；如果該花園沒有顏色，跳過； # 全部代號遍歷結束后，取顏色集合第一個顏色作為當前key 的顏色，存入結果中； # 4、反復計算更新結果，最后輸出結果；class Solution(object):def gardenNoAdj(self, N, paths):""":type N: int:type paths: List[List[int]]:rtype: List[int]"""recorder = {}for i in range(1, N+1, 1):recorder[str(i)] = []for path in paths:recorder[str(path[0])].append(path[1])recorder[str(path[1])].append(path[0])print('===recorder:', recorder)#將1的顏色置為1，從2開始遍歷result = [1]for i in range(2, N+1, 1):colors = [1, 2, 3, 4]sub_nodes = recorder[str(i)]print('==sub_nodes:', sub_nodes)for sub_node in sub_nodes:if sub_node > len(result):#沒有顏色,跳過continueelse:if result[sub_node-1] in colors:#有顏色進行移除colors.remove(result[sub_node-1])result.append(colors[0])print('==result:', result)return result# N = 3 # paths = [[1, 2], # [2, 3], # [3, 1]]N = 4 paths = [[1, 2],[3, 4]] sol = Solution() sol.gardenNoAdj(N, paths)七十.找到小鎮的法官
思路：統計所有人的入度和出度信息，將滿足出度為0，入度為 N - 1的節點輸出。
#維護兩個列表一個用于記錄入度，一個用于記錄出度，滿足入度為N-1, 出度為0的就是法官 class Solution:def findJudge(self, N, trust):input_degree = [0]*Nouput_degree = [0]*Nfor trust_ in trust:input_degree[trust_[0] - 1] += 0input_degree[trust_[1] - 1] += 1ouput_degree[trust_[0] - 1] += 1ouput_degree[trust_[1] - 1] += 0print('==input_degree:', input_degree)print('==ouput_degree:', ouput_degree)for i in range(len(input_degree)):if input_degree[i] == N-1 and ouput_degree[i] == 0:return i+1return -1 # N = 2 # trust = [[1, 2]] # N = 3 # trust = [[1, 3], # [2, 3]] # N = 3 # trust = [[1,3], # [2,3], # [3,1]] N = 4 trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] sol = Solution() res = sol.findJudge(N, trust) print(res) #維護一個列表用于記錄入度與出度的差值，差值為N-1, 就是法官 class Solution:def findJudge(self, N, trust):count = [0]*Nfor trust_ in trust:count[trust_[0] - 1] -= 1count[trust_[1] - 1] += 1print('==count:', count)for i in range(len(count)):if count[i] == N-1:return i+1return -1 # N = 2 # trust = [[1, 2]] # N = 3 # trust = [[1, 3], # [2, 3]] # N = 3 # trust = [[1, 3], # [2, 3], # [3, 1]] N = 4 trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] sol = Solution() res = sol.findJudge(N, trust) print(res)七十一.課程安排 IV
利用弗洛伊德算法找出節點與節點之間的路徑，計算出鄰接矩陣。
#佛羅伊德算法:dp矩陣先進行初始化,用兩個節點是否經過中間節點,來更新中間節點的dp矩陣 class Solution:def checkIfPrerequisite(self, n, prerequisites, queries):dp = [[0 for i in range(n)] for j in range(n)]print(dp)for prerequisite in prerequisites:dp[prerequisite[0]][prerequisite[1]] = 1print(dp)for k in range(n):#k代表中間節點for i in range(n):#i開始節點for j in range(n):#j終止節點if dp[i][k] ==1 and dp[k][j]==1:dp[i][j] = 1print(dp)res = []for querie in queries:# print(dp[querie[0]][querie[-1]])res.append(dp[querie[0]][querie[-1]])return res n = 5 prerequisites = [[0, 1],[1, 2],[2, 3],[3, 4]] queries = [[0, 4],[4, 0],[1, 3],[3, 0]]sol = Solution() res = sol.checkIfPrerequisite(n, prerequisites, queries) print('res:', res)七十四.劃分為k個相等的子集
# 1、先求出數組的平均數 avg，如果平均數 avg 不為整數，也就是說數組的數字總和不能平均的分為 k 份，那么直接返回 false； # # 2、創建一個布爾數組 flag，用來記錄 nums 數組中數字的狀態（已用還是未用）。 temp 的作用是記錄當前子集的數字總和，temp 初始為 avg ，當 temp 等于 0 時，當前這個子集也就可以確定了。index 是用來記錄遍歷數組時從哪個位置開始遍歷，以防將前面的數字重新計算。 # # 3、當 temp = 0 的時候，也就是新一個子集求解完，那么繼續求解下一個子集，k - 1，temp 重新置為 avg；當 temp ！= 0 時，就是子集還未求解完，那么繼續求解子集，繼續從數組中取數字，遞歸求解。 # # 4、當 k 個子集全部求解完，返回 true，如果一直求解不出，則返回 false。 class Solution:def canPartitionKSubsets(self, nums, k):if sum(nums) % k != 0:#先判斷能不能分成k組return Falseavg = sum(nums)/kflag = [0]*len(nums)print('==flag:', flag)return self.helper(nums, flag, avg, k, avg, 0)def helper(self, nums, flag, avg, k, temp, index):if k == 0:#k為0說明劃分好了k個子集return Trueif temp == 0:#平均數減去子集的剩下數字.如果為0繼續求解下一個子集，k-1，temp重置為avg，下標index也重置為0return self.helper(nums, flag, avg, k - 1, avg, 0)#劃分當前子集for i in range(index, len(nums)):if flag[i]:#已經使用過continueflag[i] =1 #標記使用print('==flag:', flag)# 遞歸調用子過程，父過程是否為true，取決于子過程的結果if (temp - nums[i]) >= 0 and self.helper(nums, flag, avg, k, temp - nums[i], index + 1):return True#往下執行 說明沒有使用 重置為0flag[i] = 0return Falsenums = [4, 3, 2, 3, 5, 2, 1] k = 4 target, rem = divmod(sum(nums), k) print('==target:', target) print('==rem:', rem) # nums = [129, 17, 74, 57, 1421, 99, 92, 285, 1276, 218, 1588, 215, 369, 117, 153, 22] # k = 3 sol = Solution() res = sol.canPartitionKSubsets(nums, k) print('=res:', res)總結
以上是生活随笔為你收集整理的python刷题+leetcode(第一部分)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 一篇文章搞懂数据仓库：数据仓库规范设计
- 下一篇： Andoird自定义ViewGroup实