一天一道Leetcode(190-230)

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

一天一道Leetcode（191-230）

191.位1的个数

题目：

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为’1’的个数（也成为汉明重量）

实例：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

# 将数字转化为“二进制”字符串，然后看字符串中为“1”的count个数
class Solution:def hammingWeight(self, n):n = bin(n)return n.count('1')

192-197. 统计词频（bash脚本题目，略）

198.打家劫舍

题目：

一个专业小偷，计划偷窃沿街房屋。每间房内都藏有一定的现金，影响偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警，给定一个代表每个房屋存放金额的非负整数数组，计算不触动报警装置的情况下，一夜之内能够偷窃到的最高金额

实例：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12

思路：

动态规划

• 状态定义：

  • 设动态规划列表dp，dp[i]代表前i个房子在满足条件的情况下能偷窃到的最高金额

• 转移方程：

  • 设：有n个房子，前n间能偷窃到的最高金额是dp[n]，前n - 1间能偷窃到的最高金额是dp[n - 1]，此时向这些房子后加一间房子，此房间的价值为num

  • 加一间房后：由于不能抢相邻的房子，意味着抢第n + 1间就不能抢第n间；那么前n + 1间房能偷取到的最高金额dp[n + 1]一定是以下两种情况的较大值：

    1.不抢第n + 1个房间，因此等于前n个房子的最高金额，即dp[n + 1] = dp[n];

    2.抢第n + 1个房间，此时不能抢第n个房间；因此等于前n - 1个房子的最高金额加上当前房间的价值，即dp[n + 1] = dp[n - 1] + num

  • 难道在前n间的最高金额dp[n]情况下，第n间一定被偷了么？，假设没有被偷，那么n + 1间的最大值应该也可能是dp[n + 1] = dp[n] + num，其实这种假设的情况可以被省略，因为：

    1.假设第n间没有被偷，那么此时dp[n] = dp[n - 1]，此时dp[n + 1] = dp[n] + num = dp[n - 1] + num，即两种情况合并为一种

    2.假设第n间被偷，那么此时dp[n + 1] = dp[n] + num不可取，因为偷了第n间，就不能偷第n + 1间

  • 最终的转移方程：dp[n + 1] = max(dp[n], dp[n - 1] + num)

class Solution:def rob(self, nums):cur, pre = 0, 0for num in nums:cur, pre = max(pre + num, cur), cur# 为什么不能写成以下形式：# cur = max(pre + num, cur)# pre = cur# 因为pre需要接收原来的cur值，而不是更新后的cur值，可以写成以下形式：# tmp_cur = cur# cur = max(pre + num, cur)# pre = tmp_curreturn cur

199. 二叉树的右视图

题目：

给定一棵二叉树，想象站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值

实例：

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:1            <---/   \
2     3         <---\     \5     4       <---

思路：

BFS

1.用到deque结构来模拟队列

2.队列里有一个初始节点

3.每次处理从队列中出队一个元素

4.对元素进行扩张

5.对扩张后满足某条件的节点再进行处理，根据需要进入队列，进入队列的点就是扩到下一层的点

6.然后接着循环处理deque中的元素，直到deque为空，则代表所有节点都已完成扩张

class Solution:def rightSideView(self, root):if not root: return []res = []# 构建一个队列tmp_layer = collections.deque()# 将初始节点压入tmp_layer.append(root)while len(tmp_layer):# count用来记录时某一层的第几个元素count = 0next_layer = []# 大循环，处理某一层的节点while len(tmp_layer):# 由于只要最右侧的元素，所以下面先压入队列的是右子树，然后压入左子树，只需要队列中的第一个元素tmp_node = tmp_layer.popleft()                if count == 0:res.append(tmp_node.val)count += 1# 将某个节点的右子树压入if tmp_node.right is not None:next_layer.append(tmp_node.right)# 将某个节点的左子树压入if tmp_node.left is not None:next_layer.append(tmp_node.left)# 更新下一层的tmptmp_layer = collections.deque(next_layer)return res

200. 岛屿数量

题目：

给你一个由’1’（陆地）和’0’（水）组成的二维网格，计算网格中岛屿的数量（岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成），可以假设该网格的四条边均被水包围

