华为高频手撕冲刺

简单题

两数之和

方法一，暴力破解，时间复杂度O(n^2)，空间复杂度O(1)

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:n=len(nums)for i in range(n):for j in range(i+1,n):if nums[i]+nums[j]==target:return[i,j]

方法二，哈希表，时间复杂度O(n),空间复杂度O(n)

思路：向右枚举j，将值和下标存入哈希表，然后再枚举左边的数i，找到对应下标。

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:h={}# 向右枚举j，将值和下标存入哈希表，然后再枚举左边的数i，找到对应下标for j,x in enumerate(nums):if target-x in h:return [h[target-x],j]   h[x]=j

 移动零

方法一：把非零数都移到前面，其他数都赋值为0

时间复杂度：O(n)，空间复杂度O(1)

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""i=0for j in range(len(nums)):if nums[j]!=0:nums[i]=nums[j]i+=1for x in range(i,len(nums)):nums[x]=0return nums

方法二： 双指针

思路：快慢指针，快指针在前面遍历，如果找到非零数，就与慢指针交换，慢指针向前走一步，直到所有非零元素都移动到前面。

时间复杂度O(n)，空间复杂度O(1)

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""l=0for r in range(len(nums)):if nums[r]!=0:nums[l],nums[r]=nums[r],nums[l]l+=1return nums

反转字符串 

双指针

左右指针，互相交换，然后各走一步，遍历完就完成了反转

class Solution:def reverseString(self, s: List[str]) -> None:"""Do not return anything, modify s in-place instead."""l,r=0,len(s)-1while l<r:s[l],s[r]=s[r],s[l]l+=1r-=1return s

同构字符串

思路：index方法，遍历每一个字符，然后判断每一个字符首次出现的下标是否相等，如果相等的话，则是同构，不同的话则不是同构。

最坏的情况，因为index本身复杂度是n，时间复杂度O(n^2)，空间复杂度O(1)

class Solution:def isIsomorphic(self, s: str, t: str) -> bool:for i in range(len(s)):if s.index(s[i]) != t.index(t[i]):return Falsereturn True 

反转链表

思路：反转链表后，意思就是指针更改方向，创建一个pre指针赋为None，创建一个cur指针赋值为头，让cur指针指向pre指针，然后再移动。最后返回pre指针即链表的新头节点。

注意：要存储cur指向的指针，不然会断开后面的连接

时间复杂度O(n)，空间复杂度O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:pre=Nonecur=headwhile cur:temp=cur.nextcur.next=prepre=curcur=tempreturn pre

字符串相加

 双指针，让两个指针指向尾部，模拟人工加法，处理好进位，然后再拼接起来

class Solution:def addStrings(self, num1: str, num2: str) -> str:res=""i,j,carry=len(num1)-1,len(num2)-1,0while i>=0 or j >=0:# 超出索引范围直接赋值为0，相当于长度短的数字前面填0，方便后续计算n1=int(num1[i]) if i>=0 else 0n2=int(num2[j]) if j>=0 else 0temp=n1+n2+carrycarry = temp//10res=str(temp%10)+resi,j=i-1,j-1# 循环结束时，如果carry为1，则加到头部，没有则直接返回结果return "1"+res if carry else res

找出字符串中第一个匹配项的下标

方法一：直接用Python的内置函数index或者find，可以用来寻找字符串中子串，如果能找到，则返回第一个下标，否则抛出异常。

时间复杂度O(n)

class Solution:def strStr(self, haystack: str, needle: str) -> int:try:return haystack.index(needle)except:return -1

 方法二：切片

 class Solution:def strStr(self, haystack: 'str', needle: 'str') -> 'int':for i in range(0, len(haystack) - len(needle) + 1):if haystack[i:i+len(needle)] == needle:return ireturn -1

最长和谐子序列 

 方法一：哈希表存储，用HashMap统计个数后，遍历的时候直接判断有没有相邻的数的个数统计答案即可

class Solution:def findLHS(self, nums: List[int]) -> int:cnt = defaultdict(int)ans=0for num in nums:cnt[num]+=1if num+1 in cnt:ans=max(ans,cnt[num]+cnt[num+1])if num-1 in cnt:ans=max(ans,cnt[num]+cnt[num-1])return ans

方法二：排序+双指针时间复杂度O(nlog(n))，空间复杂度O(1)

class Solution:def findLHS(self, nums: List[int]) -> int:nums.sort()left=0res=0for right in range(len(nums)):if nums[right]-nums[left]>1:left+=1if nums[right]-nums[left]==1:res=max(res,right-left+1)return res

存在重复元素

方法一：哈希集合，将数组转化为集合（会去掉重复元素），然后判断前后长度是否一致

class Solution:def containsDuplicate(self, nums: List[int]) -> bool:s=set(nums)if len(s)!=len(nums):return Trueelse:return False

 方法二：哈希表

class Solution:def containsDuplicate(self, nums: List[int]) -> bool:numset={}for i in nums:if i not in numset:numset[i]=1else:return Truereturn False

