算法训练I-简单

算法训练I-简单

挑了一些简单的算法题来做一些回顾，主要是LeetCode上面的Easy难度，各方面都有

主要使用Python来写算法

1. 两数之和

image-20250311124516327

比较笼统的能想到的两次循环，算法复杂度为O(n^2)

i按序遍历每一个元素，j从i位置往后按序遍历每个元素，计算和并比较，找出对应的i和就、

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j]==target:
                    return i,j

再来看看我们的新算法:

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

dict这种键值存储是使用哈希表实现的.

在访问过程中，我们先计算要访问数据的哈希，再使用哈希值直接访问哈希表的位置，如果能获取数据则说明data在哈希表中.所以在第二次遍历过程中，我们的时间复杂度下降到了O(1)

但由于使用了哈希表，我们的空间复杂度上升到了O(n)

所以我们的新算法的时间复杂度为O(n),空间复杂度为O(n).

27. 移除元素

image-20250311130507778

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        k=0
        for i in range(len(nums)):
            if nums[i]!=val:
                nums[k]=nums[i]
                k+=1
        return k

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

非常简单的思路，遍历nums数组，判断如果与目标值相等就跳过进行下一次处理，其实也是双指针的实现.

88. 合并两个有序数组

image-20250311131733638

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        p1=m-1
        p2=n-1
        p=m+n-1
        while p1>=0 and p2>=0:
            if nums1[p1]<=nums2[p2]:
                nums1[p]=nums2[p2]
                p2-=1
            else:
                nums1[p]=nums1[p1]
                p1-=1
            p-=1
        while p2>=0:
            nums1[p]=nums2[p2]
            p2-=1

我们倒序来遍历数组，最大值也倒着存.

每次遍历在p1和p2指向的位置，找到最大值存到p指向的位置，然后把最大值的指针和p的指针往后走一格，可以保证每次存入的都是两个数组中的最大值.

如果遍历完成p2还有剩余，倒序写入nums1数组；p1还有剩余则无需写入，因为本来就是对nums1数组的操作.

时间复杂度为O(n),空间复杂度为O(1).

20. 有效的括号

image-20250311134019655

经典栈题，但其实有一个绝妙的方法，我们先用栈来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        # 括号匹配的映射
        mapping = {')': '(', '}': '{', ']': '['}
        
        for char in s:
            if char in mapping:
                # 如果是右括号，检查栈顶是否有匹配的左括号
                top_element = stack.pop() if stack else '#'
                if top_element != mapping[char]:
                    return False
            else:
                # 如果是左括号，入栈
                stack.append(char)
        
        # 如果栈空，说明所有的括号都配对了
        return not stack

很传统的做法，左括号入栈，右括号出栈并检测是否为左括号对应的括号，栈空说明全部完成配对.

时间复杂度和空间复杂度都是O(n).

还有一个绝妙的方法

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        while '{}' in s or '[]' in s or '()' in s:
            s=s.replace('{}','')
            s=s.replace('[]','')
            s=s.replace('()','')
        return s==''

乐，括号消消乐，虽然时间复杂度大概是O(n^2),空间复杂度为O(n),每次都会创建一个新的字符串对象.

203. 移除链表元素

image-20250311135238630

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: Optional[ListNode]
        :type val: int
        :rtype: Optional[ListNode]
        """
        none_exist=ListNode(-1)
        none_exist.next=head
        pre=none_exist
        cur=head
        while cur:
            if cur.val==val:#删除节点
                pre.next=cur.next
            else:
                pre=cur
            cur=cur.next
        return none_exist.next

后面删除节点的逻辑我会写，想到怎么给出头节点的时候犯了难

后来看到可以创建一个虚拟节点来链到head，感觉很神奇

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

还有一种比较简单的递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: Optional[ListNode]
        :type val: int
        :rtype: Optional[ListNode]
        """
        if not head:
            return head
        head.next=self.removeElements(head.next,val)
        return head.next if head.val==val else head

时间复杂度为O(n)，空间复杂度也为O(n)

遍历链表返回head.next直到链表尾进行嵌套返回

就是逻辑有点难想，递归算法也不是很推荐，容易导致栈满

26. 删除有序数组中的重复项

