LeetCode 2020-03月 每日一题

3月1日:用队列实现栈

  使用队列实现栈的下列操作:
  
  push(x) — 元素 x 入栈
  pop() — 移除栈顶元素
  top() — 获取栈顶元素
  empty() — 返回栈是否为空

思路:
   见代码。。。

代码:

3月2日:反转链表

  反转一个单链表。
  
  示例:
  输入: 1->2->3->4->5->NULL
  输出: 5->4->3->2->1->NULL

思路:

  使用两个指针,一个在原链表中移动,另一个插入到新链表中。

代码: 递归的方法:

网友给的迭代的方法:

3月3日:合并排序的数组

  给定两个排序后的数组 A 和 B,其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法,将 B 合并入 A 并排序。
  
  初始化 A 和 B 的元素数量分别为 m 和 n。
  
  
  示例:
  输入:
  A = [1,2,3,0,0,0], m = 3
  B = [2,5,6], n = 3
  
  输出: [1,2,2,3,5,6]

思路:
  将B中的元素用insert插入到A中即可。注意A为空时可能会越界异常。

代码:

3月4日:腐烂的橘子🍊

  在给定的网格中,每个单元格可以有以下三个值之一:
  
  值 0 代表空单元格;
  值 1 代表新鲜橘子;
  值 2 代表腐烂的橘子。
  每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。
  
  返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1。
  
  示例 1:
  
  输入:[[2,1,1],[1,1,0],[0,1,1]]
  输出:4
  
  示例 2:
  输入:[[2,1,1],[0,1,1],[1,0,1]]
  输出:-1
  解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。
  
  示例 3:
  输入:[[0,2]]
  输出:0
  解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。

思路:
  BFS,维护一个(滚动的)列表rottings,记录每一轮新腐烂的橘子。
  每一轮中,rottings中的所有橘子🍊,都会尝试腐烂周围的橘子。如果某一轮不能腐烂新的橘子,则结束循环。
  结束循环后,如果还有未腐烂的橘子,则返回-1,否则返回轮数ans。   

代码:

3月5日:分糖果II

  排排坐,分糖果。
  
  我们买了一些糖果 candies,打算把它们分给排好队的 n = num_people 个小朋友。
  
  给第一个小朋友 1 颗糖果,第二个小朋友 2 颗,依此类推,直到给最后一个小朋友 n 颗糖果。
  
  然后,我们再回到队伍的起点,给第一个小朋友 n + 1 颗糖果,第二个小朋友 n + 2 颗,依此类推,直到给最后一个小朋友 2 * n 颗糖果。
  
  重复上述过程(每次都比上一次多给出一颗糖果,当到达队伍终点后再次从队伍起点开始),直到我们分完所有的糖果。注意,就算我们手中的剩下糖果数不够(不比前一次发出的糖果多),这些糖果也会全部发给当前的小朋友。
  
  返回一个长度为 num_people、元素之和为 candies 的数组,以表示糖果的最终分发情况(即 ans[i] 表示第 i 个小朋友分到的糖果数)。
  
  示例 1:
  输入:candies = 7, num_people = 4
  输出:[1,2,3,1]
  解释:
  第一次,ans[0] += 1,数组变为 [1,0,0,0]。
  第二次,ans1 += 2,数组变为 [1,2,0,0]。
  第三次,ans[2] += 3,数组变为 [1,2,3,0]。
  第四次,ans[3] += 1(因为此时只剩下 1 颗糖果),最终数组变为 [1,2,3,1]。
  
  示例 2:
  输入:candies = 10, num_people = 3
  输出:[5,2,3]
  解释:
  第一次,ans[0] += 1,数组变为 [1,0,0]。
  第二次,ans1 += 2,数组变为 [1,2,0]。
  第三次,ans[2] += 3,数组变为 [1,2,3]。
  第四次,ans[0] += 4,最终数组变为 [5,2,3]。

思路:
  i表示第几个小朋友,j表示分几颗糖果。
   代码:

3月6日:和为s的连续正数序列

  输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。
  
  序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
  
  示例 1:
  输入:target = 9
  输出:[[2,3,4],[4,5]]
  
  示例 2:
  输入:target = 15
  输出:[[1,2,3,4,5],[4,5,6],[7,8]]

