技巧题

发表于： 2025-02-26 分类于： Leetcode

字数： 992 阅读：≈ 2分钟

31. Next Permutation

考虑最后一个permutation：5-4-3-2-1，全部降序。

从后往前，找第一组升序的nums[i]和nums[i+1], 比如12947653，找到了nums[4]=4.
从后往前，找第一个比nums[i]大的数nums[j]，也就是 5
交换nums[i]和nums[j], 得到 12957643，此时nums[i]后面的数字全都是降序排列
把nums[i]后面的数字按升序排列，得到 12953467

128. Longest Consecutive Sequence

[100,4,200,1,3,2]

首先把所有数字都加入set中，这样判断某个数字是否存在，就只需要O(1)的时间。
在 set 中遍历每个数字x，看谁能作为一个序列的起点。如果x-1也在set中，那么x就不能作为起点，continue
如果x能作为起点，就不断地判断x+1是否在set中

169. Majority Element

摩尔计数法，只能找到数量＞数字个数一半的众数。

如 1,1,1,2,3,9,9则不行

48. Rotate Image

先水平翻转，再沿主对角线翻转

41. First Missing Positive

原地哈希，把值为i+1的元素放到数组中下标为i的地方.

遍历数组的 index，判断nums[i]是否等于 nums[nums[i]+1], 如果不等于，则用循环交换。

75. Sort Colors

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def sortColors(self, nums: List[int]) -> None:
    n=len(nums)
    p0,p2=0,n-1
    i=0
    while i<=p2: #注意这里的循环条件
        while i<=p2 and nums[i]==2:
            nums[i], nums[p2]=nums[p2], nums[i]
            p2-=1
        if nums[i]==0:
            nums[i],nums[p0]=nums[p0], nums[i]
            p0+=1
        i+=1

136

x^x=0
0^x=x
可以不断xor，来消除所有出现了两次的数字

287. Find Duplicate

类比快慢指针，判断链表中是否有环。
[1,3,4,2,2]可以看作
从 index0 开始，nums[0]=1;
到 index=1, nums[1]=3;
到 index=3, nums[3]=2;
到 index=2, nums[2]=4;
到 index=4, nums[4]=2

那么存在一个从节点 4 到节点 2的环，此时2确实是那个 duplicate

394. Decode String

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def decodeString(self, s: str) -> str:
    stack=[]
    res=""
    multi=0
    for x in s:
        if x=='[':s
            stack.append([res, multi])
            res=""
            multi=0
        elif x==']':
            preFix, m=stack.pop()
            res=preFix+m*res
        elif '0'<=x<='9':
            multi=int(x)+multi*10
        else:
            res+=x
    return res

79. Word Search

回溯。dfs(i, j, k)表示从board[i][j]开始，可以匹配word[k:], 并且不用到重复的元素。注意dfs结束后恢复数组！

88. 合并两个有序数组

倒序双指针

32. 最长有效括号

把可行的匹配括号位置上标注为1，找最长的连续1的长度

中位数

比它小的个数=比它大的个数或者
比它小的个数=比它大的个数-1

回文

可以构成回文：除了允许一个字符可以出现奇数次，所有字符都必须出现偶数次
如果有 m 种字母出现奇数次，只需修改其中 ⌊m/2⌋个字母, 就可以使这些字符组成回文

Ruoke Zhang

技巧题