LeetCode 2020-04月 每日一题

4月1日:有效括号的嵌套深度

难度中等

题目描述

有效括号字符串 仅由 "("")" 构成,并符合下述几个条件之一:

  • 空字符串
  • 连接,可以记作 ABAB 连接),其中 AB 都是有效括号字符串
  • 嵌套,可以记作 (A),其中 A 是有效括号字符串

类似地,我们可以定义任意有效括号字符串 s嵌套深度 depth(S)

  • s 为空时,depth("") = 0
  • sAB 连接时,depth(A + B) = max(depth(A), depth(B)),其中 AB 都是有效括号字符串
  • s 为嵌套情况,depth("(" + A + ")") = 1 + depth(A),其中 A 是有效括号字符串

例如:"""()()",和 "()(()())" 都是有效括号字符串,嵌套深度分别为 0,1,2,而 ")(""(()" 都不是有效括号字符串。

给你一个有效括号字符串 seq,将其分成两个不相交的子序列 AB,且 AB 满足有效括号字符串的定义(注意:A.length + B.length = seq.length)。

现在,你需要从中选出 任意 一组有效括号字符串 AB,使 max(depth(A), depth(B)) 的可能取值最小。

返回长度为 seq.length 答案数组 answer ,选择 A 还是 B 的编码规则是:如果 seq[i]A 的一部分,那么 answer[i] = 0。否则,answer[i] = 1。即便有多个满足要求的答案存在,你也只需返回 一个

示例 1:

示例 2:

题目链接

https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/

思路:

  4月难度加大了❓❓
  因为要使max(depth(A), depth(B))最小,所以让AB的深度越接近越好。假设S的深度为n,那么A的深度就为(n+1)//2
  深度优先搜索,S中的字符要么给A用,要么给B用,(总共C_n^{(n+1)//2}种可能性,复杂度较高)。需要用以下几个条件剪枝:
  ① A和B当前的左括号数-右括号数必须大于0。
  ② A和B当前的左括号数-右括号数必须小于等于(n+1)//2
  ③ 因为只要找到一种可能性就行了,因此采取贪心算法,让A的左括号尽量多(也就是深度尽量大)。

代码:

4月2日:生命游戏

难度中等

题目描述

根据 百度百科 ,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态:1 即为活细胞(live),或 0 即为死细胞(dead)。每个细胞与其八个相邻位置(水平,垂直,对角线)的细胞都遵循以下四条生存定律:

  1. 如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡;
  2. 如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活;
  3. 如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡;
  4. 如果死细胞周围正好有三个活细胞,则该位置死细胞复活;

根据当前状态,写一个函数来计算面板上所有细胞的下一个(一次更新后的)状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的,其中细胞的出生和死亡是同时发生的。

示例:

进阶:

  • 你可以使用原地算法解决本题吗?请注意,面板上所有格子需要同时被更新:你不能先更新某些格子,然后使用它们的更新后的值再更新其他格子。
  • 本题中,我们使用二维数组来表示面板。原则上,面板是无限的,但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题?

题目链接

https://leetcode-cn.com/problems/game-of-life/

思路:

  原地算法:扫描每个位置的周围八个格子,用2表示即将死亡的活细胞,用-1表示即将复活的死细胞。根据正负判断细胞之前是活的还是死的。然后再扫描一次,将2替换成0,-1替换成1即可。

代码:

4月3日:字符串转换整数 (atoi)

难度中等

题目描述

请你来实现一个 atoi 函数,使其能将字符串转换成整数。

首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下:

  • 如果第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字字符组合起来,形成一个有符号整数。
  • 假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成一个整数。
  • 该字符串在有效的整数部分之后也可能会存在多余的字符,那么这些字符可以被忽略,它们对函数不应该造成影响。

注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换,即无法进行有效转换。

在任何情况下,若函数不能进行有效的转换时,请返回 0 。

提示:

  • 本题中的空白字符只包括空格字符 ' '
  • 假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

题目链接

https://leetcode-cn.com/problems/string-to-integer-atoi/

思路:

  Python处理这种整数越界的问题就很烦。

代码:

4月4日:接雨水

难度 困难

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。

示例:

题目链接

https://leetcode-cn.com/problems/trapping-rain-water/

思路:

  先遍历一遍height,分别找到每个高度h左侧最高点右侧最高点,如果min(左侧最高点右侧最高点) > h,则可以接雨水。将每个h接的雨水数累加。   

代码:

4月5日:LFU缓存

难度困难

题目描述

设计并实现最不经常使用(LFU)缓存的数据结构。它应该支持以下操作:getput

get(key) – 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。 put(key, value) – 如果键不存在,请设置或插入值。当缓存达到其容量时,它应该在插入新项目之前,使最不经常使用的项目无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,最近最少使用的键将被去除。

进阶: 你是否可以在 O(1) 时间复杂度内执行两项操作?

示例:

题目链接

https://leetcode-cn.com/problems/lfu-cache/

思路:

  首先要理解LFU的缓存机制:
  ① LFU缓存就是在缓存容量满时,将访问次数最少key-value删除掉。
  ② get操作put操作都会访问key,使key的访问次数+1
  ③ 如果多个内容访问次数相同,则删除最先访问的(也就是最久没访问的)。
  用字典+二分法写了个效率很低的实现。

代码:

4月6日:编辑距离

难度 困难

题目描述

给定两个单词 word1word2 ,计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例 1:

示例 2:

题目链接

https://leetcode-cn.com/problems/edit-distance/

思路:

  动态规划,令dp[i][j]表示word1[:i]变成word2[:j]的最少操作数。

  先考虑为空时的情况,word1为空时,''变成word2[:j]需要加上j个个字符。同样,word2为空时,word1[:i]变成''需要减去i个字符。因此,dp[0][j]=jdp[i][0]=i

  考虑不为空的情况。如果两个字符串当前的末尾相同,即word1[i-1]==word2[j-1],那么dp[i][j]=dp[i-1][j-1]。如下如所示:

  如果两个字符串当前的末尾不同,那么有三种处理方式。即1. 删除word1末尾的元素,然后按dp[i-1][j]处理;2. 将word1末尾的元素替换成word2末尾的元素,然后按dp[i-1][j-1]处理;3. 在word1末尾添加word2末尾的元素,然后按dp[i][j-1]处理。如下图所示:

  最终dp[i][j]的值为这三种操作的操作次数中最少的。即dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1

代码:

4月7日:旋转矩阵

难度中等

题目描述

给你一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。

不占用额外内存空间能否做到?

示例 1:

示例 2:

题目链接

https://leetcode-cn.com/problems/rotate-matrix-lcci/

思路:

  其实就是48. 旋转图像换了个标题,这也太不走心了。。(我也不走心地抄一下那题的题解)
  

  扣四个边界出来。四个边界对应的点交换。每遍历一层,就往里缩一个矩阵。

代码:

4月8日:机器人的运动范围

难度中等

题目描述

地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

示例 1:

示例 1:

提示:

  • 1 <= n,m <= 100
  • 0 <= k <= 20

题目链接

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

思路:

  dfs,当数位和大于k时返回。
  

代码:

4月9日:括号生成

难度中等

题目描述

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

题目链接

https://leetcode-cn.com/problems/generate-parentheses/

思路:

  dfs。在搜索的过程中注意满足以下两个条件:

  ① 当前右括号的数量不能大于左括号的数量;

  ② 当前左括号的数量不能大于n

代码:

4月10日:翻转字符串里的单词

难度中等

题目描述

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

示例 1:

示例 2:

示例 3:

说明:

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

    进阶:

    请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

题目链接

https://leetcode-cn.com/problems/reverse-words-in-a-string/

思路:

  遇到这种题当然是愉快地调库啦。

代码:

4月11日:鸡蛋掉落

难度困难

题目描述

你将获得 K 个鸡蛋,并可以使用一栋从 1N 共有 N 层楼的建筑。

每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。

你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?

示例 1:

示例 2:

示例 3:

提示:

  1. 1 <= K <= 100
  2. 1 <= N <= 10000

题目链接

https://leetcode-cn.com/problems/super-egg-drop/

思路:

  由于鸡蛋的数量有限,碎了的鸡蛋就不能再用了,因此使用动态规划求解。
  如果只有一个鸡蛋🥚,那就只能从第一层开始一层一层试,哪一层会碎就找到了F,总共需要N次。如果有无限多的鸡蛋,用二分法即可。
  方法一:朴素遍历。考虑在第i层扔鸡蛋,扔下去的结果两种,碎、不碎。
  如果碎了,说明F0~i-1之间,还需要在0~i-1i-1层楼中搜索;
  如果没有碎,说明Fi~N之间,还需要再i+1~N层即N-i层楼中搜索。
  记dp[N][K]表示有k个鸡蛋,N层楼中确定F的具体值的最小搜索次数。那么,假设某次搜索在第i楼,根据上面的思路,在第i楼扔下,存在两种结果:碎、不碎。然后根据结果分别在i楼上面或者下面的搜索区间继续搜索F的值。
  因此可以得到递推公式dp[N][K] =min{ max(dp[i-1][K-1], dp[N-i][K]) + 1 | 1<=i<=N }
  显然,k>=1,而i为0时,表示没有任何楼层,那么dp[0][k]=0
  当k=1,只有一个鸡蛋,只能线性搜索,dp[N][K] = N。

  方法二:二分法。方法一中的i是在1~N之间逐层去试,复杂度较高。如果i第一次取N/2,然后每次用二分法向消耗鸡蛋多的半边靠近,可以减少复杂度。

  方法三:换一种dp思路。
  ① 无论你在哪层楼扔鸡蛋,鸡蛋只可能摔碎或者没摔碎,碎了的话就测楼下,没碎的话就测楼上。
  ② 无论你上楼还是下楼,总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1(当前这层楼)。
  根据这个特点,可以写出下面的状态转移方程:
  dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1
  dp[k][m - 1] 就是楼上的楼层数,因为鸡蛋个数k不变,也就是鸡蛋没碎,扔鸡蛋次数m减一;
  dp[k - 1][m - 1] 就是楼下的楼层数,因为鸡蛋个数k减一,也就是鸡蛋碎了,同时扔鸡蛋次数m减一。

代码:

  方法一:(朴素遍历,超时)

  方法二:(二分,1944ms)

  方法三:(换一种角度,172ms)

  • 4月12日:交点

    难度困难

    题目描述

    给定两条线段(表示为起点start = {X1, Y1}和终点end = {X2, Y2}),如果它们有交点,请计算其交点,没有交点则返回空值。

    要求浮点型误差不超过10^-6。若有多个交点(线段重叠)则返回 X 值最小的点,X 坐标相同则返回 Y 值最小的点。

    示例 1:

    示例 2:

    示例 3:

    提示:

    • 坐标绝对值不会超过 2^7
    • 输入的坐标均是有效的二维坐标

    题目链接

    https://leetcode-cn.com/problems/intersection-lcci/

    思路:

  写的头皮发麻。。
  ① 两直线斜率都不存在,单独考虑是否相交;
  ② 考虑某一条直线斜率不存在;
  ③ 考虑两直线平行,是否有重合部分;
  ④ 两直线不平行,是否相交。
  斜率公式:
\displaystyle k_1 = \frac{y_1'-y_1}{x_1'-x_1}, b_1 = y_1 - k_1x_1   (代码中x_表示x’)

代码:

4月13日:设计推特

难度中等

题目描述

设计一个简化版的推特(Twitter),可以让用户实现发送推文,关注/取消关注其他用户,能够看见关注人(包括自己)的最近十条推文。你的设计需要支持以下的几个功能:

  1. postTweet(userId, tweetId): 创建一条新的推文
  2. getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
  3. follow(followerId, followeeId): 关注一个用户
  4. unfollow(followerId, followeeId): 取消关注一个用户

示例:

题目链接

https://leetcode-cn.com/problems/design-twitter/

思路:

  获取所有关注的人的前10条twitter,然后按时间排序后取前10条。

代码:

4月14日:两数相加 II

难度中等

题目描述

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。 进阶:

如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。

示例:

题目链接

https://leetcode-cn.com/problems/add-two-numbers-ii/

思路:

  翻转l1l2,相加后再翻转回来。

  如果不能翻转,可以用栈来做,将两个链表对应元素的和入栈,到两个链表都结尾时再出栈并且加上进位。

代码:

4月15日:01 矩阵

难度中等

题目描述

给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:

输入:

输出:

示例 2:

输入:

输出:

题目链接

https://leetcode-cn.com/problems/01-matrix/

思路:

  方法一:bfs。将所有的"0"看做一个整体,向其他数字的位置腐蚀(将它们变成0),当格子上所有数字都为"0"时结束循环。记录循环的深度就是结果。

  方法二:动态规划,因为最近的"0"要么在左上方,要么在右下方。因此只要分别从左上角到右下角从右下角到左上角动态规划一次,就得到了最终的结果。

  其中从左上到右下的状态转移方程为dp[i][j] = min(dp[i][j], dp[i-1][j] + 1, dp[i][j-1] + 1)

代码:

  方法一:(bfs)

  方法二:(dp)

4月16日:合并区间

难度中等

题目描述

给出一个区间的集合,请合并所有重叠的区间。

示例 1:

示例 2:

题目链接

https://leetcode-cn.com/problems/merge-intervals/

思路:

  先将intervals排序,令ans=[intervals[0]],取intervals中的每一个元素尝试与ans的最后一个元素合并。如果重合,则合并后放回ans[-1];如果不重合,则appendans的最后。

代码:

4月17日:跳跃游戏

难度 中等

题目描述

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

示例 2:

题目链接

https://leetcode-cn.com/problems/jump-game/

思路:

  方法一:贪心算法。与A45. 跳跃游戏II类似,每次都跳到最划算的位置。
  方法二:从右往左遍历,如果某个位置能走到最后则截断后面的元素。如果某个元素为0则从前面找能走到它后面的。方法二比方法一用时短一些。

代码:

  方法一:

  方法二:

4月18日:盛最多水的容器

难度 中等

题目描述

给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例:

题目链接

https://leetcode-cn.com/problems/container-with-most-water/

思路:

  方法一:用lefts记录heights从左到右所有比之前最高的还高的线,rights记录从右到左所有比之前最高的还高的线。遍历leftsrights,其中必有一种组合能够容纳最多的水。
  方法二:双指针,初始时设头指针和尾指针分别为ij。我们能够发现不管是左指针向右移动一位,还是右指针向左移动一位,容器的底都是一样的,都比原来减少了 1。这种情况下我们想要让指针移动后的容器面积增大,就要使移动后的容器的高尽量大,所以我们选择指针所指的高较小的那个指针进行移动,这样我们就保留了容器较高的那条边,放弃了较小的那条边,以获得有更高的边的机会。

代码:

  方法一:

  方法二:

4月19日:统计重复个数

难度困难

题目描述

由 n 个连接的字符串 s 组成字符串 S,记作 S = [s,n]。例如,["abc",3]=“abcabcabc”。

如果我们可以从 s2 中删除某些字符使其变为 s1,则称字符串 s1 可以从字符串 s2 获得。例如,根据定义,”abc” 可以从 “abdbec” 获得,但不能从 “acbbe” 获得。

现在给你两个非空字符串 s1 和 s2(每个最多 100 个字符长)和两个整数 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2,其中 S1=[s1,n1]S2=[s2,n2]

请你找出一个可以满足使[S2,M]S1 获得的最大整数 M 。

示例:

题目链接

https://leetcode-cn.com/problems/count-the-repetitions/

思路:

  找循环节,将中间循环的部分、开头的部分和结尾的部分分别考虑,开头的as1包含bs2,中间每ms1包含ns2,最后还剩xs1包含ys2

  则S1总共包含b + (n1-a-x)//m*n + ys2S1包含anss2,那么就包含ans // n2S2

代码:

4月20日:岛屿数量

难度中等

题目描述

给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

示例 2:

题目链接

https://leetcode-cn.com/problems/number-of-islands/

思路:

  经典dfs。遍历整个矩阵,从任意"1"的位置开始dfs,同时计数+1,搜索岛屿的过程中将搜索过的位置都置为"0"。最终计数的结果就是岛屿的数量。

代码:

4月21日:统计「优美子数组」

难度中等

题目描述

给你一个整数数组 nums 和一个整数 k

如果某个 连续 子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 1:

示例 2:

示例 3:

提示:

  • 1 <= nums.length <= 50000
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= nums.length

题目链接

https://leetcode-cn.com/problems/count-number-of-nice-subarrays/

思路:

  方法一:双指针。维护一个滑动窗口,记录其中的奇数个数,如果奇数个数大于k,则左指针向右移。
  方法二:这道题的本质是统计所有相隔为(k-1)的奇数的左右偶数的乘积的和。用一个字典mem记录第i个奇数的左边的偶数个数+1。利用第i个奇数右边的偶数=第i+1个奇数左边的偶数这个性质,只要计算所有mem[temp] * mem[temp-k]的和即可。

  为了便于理解,以nums = [2,2,2,1,2,2,1,2,2,2]为例,nums中共有2个奇数。

代码:

  方法一:

  方法二:

4月22日:二叉树的右视图

难度中等

题目描述

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

示例:

题目链接

https://leetcode-cn.com/problems/binary-tree-right-side-view/

思路:

  使用层序遍历,并只保留每层最后一个节点的值。

代码:

4月23日:硬币

难度中等

题目描述

硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007)

示例1:

示例2:

说明:

注意:

你可以假设:

  • 0 <= n (总金额) <= 1000000

题目链接

https://leetcode-cn.com/problems/coin-lcci/

思路:

  动态规划。先计算最大硬币为1的种类数,再依次计算最大硬币为51025的种类数。

代码:

4月24日:数组中的逆序对

难度困难

题目描述

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例 1:

限制:

题目链接

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

思路:

  方法一:二分法,维护一个升序数组asc,存放已有的数字。由于后放进去的数字下标大,找到asc中比它大的数有几个即可。

  方法二:归并排序,先分别计算左右半边有多少逆序对,然后计算一个数在左边,一个数在右边的逆序对的个数。

代码:

  方法一:(二分法,2020ms)

  方法二:(归并排序,1464 ms)

4月25日:全排列

难度中等

题目描述

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:

题目链接

https://leetcode-cn.com/problems/permutations/

思路:

  dfs。

代码:

4月26日:合并K个排序链表

难度困难

题目描述

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

题目链接

https://leetcode-cn.com/problems/merge-k-sorted-lists/

思路:

  分治法,当只有一个链表时直接返回。否则:

  ① 合并左半边的链表,记为left

  ② 合并右半边的链表,记为right

  ③ 合并leftright(参考合并两个有序链表)。

  时间复杂度O(nlog(k))n是所有链表中元素的总和,k是链表个数。

代码:

4月27日:搜索旋转排序数组

难度 中等

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

示例 2:

题目链接

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

思路:

  nums从中间切一半,必然有一半是有序的,另一半是无序的,对有序的一半二分查找,对无序的一半递归调用该算法。
  如果第一个数nums[i] 小于中间的数nums[mid],则左半边有序,否则右半边有序。

代码:

4月28日:数组中数字出现的次数

难度中等

题目描述

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

示例 1:

示例 2:

限制:

  • 2 <= nums <= 10000

题目链接

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

思路:

  数组里面所有数异或 =目标两个数异或 。由于这两个数不同,所以异或结果必然不为0。

  假设数组异或的二进制结果为10010,那么说明这两个数从右向左数第2位是不同的。

  那么可以根据数组里面所有数的第二位为0或者1将数组划分为2个子数组。

  这样做可以将目标数必然分散在不同的数组中,而且相同的数必然落在同一个数组中。

  这两个数组里面的数各自进行异或,得到的结果就是答案。

代码:

4月29日:山脉数组中查找目标值

难度困难

题目描述

(这是一个 交互式问题

给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。

如果不存在这样的下标 index,就请返回 -1。 何为山脉数组?如果数组 A 是一个山脉数组的话,那它满足如下条件:

首先A.length >= 3

其次,在 0 < i < A.length - 1 条件下,存在 i 使得:

  • A[0] < A[1] < ... A[i-1] < A[i]
  • A[i] > A[i+1] > ... > A[A.length - 1] 你将 不能直接访问该山脉数组,必须通过 MountainArray 接口来获取数据:
  • MountainArray.get(k) – 会返回数组中索引为k 的元素(下标从 0 开始)
  • MountainArray.length() – 会返回该数组的长度 注意:

MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外,任何试图规避判题系统的解决方案都将会导致比赛资格被取消。

为了帮助大家更好地理解交互式问题,我们准备了一个样例 “答案”:https://leetcode-cn.com/playground/RKhe3ave,请注意这 不是一个正确答案

示例 1:

示例 2:

提示:

  • 3 <= mountain_arr.length() <= 10000
  • 0 <= target <= 10^9
  • 0 <= mountain_arr.get(index) <= 10^9

题目链接

https://leetcode-cn.com/problems/find-in-mountain-array/

思路:

  先根据mountain[i]mountaion[i-1]的大小关系,找到山脉⛰数组的顶峰。然后分别在左半边和右半边二分查找。

代码:

4月30日:快乐数

难度简单

题目描述

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

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

如果 n 是快乐数就返回 True ;不是,则返回 False

示例:

题目链接

https://leetcode-cn.com/problems/happy-number/

思路:

  用集合判断下一个数字是否已经出现过了。

代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注