实例：

输入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
输出：1

输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
输出：3

思路：

BFS

如果发现一个陆地，便对其进行BFS，并将可由BFS访问到的点的都置为已经访问的状态，从而代表同属一个岛屿

class Solution:def numIslands(self, grid):count = 0for row in range(len(grid)):for col in range(len(grid[0])):# 发现陆地if grid[row][col] == '1':count += 1 # 结果加1# 将其转化为0，表示已经访问过# 对发现的陆地进行扩张，即执行BFS操作，将与其相邻的陆地都标记为已经访问，下面是BFS过程grid[row][col] = '0'land_positions = collections.deque()land_positions.append([row, col])while len(land_positions):x, y = land_positions.popleft()# 对四个方向进行扩张for new_x, new_y in [[x, y+1], [x, y-1], [x+1, y], [x-1, y]]:# 判断有效性if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]) and grid[new_x][new_y] == '1':# 因为可由BFS访问到，代表同属一块岛，将其置0，代表已访问过grid[new_x][new_y] = '0'land_positions.append([new_x, new_y])return count

201. 数字范围按位与

题目：

给定范围[m, n]，其中0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含m, n两端点）

实例：

输入: [5,7]
输出: 4

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

思路：

考虑范围[m, n]，如果n比m二进制位数高，在累计按位与的过程中，数字的每一个二进制位数必然都出现过0，所以一旦出现位数不同的情况，结果必然为0

程序中，m, n在向右移位的过程中，如果m, n相等了，就说明累计按位与的左边肯定等于m, n此时的状态，这时就可以向左移回来，相当于右边所有位数都补0，相等的部分照旧

如果m, n位数不相等，肯定回移动到底，两者都为0时才会相等停止循环，这时再向左移动多少结果都是0

class Solution:def rangeBitwiseAnd(self, m, n):t = 0while m != n:m >>= 1n >>= 1t += 1return n << t

202. 快乐数

题目：

编写一个算法来判断一个数n是不是快乐数

快乐数：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为1，也可能时无限循环但始终变不到1，如果可以变为1，那么这个数就是快乐数

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

# 用一个容器记录已经出现过的数
class Solution:def isHappy(self, n):n = str(n)visited = set()while True:n = str(sum(int(i) ** 2 for i in n))if n == '1':return Trueif n in visited:return Falsevisited.add(n)

203. 移除链表元素

题目：

删除链表中等于给定值val的所有节点

实例：

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

# 迭代
class Solution:def removeElements(self, head, val):tmp = ListNode(0)tmp.next = headprev = tmplast = prev.nextwhile last:if last.val == val:prev.next = last.nextlast = prev.nextelse:prev = prev.nextlast = prev.nextreturn tmp.next
# 递归
class Solution:def removeElements(self, val):if not head: return head.next = self.removeElements(head.next, val)return head.next if head.val == val else head

204. 计数质数

题目：

统计所有小于非负整数n的质数的数量

实例：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 

输入：n = 0
输出：0

输入：n = 1
输出：0

# 笨办法，超时了
class Solution:def countPrimes(self, n):count = 0def is_prime(n):if n > 1:for i in range(2, n):if n % i == 0:return Falsereturn Truefor num in range(2, n):if is_prime(num):count += 1return count
# 厄拉多塞筛法
class Solution:def countPrime(self, n):# 给每个位置立一个flag，初始化为1isPrime = [1] * n# 创建计数器res = 0# 循环，从最小质数i开始到n循环for i in range(2, n):# 如果这个位置的Flag为1，说明数字i没有被比i小的整数除过，说明它是质数，计数+1if isPrimes[i] == 1: res += 1# 同时，i的倍数一定不是质数，将这些数的flag置为0# 设置背书j，初始化与i相等，因为i也是一点点加上来的，比如i=5时，i的4倍一定在i=4时设置为0过j = i# 当i的j倍大于n的时候跳出循环while i * j < n:# 设置i的j倍的flag为0isPrime[i * j] = 0# 自增，下一个找j + 1倍j += 1return res
# 进一步优化
class Solution:def countPrimes(self, n):if n < 2: return 0isPrimes = [1] * n# 设置0和1位为0isPrimes[0] = isPrimes[1] = 0# 在2到根号n的范围内，当一个数时质数，将它所有的比n小的倍数设置成0for i in range(2, int(n ** 0.5) + 1):if isPrimes[i] == 1:isPrimes[i * i: n: i] = [0] * len(isPrimes[i * i: n: i])return sum(isPrimes)