字符串中的第一个唯一字符

方法一：Counter法，统计字符串中每一个字符出现次数，然后遍历到第一个字符直接返回下标

时间复杂度：O(n^2)，空间复杂度O(1)

class Solution:def firstUniqChar(self, s: str) -> int:l=Counter(s)for i in s:if l[i]==1:return s.index(i)return -1

方法二：哈希表，用哈希表存储每个字符，如果出现次数大于1则值为False，等于1则为True 

class Solution:def firstUniqChar(self, s: str) -> int:dic = {}for c in s:dic[c] = not c in dicfor i, c in enumerate(s):if dic[c]: return ireturn -1

罗马数字转整数

删除排序链表中的重复元素

快慢双指针，让快指针在前面探路，发现不重复元素，就放到慢指针后面，慢指针就往前一步，一直到遍历完整张表。此时从head到slow都是不重复元素，再断开slow后面的指针，即可去重。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:slow,fast=head,headif head is None:return Nonewhile fast:if fast.val!=slow.val:slow.next=fastslow=slow.nextfast=fast.nextslow.next=Nonereturn head

删除排序数组中的重复元素 

快慢指针，同上一题

class Solution:def removeDuplicates(self, nums: List[int]) -> int:if len(nums)==0:return 0slow,fast=0,0while fast<len(nums):if nums[fast]!=nums[slow]:slow+=1nums[slow]=nums[fast]fast+=1return slow+1

最长公共前缀

方法一：Python内置函数zip，可以把多个序列中的元素打包成一个元组，zip(*可迭代对象)

例如，flower，float，flew是三个数，使用zip函数处理后，

[f,f,f],[l,l,l].[o,o,e]...，因此只需要判断这些序列去重后长度是否为1，即可判断是否能作为公共前缀

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:l=0for i in zip(*strs):if len(set(i))>1:breakl+=1return strs[0][:l]

有效的括号

括号匹配，用栈来做最佳

方法一：栈+if-else循环

时间复杂度O(n)，空间复杂度是O(n)

class Solution:def isValid(self, s: str) -> bool:if len(s)%2!=0:return Falsestk=[]for c in s:if c=="(":stk.append(")")elif c=="[":stk.append("]")elif c=="{":stk.append("}")elif not stk or stk.pop()!=c:return Falsereturn not stk

方法二：栈+哈希表 

思路：使用哈希表存储，键是左括号，值是右括号，遍历字符串，当遍历字符在哈希表中，将值压入栈中；如果栈为空，说明只有右括号，或者出栈元素跟当前元素不同，说明不匹配。

时空复杂度都是O(n)

class Solution:def isValid(self, s: str) -> bool:if len(s)%2!=0:return Falsestk=[]mp={'(':')','[':']','{':'}'}for c in s:if c in mp:stk.append(mp[c])elif not stk or stk.pop()!=c:return Falsereturn not stk

反转字符串中的元音字母

 对撞双指针，将元音字母顺序交换

class Solution:def reverseVowels(self, s: str) -> str:# a e i o u                                         #元音元素dic = {'a','e','i','o','u','A','E','I','O','U'}     #大小写元音元素集合作为判断依据pol = 0                                             #左指针por = len(s)-1                                      #右指针s_ = list(s)                                        #str类型数据无法直接查询in和not in，转换为listwhile pol < por:                                    #左右指针交错循环停止if s_[pol] in dic and s_[por] in dic:           #左右指针所指元素均在集合中s_[pol], s_[por] = s_[por], s_[pol]         #交换左右指针所指元素por -= 1                                    #右指针左移pol += 1                                    #左指针右移if s_[por] not in dic:                          #右指针所指元素不在集合中por -= 1                                    #右指针左移if s_[pol] not in dic:                          #左指针所指元素不在集合中pol += 1                                    #左指针右移return ''.join(s_)                                  #返回str格式数据

二进制转十进制

def binary_to_decimal(binary_array):# 将数组转换成字符串binary_str = ''.join(str(bit) for bit in binary_array)# 判断是否为负数is_negative = binary_str[0] == '1'if is_negative:# 对于负数，转换为原码后计算inverted = ['0' if b == '1' else '1' for b in binary_str]inverted_str = ''.join(inverted)# 加1操作decimal_value = -int(inverted_str, 2) + 1else:# 正数直接转换decimal_value = int(binary_str, 2)return decimal_value# 示例
binary_array = [1, 1, 1, 1]  # 表示-1（假设字长为4）
print(binary_to_decimal(binary_array))  # 输出: -1

反转二叉树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return Nonequeue=[root]while queue:node=queue.pop(0)if node.left:queue.append(node.left)if node.right:queue.append(node.right)node.left,node.right=node.right,node.leftreturn root

二叉树的中序遍历

快乐数 

 

中等题

三数之和