思路:
  等差数列的和,target=平均值 × 序列长度length
  序列长度一定为target × 2的因子并且大于1,遍历target × 2的因子寻找序列长度即可。
  序列越长的首个数字越小。

代码:

3月7日:队列的最大值

  请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
  
  若队列为空,pop_front 和 max_value 需要返回 -1
  
  
  示例 1:
  输入:
  [“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
  [[],1,[2],[],[],[]]
  输出: [null,null,null,2,1,2]
  
  示例 2:
  输入:
  [“MaxQueue”,”pop_front”,”max_value”]
  [[],[],[]]
  输出: [null,-1,-1]

思路:
  维护一个主队列q和一个辅助队列helper。主队列就是正常的队列,负责pushpop;辅助队列helper是一个双端队列
  push_back操作时,如果新的value大于helper队尾的元素,则一直弹出helper队尾的元素。之后再将value加到helper队尾。
  pop_front操作时,如果q的对头元素value等于helper的对头元素,则弹出helper对头的元素。
  max_value操作时,如果辅助队列不为空,则返回辅助队列对头的元素。

例如:[3, 1, 2, 4]

  初始,q=[], helper=[]
  入队列,q=[3], helper=[3];
  入队列,q=[3, 1], helper=[3, 1];
  入队列,q=[3, 1, 2], helper=[3, 2];
  入队列,q=[3, 1, 2, 4], helper=[4];
  出队列,q=[1, 2, 4], helper=[4];
  出队列,q=[2, 4], helper=[4];
  出队列,q=[4], helper=[4];
  出队列,q=[], helper=[];

代码:

3月8日:零钱兑换

  给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
  
  示例 1:
  输入: coins = [1, 2, 5], amount = 11
  输出: 3
  解释: 11 = 5 + 5 + 1
  
  示例 2:
  输入: coins = [2], amount = 3
  输出: -1

思路:
  背包🎒问题。
  1. 如果已知所有amount - coin所需的最少硬币个数,那么amount所需的最少硬币个数为 min(coinChange(amount - coin_i) + 1),coin_i∈coins。
  2. coinChange[0] = 0

代码:

3月9日:买卖股票的最佳时机

  给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
  
  如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
  
  注意你不能在买入股票前卖出股票。
  
  
  示例 1:
  输入: [7,1,5,3,6,4]
  输出: 5
  解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
   注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
  
  示例 2:
  输入: [7,6,4,3,1]
  输出: 0
  解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

思路:
  今天国际原油跌了近30%,美股熔断,这道题来的真是时候啊❄️。。。
  使用双指针,i表示买入时的下标,j表示卖出时的下标,ans存放全局利润最大值。如果卖出价格<=买入价格,则将买入价格更新为卖出价格。否则j不断向后移,如果prices[j]-prices[i]大于ans,则更新全局的ans

代码:

3月10日:二叉树的直径

  给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
  
  
  示例 :

  返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

思路:
  有点像第21场双周赛的第4题,不过稍微简单一点。。
  dfs。遍历时计算每个结点向左走的路径最大值向右走的路径最大值,以及直径
  其中 向左走的路径最大值 = max(左孩子向左走的路径最大值,左孩子向右走的路径最大值) + 1。
  向右走的路径最大值 = max(右孩子向左走的路径最大值,右孩子向右走的路径最大值) + 1。
  直径 = max(左孩子的直径,右孩子的直径,向左走的路径最大值 + 向右走的路径最大值)。

代码:

3月11日:将数组分成和相等的三个部分

  给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。
  
  形式上,如果可以找出索引 i+1 < j 且满足 (A[0] + A1 + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] + A[j-1] + … + A[A.length – 1]) 就可以将数组三等分。
  
  
  示例 1:
  输出:[0,2,1,-6,6,-7,9,1,2,0,1]
  输出:true
  解释:0 + 2 + 1 = -6 + 6 – 7 + 9 + 1 = 2 + 0 + 1
  
  示例 2:
  输入:[0,2,1,-6,6,7,9,-1,2,0,1]
  输出:false
  
  示例 3:
  输入:[3,3,6,5,-2,2,5,1,-9,4]
  输出:true
  解释:3 + 3 = 6 = 5 – 2 + 2 + 5 + 1 – 9 + 4

