小丑西瓜9

这个屌丝很懒，什么也没留下！

热门标签

一天一道LeetCode(151-190)_# 余数前面出现过,说明开始循环了,加括号 if b in loc:

作者：小丑西瓜9 | 2024-02-16 13:17:27

踩

# 余数前面出现过,说明开始循环了,加括号 if b in loc:

一天一道LeetCode（151-190）

151.翻转字符串里的单词

题目：

给定一个字符串，逐个翻转字符串中的每个单词

实例：

输入："the sky is blue"
输出："blue is sky the"
1
2

输入："  hello world!  "
输出："world! hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括
1
2
3

输入："a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个
1
2
3

输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"
1
2

输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"
1
2

class Solution:
    def reverseWords(self, s):
        s = s.strip()
        lst = s.split()
        return ' '.join(lst[::-1])
1
2
3
4
5

152.乘积最大子数组

题目：

给定一个整数数组nums，请找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积

实例：

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6
1
2
3

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组
1
2
3

思路：

类似滑动窗口

product(i, j) = product(0, j) / product(0, i)，从数组i到j的累乘等于从数组开头到j的累乘除以从数组开头i的累乘（先忽略0的情况），要考虑三种情况累乘的乘积等于0，就要重新开始

累乘的乘积小于0，要找到前面最大的负数，这样才能保证从i到j最大

累乘的乘积大于0，要找到前面最小的正数

法二：动态规划

记录前i的最小值和最大值，那么dp[i] = max(nums[i] * pre_max, nums[i] * pre_min, nums[i])

