xiaolei565

面试题03. 数组中重复的数字(简单)找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1：输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3 限制：2 <= n <= 100000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof 思路：直接用set进行接收就行，如果存在就输出，不存在就add。如果是排序的话，时间复杂度为O（nlogn），HashSet的话复杂度为O（n） 思路2：从题目描述中我们可以看出，因为所有数字都在 0 ～ n-1 的范围内，其实完全可以省掉额外的空间开辟，将每个位置的数交换映射到其对应的数组下标下面，当出现新的元素与其对应的下标中的数字相等时，即为重复数字时间复杂度：O(n)，空间复杂度：O(1) 作者：guanpengchn链接：http ...

计算机网络–TCP三次握手不管是前端，还是面各种后端，计算机网络的三次握手都是一个高频考点，常问的就是，介绍一下三次握手，然后很多情况下会加一个，为什么需要三次握手 我们先来考虑第二个问题 为什么需要三次握手TCP作为一种可靠传输控制协议，其核心思想：既要保证数据可靠传输，又要提高传输的效率。 下面的话来源于知乎上的一段高赞回答 在谢希仁《计算机网络》第四版中是这样讲”三次握手“的目的的：为了防止已经失效的连接请求报文段突然又传送到了服务端，因而产生错误”，这里只能算是表因，未涉及本质 根据TCP的协议RFC–RFC793：TCP需要seq序列号来做可靠重传或接受，为了避免连接复用时无法分辨出seq是延迟还是旧链接的seq，因此需要三次握手来确定双方的ISN（初始seq序列号） 下面是对RFC的解读： 我们首先需要知道一点就是，TCP的可靠连接是靠seq来达成的 A fundamental notion in the design is that every octet of data sent over a TCP connection has a sequence number ...

5417. 定长子串中元音的最大数目（一般）给你字符串 s 和整数 k 。 请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。 英文中的 元音字母 为（a, e, i, o, u）。 示例 1：输入：s = “abciiidef”, k = 3输出：3解释：子字符串 “iii” 包含 3 个元音字母。 示例 2：输入：s = “aeiou”, k = 2输出：2解释：任意长度为 2 的子字符串都包含 2 个元音字母。 示例 3：输入：s = “leetcode”, k = 3输出：2解释：”lee”、”eet” 和 “ode” 都包含 2 个元音字母。 示例 4：输入：s = “rhythms”, k = 4输出：0解释：字符串 s 中不含任何元音字母。 示例 5：输入：s = “tryhard”, k = 4输出：1 提示： 1 <= s.length <= 10^5s 由小写英文字母组成1 <= k <= s.length 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maxim ...

5416. 检查单词是否为句中其他单词的前缀（简单）给你一个字符串 sentence 作为句子并指定检索词为 searchWord ，其中句子由若干用 单个空格 分隔的单词组成。 请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。 如果 searchWord 是某一个单词的前缀，则返回句子 sentence 中该单词所对应的下标（下标从 1 开始）。 如果 searchWord 是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标）。 如果 searchWord 不是任何单词的前缀，则返回 -1 。字符串 S 的 「前缀」是 S 的任何前导连续子字符串。 示例 1：输入：sentence = “i love eating burger”, searchWord = “burg”输出：4解释：”burg” 是 “burger” 的前缀，而 “burger” 是句子中第 4 个单词。 示例 2：输入：sentence = “this problem is an easy problem”, searchWord = “pro”输出：2解释：”pr ...

1025. 除数博弈(一般)爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。 最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作： 选出任一 x，满足 0 < x < N 且 N % x == 0 。用 N - x 替换黑板上的数字 N 。如果玩家无法执行这些操作，就会输掉游戏。 只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。 示例 1： 输入：2输出：true解释：爱丽丝选择 1，鲍勃无法进行操作。示例 2： 输入：3输出：false解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。 提示： 1 <= N <= 1000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/divisor-game 思路1：博弈类的问题常常让我们摸不着头脑。当我们没有解题思路的时候，不妨试着写几项试试： N = 1 的时候，区间 (0, 1) 中没有整数是 n 的因数，所以此时 Alice 败。N = 2 的时候，Alice 只能拿 ...

946. 验证栈序列/面试题31. 栈的压入、弹出序列(简单)给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。 示例 1：输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出：true解释：我们可以按以下顺序执行：push(1), push(2), push(3), push(4), pop() -> 4,push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1 示例 2：输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]输出：false解释：1 不能在 2 之前弹出。 提示：0 <= pushed.length == popped.length <= 10000 <= pushed[i], popped[i] < 1000pushed 是 popp ...

876. 链表的中间结点(特别简单)亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。 游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。 亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。 假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。 示例：输入：[5,3,4,5]输出：true解释：亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。假设他取了前 5 颗，这一行就变成了 [3,4,5] 。如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。 提示： 2 <= piles.length <= 500piles.length 是偶数。1 <= pil ...

876. 链表的中间结点(特别简单)给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 示例 1：输入：[1,2,3,4,5]输出：此列表中的结点 3 (序列化形式：[3,4,5])返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了一个 ListNode 类型的对象 ans，这样：ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2：输入：[1,2,3,4,5,6]输出：此列表中的结点 4 (序列化形式：[4,5,6])由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。 提示： 给定链表的结点数介于 1 和 100 之间。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/middle-of-the-linked-list 思路：直接快慢指针就行，连奇数都不用特殊判断，由于条件中已经head非空，连 ...

739. 每日温度(一般)请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/daily-temperatures 思路：用一个栈来接收对应数比目标数小的下标节点 其他的看下面图 代码：1234567891011121314151617181920class Solution { public int[] dailyTemperatures(int[] T) { //先初始化一个等长数组，用来存输出的序列 i ...

704. 二分查找(简单)给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示例 1:输入: nums = [-1,0,3,5,9,12], target = 9输出: 4解释: 9 出现在 nums 中并且下标为 4 示例 2:输入: nums = [-1,0,3,5,9,12], target = 2输出: -1解释: 2 不存在 nums 中因此返回 -1 提示：你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-search 思路：思路就是最最正常的二分查找，没有任何改动 代码：12345678910111213141516class Solution { public int search(int[] nums, int targ ...