思路:
  先计算sum(A),如果sum(A)不能被3整除,则直接返回False
  令ave = sum(A) // 3,也就是每一段的和都为ave
  遍历数组A并求累计和,如果累计和为avecount += 1
  当count == 3时,说明已经有三段和为ave了,未使用的元素和须为0才返回True
  遍历结束后,当count == 3且没有多余数字时返回True

代码:

3月12日:字符串的最大公因子

  对于字符串 S 和 T,只有在 S = T + … + T(T 与自身连接 1 次或多次)时,我们才认定 “T 能除尽 S”。
  
  返回最长字符串 X,要求满足 X 能除尽 str1 且 X 能除尽 str2。
  
  
  示例 1:
  输入:str1 = “ABCABC”, str2 = “ABC”
  输出:”ABC”
  
  示例 2:
  输入:str1 = “ABABAB”, str2 = “ABAB”
  输出:”AB”
  
  示例 3:
  输入:str1 = “LEET”, str2 = “CODE”
  输出:””

思路:
  类似于辗转相减法,如果两字符串相同,则最大公因子为任何一个字符串
  假设str1长度大于str2,计算str1-str2,然后再递归gcdOfStrings(str1-str2, str2)。其中字符串相减定义为从开头减去,如果str1不以str2开头,则直接返回空字符串

代码:

3月13日:多数元素

  给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
  
  你可以假设数组是非空的,并且给定的数组总是存在多数元素。
  
  示例 1:
  输入: [3,2,3]
  输出: 3
  
  示例 2:
  输入: [2,2,1,1,1,2,2]
  输出: 2

思路:
  方法一:用一个字典(哈希表)记录每个数出现的次数,如果大于n//2则返回该数。
  方法二:网友给出的摩尔投票法:从第一个数开始count=1,遇到相同的就加1,遇到不同的就减1,减到0就重新换个数开始计数,总能找到最多的那个。
代码:
  方法一

  方法二

3月14日:最长上升子序列

  给定一个无序的整数数组,找到其中最长上升子序列的长度。
  
  示例:
  输入: [10,9,2,5,3,7,101,18]
  输出: 4
  解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
  说明:
  
  可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
  你算法的时间复杂度应该为 O(n2) 。
  进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

思路:
  方法一:用一个辅助数组orders记录以每个数为最大的数字时,最长上升子序列的长度。如示例中[10,9,2,5,3,7,101,18]对应的orders=[1,1,1,2,1,3,4,4]
  初始状态orders全为1,统计nums中某个数字之前所有比它小的数字的orders的最大值 + 1即为order[i]新的值。复杂度为O(n^2)
  方法二:维护一个升序的结果数组results。如果num大于结果数组中的所有元素,就将num插入到结果数组的最后。否则用num替换results中第一个大于等于num的数。
  最终results的长度即为结果。复杂度为O(nlogn)

代码:
  方法一:

  方法二:

3月15日:岛屿的最大面积

  给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
  
  找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为0。)
  
  
  示例 1:
  [[0,0,1,0,0,0,0,1,0,0,0,0,0],
   [0,0,0,0,0,0,0,1,1,1,0,0,0],
   [0,1,1,0,1,0,0,0,0,0,0,0,0],
   [0,1,0,0,1,1,0,0,1,0,1,0,0],
   [0,1,0,0,1,1,0,0,1,1,1,0,0],
   [0,0,0,0,0,0,0,0,0,0,1,0,0],
   [0,0,0,0,0,0,0,1,1,1,0,0,0],
   [0,0,0,0,0,0,0,1,1,0,0,0,0]]
  对于上面这个给定矩阵应返回 6。注意答案不应该是11,因为岛屿只能包含水平或垂直的四个方向的‘1’。
  
  
  示例 2:
  [[0,0,0,0,0,0,0,0]]
  对于上面这个给定的矩阵, 返回 0。

思路:
  经典dfs。遍历整个矩阵,从任意岛屿任意位置开始dfs,搜索过程中累计该岛屿的面积,并将该岛屿搜索过的位置都置为

