华为的高频撕手冲刺

简单题

两数之和

方法一，暴力破解，时间复杂度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)

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

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

方法二： 双指针

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

反转字符串 

双指针

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

同构字符串

map方法

zip方法

index方法

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 False
        return True 

反转链表

时间复杂度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=None
        cur=head
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        return pre

字符串相加

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

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        res=""
        i,j,carry=len(num1)-1,len(num2)-1,0
        while i>=0 or j >=0:
            # 超出索引范围直接赋值为0，相当于长度短的数字前面填0，方便后续计算
            n1=int(num1[i]) if i>=0 else 0
            n2=int(num2[j]) if j>=0 else 0
            temp=n1+n2+carry
            carry = temp//10
            res=str(temp%10)+res
            i,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 i
     	return -1

最长和谐子序列 

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

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        cnt = defaultdict(int)
        ans=0
        for num in nums:
            cnt[num]+=1
            if 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=0
        res=0
        for right in range(len(nums)):
            if nums[right]-nums[left]>1:
                left+=1
            if 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 True
        else:
            return False

 方法二：哈希表

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

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

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

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:
        h={}
        for i in s:
            h[i]=not i in h
        for j,x in enumerate(s):
            if h[c]:
                return if
        return -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,head
        if head is None:
            return None
        while fast:
            if fast.val!=slow.val:
                slow.next=fast
                slow=slow.next
            fast=fast.next
        slow.next=None
        return head

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

快慢指针，同上一题

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

最长公共前缀

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

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

有效的括号

括号匹配，用栈来做最佳

方法一：栈+if-else循环

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

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

方法二：栈+哈希表 

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s)%2!=0:
            return False
        stk=[]
        mp={'(':')','[':']','{':'}'}
        for c in s:
            if c in mp:
                stk.append(mp[c])
            elif not stk or stk.pop()!=c:
                return False
        return 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，转换为list
        while 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) + 1
    else:
        # 正数直接转换
        decimal_value = int(binary_str, 2)
    
    return decimal_value

# 示例
binary_array = [1, 1, 1, 1]  # 表示-1（假设字长为4）
print(binary_to_decimal(binary_array))  # 输出: -1

 

中等题

三数之和

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

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]:
                continue
            l=i+1
            r=n-1
            while l<r:
                s=x+nums[l]+nums[r]
                if s<0:
                    l+=1
                elif s>0:
                    r-=1
                else:
                    res.append([x,nums[l],nums[r]])
                    l+=1
                    # 删除重复元素
                    while l<r and nums[l]==nums[l-1]:
                        l+=1
                    r-=1
                    while l<r and nums[r]==nums[r+1]:
                        r-=1
        return 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 = carry
            if p1 is not None:
                val += p1.val
                p1 = p1.next
            if p2 is not None:
                val += p2.val
                p2 = p2.next
            # 处理进位情况
            carry = val // 10
            val = val % 10
            # 构建新节点
            p.next = ListNode(val)
            p = p.next
        # 返回结果链表的头结点（去除虚拟头结点）
        return dummy.next

无重复字符的最长子串

滑动窗口

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans=0
        l=0
        h=Counter()
        for r,x in enumerate(s):
            h[x]+=1
            while h[x]>1:
                h[s[l]]-=1
                l+=1
            ans=max(ans,r-l+1)
        return ans

 每日温度

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.val
            if cur.next.next.val == val:
                while cur.next and cur.next.val == val:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

跳跃游戏

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

和为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] + x

        ans = 0
        cnt = defaultdict(int)
        for sj in s:
            ans += cnt[sj - k]
            cnt[sj] += 1
        return ans

买卖股票的最佳时机

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

整数转罗马数字

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]