class Solution:
    def maxProduct(self, nums):
        if not nums: return 
        # 当前的累乘
        cur_pro = 1
        # 前面最小的整数
        min_pos = 1
        # 前面最大的负数
        max_neg = float('-inf')
        # 结果
        res = float('-inf')
        for num in nums:
            cur_pro *= num
            # 考虑三种情况
            # 当前的累乘结果大于0，要找到前面最小的正数
            if cur_pro > 0:
                res = max(res, cur_pro // min_pos)
                min_pos = min(min_pos, cur_pro)
            # 当前的累乘结果小于0，要找到前面最大的负数
            elif cur_pro < 0:
                if max_neg != float('-inf'):
                    res = max(res, cur_pro // max_neg)
                else:
                    res = max(res, num)
                max_neg = max(max_neg, cur_pro)
            # 当前累乘结果等于0，重新开始
            else:
                cur_pro = 1
                min_pos = 1
                max_neg = float('-inf')
                res = max(res, num)
        return res
# 法二：动态规划
class Solution:
    def maxProduct(self, nums):
        if not nums: return
        res = nums[0]
        pre_max = nums[0]
        pre_min = nums[0]
        for num in nums[1:]:
            cur_max = max(pre_max * num, pre_min * num, num)
            cur_min = min(pre_max * num, pre_min * num, num)
            res = max(res, cur_max)
            pre_max = cur_max
            pre_min = cur_min
        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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

153.寻找旋转排序数组中的最小值

题目：

假设按照升序排序的数组在预先未知的某个点上进行了旋转，例如，数组[0, 1, 2, 3, 4, 5, 6, 7]可能变为[4, 5, 6, 7, 0, 1, 2]，请找出其中最小元素

实例：

输入：nums = [3,4,5,1,2]
输出：1
1
2

输入：nums = [4,5,6,7,0,1,2]
输出：0
1
2

输入：nums = [1]
输出：1
1
2

class Solution:
    def findMin(self, nums):
        return min(nums)
#---------------------------------------------------------------
# 二分法
class Solution:
    def findMin(self, nums):
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (rignt - left) // 2
            if nums[right] < nums[mid]:
                left = mid + 1
            else:
                right = mid
        return nums[left]
# 当nums[mid] > nums[right]，说明在mid左半边的递增区域，说明最小元素在>mid区域
# 当nums[mid] <= nums[right]，说明在mid右半边的递增区域，说明最小元素在<=mid区域
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

154.寻找旋转排序数组中的最小值 II

题目：

假设按照升序排列的数组在预先未知的某个点上进行了旋转（例如，数组[0, 1, 2, 4, 5, 6, 7]可能变为[4, 5, 6, 7, 0, 1, 2]，请找出其中最小的元素

注意：数组中可能存在重复元素

实例：

输入: [1,3,5]
输出: 1
1
2

输入: [2,2,2,0,1]
输出: 0
1
2

思路：

旋转排序数组nums可以被拆分为2个排序数组nums1，nums2，并且nums1任意一元素 >= nums2任意一元素，因此，考虑二分法寻找两数组的分界点nums[i]（即第二个数组的首个元素）
设置left, right指针在nums数组两端，mid为每次二分的中点：
- 当nums[mid] > nums[right]时，mid一定在1个排序数组中，i一定满足mid < i <= right，因此，执行left = mid + 1
- 当nums[mid] < nums[right]时，mid一定在第2个排序数组中，i一定满足left < i <= mid因此，执行right = mid
- 当nums[mid] == nums[right]时，由于数组中的元素可能重复，难以判断分界点i指针区间
  - 采用right = right - 1的方法，证明：
    
    1.此操作不会使数组越界：因为迭代条件保证right > left >= 0
    
    2.此操作不会使最小值丢失：假设nums[right]是最小值，有两种情况
    - 若nums[right]是唯一最小值：那就不可能满足判断条件nums[mid] == nums[right]因为mid < right (left != right且mid = (left + right) // 2向下取整）
    - 若nums[right]不是唯一最小值，由于mid < right而nums[mid] == nums[right]，即还有最小值存在于[left, right - 1]区间，因此不会丢失最小值

class Solution:
    def findMin(self, nums):
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:
                right = right - 1
        return nums[left]
1
2
3
4
5
6
7
8
9
10
11
12

155.最小栈

题目：

设计一个支持push, pop, top操作，并能在常数时间内检索到最小元素的栈

push(x)——将元素x推入栈中
pop()——删除栈顶的元素
top()——获取栈顶元素
getMin()——检索栈中的最小元素

实例

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, x):
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
    def pop(self):
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()
    def top(self):
        return self.stack[-1]
  	def getMin(self):
        return self.min_stack[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

160.相交链表

题目：

找到两个单链表相交的起始节点，如下面的两个链表

在这里插入图片描述

在节点c1开始相交

实例：

在这里插入图片描述

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点
1
2
3

思路：

在这里插入图片描述

分别为链表A和链表B设置指针A和指针B，然后开始遍历链表，如果遍历完当前链表，则将指针指向另外一个链表的头部继续遍历，直到两个指针相遇，最终两个指针分别走过的路径为：

A：a + c + b

B：b + c + a

明显a + c + b = b + c + a，因而如果两个链表相交，则指针A和指针B必定在相交节点相遇

class Solution:
    def getIntersectionNode(self, headA, headB):
        if not headA or not headB:
            return None
        nodeA = headA
        nodeB = headB
        while nodeA != nodeB:
            nodeA = nodeA.next if nodeA else headB
            nodeB = nodeB.next if nodeB else headA
        return nodeA
1
2
3
4
5
6
7
8
9
10

162.寻找峰值

题目：

峰值元素是指其值大于左右相邻值得元素

给定一个输入数组nums，其中 $\not= nums[i+1]$ ，找到峰值元素，并返回其索引

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可，可以假设 $-\infin$

实例：

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2
1
2
3

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6
1
2
3
4

# 法一：直接求
class Solution:
    def findPeakElement(self, nums):
        n = len(nums)
        max_num = max(nums)
        max_idx = nums.index(max_num)
        if max_idx < n:
            return max_idx
# 法二：二分法
class Solution:
    def findPeakElement(self, nums):
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

164.最大间距

题目：

给定一个无序数组，找出数组在排序之后，相邻元素之间的最大差值，如果数组元素个数小于2，则返回0

实例

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3
1
2
3

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0
1
2
3

说明：

可以假设数组中所有元素都是非负数，且数值在32位有符号整数范围内
请尝试在线性时间复杂度和空间复杂度条件下解决问题

class Solution:
    def maximumGap(self, nums):
        nums = sorted(nums)
        n = len(nums) - 1
        if n < 2 :
            return 0
        max_gap = 0
        for i in range(n):
            cur_gap = nums[i+1] - nums[i]
            if cur_gap > max_gap:
                max_gap = cur_gap
        return max_gap
1
2
3
4
5
6
7
8
9
10
11
12

165.比较版本号

题目：

给你两个版本号version1和version2，请比较他们

版本号由一个或多个修订号组成，各修订号由一个'.'连接，每个修订号由多位数字组成，可能包含前导零。每个版本号至少包含一个字符。修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。例如2.5.33和0.1都是有效的版本号

比较版本号时，请按照从左到右的顺序依次比较他们的修订号，比较修订号时，只需要比较忽略任何前导零后的整数值。也就是说，修订号1和修订号001相等，如果版本号没有指定某个下标处的修订号，则该修订号为0。例如版本1.0小于版本1.1，因为他们下标为0的修订号相同，而下标为1的修订号分别为0和1

实例：

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"
1
2
3

输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"
1
2
3

输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2
1
2
3

输入：version1 = "1.0.1", version2 = "1"
输出：1
1
2

输入：version1 = "7.5.2.4", version2 = "7.5.3"
输出：-1
1
2

class Solution:
    def compareVersion(self, version1, version2):
        ver1 = version1.split('.')
        ver2 = version2.split('.')
       	while ver1 or ver2:
            x = int(ver1.pop(0)) if ver1 else 0
            y = int(ver2.pop(0)) if ver2 else 0
            if x == y:
                continue
            if x > y: return 1
            if x < y: return -1
        return 0
1
2
3
4
5
6
7
8
9
10
11
12

166.分数到小数

题目：

给定两个整数，分别表示分数的分子numerator和分母denominator，以字符串形式返回小数，如果小数部分为循环小数，则将循环的部分括在括号内，如果存在多个答案，只需返回任意一个，对于所有给定的输入，保证答案字符串的长度小于 $10^4$

实例：

输入：numerator = 1, denominator = 2
输出："0.5"
1
2

输入：numerator = 2, denominator = 1
输出："2"
1
2

输入：numerator = 2, denominator = 3
输出："0.(6)"
1
2

输入：numerator = 4, denominator = 333
输出："0.(012)"
1
2

输入：numerator = 1, denominator = 5
输出："0.2"
1
2

class Solution:
    def fractionToDecimal(self, numerator, denominator):
        if numerator == 0: return '0'
        res = []
        # 先判断正负，异或作用就是两个数不同，为True
        if (numerator > 0) ^ (denominator > 0):
            res.append('-')
        numerator, denominator = abs(numerator), abs(denominator)
        # 判断有没有小数，divmod方法得到商和余数的元组，例如2 / 3，那么a = 0, b = 2
        a, b = divmod(numerator, denominator)
        res.append(str(a))
        # 无小数
        if b == 0:
            return ''.join(res)
        res.append('.')
        # 处理余数，把所有出现过的余数记录下来
        loc = {b: len(res)}
        while b:
            b *= 10
            a, b = divmod(b, denominator)
            res.append(str(a))
            # 如果余数前面出现过，说明开始循环，加括号
            if b in loc:
                res.insert(loc[b], '(')
                res.append(')')
                break
            # 记录位置
            loc[b] = len(res)
        return ''.join(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
27
28
29

167.两数之和 II - 输入有序数组

题目：

给定一个已按照升序排列的有序数组，找到两个数使得他们相加之和等于目标数，函数应该返回这两个数的下标值index1和index2，其中index1必须小于index2

实例：

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
1
2
3

思路：

双指针

# 双指针
class Solution:
    def towSum(self, numbers, target):
        left, right = 0, len(numbers) - 1
        while left <= right:
            res = numbers[left] + numbers[right]
            if res == target:
                return (left+1, right+1)
            elif res < target:
                left += 1
            elif res > target:
                right -= 1
# 哈希表
class Solution:
    def twoSum(self, numbers, target):
        dct = dict()
        for index, num in enumerate(numbers):
            if num in dct:
                return (dct.get(num)+1, index+1)
            dct[target-num] = index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

168.Excel表列名称

题目：

给定一个正整数，返回它在Excel表中相对应的列名称

实例：

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
    ...
1
2
3
4
5
6
7
8

输入: 1
输出: "A"
1
2

输入: 28
输出: "AB"
1
2

输入: 701
输出: "ZY"
1
2

十进制转二十六进制

class Solution:
    def convertToTitle(self, n):
        res = ''
        while n:
            n, y = divmod(n, 26)
            if y == 0:
                n -= 1
                y = 26
            res = chr(y + 64) + res
        return res
1
2
3
4
5
6
7
8
9
10

169.多数元素

题目：

给定一个大小为n的数组，找到其中的多数元素（多数元素是指在数组中出现次数大于 $\lfloor{n/2}\rfloor$ 的元素）

实例：

输入: [3,2,3]
输出: 3
1
2

输入: [2,2,1,1,1,2,2]
输出: 2
1
2

思路：

摩尔投票法

如何在任意多的候选人中（选票无序），选出获得票数最多的那个

1.对抗阶段：分属两个候选人的票数进行两两对抗抵消

2.计数阶段：计算对抗结果中最后留下的候选人票数是否有效

class Solution:
    def majorityElement(self, nums):
        major = 0
        count = 0
        for n in nums:
            # 从0开始计数，如果从头开始，或者计数为0，那么major就等于当前遍历的数字
            if count == 0:
                major = n
            # 如果major和当前遍历到的数字相等，那么计数加一，反之减一
            if n == major:
                count += 1
            else:
                count -= 1
        return major
1
2
3
4
5
6
7
8
9
10
11
12
13
14

171. Excel表序列号

题目：

给定一个Excel表格中的列名称，返回其相应的序列号

实例：

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...
1
2
3
4
5
6
7
8

输入: "A"
输出: 1
1
2

输入: "AB"
输出: 28
1
2

输入: "ZY"
输出: 701
1
2

class Solution:
    def titleToNumber(self, s):
        d = len(s)
        value = 0
        sdict = dict()
        for i in range(1, 27):
            sdict[chr(i + 64)] = i
        for i in s:
            if d > 0:
                value += sdict[i] * 26 ** (d-1)
                d -= 1
        return value
1
2
3
4
5
6
7
8
9
10
11
12

172.阶乘后的零

题目：

给定一个整数n，返回n!结果尾数中零的数量

实例：

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
1
2
3

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
1
2
3

# 笨办法
class Solution:
    def trailingZeroes(self, n):
        res = 1
        count = 0
        for i in range(1, n+1):
            res *= i
        res = list(str(res))
        while True:
            tail = res.pop()
            if tail == '0':
                count += 1
                continue
            break
        return count
# 能在末尾形成0，来自因子2和5，只有有5，就一定存在一个数可以拆成2，这样末尾就有0了
class Solution:
    def trailingZeroes(self, n):
        res = 0
        while n > 0:
            n //= 5
            res += n
        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

173.二叉搜索树迭代器

题目：

实现一个二叉搜索树迭代器，使用二叉搜索树的根节点初始化迭代器，调用next()将返回二叉搜索树中的下一个最小的数

实例：

在这里插入图片描述

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // 返回 3
iterator.next();    // 返回 7
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 9
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 15
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 20
iterator.hasNext(); // 返回 false
1
2
3
4
5
6
7
8
9
10

class BTSTIterator:
    def __init__(self, root):
        self.stack = []
        self.push_stack(root)
    def next(self):
        tmp = self.stack.pop()
        if tmp.right:
            self.push_stack(tmp.right)
        return tmp.val
    def hasNext(self):
        return bool(self.stack)
    def push_stack(self, node):
        while node:
            self.stack.append(node)
            node = node.left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

174.地下城游戏（略）

175. 组合两个表

# 表1：person
+-------------+---------+
| 列名         | 类型     |
+-------------+---------+
| PersonId    | int     |
| FirstName   | varchar |
| LastName    | varchar |
+-------------+---------+
PersonId 是上表主键
1
2
3
4
5
6
7
8
9

# 表2：Address
+-------------+---------+
| 列名         | 类型    |
+-------------+---------+
| AddressId   | int     |
| PersonId    | int     |
| City        | varchar |
| State       | varchar |
+-------------+---------+
AddressId 是上表主键
1
2
3
4
5
6
7
8
9
10

编写一个SQL查询，满足条件：无论person是否有地址信息，都需要基于上述两表提供person的以下信息

FirstName, LastName, City, State
1

select
	FirstName,
	LastName,
	City,
	State
from
	Person p
left outer join
	Address a
on p.PersonId = a.PersonId
1
2
3
4
5
6
7
8
9
10

176.第二高的薪水（SQL题目，略）

177、178（SQL题目，略）

179. 最大数

题目：

给定一组非负整数nums，重新排列他们每个数字的顺序（每个数字不可拆分）使之组成一个最大的整数

注意：输出结果可能非常大，所以需要返回一个字符串而不是整数

实例：

输入：nums = [10,2]
输出："210"
1
2

输入：nums = [3,30,34,5,9]
输出："9534330"
1
2

输入：nums = [1]
输出："1"
1
2

输入：nums = [10]
输出："10"
1
2

# a = '3', b = '30', a < b
# 两个数排序比较，如果x + y > y + x，则x应该排在y的左边，这样最后才能得到最大值，默认排序是从低到高，所以重载比较运算符__lt__
class StrLt(str):
    def __lt__(x, y):
        return x+y > y+x
    
class Solution:
    def largestNumber(self, nums):
        nums = list(map(str, nums))
        nums.sort(key=StrLt)
        return ''.join(nums) if nums[0] != '0' else '0'
1
2
3
4
5
6
7
8
9
10
11

180-186（SQL题目，略）

187.重复的DNA序列

题目：

所有的DNA都由一系列缩写为’A’，‘C’，‘G’，和’T’的核苷酸组成，例如：'ACGAATTCCG'，在研究DNA时，识别DNA中的重复序列有时会对研究非常有帮助。编写一个函数来找出所有目标子串，目标子串长度为10，且在DNA字符串s中出现次数超过一次

实例：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
1
2

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]
1
2

class Solution:
    def findRepeatedDnaSequences(self, s):
        from collections import defaultdict
        visited = set()
        res = set()
        for i in range(0, len(s)-9):
            tmp = s[i: i+10]
            if tmp in visited:
                res.add(tmp)
            visited.add(tmp)
        return list(res)
1
2
3
4
5
6
7
8
9
10
11

188. 买卖股票的最佳时机 IV（略…太难了T_T）

题目：

给定一个整数数组prices，它的第i个元素prices[i]是一支给定的股票在第i天的价格，设计一个算法来计算你所能获取的最大利润，最多可以完成k笔交易

注意：不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）

实例：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 
1
2
3

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3
1
2
3
4

189. 旋转数组

题目：

给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数

实例：

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
1
2
3
4
5
6

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
1
2
3
4
5

class Solution:
    def rotate(self, nums):
        n = len(nums)
        num1 = nums[: n-k]
        del nums[: n-k]
        nums += num1
# 三次翻转
class Solution:
    def rotate(self, nums):
        n = len(nums)
        k = k % n
        def swap(l, r):
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
        swap(0, n-k-1)
        swap(n-k, n-1)
        swap(0, n-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

190.颠倒二进制位

题目：

颠倒给定的32位无符号整数的二进制位

实例：

输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
1
2
3
4

输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
1
2
3
4

class Solution:
    def def reverseBits(self, n):
        str1 = bin(n) # 转换位二进制字符串
        str2 = str1[2: ].zfill(32) # 去掉前'0b'后填充为32位
        str3 = str2[::-1] # 字符串反转
        return int(str3, 2) # 转为10进制
    
    
 # zfill()方法：返回指定长度字符串，原字符串右对其，前面填充0
 # 三次翻转法
 class Solution:
	def rotate(self, nums):
	        n = len(nums)
	        k = k % n
	        def swap(l, r):
	            while l < r:
	                nums[l], nums[r] = nums[r], nums[l]
	                l += 1
	                r -= 1
	        swap(0, n-k-1)
	        swap(n-k, n-1)
	        swap(0, n-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/93655

一天一道LeetCode(151-190)_# 余数前面出现过,说明开始循环了,加括号 if b in loc:

一天一道LeetCode（151-190）

文章目录

151.翻转字符串里的单词

152.乘积最大子数组

153.寻找旋转排序数组中的最小值

154.寻找旋转排序数组中的最小值 II

155.最小栈

160.相交链表

162.寻找峰值

164.最大间距

165.比较版本号

166.分数到小数

167.两数之和 II - 输入有序数组

168.Excel表列名称

169.多数元素

171. Excel表序列号

172.阶乘后的零

173.二叉搜索树迭代器

174.地下城游戏（略）

175. 组合两个表

176.第二高的薪水（SQL题目，略）

177、178（SQL题目，略）

179. 最大数

180-186（SQL题目，略）

187.重复的DNA序列

188. 买卖股票的最佳时机 IV（略…太难了T_T）

189. 旋转数组

190.颠倒二进制位