代码:

3月16日:字符串压缩

  字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短,则返回原先的字符串。你可以假设字符串中只包含大小写英文字母(a至z)。
  
  
  示例1:
   输入:”aabcccccaaa”
   输出:”a2b1c5a3″
  
  示例2:
   输入:”abbccd”
   输出:”abbccd”
   解释:”abbccd”压缩后为”a1b2c2d1″,比原字符串长度更长。

思路:
  用now记录重复的字符,count记录重复的次数。如果当前字符不为now,则将now更新为当前字符,count则重新开始计数。

代码:

3月17日:拼写单词

  给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。
  
  假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。
  
  注意:每次拼写时,chars 中的每个字母都只能用一次。
  
  返回词汇表 words 中你掌握的所有单词的 长度之和。
  
  
  示例 1:
  输入:words = [“cat”,”bt”,”hat”,”tree”], chars = “atach”
  输出:6
  解释:
  可以形成字符串 “cat” 和 “hat”,所以答案是 3 + 3 = 6。
  
  示例 2:
  输入:words = [“hello”,”world”,”leetcode”], chars = “welldonehoneyr”
  输出:10
  解释:
  可以形成字符串 “hello” 和 “world”,所以答案是 5 + 5 = 10。

思路:
  用一个字典记录每个字母出现的次数,对于words中的一个单词,每使用一个字母该字母的剩余次数就减1,如果字母够用则能够拼写该单词。
代码:

3月18日:矩形重叠

  矩形以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。
  
  如果相交的面积为正,则称两矩形重叠。需要明确的是,只在角或边接触的两个矩形不构成重叠。
  
  给出两个矩形,判断它们是否重叠并返回结果。
  
  
  示例 1:
  输入:rec1 = [0,0,2,2], rec2 = [1,1,3,3]
  输出:true
  
  示例 2:
  输入:rec1 = [0,0,1,1], rec2 = [1,0,2,1]
  输出:false

思路:
  方法一:通过中心点计算,分别在xy方向上比较两个矩形中心的距离和它们的边长之和。(这种方法一般也用来判断两个圆是否重合)。
  方法二:卡死几种不相交的情况,其他都为True。

代码: 方法一:

方法二:

3月19日:最长回文串

  给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
  
  在构造过程中,请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
  
  注意:
  假设字符串的长度不会超过 1010。
  
  
  示例 1:
  输入:
  ”abccccdd”
  
  输出:
  7
  
  解释:
  我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。

思路:
  统计s中的字母,出现偶数次的全部使用,出现奇数次的少使用一次。最后还可以用一个出现奇数次的字母放在回文串的正中间。
代码:

  方法一:

  网友给出的一行代码的实现方法:

3月20日:最小的k个数

  输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
  
  示例 1:
  输入:arr = [3,2,1], k = 2
  输出:[1,2] 或者 [2,1]
  
  示例 2:
  输入:arr = [0,1,2,1], k = 1
  输出:[0]

思路:
  方法一:排序,时间复杂度O(nlogn)
  方法二:利用快速排序中的partition,由于每次partition后左边的数必小于右边的数,因此只需要对k所在的半边继续partition即可。时间复杂度<O(nlogn)
  方法三:构建最小堆,然后取前k个:时间复杂度O(n+klogn)
代码:
  方法一:

  方法二:

  方法三:

3月21日:水壶问题

  有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水?
  
  如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。
  
  你允许:
  
  装满任意一个水壶
  清空任意一个水壶
  从一个水壶向另外一个水壶倒水,直到装满或者倒空
  
  示例 1: (From the famous “Die Hard” example)
  输入: x = 3, y = 5, z = 4
  输出: True
  
  示例 2:
  输入: x = 2, y = 6, z = 5
  输出: False

思路:
  找到xy的最大公约数能否z被整除。另外要保证z <= x + y
代码:

3月22日:使数组唯一的最小增量

  给定整数数组 A,每次 move 操作将会选择任意 A[i],并将其递增 1。
  
  返回使 A 中的每个值都是唯一的最少操作次数。
  
  示例 1:
  输入:[1,2,2]
  输出:1
  解释:经过一次 move 操作,数组将变为 [1, 2, 3]。
  
  示例 2:
  输入:[3,2,1,2,1,7]
  输出:6
  解释:经过 6 次 move 操作,数组将变为 [3, 4, 1, 2, 5, 7]。
  可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。