205. 同构字符串

题目：

给定两个字符串s和t，判断他们是否是同构的（如果s中的字符串可以被替换得到t，那么这两个字符串是同构的），所有出现的字符都必须用另一个字符替换，同时保留字符的顺序，两个字符不能映射到同一个字符上，但字符可以映射自己本身。（s和t有相同长度）

实例：

输入: s = "egg", t = "add"
输出: true

输入: s = "foo", t = "bar"
输出: false

输入: s = "paper", t = "title"
输出: true

class Solution:def isIsomorphic(self, s, t):if not s: return Truedic = dict()for i in range(len(s)):if s[i] not in dic:if t[i] in dic.values():return Falseelse:dic[s[i]] = t[i]else:if dic[s[i]] != t[i]:return Falsereturn True

207. 课程表

题目：

这个学期必须选修numCourse门课程，记为0到numCourse - 1，再选修某些课程之前需要一些先修课程，例如，想要学习课程0，需要先完成课程1，用一个匹配来表示他们[0, 1]

给定课程的总量以及他们的先决条件，请判断是否可能完成所有课程的学习？

实例：

输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

思路：

广度优先遍历

1.统计课程安排图中每个节点的入度，生成入度表indegrees

2.借助一个队列，将所有入度为0的节点入队

3.当queue非空时，一次将队首节点出队，再课程安排图中删除此节点pre:

• 并不是真正从邻接表中删除此节点pre，而是将此节点对应所有邻接节点cur的入度-1，即indegrees[cur] -= 1
• 当入度-1后邻接节点cur的入度为0，说明cur所有的前驱节点已经被“删除”，此时将cur入队

4.在每次pre出队时，执行numCourses–;

• 若整个课程安排时有向无环图（即可以安排），则所有节点一定都入队并出队过，即完成拓扑排序，换个角度说，如果课程安排图中存在环，一定又节点的入度始终不为0
• 因此，拓扑排序出队次数等于课程个数，返回numCourses == 0判断课程是否可以成功安排

class Solution:def canFinish(self, numCourses, prerequisites):from collections import dequeindegrees = [0 for _ in range(numCourses)]adjacency = [[] for _ in range(numCourses)]queue = deque()for cur, pre in prerequisites:indegrees[cur] += 1adjacency[pre].append(cur)for i in range(len(indegrees)):if not indegrees[i]:queue.append(i)while queue:pre = queue.popleft()numCourses -= 1for cur in adjacency[pre]:indegrees[cur] -= 1if not indegrees[cur]:queue.append(cur)return not numCourses

208. 实现Trie（前缀树）

题目：

实现一个Trie（前缀树），包含insert, search, 和startsWith这三个操作

实例：

Trie trie = new Trie();trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

class Solution:def __init__(self):self.lookup = {}def insert(self, word):tree = self.lookupfor a in word:if a not in tree:tree[a] = {}tree = tree[a]tree['#'] = '#'def search(self, word):tree = self.lookupfor a in word:if a not in tree:return Falsetree = tree[a]if '#' in tree:return Truereturn Falsedef startsWith(self, prefix):tree = self.lookupfor a in prefix:if a not in tree:return Falsetree = tree[a]return True

209. 长度最小的子数组

题目：

给定一个含有n个正整数的数组和一个正整数s，找出该数组中满足其和>= s的长度最小的连续子数组，并返回其长度，如果不存在符合条件的子数组，返回0

实例：

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组