先给数组排序，固定好一个值，再创建两个对撞指针，遍历整张表，然后删除重复的元素。

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()res = []n=len(nums)for i in range(n-2):x=nums[i]if i>0 and x==nums[i-1]:continuel=i+1r=n-1while l<r:s=x+nums[l]+nums[r]if s<0:l+=1elif s>0:r-=1else:res.append([x,nums[l],nums[r]])l+=1# 删除重复元素while l<r and nums[l]==nums[l-1]:l+=1r-=1while l<r and nums[r]==nums[r+1]:r-=1return res

 反转字符串中的单词

class Solution:def reverseWords(self, s: str) -> str:# 删除首尾空格s=s.strip()# 分割字符串strs=s.split()# 翻转单词列表strs.reverse()return " ".join(strs)

合并区间

 

两数相加

新建一个链表，使用虚拟头结点，然后计算两条链表的值，处理好进位

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译。
# 本代码的正确性已通过力扣验证，如有疑问，可以对照我的 java 代码查看。class Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:# 在两条链表上的指针p1, p2 = l1, l2# 虚拟头结点（构建新链表时的常用技巧）dummy = ListNode(-1)# 指针 p 负责构建新链表p = dummy# 记录进位carry = 0# 开始执行加法，两条链表走完且没有进位时才能结束循环while p1 is not None or p2 is not None or carry > 0:# 先加上上次的进位val = carryif p1 is not None:val += p1.valp1 = p1.nextif p2 is not None:val += p2.valp2 = p2.next# 处理进位情况carry = val // 10val = val % 10# 构建新节点p.next = ListNode(val)p = p.next# 返回结果链表的头结点（去除虚拟头结点）return dummy.next

无重复字符的最长子串

滑动窗口

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:ans = left = 0window = set()  # 维护从下标 left 到下标 right 的字符for right, c in enumerate(s):# 如果窗口内已经包含 c，那么再加入一个 c 会导致窗口内有重复元素# 所以要在加入 c 之前，先移出窗口内的 cwhile c in window:  # 窗口内有 cwindow.remove(s[left])left += 1  # 缩小窗口window.add(c)  # 加入 cans = max(ans, right - left + 1)  # 更新窗口长度最大值return ans

 每日温度

创建一个列表，创建一个空单调栈，倒着遍历温度，如果当前栈中元素小于当前温度，则出栈，直到找到大于当前温度的元素，如果栈为空说明没有，则赋值为0，否则赋值为栈顶元素-当前下标

时间复杂度O(n)，空间复杂度是O(n)

class Solution:def dailyTemperatures(self, temperatures):n = len(temperatures)res = [0]*n# 这里放元素索引，而不是元素s = []# 单调栈模板for i in range(n-1, -1, -1):while s and temperatures[s[-1]] <= temperatures[i]:s.pop()# 得到索引间距res[i] = 0 if not s else s[-1] - i# 将索引入栈，而不是元素s.append(i)return res

删除排序链表中重复元素II

class Solution:def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:cur = dummy = ListNode(next=head)while cur.next and cur.next.next:val = cur.next.valif cur.next.next.val == val:while cur.next and cur.next.val == val:cur.next = cur.next.nextelse:cur = cur.nextreturn dummy.next

跳跃游戏

思路：初始化一个值，表示当前能到达的最大位置，然后遍历nums，如果max_i大于当前下标，且i+jump大于当前能到达最大位置，则更新，最后输出能否到达尾部。

时间复杂度O(n)，空间复杂度O(1)

class Solution:def canJump(self, nums: List[int]) -> bool:max_i=0for i,jump in enumerate(nums):if max_i>=i and i+jump>max_i:max_i=i+jumpreturn max_i>=len(nums)-1

和为K的子数组

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:s = [0] * (len(nums) + 1)for i, x in enumerate(nums):s[i + 1] = s[i] + xans = 0cnt = defaultdict(int)for sj in s:ans += cnt[sj - k]cnt[sj] += 1return ans

买卖股票的最佳时机

class Solution:def maxProfit(self, prices: List[int]) -> int:ans = 0min_pirce = prices[0]for p in prices:ans = max(ans, p - min_pirce)min_pirce = min(min_pirce, p)return ans

救生艇

class Solution:def numRescueBoats(self, people: List[int], limit: int) -> int:if people is None or len(people)==0:return 0# 创建对撞指针p1 = 0p2 = len(people)-1res = 0people.sort()while p1<=p2:# 如果头和尾相加小于限制，则头指针+1，表示可以坐一艘船if people[p1]+people[p2]<=limit:p1+=1# 如果超重，则尾指针-1，表示尾部单独坐一艘船p2-=1res+=1return res

整数转罗马数字

R = (("", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"),  # 个位("", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"),  # 十位("", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"),  # 百位("", "M", "MM", "MMM"),  # 千位
)class Solution:def intToRoman(self, num: int) -> str:return R[3][num // 1000] + R[2][num // 100 % 10] + R[1][num // 10 % 10] + R[0][num % 10]

零钱兑换II

最后一块石头的重量II