思路:
  先将A排序,然后令cur=A[0]cur每次+1curA[i]的差即为A[i]所需要的增量。
  当A[i]大于cur时,说明A[i]不需要增量也不会重复了,令cur=A[i]
  例如A=[1,1,2,2,3,7]时:
  cur=[1,2,3,4,5,7], ans=(2-1)+(3-2)+(4-2)+(5-3)=6
  

代码:

3月23日:链表的中间结点

  给定一个带有头结点 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,我们返回第二个结点。

思路:
  先遍历一遍算出链表的长度,然后再重新从头取一半返回。
代码:

3月24日:按摩师

  一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。
  
  注意:本题相对原题稍作改动
  
  
  示例 1:
  输入: [1,2,3,1]
  输出: 4
  解释: 选择 1 号预约和 3 号预约,总时长 = 1 + 3 = 4。
  
  示例 2:
  输入: [2,7,9,3,1]
  输出: 12
  解释: 选择 1 号预约、 3 号预约和 5 号预约,总时长 = 2 + 9 + 1 = 12。
  
  示例 3:
  输入: [2,1,4,5,3,1,1,3]
  输出: 12
  解释: 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约,总时长 = 2 + 4 + 3 + 3 = 12。

思路:
  动态规划,dp[i]表示如果第i个做了,最大值是多少。因为第i个做了,要么第i-2个也做,要么第i-3个也做。因此有递推公式dp[i]=nums[i-1]+max(dp[i-2], dp[i-3])
代码:

3月25日:三维形体的表面积

  在 N * N 的网格上,我们放置一些 1 * 1 * 1  的立方体。
  
  每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。
  
  请你返回最终形体的表面积。
  
  示例 1:
  输入:[[2]]
  输出:10
  
  示例 2:
  输入:[[1,2],[3,4]]
  输出:34
  
  示例 3:
  输入:[[1,0],[0,2]]
  输出:16
  
  示例 4:
  输入:[[1,1,1],[1,0,1],[1,1,1]]
  输出:32
  
  示例 5:
  输入:[[2,2,2],[2,1,2],[2,2,2]]
  输出:46

思路:
  先不考虑左右相邻的情况,高度为h的正方体有4 * h+2个面。
  考虑两个相邻,矮的会和高的重叠,减少min_height * 2个面。
代码:

3月26日:车的可用捕获量

  在一个 8 x 8 的棋盘上,有一个白色车(rook)。也可能有空方块,白色的象(bishop)和黑色的卒(pawn)。它们分别以字符 “R”,“.”,“B” 和 “p” 给出。大写字符表示白棋,小写字符表示黑棋。
  
  车按国际象棋中的规则移动:它选择四个基本方向中的一个(北,东,西和南),然后朝那个方向移动,直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。另外,车不能与其他友方(白色)象进入同一个方格。
  
  返回车能够在一次移动中捕获到的卒的数量。
   
  
  示例 1:
  
  输入:[[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”R”,”.”,”.”,”.”,”p”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”]]
  输出:3
  解释:
  在本例中,车能够捕获所有的卒。
  
  示例 2:
  
  输入:[[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”p”,”p”,”p”,”p”,”p”,”.”,”.”],[“.”,”p”,”p”,”B”,”p”,”p”,”.”,”.”],[“.”,”p”,”B”,”R”,”B”,”p”,”.”,”.”],[“.”,”p”,”p”,”B”,”p”,”p”,”.”,”.”],[“.”,”p”,”p”,”p”,”p”,”p”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”]]
  输出:0
  解释:
  象阻止了车捕获任何卒。
  
  示例 3:
  
  输入:[[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“p”,”p”,”.”,”R”,”.”,”p”,”B”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”B”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”p”,”.”,”.”,”.”,”.”],[“.”,”.”,”.”,”.”,”.”,”.”,”.”,”.”]]
  输出:3
  解释:
  车可以捕获位置 b5,d6 和 f5 的卒。