# 滑动窗口
class Solution:def minSubArrayLen(self, s, nums):if not nums: return 0left = 0cur = 0res = float('inf')# 设置right指针，并累加数组结果for right in range(len(nums)):cur += nums[right]# 当当前累加结果大于目标值，用累加结果减去left对应的值，同时left右移一位while cur >= s:res = min(res, right - left + 1)cur -= nums[left]left += 1return res if res != float('inf') else 0
# 前缀和 + 二分搜索
class Solution:def minSubArrayLen(self, s, nums):if not nums: return 0for i in range(1, len(nums)):nums[i] == nums[i - 1]if nums[-1] < s:return 0res = float('inf')nums = [0] + numsfor i in range(1, len(nums)):if nums[i] - s >= 0:loc = bisect.bisect_left(nums, nums[i] - s)if nums[i] - nums[loc] >= s:res = min(res, i - loc)continueif loc > 0:res = min(res, i - loc + 1)return res

210. 课程表 II（拓扑排序，还不懂…）

题目：

现在共有n门课程需要选，记为0到n-1，在选修某些课程之前需要一些先修课程，例如，想要学习课程0，需要先完成课程1，用一个匹配来表示他们：[0, 1]

给定课程总量以及他们的先决条件，返回为了学完所有课程安排的学习顺序，可能会有多个正确顺序，只需要返回一种即可，如果不可能完成所有课程，返回一个空数组

实例：

输入: 2, [[1,0]] 
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1]

输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3]

211. 添加与搜索单词 - 数据结构设计

题目：

设计一个数据结构，支持添加新单词和查找字符串是否与任何先前添加的字符串匹配，实现词类WordDictionary:

• WordDictionary()初始化词典对象
• void addWord(word)将word添加到数据结构中，之后可以对它进行匹配
• bool search(word)如果数据结构中存在字符串与word匹配，则返回true，否则返回false，word中可能包含一些'.'，每个.，都可以表示任何一个字母

实例：