image-20250311143820609

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        unique=0
        for repeat in range(len(nums)):
            if nums[unique]!=nums[repeat]:
                unique+=1
                nums[unique]=nums[repeat]
        return unique+1

双指针遍历.算法时间复杂度O(n)，空间复杂度O(1),遍历找到不同数字时跳过.

206. 反转链表

image-20250311152911706

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def reverseList(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        pre=None
        cur=head
        while cur:
            tmp=cur.next
            cur.next=pre
            pre=cur
            cur=tmp
        return pre

运行的时候记录前驱节点pre、现有节点cur、后继节点tmp.

遍历到当前节点，通过cur.next获取到后继节点;

将当前节点指向前驱节点cur.next=pre,并将前驱节点更新为当前节点，当前节点更新为后继节点，来实现一次链表的反转.

时间复杂度为O(n),空间复杂度为O(1).

21. 合并两个有序链表

image-20250311153740011

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        head = ListNode(-1)
        prev = head
        while list1 and list2:
            if list1.val<=list2.val:
                prev.next=list1
                list1=list1.next
            else:
                prev.next=list2
                list2=list2.next
            prev=prev.next
        prev.next=list1 if list1 else list2
        return head.next

由于头结点不确定，我们新建一个空链表节点作为head，遍历list1和list2取较小值加入链表，直到有一方被遍历完成后将剩余一方直接链入链表即可.

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

121. 买卖股票的最佳时机

image-20250311154616044

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        mint=prices[0]
        maxt=0
        for i in range(1,len(prices)):
            mint=min(mint,prices[i])
            maxt=max(maxt,prices[i]-mint)
        return maxt

需要一点思考.

我们认为能获取的最大利润应该是遍历过程中，所有时刻能得到的最大利润的最大值

所以遍历记录最小值，再取所有时刻买入所得最大利润的最大值，遍历结束就是我们得到的最大利润maxt.

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

13. 罗马数字转整数

image-20250311161430839

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        mapdict={"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
        specialdict={"IV":4,"IX":9,"XL":40,"XC":90,"CD":400,"CM":900}
        substr=""
        i=len(s)-1
        value=0
        while i>=0:
            substr=s[i-1:i+1] #取i-1 和 i位置构成的两位子串
            if i>0 and substr in specialdict:
                value+=specialdict[substr]
                i-=2
            else:
                value+=mapdict[s[i]]
                i-=1
        return value

有点绕啊，我们来分析一下逻辑

大概就是倒序遍历，匹配到符合规则的两位子串就计算值然后往前遍历，如果不符合子串规则就直接计算值并累加. 注意i>0，不然可能取子串会导致访问越界.

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

530. 二叉搜索树的最小绝对差

image-20250311172149041

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        res=[]
        self.getMidTreeArray(root,res) #现在res是一个递增的数组
        min=abs(res[0]-res[1])
        for i in range(1,len(res)-1):
            tmp=abs(res[i]-res[i+1])
            if tmp < min: min = tmp
        return min

    def getMidTreeArray(self,root,res):
        if not root:
            return
        self.getMidTreeArray(root.left,res)
        res.append(root.val)
        self.getMidTreeArray(root.right,res)

不难看出根据中序遍历我们可以得到一个升序数组，随后我们遍历取得最小差即可

时间复杂度O(n) 空间复杂度O(n) 我们多创建了一个res数组来辅助排序

69. x 的平方根

image-20250311183037928

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x==0 or x==1:
            return x
        return self.AreaSearch(x,0,x)
    def AreaSearch(self,x,left,right):
        mid=(left+right)//2
        if mid*mid<=x and (mid+1)*(mid+1)>x:
            return mid
        if mid*mid<x:
            return self.AreaSearch(x,mid,right)
        else:
            return self.AreaSearch(x,left,mid)

时间复杂度O(log n) 空间复杂度O(log n)

二分查找递归查找平方根

70. 爬楼梯

image-20250311185247409

经典老题爬楼梯

1
2
3
4
5
6
7
8
9
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==1:return 1
        if n==2:return 2
        return self.climbStairs(n-2)+self.climbStairs(n-1)

在最坏情况下，递归树的节点数大约是 2^n，即总共调用了 O(2^n) 次，时间复杂度为 O(2^n) ，坏

递归一下，结果发现会超时，算法效率还是不够高，原因是大量的重复计算，我们来优化一下，避免重复计算

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<4:return n
        result=[0,1,2,3]
        for i in range(3,n):
            result.append(result[i]+result[i-1])
        return result[n]

时间复杂度O(n),空间复杂度O(n)

1047. 删除字符串中的所有相邻重复项

image-20250311191941087

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def removeDuplicates(self, s):
        """
        :type s: str
        :rtype: str
        """
        while True:
            new_s = ""
            head = 0
            while head < len(s):
                if head + 1 < len(s) and s[head] == s[head + 1]:
                    head += 2 
                    continue
                new_s += s[head]
                head += 1
            if new_s == s:
                break
            s = new_s
        return s

时间复杂度O(n)，空间复杂度O(n)，检验到新字符串和原字符串相同则停止，但是对于太大的测试用例还是超时了.

怎么办？改！想起来刚好可以用栈来写一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def removeDuplicates(self, s):
        """
        :type s: str
        :rtype: str
        """
        new_s=[]
        for i in s:
            if new_s==[]:
                new_s.append(i)
                continue
            if new_s[-1]==i:
                new_s.pop()
                continue
            new_s.append(i)
        return "".join(new_s)

108. 将有序数组转换为二叉搜索树

image-20250311204004239

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: Optional[TreeNode]
        """
        def TreeBuilder(left,right):
            if left>right:
                return None
            mid = (left+right)//2
            root = TreeNode(nums[mid])
            root.left=TreeBuilder(left,mid-1)
            root.right=TreeBuilder(mid+1,right)
            return root
        return TreeBuilder(0,len(nums)-1)

定义一个TreeBuilder辅助构建函数,用于帮助构建子树.

时间复杂度为 O(n) 空间复杂度为 O(log n)

125. 验证回文串

image-20250311205228915

回文串最速传说

1
2
3
4
5
6
7
8
class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = ''.join(filter(lambda c: c.isalnum(), s)).lower()
        return s==s[::-1]

136. 只出现一次的数字

image-20250311211243495

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result=nums[0]
        for i in range(1,len(nums)):
            result=result^nums[i]
        return result

非常优秀的思路，利用两次异或恢复原始值可以得到只出现一次的数字.

141. 环形链表

image-20250311212846348

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def (self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy = ListNode(-1)  # 创建一个虚拟头节点
        prev = dummy  # prev 指针用于追踪链表合并过程

        while list1 and list2:
            if list1.val <= list2.val:
                prev.next = list1
                list1 = list1.next
            else:
                prev.next = list2
                list2 = list2.next
            prev = prev.next  # 移动 prev 指针

        # 连接剩余部分（如果有）
        prev.next = list1 if list1 else list2

        return dummy.next  # 返回合并后的链表

144. 二叉树的前序遍历

image-20250311213129548

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        res=[]
        def Traversal(res,root):
            if not root:return
            res.append(root.val)
            Traversal(res,root.left)
            Traversal(res,root.right)
        Traversal(res,root)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        res=[]
        stack=[]
        stack.append(root)
        while stack!=[]:
            node = stack.pop()
            if not node:
                return []
            if node:
                res.append(node.val)
            if(node.right):
                stack.append(node.right)
            if(node.left):
                stack.append(node.left)
        return res

递归+迭代

697. 数组的度

image-20250312125223088

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def findShortestSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic={}
        for i,num in enumerate(nums):
            if num in dic:
                dic[num][0]+=1 #记录数字出现的次数
                dic[num][2]=i #更新数字最后一次出现的位置
            else:
                dic[num]=[1,i,i] #记录数字出现了一次，第一次和最后一次出现的位置
        maxNum = minLen = 0
        for count,left,right in dic.values():
            length = right - left + 1
            if count > maxNum:
                maxNum = count
                minLen = length
            elif maxNum == count: #判断是否存在更小长度
                if minLen > length:
                    minLen = length
        return minLen

用哈希表来实现比较优雅

2703. 返回传递的参数的长度

image-20250312130107396

神秘的Javascript基础题

1
2
3
var argumentsLength = function(...args) {
    return args.length
};

3099. 哈沙德数

image-20250312130132749

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def sumOfTheDigitsOfHarshadNumber(self, x):
        """
        :type x: int
        :rtype: int
        """
        s=str(x)
        sum=0
        for i in s:
            sum +=int(i)
        return sum if x%sum==0 else -1

705. 设计哈希集合

image-20250312132635646

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class MyHashSet(object):

    def __init__(self):
        self.data=[False]*1000001

    def add(self, key):
        """
        :type key: int
        :rtype: None
        """
        self.data[key]=True
        

    def remove(self, key):
        """
        :type key: int
        :rtype: None
        """
        self.data[key]=False

    def contains(self, key):
        """
        :type key: int
        :rtype: bool
        """
        return self.data[key]

哈希表实现起来比较复杂，稍后再看看

面试题 01.01. 判定字符是否唯一

image-20250312130745039

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def isUnique(self, astr):
        """
        :type astr: str
        :rtype: bool
        """
        dic={}
        for char in astr:
            if not char in dic:
                dic[char]=1
            else:
                return False
        return True
1
2
3
class Solution:
    def isUnique(self, astr: str) -> bool:
        return len(astr) == len(set(astr))

也可以灵活使用集合去重

面试题 03.04. 化栈为队

image-20250312133350215

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class MyQueue(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.pushs=[]
        self.pops=[]
        

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        self.pushs.append(x) #push压栈

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if len(self.pops)==0: # 优先弹出pops栈栈顶元素，没有的话把push栈元素倒过去，push栈底会成为pop栈顶
            for i in range(len(self.pushs)):
                self.pops.append(self.pushs.pop())
        return self.pops.pop()

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        top = self.pop()
        self.pops.append(top) #pop出来然后再return
        return top
        

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        if len(self.pushs)==0 and len(self.pops)==0:
            return True
        else:
            return False


# 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()

350. 两个数组的交集 II

image-20250312135955907

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        dic={}
        res=[]
        for i in nums1:
            if i in dic:
                dic[i]+=1
            else:
                dic[i]=1
        for j in nums2:
            if j in dic:
                if dic[j]>0:
                    dic[j]-=1
                    res.append(j)
        return res

392. 判断子序列

image-20250312170252232

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        head1,head2=0,0
        if s=="":return True
        while head1!=len(s):
            flag=False 
            while head2!=len(t):
                if s[head1]==t[head2]:
                    flag=True
                    head2+=1
                    break
                head2+=1
            if not flag:
                return False
            head1+=1
        return True

409. 最长回文串

image-20250312172526402

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        dic={}
        for i in s:
            if i in dic:
                dic[i]+=1
            else:
                dic[i]=1
        length=0
        flag=True
        for key,value in enumerate(dic.values()):
            if value%2==1 and flag:  #第一个奇数直接加
                flag=False
                length+=value
            else:
                length+=value-value%2 #最近的偶数
        return length

1378. 使用唯一标识码替换员工ID

image-20250312173919139

image-20250312173932086

SQL语句题，有点意思

SQL中JOIN相关子句是用于将两个或者多个表结合起来，进行相关操作。

Left Join把Employees和EmployeeUNI拼起来,根据条件Employees.id = EmployeeUNI.id.

生成一张这样的表

id name id unique_id
1 Alice null null
7 Bob null null
11 Meir 11 2
90 Winston 90 3
3 Jonathan 3 1

Employees为主表，EmployeeUNI 为副表

选择EmployeeUNI.unique_id, Employees.name 作为所需字段

1
2
3
4
5
6
7
8
SELECT 
    EmployeeUNI.unique_id, Employees.name
FROM 
    Employees
LEFT JOIN 
    EmployeeUNI 
ON 
    Employees.id = EmployeeUNI.id;

最后的输出

unique_id name
null Alice
null Bob
2 Meir
3 Winston
1 Jonathan

509. 斐波那契数

image-20250312174451984

常规思路都是拿递归来做，但那样会有大量冗余计算，我们这里用一个简单一点的实现

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def fib(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<=1:return n
        res=[0,1]
        for i in range(2,n+1):
            res.append(res[i-2]+res[i-1])
        return res[n]

189. 轮转数组

image-20250312174514029

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        k=k%n
        nums[:]=nums[-k:]+nums[0:-k]