- 博客(211)
- 收藏
- 关注
RSS订阅原创 LeetCode 1249. Minimum Remove to Make Valid Parentheses - FB高频题1
首先要搞清楚左右小括号的匹配原则，当遇到一个左括号时，后面必须要有一个右括号才能匹配，要是直到最后也没出现右括号则该左括号为无效需被删除；当遇到一个右括号时，其前面必须要有一个等着匹配的左括号，否则该右括号为无效需要被删除。
2022-04-21 23:29:38
442
原创 LeetCode 1229. Meeting Scheduler - 亚马逊高频题32
这题其实就是一道典型的关于间隔的题。跟LeetCode 759. Employee Free Time非常相似，因此可以用类似的优先级队列的解法，具体的解题思路可以参考LeetCode 759. Employee Free Time。然而，题目说的只是两个人的会面，即只要从两个数组中找出有重叠且长度超过duration的时间间隔，因此可以用双指针法。
2022-04-10 11:29:07
846
原创 LeetCode 2134. Minimum Swaps to Group All 1‘s Together II - 亚马逊高频题31
这题根LeetCode 1151. Minimum Swaps to Group All 1‘s Together一样，也是给定一个二进制序列nums（即数组中只含有0或1），可以通过交换数组中0和1的位置使得所有1都连在一起，问最少要交换多少次才能使所有1连在一起，要求返回最小交换次数。唯一不同的是，数组nums一个环形数组，即数组最后一个数跟第一个数是首尾相连。因此这题仍然可以用一样的滑动窗口(Sliding Window)法
2022-04-09 10:28:44
602
原创 LeetCode 1856. Maximum Subarray Min-Product - 亚马逊高频题30
题目对数组的最小积做了定义，即数组中的最小值与数组和的乘积。现在给定一个数组，要求从所有子数组找出具有最大的最小积的那个，返回最大的最小积。暴力解法当然是计算每个子数组的最小积，从中找出最大的那个。所有子数组的问题都可以用暴力解法，但所有的子数组问题也都有更优解。算法实现可参考单调栈(Monotonic Stack)系列题。
2022-04-08 11:05:29
501
原创 LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit - 亚马逊高频题29
题目给定一个整型数组nums和一个整数limit，要求找到一个最长的子数组，使得该子数组中的任意两个数的差的绝对值都小于等于limit。我们知道数组中任意两个数的差的绝对值的范围都不会超过数组中的最大值与最小值的差，因此我们只要关心子数组中的最大值和最小值，知道最大值与最小值的差不超过limit就符合题目要求。本题的暴力解法就是，就是用两个循环找出从任意一个位置出发满足条件的所有最长子数组。暴力解法的时间复杂度是O(n^2)会超时。关于子数组的问题，最常用的一种解法就是移动窗口（Sliding Wi
2022-04-07 23:14:21
823
原创 LeetCode 2214. Minimum Health to Beat Game - 亚马逊高频题28
题目说你在玩闯关游戏，从第0关到第n-1关一共n关，每闯一关都将失去一定点数的血。给定一个数组damage，其中damage[i]表示闯过第i关需要失血的点数。另外还给定了一个整数armor表示一个装备，装备可以在任意一关使用但最多只能使用一次，一次最多可以补血的点数为armor。为了能成功闯过所有关，最后至少要剩下一滴血，问在开始游戏前你最少需要多少点的血。题目看起来挺吓人其实是一道easy题。
2022-04-06 10:55:14
3896
1
原创 LeetCode 560. Subarray Sum Equals K - 亚马逊高频题27
很显然可以用暴力解法，算出每个子数组的和，判断和是否等于k。也很显然，暴力解法不是出题者所要的，一定会有更优解。只要是关于子数组和的问题，我们需要很快地想到前缀和的概念，所谓前缀和就是数组中的每一个位置到数组头的所有元素的和。有了每个位置的前缀和，就可以快速的算出任意一个子数组的和，对于一个子数组，它的和就是子数组结尾位置的前缀和减去第一个位置的前一个位置的前缀和。
2022-04-05 10:36:44
620
原创 LeetCode 582. Kill Process - 亚马逊高频题26
明显，终止一个进程，受到影响的只有以该进程为根的子树里的所有子进程，而其它进程并不受影响。因此我们只要先根据给定的进程ID数组pid和父进程ID数组ppid构造成一棵树（其实也是一个图形结构），然后从要终止的进程kill出发遍历（BFS或DFS均可）以它为根的子树，子树中的每个进程都将被终止，因此只要把遍历到的进程ID放入结果链表中即可。
2022-04-04 11:11:54
659
原创 LeetCode 1339. Maximum Product of Splitted Binary Tree - 亚马逊高频题25
由于移除树中的任意一条边都将变成两棵子树，因此最直观的做法就是移除每条边算出两棵子树的和，再计算它们的乘积，从中找出乘积最大值。但是每移除一条边再计算两棵子树和，将有很大计算量，有很多的重复计算。
2022-04-03 22:41:31
649
原创 LeetCode 2130. Maximum Twin Sum of a Linked List - 亚马逊高频题24
根据题意，其实就是把一个具有n个（n为偶数）的链表从正中间把链表分成两部分，即为两个节点个数相等的子链表，那么所有的双胞胎节点就是，第一个子链表从头到尾与第二个链表从尾到头一一对应构成一对对双胞胎节点，从这些匹配的双胞胎节点中找出和最大的那一对。
2022-04-02 10:15:48
811
原创 LeetCode 2021. Brightest Position on Street - 亚马逊高频题23
题目看起来比较高大上，但仔细再读一遍搞清题意，会发现它跟LeetCode 370. Range Addition如出一辙，还是LeetCode 253. Meeting Rooms II的变形题。
2022-04-01 21:43:13
641
原创 LeetCode 1010. Pairs of Songs With Total Durations Divisible by 60 - 亚马逊高频题22
关于取模运算，我们知道要是两个数的和能被60整除，那么两个数分别与60相除的余数和也将等于60。有了以上概念，那么这题就变成了判断两个数分别与60相除后的余数和是否等于60，其实它就是LeetCode的第一题(Two Sum)的变形题了。
2022-03-31 23:16:05
365
原创 LeetCode 735. Asteroid Collision - 亚马逊高频题21
根据题意，只有向右方向的小行星在左边和向左方向的小行星在右边才会相撞，如果相撞的两个小行星大小相等将一起爆掉。这个看起来很像大小括号匹配的那一题，向右移动的就像是左括号，向左移动的就像是右括号，因此本题也可以用堆栈来解。
2022-03-31 21:59:55
482
原创 LeetCode 1730. Shortest Path to Get Food - 亚马逊高频题20
这是一道常规的关于最短路径的题，显然宽度优先搜索(BFS)是首选。基本思路就是第一步从当前位置同时向上下左右移动到下一个不是障碍物的位置，第二步再从所有到达的位置向上下左右四个方向出发移动到下一个不是障碍物的位置，第三步以及后面的每一步都做类似的移动，直到第一次到达食物单元就可以停止，所经过的步数就是最短路径。
2022-03-30 21:26:34
861
原创 LeetCode 1167. Minimum Cost to Connect Sticks - 亚马逊高频题19
根据题意，花费是由棍子长度决定的，棍子越长花费越多。另外两根棍子连在一起后，还需要跟后面的棍子连在一起，也就是说先被挑中连接的棍子，将会在后面再次跟其它棍子相连接，它们的花费也将会被累加。本着贪心法则，我们当然希望长的棍子花费尽量少地被累加，因此我们应该每次先挑最短的两根相连，尽可能地把长的棍子留到后面。
2022-03-29 21:26:26
463
原创 LeetCode 1628. Design an Expression Tree With Evaluate Function - 亚马逊高频题18
本题麻烦的是要把题目搞明白，搞定题意后代码实现就相对简单。题目其实考察的是两点，一个是关于面向对象设计(OOP)，即有关类的多态性(polymorphism)以及继承类的实现等；另一个就是实现把数组postfix转成二叉树的算法。
2022-03-28 21:40:51
671
原创 LeetCode 1275. Find Winner on a Tic Tac Toe Game - 亚马逊高频题17
最简单的方法就是，每走一步就判断一下行，列或两条对角线是否有3个相同的棋子，如果有就知道谁是赢家，没有就判断是否为平局，还没平局就继续走直到所有moves走，最后如果棋盘还没满就是“Pending”。因为棋盘是一个3x3的小矩阵，计算量不大，所以可以用以上的解法，这也是这道为什么是 ‘easy’ 级别的。但是如果换成是一个n x n（n很大）的矩阵，那计算量就会很大。因此需要想想有没更优解法。
2022-03-27 23:07:24
718
原创 LeetCode 11. Container With Most Water - 亚马逊高频题16
最直观的就是用暴力解法，用两个for循环，从左到右，计算每根柱子与其右边的所有柱子形成的水槽的装水量，实时更新最大装水量，循环结束即可得到答案。不过既然这题能成为Amazon的高频题，除了暴力解法肯定还有更优解法。
2022-03-26 22:15:02
569
原创 LeetCode 12. Integer to Roman - 亚马逊高频题15
题目要求把一个整数转换成罗马数字。仔细观察就会发现个位上的数只由I,V,X组成，十位上的数只由X,L,C组成，百位数上的数只由C,D,M组成，千位上的数由于最大只到3因此只由M；另外一个规律就是各个位上的相同数字构造方式是相同的只是组成的字母不同而已。
2022-03-25 19:34:53
624
原创 LeetCode 1481. Least Number of Unique Integers after K Removals - 亚马逊高频题14
题目给定一个数组arr和一个整数，问从数组中删除k个数后所剩下的最少的唯一整数的个数是多少？本着贪心原则，要使得最后剩下的唯一整数个数最少，那就要尽可能多地删除唯一整数，尽量让出现频率高的数留下。很显然我们应该从出现频率最少的数开始删除。
2022-03-24 22:10:04
537
原创 LeetCode 79. Word Search - 亚马逊高频题13
题目给定一个m x n的字符矩阵board和一个单词word，问board中是否存在word单词。board中的单词构造是从任意一个字符出发沿着上下左右任意方向形成的任意字符序列。这道题可以跟LeetCode 212. Word Search II一起刷，两道题基本思路差不多都是用DFS(深度优先搜索)。
2022-03-23 21:53:53
297
原创 LeetCode 273. Integer to English Words - 亚马逊高频题12
根据限制条件我们知道给定的是一个32位非负整数，即范围是0~2147483647，也就是说最大就是10亿(Billion)级别的。另外我们知道英文对数的书写是每隔三位用一个逗号，即每隔三位换一种表达（Thousand, Million, Billion）。也因此一个数的每一位的英文表达是：个、十，百、个千、十千、百千、个百万、十百万、百百万、个十亿、十十亿、百十亿。
2022-03-22 21:30:03
590
原创 LeetCode 994. Rotting Oranges - 亚马逊高频题11
其实是从所有烂橘子开始，每一分钟向四周扩散把四周的好橘子变烂，不停地扩散直到所有烂橘子周围没有好橘子为止。很显然这是一道用宽度优先搜索BFS算法求最短路径的题。
2022-03-21 21:49:46
519
原创 LeetCode 1567. Maximum Length of Subarray With Positive Product - 亚马逊高频题10
这是一道典型的动态规划题（Dynamic Programming）。如果能知道数组从每个数开始向左乘积为正的最长子数组的长度，那么所有中最长的那个就是最后的答案。从一个数开始向左乘积为正的最长子数组，取决该数本身的值以及它前一个数的状态。数组的第一个数的状态是确定的，因此可以从左到右传递状态求出所有数的状态。每个数需要维护两个状态，乘积为正的最长子数组的长度positiveLen和乘积为负的最长子数组的长度negetiveLen。
2022-03-20 10:40:47
409
原创 LeetCode 1152. Analyze User Website Visit Pattern - 亚马逊高频题9
题目是关于统计用户访问网站的习惯规律，给定两个字符串数组username和website以及一个整型数组timestamp。三个数组长度相同，三个数组的第i个元素[username[i], website[i], timestamp[i]]组成一组，表示用户username[i]在时间timestamp[i]访问了网站website[i]。要求返回具有最大分数的pattern，如果pattern有多个则结果按字典序顺序排列。题目很长但不难，只要读懂题目基本上就知道解法。代码实现稍微麻烦细节要多注意
2022-03-20 04:36:47
386
原创 LeetCode 212. Word Search II - 亚马逊高频题8
很容易想到的是从矩阵每个位置出发，利用DFS算法遍历每个字符，遍历过程中从出发字符到当前字符就会形成一个字符序列，判断该字符序列是否是words中的一个单词。从一个字符出发遍历整个矩阵的时间复杂度为O(m x n)，每个位置出发都遍历一遍总的时间复杂度就是O((m x n )^2)。看到这种时间复杂度就要想想有没有更优解法。本题属于字符匹配问题，很自然就会想到高效的前缀树（Trie Tree or Prefix Tree）
2022-03-18 22:16:43
441
原创 LeetCode 828. Count Unique Characters of All Substrings of a Given String - 亚马逊高频题7
直观方法是找出所有子字符串，对每个子字符串挨个统计单一字符的个数，很显然计算量是巨大。这里我们要统计的是所有字符串中单一字符的个数，其实换角度看问题，最终所有子字符串中单一字符的总个数跟以每个字符为单一字符（只出现一次）的子字符串的总个数是相同的
2022-03-17 21:56:15
582
原创 LeetCode 1472. Concatenated Words - 亚马逊高频题6
题目给定一个字符串数组words，数组中含有一系列长度不等的单词（无重复单词），要求找出所有可以由数组中更短的单词连接而成的单词。一个单词肯定是由比它自身长度短的单词连接而成，显然对于数组words里单词，我们应该从短到长进行判断，因此首先应该对words里单词按长度进行排序，然后在从左到右判断依次当前单词是否可以由它前面的单词连接而成。那么该如何判断一个单词是否能由一组更短的单词连接而成呢？这里可以使用动态规划来解。
2022-03-16 22:19:19
124
原创 LeetCode 1151. Minimum Swaps to Group All 1‘s Together - 亚马逊高频题5
首先来看一下数组中一共有多少个1，假设长度为n的数组含有m个1，那么最终会在数组的某一个位置形成一个长度为m的全为1的子序列。很明显任意一个长度为m的子序列都可以通过交换变成全为1，只是交换次数不同而已，由此可以想到用滑动窗口（sliding window）
2022-03-15 22:27:32
596
原创 LeetCode 1492. The kth Factor of n - 亚马逊高频题4
题目给定两个正整数n和k，要求找出n的所有因子数按从小到大排好序后的第k个因子。一个正整数的因子是从1到n（包括n本身）能被n整除的所有整数。因此本题可以直接用一个for循环从1开始到n挨个找出能被n整除的整数，当到达了第k个能被n整除的数，该数就是要找的第k个因子。但是本题的难度级别被标位medium，必然有更优解法。
2022-03-14 22:18:06
585
原创 LeetCode 2104. Sum of Subarray Ranges - 亚马逊高频题3
暴力解法是要算出每个子数组的最大值和最小值的差然后再求和，换种思路，要是能算出所有子数组的最大值总和与最小值总和然后再求差，那么其结果是一样的。于是题目就可以变成先找出所有子数组的最大值的和，再找出所有子数组的最小值的和。印象中LeetCode中有类似的题。
2022-03-13 22:28:22
1353
原创 LeetCode 370. Range Addition - 亚马逊高频题2
暴力解法是每次用一个for循环从startIdxi到endIdxi结束把数组arr的[startIdxi, endIdxi]范围的所有值都加上值inci。可是出题的目的显然不是要用暴力解法。仔细再读一遍就会发现这题其实跟LeetCode 253. Meeting Rooms II很像。
2022-03-12 21:21:49
5594
原创 LeetCode 926. Flip String to Monotone Increasing - 亚马逊高频题
给定一个二进制字符串，你可以将字符串里的‘0’翻转成‘1’，或把‘1’翻转成‘0’。问最少要翻转多少次就可以使其变成单调递增的？根据题目对单调性的定义，把一个二进制字符串变成单调递增的，最终所有‘0’都应该集中在字符串前面，所有‘1’都集中在字符串后面。
2022-03-11 22:42:01
223
原创 LeetCode 663. Equal Tree Partition - 二叉树（Binary Tree）系列题30
题目说给定一棵二叉树，问是否能够找到一条边，移除这条边后形成两棵子树，使得这两棵子树的节点值和相等？二叉树和数组经常是可以类比的，还是先来看一下数组。给定一个数组，是否能找到一个位置把数组分成两个部分使得两部分的和相等？
2022-03-10 22:40:13
422
原创 LeetCode 814. Binary Tree Pruning - 二叉树（Binary Tree）系列题29
给定一棵二叉树，要求把所有不含节点值为1的子树剪掉。这一道关于二叉树修剪的问题，实际生活中要修剪一棵树肯定是从叶子开始修剪。同样的，本题也应该从叶节点开始从底向上修剪。
2022-03-09 22:42:35
102
原创 LeetCode 538. Convert BST to Greater Tree - 二叉树（Binary Tree）系列题28
给定一棵二叉搜索树(Binary Search Tree)，要求把它转换成一棵更大树（Greater Tree）。所谓更大树，就是把原二叉搜索树中的每一个节点值变成它自身值加上原树中比该节点值大的所有节点值的和。先来看一下如果给定的是一个数组，如何把数组中每个数变成它自身加上所有比它大的数的总和？其实只要先把数组排序，那么数组中每个数所在位置之后的所有数都是比它大的数，因此只要从后往前进行累加就可以达到目的。
2022-03-08 23:03:01
316
原创 LeetCode 623. Add One Row to Tree - 二叉树（Binary Tree）系列题27
给定一棵二叉树和两个整数val和depth，根节点所在层定义为第一层，要求新增加一层节点值都为val的节点，作为树的新的第depth层（也就是说新增加的一层在原来第depth-1层的下一层）。
2022-03-07 23:25:26
140
原创 LeetCode 549. Binary Tree Longest Consecutive Sequence II - 二叉树系列题26
给定一棵二叉树，要求找出最长的连续路径，连续路径是相邻两个节点值相差1，但是沿着路径必须是递增的或递减的（不能是部分递增部分递减）。另外还规定路径不一定必须是从上往下的即从父节点到子节点，还可以是穿过一个节点的路径，即从子节点到父节点再到另一个子节点（只要是连续的即可）。
2022-03-06 23:29:26
211
原创 LeetCode 337. House Robber III - 二叉树系列题25
问题的关键是不能连续偷两个房子，如果是从上往下偷，那么偷了当前节点就不能偷它的两个子节点；如果是从下往上偷，那么偷了当前节点就不能偷它的父节点。
2022-03-05 22:30:26
505
原创 LeetCode 508. Most Frequent Subtree Sum - 二叉树系列题24
一棵二叉树，以它的每一个节点为根节点构成一棵棵子树，每棵子树的所有节点值的和叫做子树和，不同子树的子树和有可能相同，现在要求找出出现频率最高的所有子树和。暴力解法就是以每个节点为根节点求出它们对应子树的和，同时统计每个子树和出现的次数，从而找出出现次数最多的所有子树和。然而，如果每次都重复计算每棵子树的和，将耗费太多时间做重复计算
2022-03-04 23:14:57
414
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人