["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

class WordDictionary:def __init__(self):from collections import defaultdictself.lookup = {}def addWord(self, word):tree = self.lookupfor a in word:tree = tree.setdefault(a, {})tree['#'] = {}def search(self, word):def helper(word, tree):if not word:if '#' in tree:return Truereturn Falseif word[0] == '.':for t in tree:if helper(word[1:], tree[t]):return Trueelif word[0] in tree:if helper(word[1:], tree[word[0]]):return Truereturn Falsereturn helper(word, self.lookup)

212. 单词搜索 II（未解决）

213. 打家劫舍 II

题目：

一个专业小偷，计划偷窃沿街房屋，每间房内都藏有一定现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的，同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋再同一晚上被小偷闯入，系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组，计算在不触动警报装置的情况下，能够偷窃到的最高金额

实例：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 

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

思路：

环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，因此可以把此环状排列房间问题简化成两个单排排列房子问题：

1.在不偷窃第一个房子的情况下（即nums[1:]），最大金额是p1

2.在不偷窃最后一个房子的情况下（即nums[: n-1]），最大金额是p2

综合偷窃最大金额：为以上两种情况的较大值，即max(p1, p2)

class Solution:def rob(self, nums):def my_rob(nums):cur, pre = 0, 0for num in nums:cur, pre = max(pre + num, cur), curreturn curreturn max(my_rob(nums[:-1]), my_rob(nums[1:])) if len(nums) != 1 else nums[0]

214. 最短回文串（未解决）

215. 数组中的第k个最大元素

题目：

在未排序的数组中找到第k个最大的元素，需要找的是数组排序后的第k个最大元素，而不是第k个不同的元素

实例：

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

class Solution:def findKthLargest(self, nums, k):if not nums: return Nonenums = sorted(nums, reverse=True)return nums[k-1]

216. 组合总和 II

题目：

找出所有相加之和为n的k个数的组合，组合中只允许含有1-9的正整数，并且每种组合中不存在重复数字

实例：

输入: k = 3, n = 7
输出: [[1,2,4]]

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

思路：

回溯+剪枝

1.初始化结果数组res

2.定义回溯函数help(count, i, tmp, target)，其中count表示当前已经使用的数字数，i表示当前访问的数字，tmp表示当前中间结果，target表示下一步的目标和

• 若count == k，说明已经使用了k个数：
  • 若target == 0，表示tmp的和等于n，将tmp加入res
  • return
• 遍历区间[i, 10]:
  • 剪枝，若j > target，说明接下来的数字都比目标和大，break
  • 执行回溯help(count + 1, j + 1, tmp + [j], target - j)

3.执行help(0, 1, [], n)

4.返回res

class Solution:def combinationSum3(self, k, n):res = []def helper(count, i, tmp, target):if count == k:if target == 0:res.append(tmp)return for j in range(i, 10):if j > target:breakhelper(count+1, j+1, tmp+[j], target-j)helper(0, 1, [], n)return res

217. 存在重复元素

题目：

给定一个整数数组，判断是否存在重复元素，如果任意一值在数组中出现至少两次，返回True，如果每个元素都不相同，返回False

实例：

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

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

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

class Solution:def containsDuplicate(self, nums):dic = {}for num in nums:if num not in dic:dic[num] = 1else:dic[num] += 1for ele in dic.values():if ele != 1:return Truereturn False
# -----------------------------------------
class Solution:def containsDuplicate(self, nums):dic = {}for num in nums:if dic.get(num):return Truedic[num] = 1return False
# ---------------------------------------------
class Solution:def containsDuplicate(self, nums):return len(nums) != len(set(nums))

218. 天际线问题（未解决）

219. 存在重复元素 II

题目：

给定一个整数数组和一个整数k，判断数组中是否存在两个不同的索引i和j，使得nums[i] = nums[j]，并且i和j的差绝对值至多为k

实例：

输入: nums = [1,2,3,1], k = 3
输出: true

输入: nums = [1,0,1,1], k = 1
输出: true

输入: nums = [1,2,3,1,2,3], k = 2
输出: false

class Solution:def containsNearbyDuplicate(self, nums, k):dic = {}for key, v in enumerate(nums):if v not in dic or (key - dic[v]) > k:dic[v] = keyelse:return Trueelse:return False

220. 存在重复元素 III

题目：

在整数数组nums中，是否存在两个下标i, j，使得nums[i]和nums[j]的差的绝对值小于等于t，且满足i和j的差的绝对值也小于等于k

实例：

输入: nums = [1,2,3,1], k = 3, t = 0
输出: true

输入: nums = [1,0,1,1], k = 1, t = 2
输出: true

输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

思路：

桶

定义桶的大小是t + 1, nums[i] // (t + 1)决定放入几号桶，这样在一个桶里面的任意两个的绝对值差值都<= t

先不考虑索引差值最大为k的限制，那么遍历nums每一个元素，并把他们放入相应的桶中，有两种情况会返回True

• 要放入的桶已经有其他元素了，这时将nums[i]放进去满足差值<= t
• 可能存在前面一个桶的元素并且与nums[i]的差值<= t或者存在后面一个桶的元素并且与nums[i]的差值<= t

根据返回True的第一个条件，可以知道后面桶的元素最多也只能有一个

接着考虑限制桶中的索引差最大为k，当i >= k时：需要删除存放着nums[i - k]的那个桶（编号为nums[i-k] // (t + 1) )

这样就能保证遍历到第i+1个元素时，全部桶中元素的索引最小值是i - k + 1，就满足题目对索引的限制了

class Solution:def containsNearbyAlmostDuplicate(self, nums, k, t):if t < 0 or k < 0:return Falseall_buckets = {}# 将桶的大小设置为t+1bucket_size = t + 1for i in range(len(nums)):# 决定放入哪个桶bucket_num = nums[i] // bucket_size# 如果桶中已经有元素了，将nums[i]放入桶中if bucket_num in all_buckets:return Trueall_buckets[bucket_num] = nums[i]if (bucket_num - 1) in all_buckets and abs(all_buckets[bucket_num - 1] - nums[i]) <= t:return Trueif (bucket_num + 1) in all_buckets and abs(all_buckets[bucket_num + 1] - nums[i]) <= t:return True# 如果不构成返回条件，那么当i >= k 时就要删除旧桶，以维持桶中的元素索引跟下一个i+1索引只差不超过kif i >= k:all_buckets.pop(nums[i-k] // bucket_size)return False

221. 最大正方形

题目：

在一个由’0’和’1’组成的二维矩阵内，找到只包含’1’的最大正方形，并返回其面积

实例：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

思路：

动态规划

dp[i][j]代表以i, j为正方形右下角的最大表厂是多少

状态转移方程：在matrix[i][j]==1的情况下dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][-1]) + 1

