制作网站软件排行榜,重庆好的seo平台,湖北网站建设专家,完全备份wordpress题11#xff08;中等#xff09;#xff1a; 思路#xff1a;
这种题目第一眼就是双循环#xff0c;但是肯定不行滴#xff0c;o(n^2)这种肯定超时#xff0c;很难接受。
所以要另辟蹊径#xff0c;我们先用俩指针#xff08;标志位#xff09;在最左端和最右端中等 思路
这种题目第一眼就是双循环但是肯定不行滴o(n^2)这种肯定超时很难接受。
所以要另辟蹊径我们先用俩指针标志位在最左端和最右端我们知道这个容器的最大容积是看最短的那条木桶效应嘛。如果我们让长的那一条再怎么大都影响不了容积所以我们加上底不变的话要找最大容积肯定要变短边嘛动长边又改变不了什么也就是说这个时候移动长边得到的一定不是。思路打开就写代码
python代码 class Solution: def maxArea(self, height: List[int]) - int: left0 rightlen(height)-1 max_area0 while leftright: hmin(height[left],height[right]) wright-left areah*w max_areamax_area if max_areaarea else area if height[left]height[right]: left1 else: right-1 return max_area 题12中等 思路
作为爬虫玩家这种东西直接给个关系映射就好了啊谁会去思考4,9特殊情况啊
python代码 class Solution:def intToRoman(self, num: int) - str:Roman_strtran_json{1:I,4:IV,5:V,9:IX,10:X,40:XL,50:L,90:XC,100:C,400:CD,500:D,900:CM,1000:M,}i10while 1:if num1:break#获得在各个位的数字h_numnum%10numint(num/10)if h_num0:i*10elif h_num4:Roman_strh_num*tran_json[i/10]Roman_stri*10elif h_num4:Roman_strtran_json[4*i/10]Roman_stri*10elif h_num9:Roman_strtran_json[5*i/10](h_num-5)*tran_json[i/10]Roman_stri*10elif h_num9:Roman_strtran_json[9*i/10]Roman_stri*10return Roman_str 题13简单 思路
和上面一样不想那么多直接用json存下换算规则就像处理爬虫的字体加密一样不想什么方法直接字体识别出键值对来就套用懒得看什么先转unicode啥的
python代码 class Solution: def romanToInt(self, s: str) - int: R_cout0 tran_json{ I:1, V:5, X:10, L:50, C:100, D:500, M:1000 } ts_json{ IV:4, IX:9, XL:40, XC:90, CD:400, CM:900 } for key,value in ts_json.items(): ss.replace(key,|str(value)) for key,value in tran_json.items(): ss.replace(key,|str(value)) R_coutsum(list(map(int,s.strip(|).split(|)))) return R_cout 题14简单 思路
双for循环直接解决了
python代码 class Solution: def longestCommonPrefix(self, strs: List[str]) - str: pub_str for i in range(min([len(s) for s in strs])): kstrs[0][i] for j in range(1,len(strs)): if k!strs[j][i]: return pub_str pub_strk return pub_str 题15中等 思路
和前面一个容器的那个一样用双指针法我们将nums排好序固定一个起始的话如果大的话移动右指针小的话移动左指针。
python代码 class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: nums.sort() result[] n_lenlen(nums) for i in range(len(nums)): posi if nums[i] 0: break # 跳过可能重复的数字避免重复的三元组 if i 0 and nums[i] nums[i-1]: continue leftpos1 rightn_len-1 #预处理如果前两个加最后一个都大的话就删了最后一个 while leftright: if nums[pos]nums[left]nums[right]0: right-1 n_len-1 else: break while leftright: total nums[i] nums[left] nums[right] if total0: result.append([nums[pos],nums[left],nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif total0: right-1 else: left1 return result 题16中等 思路
双指针法和15题差不多就是要排除了如果totaltarget则排除了更小的left右移如果totaltarget则排除了更大的right左移
python代码 class Solution:def threeSumClosest(self, nums: List[int], target: int) - int:nums.sort()sumnums[0]nums[1]nums[2]for i in range(len(nums)):if i0 and nums[i]nums[i-1]:continueleft i 1right len(nums) - 1while left right:totalnums[i]nums[left]nums[right]if abs(target-total)abs(target-sum):sumtotalif totaltarget:left1elif totaltarget:right-1else:return targetreturn sum 题17中等 思路
枚举列出来就好了能过就行虽然时间复杂度有点
python代码 class Solution: def letterCombinations(self, digits: str) - List[str]: if digits: return [] btn_json{ 1:, 2:abc, 3:def, 4:ghi, 5:jkl, 6:mno, 7:pqrs, 8:tuv, 9:wxyz, } res_list[] for i in digits: resbtn_json[i] tmp_listres_list res_list[nj for n in tmp_list for j in res] return res_list 题18中等 思路
两数和三数和三数接近这几题好玩吧没尽兴就又来了一个4数和一样的
python代码 class Solution: def fourSum(self, nums: List[int], target: int) - List[List[int]]: nums.sort() res_list[] for i in range(len(nums)): if i0 and nums[i]nums[i-1]: continue tmp_targettarget-nums[i] for j in range(i1,len(nums)): if ji1 and nums[j]nums[j-1]: continue leftj1 rightlen(nums)-1 while leftright: totalnums[left]nums[right]nums[j] if totaltmp_target: res_list.append([nums[i],nums[j],nums[left],nums[right]]) while leftright and nums[left]nums[left1]: left1 while leftright and nums[right]nums[right-1]: right-1 left1 right-1 elif totaltmp_target: left1 else: right-1 return res_list 题19中等 思路
这个用c应该比较容易理解
python代码 # Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: n_len1 phead while 1: if p.next!None: n_len1 pp.next else: break posn_len-n phead if pos0: headhead.next return head for i in range(pos-1): pp.next p.nextp.next.next return head 题20简单 思路
这个就是金典的栈的运用啊我之前还有一个文章是表达式的转换来着
python代码 class Solution: def isValid(self, s: str) - bool: s_stack[] for i in s: if i( or i{ or i[: s_stack.append(i) elif i): if len(s_stack)!0 and s_stack[-1](: s_stack.pop() else: return False elif i }: if len(s_stack)!0 and s_stack[-1] {: s_stack.pop() else: return False elif i ]: if len(s_stack)!0 and s_stack[-1] [: s_stack.pop() else: return False if len(s_stack)0: return True else: return False