思路:
  先找到车的位置,再上下左右各自移动判断就好了。

代码:

3月27日:卡牌分组

  给定一副牌,每张牌上都写着一个整数。
  
  此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组:
  
  每组都有 X 张牌。
  组内所有的牌上都写着相同的整数。
  仅当你可选的 X >= 2 时返回 true。
  
  
  示例 1:
  输入:[1,2,3,4,4,3,2,1]
  输出:true
  解释:可行的分组是 [1,1],[2,2],[3,3],[4,4]
  
  示例 2:
  输入:[1,1,1,2,2,2,3,3]
  输出:false
  解释:没有满足要求的分组。
  
  示例 3:
  输入:1
  输出:false
  解释:没有满足要求的分组。
  
  示例 4:
  输入:[1,1]
  输出:true
  解释:可行的分组是 [1,1]
  
  示例 5:
  输入:[1,1,2,2,2,2]
  输出:true
  解释:可行的分组是 [1,1],[2,2],[2,2]

思路:
  先计数,再求所有出现次数的最大公约数。
代码:

3月28日:单词的压缩编码

  给定一个单词列表,我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
  
  例如,如果这个列表是 [“time”, “me”, “bell”],我们就可以将其表示为 S = “time#bell#” 和 indexes = [0, 2, 5]。
  
  对于每一个索引,我们可以通过从字符串 S 中索引的位置开始读取字符串,直到 “#” 结束,来恢复我们之前的单词列表。
  
  那么成功对给定单词列表进行编码的最小字符串长度是多少呢?
  
  
  示例:
  输入: words = [“time”, “me”, “bell”]
  输出: 10
  说明: S = “time#bell#” , indexes = [0, 2, 5] 。

思路:
  其实意思就是计算有几个后缀不同的单词。暴力计算会超时。
  将每个字符串都倒序,然后排序,这样就只需要比较相邻的字符串即可。
代码:

3月29日:地图分析

  你现在手里有一份大小为 N x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地,你知道距离陆地区域最远的海洋区域是是哪一个吗?请返回该海洋区域到离它最近的陆地区域的距离。
  
  我们这里说的距离是『曼哈顿距离』( Manhattan Distance):(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 – x1| + |y0 – y1| 。
  
  如果我们的地图上只有陆地或者海洋,请返回 -1。
  
  
  示例 1:
  
  输入:[[1,0,1],[0,0,0],[1,0,1]]
  输出:2
  解释:
  海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大,最大距离为 2。
  
  示例 2:
  
  输入:[[1,0,0],[0,0,0],[0,0,0]]
  输出:4
  解释:
  海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大,最大距离为 4。

思路:
  跟腐烂的橘子🍊类似,就直接复制它的代码了。
代码:

3月30日:圆圈中最后剩下的数字(约瑟夫环)

  0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
  
  例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。
  
  
  示例 1:
  输入: n = 5, m = 3
  输出: 3
  
  示例 2:
  输入: n = 10, m = 17
  输出: 2
   
  限制:
  
  1 <= n <= 10^5
  1 <= m <= 10^6

思路:
  约瑟夫环。
  方法一:给每个数字一个标记代表它有没有被删除,每次都逐个遍历,当没有删除的数字累计到m时,就删除当前数字。由于题目数据量大必定会超时
  方法二:模拟数字的删除,每次删除就把该元素从数组中移除,通过计算下标来获取下一个要删除的位置。(耗时2000ms)
  方法三:公式法。f(N,M)=(f(N−1,M)+M)%N。(耗时80ms)

代码:
  方法二:

  方法三:

3月31日:排序树组

  给你一个整数数组 nums,将该数组升序排列。
  
  
  示例 1:
  输入:nums = [5,2,3,1]
  输出:[1,2,3,5]
  
  示例 2:
  输入:nums = [5,1,1,2,0,0]
  输出:[0,0,1,1,2,5]
   
  提示:
  
  1 <= nums.length <= 50000
  -50000 <= nums[i] <= 50000

思路:
  nums[i]是有范围的,使用计数排序比直接sorted快。

代码:

  
3月的终于刷完啦~~~撒花✿✿✿
  

发表评论

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