一天一道LeetCode(151-190)

本文主要是介绍一天一道LeetCode(151-190)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一天一道LeetCode（151-190）

文章目录

- - 一天一道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.颠倒二进制位

151.翻转字符串里的单词

题目：

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

实例：

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

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

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

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

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

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

152.乘积最大子数组

题目：

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

实例：

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

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

思路：

类似滑动窗口

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 = 1min_pos = 1max_neg = float('-inf')res = max(res, num)return res
# 法二：动态规划
class Solution:def maxProduct(self, nums):if not nums: returnres = 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_maxpre_min = cur_minreturn res

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

题目：

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

实例：

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

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

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

class Solution:def findMin(self, nums):return min(nums)
#---------------------------------------------------------------
# 二分法
class Solution:def findMin(self, nums):left = 0right = len(nums) - 1while left < right:mid = left + (rignt - left) // 2if nums[right] < nums[mid]:left = mid + 1else:right = midreturn nums[left]
# 当nums[mid] > nums[right]，说明在mid左半边的递增区域，说明最小元素在>mid区域
# 当nums[mid] <= nums[right]，说明在mid右半边的递增区域，说明最小元素在<=mid区域

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

题目：

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

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

实例：

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

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

思路：

旋转排序数组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) - 1while left < right:mid = (left + right) // 2if nums[mid] > nums[right]:left = mid + 1elif nums[mid] < nums[right]:right = midelse:right = right - 1return nums[left]

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.

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]

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 个节点

思路：

在这里插入图片描述

分别为链表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 NonenodeA = headAnodeB = headBwhile nodeA != nodeB:nodeA = nodeA.next if nodeA else headBnodeB = nodeB.next if nodeB else headAreturn nodeA

162.寻找峰值

题目：

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

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

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

实例：

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

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

# 法一：直接求
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 = 0right = len(nums) - 1while left < right:mid = left + (right - left) // 2if nums[mid] < nums[mid + 1]:left = mid + 1else:right = midreturn left

164.最大间距

题目：

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

实例

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

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

说明：

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

class Solution:def maximumGap(self, nums):nums = sorted(nums)n = len(nums) - 1if n < 2 :return 0max_gap = 0for i in range(n):cur_gap = nums[i+1] - nums[i]if cur_gap > max_gap:max_gap = cur_gapreturn max_gap

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"

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

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

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

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

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 0y = int(ver2.pop(0)) if ver2 else 0if x == y:continueif x > y: return 1if x < y: return -1return 0

166.分数到小数

题目：

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

实例：

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

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

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

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

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

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

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

题目：

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

实例：

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

思路：

双指针

# 双指针
class Solution:def towSum(self, numbers, target):left, right = 0, len(numbers) - 1while left <= right:res = numbers[left] + numbers[right]if res == target:return (left+1, right+1)elif res < target:left += 1elif 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

168.Excel表列名称

题目：

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

实例：

    1 -> A2 -> B3 -> C...26 -> Z27 -> AA28 -> AB ...

输入: 1
输出: "A"

输入: 28
输出: "AB"

输入: 701
输出: "ZY"

十进制转二十六进制

class Solution:def convertToTitle(self, n):res = ''while n:n, y = divmod(n, 26)if y == 0:n -= 1y = 26res = chr(y + 64) + resreturn res

169.多数元素

题目：

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

实例：

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

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

思路：

摩尔投票法

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

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

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

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

171. Excel表序列号

题目：

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

实例：

    A -> 1B -> 2C -> 3...Z -> 26AA -> 27AB -> 28 ...

输入: "A"
输出: 1

输入: "AB"
输出: 28

输入: "ZY"
输出: 701

class Solution:def titleToNumber(self, s):d = len(s)value = 0sdict = dict()for i in range(1, 27):sdict[chr(i + 64)] = ifor i in s:if d > 0:value += sdict[i] * 26 ** (d-1)d -= 1return value

172.阶乘后的零

题目：

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

实例：

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

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

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

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

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.valdef hasNext(self):return bool(self.stack)def push_stack(self, node):while node:self.stack.append(node)node = node.left

174.地下城游戏（略）

175. 组合两个表

# 表1：person
+-------------+---------+
| 列名         | 类型     |
+-------------+---------+
| PersonId    | int     |
| FirstName   | varchar |
| LastName    | varchar |
+-------------+---------+
PersonId 是上表主键

# 表2：Address
+-------------+---------+
| 列名         | 类型    |
+-------------+---------+
| AddressId   | int     |
| PersonId    | int     |
| City        | varchar |
| State       | varchar |
+-------------+---------+
AddressId 是上表主键

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

FirstName, LastName, City, State

selectFirstName,LastName,City,State
fromPerson p
left outer joinAddress a
on p.PersonId = a.PersonId

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

177、178（SQL题目，略）

179. 最大数

题目：

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

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

实例：

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

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

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

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

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

180-186（SQL题目，略）

187.重复的DNA序列

题目：

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

实例：

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

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

class Solution:def findRepeatedDnaSequences(self, s):from collections import defaultdictvisited = 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)

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

题目：

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

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

实例：

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

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

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,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

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 % ndef swap(l, r):while l < r:nums[l], nums[r] = nums[r], nums[l]l += 1r -= 1swap(0, n-k-1)swap(n-k, n-1)swap(0, n-1)

190.颠倒二进制位

题目：

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

实例：

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

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

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 % ndef swap(l, r):while l < r:nums[l], nums[r] = nums[r], nums[l]l += 1r -= 1swap(0, n-k-1)swap(n-k, n-1)swap(0, n-1)