I、498. 对角线遍历（蛇形） 一、题目描述 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。 示例: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,4,7,5,3,6,8,9] 解释: 说明: 给定矩阵中的元素总数不会超过 100000 。 二、解题思路 & 代码 2.1 对角线迭代和翻转 算法 初始化数组 result，用于存储最后结果。 使用一个外层循环遍历所有的对角线。第一行和最后一列的元素都是...

一、题目描述 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。 示例 1: 输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL 示例 2: 输入: 2->1->3->5->6->4->7->NULL 输出: 2->3-&gt...

一、题目描述 给定一棵二叉搜索树，请找出其中第k大的节点。 示例 1: 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 4 示例 2: 输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 4 限制： 1 ≤ k ≤ 二叉搜索树元素个数 二、解题思路 & 代码 解法基于此性质：二叉搜索树的中序遍历为 递增序列 。 根据以上性质，易得二...

一、题目描述 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。 示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: True 解释: 你可以删除c字符。 注意: 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。 二、解题思路 & 代码 双指针 + 贪心算法 class Solution: def validPalindrome(self, s: str) -> bool: def checkPalindrome...

目录 1. 赛马次数 2. 用绳子计时 15 分钟 3. 九球称重 4. 药丸称重 5. 得到 4 升的水 6. 扔鸡蛋 7. 砝码秤盐 8. 拿到最后一本书（腾讯） 9. 裁绳子 2 刀形成三角形的概率 10. 抛硬币，先抛到正面获胜 11. 1-100的灯最后关的灯的编号 12. n个人中至少有两个人生日相同的概率 13. 怎样估算上海市理发师的数量？ 14. 一个孩子是女孩的情况下...

一、题目描述 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a plan, a canal: Panama" 输出: true 示例 2: 输入: "race a car" 输出: false 二、解题思路 & 代码 2.1 直接取反比较 class Solution: def isPalindrome(self, s: str) -> bool: s_list= [ch.lo...

一、题目描述 给定一个仅包含大小写字母和空格 ’ ’ 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。 如果不存在最后一个单词，请返回 0 。 说明：一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。 示例: 输入: "Hello World" 输出: 5 二、解题思路 & 代码 由于要获取最后一个单词的长度，需要从尾开始遍历。 但是结尾处还可能有空格 所以一般的解题思路为，先去掉末尾的空格，然后从尾向前开始遍历，直到遇到第一个空格处结束。 但这里可以取一个巧，我们可以通过...

42. 接雨水（二维） 一、题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例: 输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6 二、解题思路 & 代码 2.1 按列求 求每一列的水，我们只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。 装水的多少，当然根据木桶效应，我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。 ...

dic1 = { 'a':1, 'b':2, 'c':3} # keys = list(dic1) keys = dic1.keys() keys.remove('b') print(keys) 报错 AttributeError: 'dict_keys' object has no attribute 'remove' 改为如下即可： dic1 = { 'a':1, 'b':2, 'c':3} keys = list(dic1) # keys = dic1.keys() keys.remove('b') print(keys) 输出： ['a', 'c']

# Dijkstra算法——通过边实现松弛 # 指定一个点到其他各顶点的路径——单源最短路径 # 每次找到离源点最近的一个顶点，然后以该顶点为重心进行扩展 # 最终的到源点到其余所有点的最短路径 # 一种贪婪算法 def Dijkstra(G, v0, INF = float('inf')): """ 使用 Dijkstra 算法计算指定点 v0 到图 G 中任意点的最短路径的距离 INF 为设定的无限远距离值 此方法不能解决负权值边的图 """ book = set() minv = v0 # ...

209. 长度最小的子数组 一、题目描述 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。 示例： 输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。 进阶： 如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。 二、解题思路 & 代码 2.1 方法一：暴力法（Python 超时） 暴力法是最直观的方法。初始化子数组的最小长度为无穷...

一、题目描述 一个环，有n个点（编号 0 ~ n-1 ）, 问从0点出发，经过k步回到原点（0点）有多少种方法 ? 二、解题思路 & 代码 再回到 0 点可以从右面回来，也可以从左面回来，即先到达旁边的一个点，看看有多少回来的方法即可。所以运用动态规划的思想，我们可以写出递推式如下： d p ( k , j ) = d p ( k − 1 , j − 1 ) + d p ( k − 1 , j + 1 ) dp(k, j) = dp(k-1, j-1) + dp(k-1, j+1) dp(k,j)=dp(k−1,j−1)+dp(k−1,j+1) d p ( k , j ...

一、题目描述 有 1000 只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，它会在 15 分钟内死去。 问题来了，如果需要你在一小时内，弄清楚哪只水桶含有毒药，你最少需要多少只猪？ 回答这个问题，并为下列的进阶问题编写一个通用算法。 进阶: 假设有 n 只水桶，猪饮水中毒后会在 m 分钟内死亡，你需要多少猪（x）就能在 p 分钟内找出 “有毒” 水桶？这 n 只水桶里有且仅有一只有毒的桶。 提示： 1. 可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。 2. 小猪喝完水后，必须有 m 分钟的冷却时间。在这段时间里，只允...

一、题目描述 有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。 剩下的乘客将会： 如果他们自己的座位还空着，就坐到自己的座位上， 当他们自己的座位被占用时，随机选择其他座位 第 n 位乘客坐在自己的座位上的概率是多少？ 示例 1： 输入：n = 1 输出：1.00000 解释：第一个人只会坐在自己的位置上。 示例 2： 输入: n = 2 输出: 0.50000 解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。 提示： 1 <= n <= 10^5 二、解题思路 & ...