class Solution:def maximalSquare(self, matrix):if not matrix: return 0row = len(matrix)col = len(matrix[0])dp = [[0] * (col + 1) for _ in range(row + 1)]res = 0for i in range(1, row+1):for j in range(1, col+1):if matrix[i-1][j-1] == '1':dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1res = max(res, dp[i][j] ** 2)return res

222. 完全二叉树的节点个数

题目：

给出一个完全二叉树，求出该树的节点个数

说明：

完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为h层，则该层包含1~$2^h$个节点

实例：

输入: 1/ \2   3/ \  /
4  5 6输出: 6

class Solution:def countNodes(self, root):if not root: return 0left_height = 0left_node = rootright_height = 0right_node = rootwhile left_node:left_node = left_node.leftleft_height += 1while right_node:right_node = right_node.rightright_height += 1if left_height == right_height:return pow(2, left_height) - 1return 1 + self.countNodes(root.left) + self.countNodes(root.right)

223. 矩形面积

题目：

在二维平面上计算出两个由直线构成的矩形重叠后形成的总面积。每个矩形由其左下顶点和右上顶点坐标表示

实例：

输入: -3, 0, 3, 4, 0, -1, 9, 2
输出: 45

class Solution:def computeArea(self, A, B, C, D, E, F, G, H):# 调整两个矩形位置，让第一个矩形靠左边if A > E:return self.computeArea(E, F, G, H, A, B, C, D)if B >= H or D <= F or C <= E:return abs(A - C) * abs(B - D) + abs(E - G) * abs(F - H)down = max(A, E)up = min(C, G)left = max(B, F)right = min(D, H)return abs(A - C) * abs(B - D) + abs(E - G) * abs(F - H) - abs(up - down) * abs(left - right)

224. 基本计算器

题目：

实现一个基本的计算器来计算一个简单的字符串表达式s的值

实例：

输入：s = "1 + 1"
输出：2

输入：s = " 2-1 + 2 "
输出：3

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

栈

class Solution:def calculate(self, s):res = 0stack = []sign = 1i = 0n = len(s)while i < n:if s[i] == '':i += 1elif s[i] == '-':sign = -1i += 1elif s[i] == '+':sign = 1i += 1elif s[i] == '(':stack.append(res)stack.append(sign)res = 0sign = 1i += 1elif s[i] == ')':res = res * stack.pop() + stack.pop()i += 1# isdigit()检测字符串是否只由数字组成elif s[i].isdigit():tmp = int(s[i])i += 1while i < n and s[i].isdigit():tmp = tmp * 10 + int(s[i])i += 1res += tmp * signreturn res

225. 用队列实现栈

题目：

使用队列实现栈的下列操作：

• push(x) – 元素x入栈
• pop() – 移除栈顶元素
• top() – 获取栈顶元素
• empty() – 返回栈是否维空

class MyStack:def __init__(self):self.q = []def push(self, x):self.q.append(x)q_length = len(self.q)while q_length > 1:self.q.append(self.q.pop(0))q_length -= 1def pop(self):return self.q.pop(0)def top(self):return self.q[0]def empty(self):return not bool(self.q)

226. 翻转二叉树

题目：

翻转一棵二叉树

实例：

     4/   \2     7/ \   / \
1   3 6   9

  	 4/   \7     2/ \   / \
9   6 3   1

# 递归
class Solution:def invertTree(self, root):if not root: return Noneroot.left, root.right = root.right, root.leftself.invertTree(root.left)self.invertTree(root.right)return root
# 迭代
class Solution:def invertTree(self, root):if not root: return Nonefrom collections import dequequeue = deque()queue.append(root)while queue:node = queue.popleft()node.left, node.right = node.right, node.leftif node.left:queue.append(node.left)if node.right:queue.append(node.right)return root

227. 基本计算器

题目：

实现一个基本的计算器来计算一个简单的字符串表达式的值，字符串表达式仅包含非负整数，+, -, *, / 四种运算符和空格，整数除法仅保留整数部分

