Leetcode重点250题思路(Part 5)

本文的选题依据来自 https://cspiration.com/leetcodeClassification 中的划分,下面的序号以 Leetcode 英文版为准

⭐51.N-Queens

lb17fH.png
lb3Fcn.png

  • 经典的 N 皇后问题,它可以通过回溯法解决,本题主要注意的点是验证冲突,所以我在 valid 中写了三个方向(上方,左上,右上)的校验,然后就是对数据进行遍历,注意加入数据后进行痕迹消除

52.N-Queens II

lb8nqP.png
lbGYfe.png

  • 对 N 皇后问题的解法进行统计,直接对上题中的结果进行统计即可

⭐53.Maximum Subarray

lbJM9g.png
lbJU4U.png

  • 最大子序列问题是典型的 DP 问题,将 dp 数组填满即可,对于 dp[i-1]小于 0 的情况,说明前面的子序列之和小于 0,所以进行舍弃;否则就用当前数值加上之前子序列之和

54.Spiral Matrix

lbYddP.png
lbtGkV.png

  • 没有太多技巧,每个方向判断

55.Jump Game

lbNvxe.png
lbU8RU.png

  • 该题主要是理解 i 和 max 的意思,i 代表当前所在下标,而 max 代表之前的点能到达的最远位置,如果 i>max 就代表,当前坐标已经大于之前能到达的最远距离了,所以返回 false,否则更新 max 值

56.Merge Intervals

lb0ZYq.png
lb010J.png

  • 使用扫描线算法先对数组进行排序,排序规则是 start 小的在前,之后就是顺序比较两个相邻元素的大小,取 start 的最小和 end 的最大值

57.Insert Interval

lb0vB4.png
lbBlgf.png

  • 同样使用扫描线算法进行合并

58.Length of Last Word

lbrZtA.png
lbr9l6.png

  • 没什么好说的

59.Spiral Matrix II

lbrU10.png
lbr6hR.png

  • 没有太多技巧,每个方向判断

⭐60.Permutation Sequence

lbr74A.png
lqpfYD.png

  • 该题主要是要理解全排列的组合方式,以 1234 为例,它总共有 4!=24 种排列。当第一位决定后,第二位共有 3!=6 种排列;当第二位决定后,第三位共有 2!=2 种排列;当第三位决定后,第四位只有 1 种选择了,以 n=4,k=17 为例,最高位可以取 1234 中的一个,每个数字出现 3!次(因为当最高位决定了,后面三位可以任意排列,所以最高位会出现 3!次),当 k=16(为编程方便,程序以 0 为开始),第一位的下标是 16/6=2,因为每个可以出现 6 次,那么除以 6 之后自然能够得出当前应该出现的数字下标是几,此时下标为 2 的数字 3 被选出。此时 3 被删除,只剩下 124
  • 从 124 中取一个,k=16,在此轮中的 k=16%(3!)=4,这里取余是因为这个位置是第三组(k/6=2)的第五个(k%6=4)数字,剩下的处理和上面一样,每个数字出现的 2!=2 次,第二数字的下标为 4/2=2,故 4 被取出,并被移除
  • 从 12 中取一个,k=4,在此论中的 k=4%(2!)=0,而剩下数字出现 1!=1 次,所以第三个数字下标为 0/1=0,在 12 中就是 1 被取出,只剩下 2,故结果是 3412