实例：

输入: "3+2*2"
输出: 7

输入: " 3/2 "
输出: 1

输入: " 3+5 / 2 "
输出: 5

class Solution:def calculate(self, s):stack = []num, sign = 0, '+'for i in range(len(s)):if s[i].isdigit():num = num * 10 + int(s[i])if s[i] in '+-*/' or i == len(s) - 1:if sign == '+':stack.append(num)elif sign == '-':stack.append(-num)elif sign == '*':stack.append(stack.pop() * num)else:stack.append(int(stack.pop() / num))num = 0sign = s[i]return sum(stack)

228. 汇总区间

题目：

给定一个无重复元素的有序整数数组nums，返回恰好覆盖数组中所有数字的最小有序区间范围列表，也就是说nums的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于nums的数字x

实例：

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

输入：nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

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

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

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

class Solution:def summaryRanges(self, nums):n = len(nums)# 初始化双指针，均指向数组头部left = 0right = 0ans = []# 开始遍历while right < n:# 数组有序，先限定边界，查找间隔大于1的部分while right < n - 1 and nums[right] + 1 == nums[right + 1]:right += 1# 找到间隔后，将前面连续部分按照规定格式添加到结果列表中tmp = [str(nums[left])]if nums[left] != nums[right]:tmp.append('->')tmp.append(str(nums[right]))ans.append(''.join(tmp))# 维护更新right和leftright += 1left = rightreturn ans

229. 求众数 II

题目：

给定一个大小为n的整数数组，找出其中所有出现超过$\lfloor n/3\rfloor$次的元素，尝试设计时间复杂度为O(n)、空间复杂度为O(1)的算法

实例：

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

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

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

思路：

摩尔投票法

核心：每次都拿走3个不一样的数，那么最后剩下的一定是A, B

拿走的三个数抵消可以分为三种情况：

1.包括A、B

将柱形图的三个柱形都减一，得到新的柱形图最高的仍然是A、B，不影响最终结果

2.只包括A、B其中一个，假设是A

虽然A减少了1，但是其他数的柱形图也减少了1， 得到的新柱形图最高的仍然是A，B，不影响最终结果

3.都不包括A、B

其他数的柱形减少，得到的新柱形图仍然是A、B最高，不影响最终结果

class Solution:def majorityElement(self, nums):a, b, count_a, count_b = 0, 0, 0, 0res = []for i in nums:if a == i:count_a += 1continueif b == i:count_b += 1continueif count_a == 0:a = icount_a = 1continueif count_b == 0:b = icount_b = 1continuecount_a -= 1count_b -= 1count_a, count_b = 0, 0for j in nums:if j == a:count_a += 1elif j == b:count_b += 1if count_a > len(nums) / 3:res.append(a)if count_b > len(nums) / 3:res.append(b)return res

230. 二叉搜索树中第k小的元素

题目：

给定一个二叉搜索树，编写一个函数kthSmallest来查找其中第k个最小的元素

实例：

输入: root = [3,1,4,null,2], k = 13/ \1   4\2
输出: 1

输入: root = [5,3,6,2,4,null,null,1], k = 35/ \3   6/ \2   4/1
输出: 3

# 递归
class Solution:def kthSmallest(self, root, k):res = Nonedef helper(root):# nonlocal关键字用来在函数或其他作用域中使用外层（非全局）变量nonlocal k, resif root.left: helper(root.left)k -= 1if k == 0:res = root.valreturn if root.right: helper(root.right)helper(root)return res
# 迭代
class Solution:def kthSmallest(self, root, k):cur = rootstack = []while cur or stack:while cur:stack.append(cur)cur = cur.lefttmp = stack.pop()k -= 1if k == 0:return tmp.valif tmp.right:cur = tmp.rightcount_b = 1continuecount_a -= 1count_b -= 1count_a, count_b = 0, 0for j in nums:if j == a:count_a += 1elif j == b:count_b += 1if count_a > len(nums) / 3:res.append(a)if count_b > len(nums) / 3:res.append(b)return res

这篇关于一天一道Leetcode(190-230)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---