LeetCode经典面试150题题解
88. 合并两个有序数组
Problem: 88. 合并两个有序数组
思路
使用“双指针”技术,从两个数组的末尾开始比较元素,然后将较大的元素放入nums1的末尾。这样,我们可以确保nums1在每一步都保持有序。这种方法的关键在于我们从后往前填充nums1,这样就不会覆盖nums1中尚未处理的元素。
解题方法
-
初始化两个指针 p1 和 p2 到 nums1 和 nums2 的初始元素的最后一个位置上,然后再用一个指针 p 指向 nums1 的最后一个位置。
-
比较 nums1[p1] 和 nums2[p2] 的值,将较大的值放入 nums1[p] 的位置上,然后将 p 指针和较大值的指针都向前移动一位。
-
重复步骤 2,直到 p1 或 p2 小于 0,这意味着 nums1 或 nums2 的元素已经全部放入 nums1 中。
-
如果 p2 还没有小于 0,那么将 nums2 中剩余的元素复制到 nums1 的前面。
复杂度
时间复杂度:
时间复杂度是 O(m+n),其中m和n分别是 nums1 和 nums2 的长度。在最坏的情况下,我们可能需要遍历 nums1 和 nums2 中的所有元素。因为我们只遍历每个元素一次,所以时间复杂度是线性的。
空间复杂度:
空间复杂度是O(1)。这是因为我们没有使用额外的空间来存储数据。所有的操作都是在原地进行的,我们只是使用了几个额外的变量来保存索引。因此,空间复杂度是常数的。
Code
func merge(nums1 []int, m int, nums2 []int, n int) { |
27. 移除元素
Problem: 27. 移除元素
思路
这题如果直接用Go的切片功能去删除元素会出现问题,因为一遍遍历数组一边修改数组会导致遍历时的索引出现问题,所以我们还是继续用双指针。双指针技术在数组或链表的问题中非常常用,它可以帮助我们以线性时间复杂度解决问题。
解题方法
创建两个指针,一个用于遍历数组(我们称之为右指针),另一个用于指向下一个将要插入的位置(我们称之为左指针)。
从左到右遍历数组,对于每一个元素,检查它是否等于给定的值。
如果元素不等于给定的值,就把它复制到左指针指向的位置,然后把左指针向右移动一位。
如果元素等于给定的值,就忽略它,不做任何操作。
遍历完数组后,左指针的位置就是新的数组长度。
复杂度
时间复杂度:
这两段代码都是通过一次遍历完成的,其中 n 是数组的长度。在遍历过程中,每个元素都被访问一次并进行一次比较操作,因此,时间复杂度是 O(n)。
空间复杂度:
这两段代码都是在原地修改数组,没有使用额外的数组或其他数据结构。除了输入数组外,只使用了常数个变量(例如,左指针、右指针和 val)。因此,空间复杂度是 O(1)。
Code
func removeElement(nums []int, val int) int { |
26.删除有序数组中的重复项
Problem: 26. 删除有序数组中的重复项
思路
代码的主要思想是使用两个指针,一个慢指针 i 和一个快指针 j,同时遍历数组。其中,慢指针指向当前处理的元素,快指针用于寻找下一个不同的元素。
解题方法
首先检查数组是否为空,如果为空,则直接返回0,因为没有元素需要处理。
初始化两个指针 i 和 j,并设置 i=0。这里,i 是一个慢指针,它表示已处理的不同元素的数量,j 是一个快指针,用于遍历数组寻找下一个不同的元素。
使用一个 for 循环,从 j=1 开始遍历数组。在每次迭代中,检查 nums[j] 是否与 nums[i] 不同。如果 nums[j] 与 nums[i] 不同,这意味着我们找到了一个新的不同的元素。此时,我们将 nums[j] 的值赋给 nums[i+1],并将 i 的值加1,表示我们找到了一个新的不同的元素。当 for 循环结束时,i+1 的值就是数组中不同元素的数量。因此,我们返回 i+1。
复杂度
时间复杂度:
时间复杂度是O(n),因为我们只遍历数组一次。
空间复杂度:
空间复杂度是 O(1),因为我们只使用了常数个额外的变量。
Code
func removeDuplicates(nums []int) int { |
80.删除有序数组中的重复项 II
Problem: 80. 删除有序数组中的重复项 II
思路
这道题目要求我们在一个有序数组中删除重复项,使每个元素最多出现两次,并返回新的数组长度。在不使用额外空间的条件下,我们可以考虑使用双指针的方法来解决这个问题。
注意题给数组为有序数组
解题方法
我们使用两个指针,一个用于遍历数组(fast),另一个指向当前修改的位置(slow)。
具体步骤如下:
如果数组的长度小于等于2,那么所有的元素都应该保留,因为他们的出现次数都不会超过2次,所以直接返回数组的长度即可。
初始化两个指针,slow = 2 和 fast = 2。slow指针表示处理过的数组的长度,fast指针表示已经检查过的数组的长度。
当 fast < n时,比较 nums[slow - 2] 和 nums[fast],如果相等,则说明已经有两个数相等,fast指针继续前进。如果不相等,将 nums[fast]的值复制到 nums[slow],然后增加 slow 和 fast。
返回 slow,表示处理后的数组长度。
复杂度
时间复杂度: O(n)
这是因为我们只需要遍历一次数组。
空间复杂度: O(1)
我们只使用了常数级别的额外空间。
Code
func removeDuplicates(nums []int) int { |
169. 多数元素
Problem: 169. 多数元素
思路
这道题目要求我们找到一个数组中的多数元素,即出现次数大于数组长度一半的元素。由于题目保证一定存在这样的多数元素,我们可以使用Boyer-Moore投票算法来解决这个问题。
解题方法
Boyer-Moore投票算法的核心思想是利用“多数元素”的定义,即它的出现次数至少是数组长度的一半。这意味着,如果我们在遍历数组的过程中,对所有非多数元素进行投票(计数),那么当我们遇到多数元素时,计数器应该会增加,直到超过数组长度的一半。在这个过程中,我们只需要维护一个或两个候选多数元素及其计数。
Boyer-Moore投票算法
Boyer-Moore 投票算法的步骤如下:
维护一个候选主要元素 candidate 和候选主要元素的出现次数count。
初始时candidate 为任意值,count=0。
遍历数组nums 中的所有元素,遍历到元素 x 时,进行如下操作:
如果count=0,则将 x 的值赋给candidate,否则不更新candidate 的值;
如果 x=candidate,则将 count 加 1,否则将count 减 1。
遍历结束之后,candidate的值可能为主要元素。(可能的原因是,如果是这样的一个数组[1,2,3],那么剩下的元素是3,但是3并不是数量超过一半的元素)
可以类比为打擂台,candidate就是守擂的多数元素。接着遍历给定数组,如果遇到的同一个类型的数,那么守擂的人数就增加,对应count++;如果遇到的事不同类型的数字,那么守擂方就和打擂台的人同归于尽,对应count–。当count为0时,说明原守擂人已经全部GG了,于是把candidate设置为当前的这个数,作为新的守擂人。
由于一开始不知道谁是势力最大的帮派,所以各个不同帮派之间两两火并。最后剩下来的一定是势力最大的帮派。
就算所有小帮派知道谁是势力最大的帮派,他们“群起攻之”。每一个小帮派的人都消耗掉势力最大的帮派的一个人。但是由于势力最大的帮派的人数大于一半,所以即使这样,最后剩下来的还是大帮派的人。
以上就是Boyer-Moore 投票算法最通俗易懂的解释。
复杂度
时间复杂度:
O(n)
这个算法只需要遍历数组一次,因此时间复杂度是线性的。
空间复杂度:
O(1)
由于我们只需要一个或两个候选元素和它们的计数器,所以空间复杂度是常数级别的。
Code
func majorityElement(nums []int) int { |
189.轮转数组
Problem: 189. 轮转数组
思路
当拿到这个问题时,我们的目标是将一个整数数组 nums 向右轮转 k 个位置。这个问题可以通过几种不同的方法解决,但考虑到题目中提到的“原地”算法和空间复杂度为 O(1) 的要求,我们选择一种不需要额外空间的解决方案。
解题方法
我们选择的解题方法是三次反转法,这种方法简单且满足原地操作的要求。具体步骤如下:
反转整个数组:首先,我们反转整个数组 nums,这样原本在数组末尾的元素就会被移动到数组的开头。
反转前 k 个元素:接下来,我们只反转数组的前 k 个元素。这一步将数组的前 k 个元素放置到正确的位置。
反转剩余的元素:最后,我们反转数组中剩余的部分(从第 k+1 个元素到数组末尾),这样所有的元素都会被放置到正确的位置。
复杂度
时间复杂度:
O(n)
这个算法需要三次遍历整个数组来完成反转,因此时间复杂度是线性的,与数组的长度成正比。
空间复杂度:
O(1)
由于我们是在原地进行操作,没有使用额外的存储空间,所以空间复杂度是常数级别的。
func rotate(nums []int, k int) { |
121.买卖股票的最佳时机
Problem: 121. 买卖股票的最佳时机
思路
这个问题的关键在于理解股票价格的变化趋势,并找到买入和卖出的最佳时机。由于我们只能进行一次交易,我们需要寻找一个价格的波谷(买入点)和一个紧随其后的价格波峰(卖出点)。
解题方法
代码采用了一种自底向上的方法来解决这个问题。这种方法的核心思想是从数组的最后一个元素开始向前遍历,动态地更新最大利润。
- 初始化:首先,我们初始化 maxPrice 为数组的最后一个元素,这是我们假设的初始卖出价格。同时,result 初始化为0,这是我们的最大利润。
- 逆序遍历:然后,我们从倒数第二个元素开始逆序遍历整个数组。
- 更新最大利润:在每次迭代中,我们计算以当前价格为卖出点的最大利润(maxPrice - prices[i]),并将其与已有的 result 比较,取较大者作为新的最大利润。
- 更新卖出价格:同时,我们也更新 maxPrice,使其为当前价格和之前 maxPrice 中的较大者。
- 返回结果:遍历结束后,result 就是我们要找的最大利润。
复杂度
时间复杂度:
O(n),其中 n 是数组 prices 的长度。这是因为我们只遍历了一次数组。
空间复杂度:
O(1),我们只使用了两个额外的变量,与输入数组的大小无关。
Code
func maxProfit(prices []int) int { |
122.买卖股票的最佳时机 II
Problem: 122. 买卖股票的最佳时机 II
思路
这个问题是关于股票交易的,目标是找到所有可能的交易对,使得利润最大化。题目要求我们在一个给定的数组中,找到所有可能的交易对,并且每次交易都是买入后卖出,从而获得最大利润。
解题方法
对于这个问题,我们可以采用一种贪心算法的思想。具体来说,我们可以遍历整个数组,对于每对相邻的天数,如果第二天的价格高于第一天,我们就认为这是一个买入和卖出的机会,从而获得利润。我们将所有这样的利润累加起来,就可以得到最大利润。
复杂度
时间复杂度:
O(n)
我们只需要遍历一次数组,时间复杂度为线性。
空间复杂度:
O(1)
我们只需要一个变量来存储结果,空间复杂度为常数。
Code
func maxProfit(prices []int) int { |
55.跳跃游戏
Problem: 55. 跳跃游戏
思路
思路很简单,利用贪心的思想,只要维护一个能到达的最远距离,就能保证当前索引到最远可达距离之间的所有元素都能到达。
解题方法
- 如果数组长度为1,则直接返回true,因为只有一个位置,无需跳跃。
- 如果数组的第一个元素为0,返回false,因为无法从起始位置跳到任何地方。
使用一个变量max_step来跟踪当前可以到达的最远索引。 - 遍历数组,更新max_step为当前可跳跃距离和max_step两者中的最大值
- 如果当前元素为0且max_step为0且当前索引不是数组的最后一个索引,则返回false,因为这意味着在某个点上无法前进。
- 每次循环结束时,max_step减1,对应向前进了一格。
复杂度
时间复杂度:
我们只遍历了一遍数组,因此时间复杂度为O(1)
空间复杂度:
我们是就地操作的,除了维护最大可达距离的几个变量外,没有产生额外的空间。故空间复杂度为O(1)
Code
func canJump(nums []int) bool { |
45.跳跃游戏 II
Problem: 45. 跳跃游戏 II
思路
贪心的思想,确保每次跳的最远,一直往前跳即可。
解题方法
首先判断如果从改点直接尽力跳能否到达终点?如果能就直接跳并退出循环;如果不能直接到达终点,就寻找如何让自己接下来能够跳的更远:维护一个可以跳跃到达的最远距离,最远距离=该节点的跳跃距离+距离起跳点的距离。每次起跳前都检测自己的跳跃范围内,如何跳才能让自己下一步到达的距离更远。
复杂度
时间复杂度:
在jump函数中,主循环会持续进行直到step等于len(nums)-1,这意味着主循环会遍历整个数组nums。在循环体内,find_max_step函数被调用,该函数本身也是一个循环,它将遍历从step开始的nums[step]个元素。
因此,jump函数的时间复杂度主要由以下两部分组成:
主循环的时间复杂度:由于step每次增加的值取决于find_max_step函数的返回值,且每次至少增加1,最坏情况下,如果nums中的每个元素都为1,那么step需要增加到len(nums)-1,此时主循环的时间复杂度为O(n)。
find_max_step函数的时间复杂度:在最坏的情况下,这个函数将遍历nums[step]个元素,由于step的值在每次主循环迭代中增加,所以这个函数在整个算法执行过程中的总时间复杂度为O(n^2)。
综合以上两点,整个算法的时间复杂度为O(n^2)。但step的值为n时主函数只需要执行一次,所以实际情况复杂度会比理论上的复杂度更低。
空间复杂度:
在代码中,除了输入数组nums外,没有使用额外的存储空间来存储数据结构。find_max_step函数中的变量max_step和max_id仅用于临时存储,它们的大小不随输入规模n的变化而变化。
因此,空间复杂度为O(1)。
Code
func jump(nums []int) int { |
274.H 指数
Problem: 274. H 指数
思路
这个问题要求我们计算一个研究者的h指数,即至少有h篇论文被引用了h次或以上。解决这个问题的关键在于理解h指数的定义,并找到一种有效的方法来确定满足条件的最小h值。
解题方法
- 构建额外数组:首先,我们创建一个额外的数组 m,大小为 len(citations) + 1,用来统计引用次数小于或等于每个可能的h值的论文数量。
- 统计论文数量:遍历 citations 数组,对于每个引用次数 i,我们增加 m[min(len(citations), i)] 的计数,这样 m[j] 就代表了引用次数小于或等于 j 的论文数量。
- 倒序遍历:然后,我们从 m 数组的末尾开始倒序遍历,累加每个 m[j] 的值到变量 s 中,这个累加值 s 表示引用次数大于或等于 j 的论文数量。
- 找到h指数:当我们找到第一个满足 s >= j 的 j 时,这个 j 就是研究者的h指数。
复杂度
时间复杂度:
O(n)
我们只需要遍历一次 citations 数组来构建 m 数组,然后再遍历一次 m 数组来找到h指数,因此总的时间复杂度是线性的。
空间复杂度:
O(n)
我们创建了一个大小为 len(citations) + 1 的额外数组 m,因此空间复杂度是线性的。
Code
func hIndex(citations []int) int { |
380.O(1) 时间插入、删除和获取随机元素
Problem: 380. O(1) 时间插入、删除和获取随机元素
思路
Go本身自带哈希表,用map数据结构去模拟RandomSet类。
解题方法
一开始的思路是完全用一个map去实现,但是遇到了两个问题:
- 在处理最后一个GetRandom函数时,本来想用map的特性去处理。即为了保证代码安全性,map在用for进行迭代时返回的顺序是随机的。但是由于底层的某些原因,在共有n个且不足8个元素时,第一个元素的概率将是(8-n+1)/8而不是1/n。导致第一个元素出现的概率过大无法通过判题器。具体原因可以参考这篇文章:golang Map迭代的随机性。
- 所以我选择在GetRandom函数中手动创建一个切片,把map的键导出后再用随机数输出。但是每次调用一次GetRandom函数必然需要遍历一次map,因此时间复杂度为O(n),导致最后提交代码时TE超时了。
所以我决定折中一下,在创建类时自带一个切片,用map储存数据->切片下标的映射,切片储存实际的数据。这样在GetRandom函数中就不需要再遍历map了。
复杂度
时间复杂度:
map的底层是哈希表,插入和删除操作均为O(1),故时间复杂度为O(1)
空间复杂度:
RandomSet类创建了和数据等大的map和一个切片,因此占空间复杂度为O(n)。
Code
type RandomizedSet struct { |
238.除自身以外数组的乘积
Problem: 238. 除自身以外数组的乘积
思路
这道题目要求我们计算一个数组中,除了每个元素自身之外,其他所有元素的乘积。题目中明确指出,数组中任意元素的全部前缀元素和后缀元素的乘积都在32位整数范围内,这意味着我们可以使用一个整数来存储这些乘积。
解题方法
解题的关键在于,我们可以将问题分解为两个部分:计算每个元素左边所有元素的乘积,以及计算每个元素右边所有元素的乘积。然后,将这两个乘积相乘,就可以得到除了当前元素之外的乘积。
-
初始化:创建一个答案数组ans,其长度与输入数组nums相同,并将ans[0]初始化为1,因为第一个元素左边没有元素。
-
计算左侧乘积:从第二个元素开始,将每个元素与其左侧所有元素的乘积累加到答案数组中。这可以通过一个临时变量tmp来实现,它存储当前元素左侧的乘积。
-
计算右侧乘积:从倒数第二个元素开始,更新答案数组,将每个元素与其右侧所有元素的乘积累加到对应的答案元素上。
-
注意:由于我们不能使用除法,所以我们不能简单地将左侧乘积除以当前元素来得到最终答案。相反,我们需要在计算右侧乘积时,将当前元素的右侧乘积与左侧乘积相乘。
复杂度
时间复杂度:
O(n),其中n是数组nums的长度。这是因为我们只需要遍历数组两次。
空间复杂度:
O(1),我们只使用了有限的额外空间(答案数组ans和临时变量tmp),它们的大小不随输入数组的大小而变化。
Code
func productExceptSelf(nums []int) []int { |
134.加油站
Problem: 134. 加油站
思路
最简单粗暴的思路就是一个一个遍历加油站,看能否到达。但是需要优化,不然会TE超时。
解题方法
最开始我的想法是将gas数组和cost数组相减,由于必须要保证启动时汽油充足,所以只需要考虑相减后结果为正数的加油站,再开始遍历。可惜时间复杂度还是太高,最后虽然通过了判题器但是耗时也是最大的那一批擦边过。
另一种简化方法是:经过研究发现,如果从第X个加油站出发,抵达Y加油站后没油了,那么可以证明在X~Y之间的所有加油站,最后都不可能抵达第Y+1个加油站。也就是说,我们在Y加油站瘫痪后,下一次可以直接从Y+1加油站出发,跳过了Y-X中间的所有加油站。经过简化后,耗时大大减短。
复杂度
时间复杂度:
我们只需要遍历一遍数组,所以时间复杂度为O(N)。
空间复杂度:
没有使用额外空间,故空间复杂度为O(1)。
Code
func canCompleteCircuit(gas []int, cost []int) int { |
135.分发糖果
Problem: 135. 分发糖果
思路
这道题目要求给每个孩子分配糖果,满足以下两个条件:
每个孩子至少分配到 1 个糖果。
相邻两个孩子中,评分更高的孩子获得更多的糖果。
为了满足这些条件,我们可以采用双遍历的方法来解决这个问题:
第一次从左到右遍历,保证每个孩子比左边评分低的孩子多。
第二次从右到左遍历,保证每个孩子比右边评分低的孩子多。
通过这样的双向遍历,可以确保每个孩子得到的糖果数量既满足基本条件,又保证了相邻孩子评分高的糖果多。
解题方法
初始化一个数组 candies,大小与 ratings 相同,初始值都为 1,因为每个孩子至少分配到 1 个糖果。
从左到右遍历 ratings,如果 ratings[i] > ratings[i-1],那么 candies[i] = candies[i-1] + 1。
从右到左遍历 ratings,如果 ratings[i] > ratings[i+1],那么 candies[i] = max(candies[i], candies[i+1] + 1),因为要同时考虑之前从左到右遍历的结果。
最后将 candies 数组中的值加起来就是所需的最少糖果数。
复杂度
时间复杂度:
因为我们需要两次遍历 ratings 数组,第一次从左到右,第二次从右到左。
空间复杂度:
需要一个与 ratings 等长的数组 candies 来存储每个孩子的糖果数。
Code
func candy(ratings []int) int { |
42.接雨水
Problem: 42. 接雨水
思路
思路有二,一种是我自己最开始的设想,一种是GPT给出的思想。
初始代码通过逐层处理每个高度来计算接雨水的格子数。
优化版本使用双指针法。
解题方法
解法一
-
找到最高的柱子:首先遍历整个数组,找到最高的柱子位置 max_i 和高度 max_h。
-
逐层处理:从最高的柱子高度开始,一层一层处理每一层的雨水量,直到所有柱子的高度都变为0。
-
遍历当前数组:每层开始时,重置 left_flag 和 space。
如果 left_flag 还没有设置,并且当前柱子高度不为0,则设置 left_flag 表示遇到了第一个柱子。
如果 left_flag 已经设置,当前柱子高度不为0,并且之前记录了空格数量,则累加雨水量到 ans,重置 space。
如果 left_flag 已经设置,并且当前柱子高度为0,则累加空格数到 space。
如果当前柱子高度不为0,则将当前柱子的高度减1。
重复以上步骤直到最高柱子的高度为0。
解法二
-
初始化左右指针:初始化两个指针 left 和 right 分别指向数组的起始位置和结束位置。
-
初始化左右最大高度:初始化 leftMax 和 rightMax 分别为数组起始和结束位置的高度。
-
遍历数组:
比较 height[left] 和 height[right]:
如果 height[left] 较小,则:
如果 height[left] 大于等于 leftMax,则更新 leftMax;
否则,累加 leftMax 与 height[left] 之差到总雨水量 ans;
移动左指针 left 向右一格。
如果 height[right] 较小或相等,则:
如果 height[right] 大于等于 rightMax,则更新 rightMax;
否则,累加 rightMax 与 height[right] 之差到总雨水量 ans;
移动右指针 right 向左一格。
终止条件:当左右指针相遇时,遍历结束。
复杂度
时间复杂度:
其中原始代码由于每一层都需要遍历整个数组,时间复杂度接近 ,其中 是数组长度, 是最高柱子的高度。如果数组中存在很高的柱子,遍历次数会非常多。所以我自己的代码遇到了TLE超时错误,通过例320/322,不通过的例子中柱子的高度达到了近十万……
优化版本由于每个元素最多只会被处理一次,时间复杂度为 ,其中 是数组长度。
空间复杂度:
原始代码和优化代码都只是用了常数级的额外空间,故空间复杂度是
Code
解法一
func trap(height []int) int { |
解法二
func trap(height []int) int { |
13.罗马数字转整数
Problem: 13. 罗马数字转整数
思路
看到这一题,我们需要将罗马数字字符串转换为整数。罗马数字有一些特定的规则:
- 相同字符的重复表示加法,例如 “III” 表示 3。
- 小的数字放在大的数字前面表示减法,例如 “IV” 表示 4。
- 小的数字放在大的数字后面表示加法,例如 “VI” 表示 6。
- 基于这些规则,我们可以通过遍历字符串来进行转换。
解题方法
-
建立一个哈希表 dic,将罗马数字字符映射到对应的整数值。
-
初始化一个变量 ans 用于存储最终的结果。
-
遍历字符串 s:
对于每一个字符 s[i],如果当前字符的值小于下一个字符的值(即 dic[s[i]] < dic[s[i+1]]),则减去当前字符的值,因为这意味着这是一个减法操作。
否则,加上当前字符的值。
最终得到的 ans 就是转换后的整数值。
复杂度
时间复杂度:
我们只需要遍历字符串一次,因此时间复杂度为 ,其中 是字符串的长度。
空间复杂度:
除了存储映射关系的哈希表外,我们只使用了常数级别的额外空间。
Code
func romanToInt(s string) int { |
12.整数转罗马数字
Problem: 12. 整数转罗马数字
思路
暴力打表,同时运用贪心的算法尽可能的多匹配字符串。
解题方法
建立起数字映射表,然后从最大的数字开始匹配,并输出转换后的字符串
复杂度
时间复杂度:
,因为虽然有循环,但是循环次数是固定的,与输入大小无关。
空间复杂度:
,只使用了固定大小的额外空间
Code
|
58.最后一个单词的长度
Problem: 58. 最后一个单词的长度
思路
直接调包,用strings.Split函数切割字符串,再打印最后一个单词的长度。
解题方法
用Split分隔后,从最后一项开始寻找非空字符串,然后返回长度。
复杂度
时间复杂度:
Split函数复杂度为,故时间复杂度为。
空间复杂度:
创建了一个原字符串大小的切片,故空间复杂度为
Code
import "strings" |
14.最长公共前缀
Problem: 14. 最长公共前缀
思路
思路有很多,可以横向搜索,也可以纵向搜索。这里我用的是纵向搜索。
解题方法
搜索每一个字符串中的第i个字符是否相等,如果不相等或者i等于某个子串的长度,查找结束,返回字符串即最长公共前缀。
复杂度
时间复杂度:
时间复杂度为,m是最长公共前缀的长度,n是字符串的个数。
空间复杂度:
空间复杂度为,没有使用额外空间。
Code
func longestCommonPrefix(strs []string) string { |
151.反转字符串中的单词
Problem: 151. 反转字符串中的单词
思路
灵活调包,用strings包下的Split和Join函数处理。
解题方法
首先用Split函数把字符串以空格为间隙切割成字符切片,然后从后往前遍历所有长度不为0的元素,倒序添加进新的切片并加上一个空格。
记住循环结束后要弹出结尾的空格。最后用Join函数合并字符切片转为字符串即可。
复杂度
时间复杂度:
Split函数的操作时间复杂度为,故时间复杂度应为。
空间复杂度:
创建了一个切片储存倒序字符串,故空间复杂度应为。
Code
import "strings" |
6.Z字形变换
Problem: 6. Z 字形变换
思路
这题与其说是Z字形变换,倒不如说是N字形……
可以通过模拟字符串的方式解决,即通过变换规律推导出结果矩阵,依次填充后再输出矩阵为字符串。同时,还可以通过压缩矩阵的方式降低空间复杂度。
但我们还可以通过推导规律直接写出矩阵对应id对应的字符串。
解题方法
观察矩阵:
0 0+t 0+2t 0+3t |
设矩阵的字符位置为idx,对应字符串s的位置为i。则不难发现规律:
- 矩阵变换周期为
- 对矩阵第一行,只对应一个元素:
- 对矩阵最后一行,也只对应一个元素:
- 对其余行,对应两个元素:与
故可直接构造代码。
复杂度
时间复杂度:
,其中n为字符串s的长度。s中的每个字符仅会被访问一次,因此时间复杂度为 。
空间复杂度:
,返回值不计入空间复杂度。
Code
func convert(s string, numRows int) string { |
28.找出字符串中第一个匹配项的下标
Problem: 28. 找出字符串中第一个匹配项的下标
思路
本来以为是KMP字符串匹配算法,结果是简单题???那就直接用内置的语言库秒了。
不过有点恶心的是,我们数据结构和算法设计都没有讲过KMP,我还得自学一遍……也许某天我会专门出一篇讲解KMP算法的博客吧。目前可以参考力扣官方的题解当代餐:实现 strStr()
解题方法
直接调库strings.Index()函数。
复杂度
时间复杂度:
Golang中 substr长度大于64/32(视CPU的情况而定)的情况,
查找采用的rabin-karp算法,它是由Richard M. Karp和 Michael O. Rabin在1987年提出的。它的时间复杂度为,最坏情况下的时间复杂度为。
Go的strings.Index()函数底层实现参考文章:GOLANG STRINGS中的INDEX函数(字符串查找)
空间复杂度:
没有使用额外空间,复杂度为
Code
import "strings" |
68.文本左右对齐
> Problem: 68. 文本左右对齐
思路
这道题目是关于文本左右对齐的问题,需要在给定的最大宽度下,将一系列单词进行排版,使得每一行的文本符合左右对齐的要求。关键点在于如何计算和分配每一行的空格,使得文本能够对齐。
解题方法
这里参照了力扣的官方题解文本左右对齐,总结出了以下规律:
- 当前行是最后一行:单词左对齐,且单词之间应只有一个空格,在行末填充剩余空格;
- 当前行不是最后一行,且只有一个单词:该单词左对齐,在行末填充空格;
- 当前行不是最后一行,且不只一个单词:设当前行单词数为,空格数为,我们需要将空格均匀分配在单词之间,则单词之间至少有个空格,应该填在前个单词之间。因此,前个单词之间填充个空格,其余单词之间应该填充个空格。
复杂度
时间复杂度:
,m是数组words中所有字符串的长度之和。
空间复杂度:
Code
func fullJustify(words []string, maxWidth int) (ans []string) { |
125.验证回文串
> Problem: 125. 验证回文串
思路
要验证回文串的思路其实很简单,核心就是用双指针进行遍历判断。本题还在原先的基础上添加了空格、符号等字符进行干扰,要求清洗字符串并忽略大小写后再进行判断。要实现这两点的方法很多。
解题方法
一种方法是简单粗暴的调包,用string包的ToLower()转换字符串为全小写,然后再调用regexp包的Compile()与ReplaceAllString()来进行正则清洗后再进行回文串的判断。但这种方法会产生额外的字符串储存开销,而且正则编译比较耗时。
第二种方法就是直接在原字符串上进行操作,这样做更加省时快捷。
复杂度
时间复杂度:
方法一:时间复杂度:
将字符串全部转换为小写:。
使用正则表达式删除非字母数字字符:。
再次遍历清理后的字符串进行回文检查:。
方法二:时间复杂度: O(n)
遍历字符串一次,同时从两端向中间扫描,跳过非字母数字字符。
比较字符时,将小写字母转换为大写字母(如果需要)。
空间复杂度:
方法一:,使用了额外的字符串存储转换后的结果和清理后的结果。
方法二:,除了几个变量外,没有使用额外的空间。
Code
方法一:
import ( |
方法二
import "unicode" |
392.判断子序列
> Problem: 392. 判断子序列
思路
一道比较简单的字符串处理题,用双指针和贪心思想依次遍历即可。
解题方法
设置两个指针p1、p2,分别指向字符串s、t。假如p2指向的字符和p1指向的相同,那么就同时右移指针;如果不同,就只右移p2指针用于寻找下一个匹配字符。当t被遍历完时说明寻找失败;如果是s先被遍历完则说明寻找成功。
注意,空字符串是任何字符串的子串;当t为空串时,除s也为空串外应直接返回false。
复杂度
时间复杂度:
,m和n分别是s和t字符串的长度。
空间复杂度:
,没有产生额外的空间。
Code
func isSubsequence(s string, t string) bool { |
167.两数之和 II - 输入有序数组
Problem: 167. 两数之和 II - 输入有序数组
思路
很简单的一道题,已知题目条件数组为非递减有序数组,则用二分查找的思想来寻找两数之和就好。
解题方法
设置两个指针left和right,分别指向数组两端,并计算两数之和sum。如果sum<target,则left++;如果sum>target,则right–;如果sum=target,则返回left+1和right+1的数组即可。
复杂度
时间复杂度:
,n为题给数组长度。
空间复杂度:
,只使用了常数级的额外空间。
Code
func twoSum(numbers []int, target int) []int { |
11.盛最多水的容器
Problem: 11. 盛最多水的容器
思路
要求接最多的雨水,如果我们选择遍历所有情况,那么时间复杂度将为,所以我们选择用双指针的做法,将时间复杂度优化到。
和接雨水思路类似,往往这种需要根据数组元素求最值的题目用双指针会大大简便计算。
解题方法
设置两个指针分别指向高度数组的两端,计算体积并更新最大值。每次计算完后,移动指向高度较矮边的指针,直到两个指针相遇为止结束。
复杂度
时间复杂度:
,因为只遍历了一遍数组。
空间复杂度:
,只使用了常量级别的额外空间。
Code
func maxArea(height []int) int { |
15.三数之和
> Problem: 15. 三数之和
思路
一道非常经典的面试题,相比于基本的两数之和,题目考察的是无序数组的三数之和。我们可以先固定一个元素,这样我们就只需要移动两个元素了,自然而然就会想到用双指针。由于数组无序,所以我们需要先对数组预处理进行排序,然后再调用双指针进行后续处理。
解题方法
在对数组进行排序后,创建三个指针i,left,right。其中i初始指向数组最左端元素用于遍历每个固定的数组元素。left和right应该位于i+1和n-1的位置,接着移动指针求和直到满足条件为止。
注意的是,题目要求结果不能有重复,所以需要加入一些判断条件来去重。
复杂度
时间复杂度:
外层循环时间复杂度为,内层循环时间复杂度为,故总时间复杂度为。
空间复杂度:
额外的排序的空间复杂度为,故空间复杂度为。
Code
import "sort" |
209.长度最小的子数组
Problem: 209. 长度最小的子数组
思路
这道题目要求找到长度最小的连续子数组,使得其元素之和大于等于给定的整数 s。由于子数组的元素必须是连续的,暴力解法(检查所有可能的子数组)虽然可以解决问题,但时间复杂度过高。考虑到这一点,使用滑动窗口的方法是更为合适的选择。
解题过程
滑动窗口的思路是将子数组的边界设为两个指针 start 和 end,初始时都指向数组的起始位置。我们不断地向右移动 end 指针来扩大窗口的大小,直到窗口内的子数组的和 sum 大于等于 s,此时记录当前子数组的长度并尝试通过移动 start 指针来缩小窗口,找到更小的满足条件的子数组。
复杂度
时间复杂度: O(n),其中 n 为数组的长度。start 和 end 指针各自最多移动 n 次,因此整体时间复杂度为线性。
空间复杂度: O(1)。我们只使用了固定大小的额外空间,空间复杂度为常数。
Code
func minSubArrayLen(s int, nums []int) int { |
3.无重复字符的最长子串
Problem: 3. 无重复字符的最长子串
思路
用滑动窗口来跟踪当前正在检查的子串,并使用哈希表来存储当前窗口中每个字符的位置。如果遇到重复字符,就缩小窗口的左边界,从而移除重复的字符。
解题过程
创建一个哈希表,键名为字符,键值为整数代表该字符是否存在。从字符串最左边开始往右遍历并维护不重复字符子串长度,如果发现重复字符就把窗口向右移动,直接从右边界开始重新搜寻。
复杂度
时间复杂度: ,其中 n 是字符串的长度。end 指针在最坏情况下会遍历字符串中的每个字符一次,start 也最多会遍历每个字符一次,所以整体时间复杂度为线性。
空间复杂度: ,其中 m 是字符集的大小,n 是字符串的长度。哈希表存储的字符数量最多是 m,但在极端情况下可能会存储整个字符串的字符,因此空间复杂度为 O(min(m, n))。
Code
func lengthOfLongestSubstring(s string) int { |
30.串联所有单词的子串
Problem: 30. 串联所有单词的子串
思路
这道题要求我们在字符串 s 中找到所有的串联子串的起始位置。每个串联子串必须包含 words 数组中的所有字符串,并且这些字符串可以以任意顺序排列连接。要解决这个问题,我们可以采用滑动窗口和哈希表的组合策略,逐步扫描字符串 s,并检查是否存在符合条件的子串。
解题过程
假设 words 数组中的每个字符串长度为 wordLen,words 的总长度为 totalLen = len(words) * wordLen。
我们需要在字符串 s 中找到所有长度为 totalLen 的子串,并检查这些子串是否由 words 数组中的所有字符串拼接而成。
由于子串的长度是固定的 totalLen,我们可以在 s 中以 wordLen 为步长移动窗口,逐步检查窗口内的子串是否符合要求。
将字符串 s 分成多个长度为 wordLen 的段落,每次检查段落是否在 words 数组中。如果找到符合条件的子串,就记录其起始位置。
使用两个哈希表:一个记录 words 中每个字符串出现的频率,另一个记录当前窗口中每个字符串出现的频率。
当两个哈希表相等时,说明当前窗口内的子串是 words 的一个排列。
复杂度
- 时间复杂度: ,其中 n 是字符串 s 的长度。我们以 wordLen 为步长,遍历字符串,并在每一步比较哈希表的内容,因此时间复杂度近似为线性的。
- 空间复杂度: ,我们使用的哈希表最多需要存储 words 中所有字符串的计数。
Code
func findSubstring(s string, words []string) []int { |
76.最小覆盖子串
Problem: 76. 最小覆盖子串
思路
典型的滑动窗口问题,要求我们在字符串 s 中找到最小的子串,使得这个子串包含字符串 t 中的所有字符。
我们用两个指针 left 和 right 表示一个滑动窗口,初始时都指向字符串 s 的起始位置。随着 right 指针的移动,我们扩展窗口的右边界,将字符逐个加入窗口。当窗口内包含了字符串 t 的所有字符(包括重复字符),我们可以尝试缩小窗口(即移动 left 指针),以找到更小的子串。在每次找到符合条件的子串后,记录其长度,并与之前找到的最小子串长度进行比较,保留更小的子串。
一个哈希表 targetCount 用来存储字符串 t 中每个字符的频率。另一个哈希表 windowCount 用来存储当前滑动窗口中每个字符的频率。我们通过比较 windowCount 和 targetCount 来判断窗口是否包含了 t 中的所有字符。
扩展窗口:将 right 指针指向的字符加入 windowCount,然后向右移动 right 指针。
收缩窗口:当窗口包含了 t 中的所有字符时,尝试移动 left 指针缩小窗口,直到窗口不再包含 t 的所有字符为止。
解题过程
初始化:
使用 targetCount 记录字符串 t 中的每个字符及其出现次数。
初始化两个指针 left 和 right,right 从头开始遍历字符串 s。
变量 minLen 用来记录当前找到的最小子串的长度,minStart 用来记录这个子串的起始位置。
滑动窗口遍历:
随着 right 指针的移动,将字符加入 windowCount,并检查窗口是否包含了 t 中的所有字符。
如果当前窗口包含了 t 的所有字符,记录当前窗口的长度,并尝试缩小窗口,即移动 left 指针。
更新最小子串:
每次找到符合条件的窗口时,比较其长度与 minLen,如果更小,则更新 minLen 和 minStart。
最终结果:
如果 minLen 没有被更新过,说明不存在满足条件的子串,返回空字符串 “”。
否则,返回 s 中从 minStart 开始、长度为 minLen 的子串。
复杂度
- 时间复杂度: ,其中 m 是字符串 s 的长度,n 是字符串 t 的长度。每个字符在滑动窗口内最多进出一次,因此整个算法的时间复杂度是线性的。
- 空间复杂度: (因为英文字母的数量是固定的,为 26 个),哈希表的大小不会超过 26 个字符。
Code
func minWindow(s string, t string) string { |
36.有效的数独
Problem: 36. 有效的数独
思路
根据题给要求检查数独即可,分别按照行、列、小九宫格来依次检查。
解题过程
创建两个二维数组rows和columns,一个三维数组subboxes,用来储存九宫格在对应位置上的数字出现次数。遍历一遍数组,注意到九宫格中的位置i、j,分别对应rows[i],columns[j],subboxes[i/3][j/3]。于是只要扫描到一个数字,就将三个表格的index分别+1,index=board[i][j]-1
复杂度
- 时间复杂度:
- 空间复杂度:
Code
func isValidSudoku(board [][]byte) bool { |
54.螺旋矩阵
Problem: 54. 螺旋矩阵
思路
题目要求按照顺时针螺旋顺序返回矩阵中的所有元素。我们可以通过设置四个边界(上、下、左、右)来控制遍历方向,并不断缩小边界范围,直到遍历完所有元素。
这种方法属于模拟法,即通过人为模拟出遍历矩阵的顺序,依次遍历边界并将其缩小,直至不再有元素可遍历。
解题过程
每次遍历按以下顺序进行:
从左到右遍历当前上边界,并将上边界向下移动。
从上到下遍历当前右边界,并将右边界向左移动。
从右到左遍历当前下边界,并将下边界向上移动。
从下到上遍历当前左边界,并将左边界向右移动。
当四个边界交叉时,说明已经没有未遍历的元素,结束循环。
复杂度
- ,其中 是矩阵的行数, 是矩阵的列数。我们需要遍历矩阵中的每个元素,所以时间复杂度与矩阵中的元素数量成正比。
- (不考虑返回结果的空间),只使用了固定数量的额外变量。
Code
func spiralOrder(matrix [][]int) []int { |
48.旋转图像
Problem: 48. 旋转图像
思路
本题要求将一个 n x n
的二维矩阵表示的图像顺时针旋转 90 度,且要求 原地旋转,即不能使用额外的矩阵空间。通过分析,我们可以得出一种有效的思路:首先 转置矩阵,然后对每一行进行 水平翻转。
关键点:
- 转置矩阵:将矩阵的行和列进行交换,即将矩阵
matrix[i][j]
和matrix[j][i]
进行交换。这样,矩阵的对角线上的元素保持不变,而其他元素会发生位置变化。 - 水平翻转每一行:将矩阵中的每一行从左右两端开始交换元素,直到中间为止。
通过这两个操作,我们可以在原地完成 90 度顺时针旋转。
解题过程
第一步:转置矩阵
转置矩阵的基本操作是将矩阵的行和列交换。对于一个 n x n
的矩阵,我们只需要交换矩阵的上三角部分与下三角部分的元素。具体来说,对于每一对 (i, j),交换 matrix[i][j]
和 matrix[j][i]
。
第二步:水平翻转每一行
转置完成后,矩阵的列已经变成了行,接下来我们需要水平翻转每一行。即将每一行的第 left
个元素和第 right
个元素交换,left
从 0 开始,right
从 matrixSize - 1
开始,直到它们相遇。
为什么这些步骤能实现 90 度顺时针旋转?
因为 转置 操作会将原来的列变成行,为旋转打下基础。
水平翻转 则完成了顺时针旋转的效果,因为顺时针旋转就是先转置,然后从右至左反转每一行。
复杂度
-
时间复杂度:
转置操作和水平翻转操作都需要遍历整个矩阵,每次遍历的时间复杂度是 ,因此总的时间复杂度是 。 -
空间复杂度:
我们只使用了常数空间来交换元素,因此空间复杂度是 ,满足了题目要求的原地旋转。
Code
void rotate(int** matrix, int matrixSize, int* matrixColSize) { |
73.矩阵置零
Problem: 73. 矩阵置零
思路
本题要求我们在一个 m x n 的矩阵中,如果某个元素为零,则将其所在的行和列全部置零。并且需要使用原地算法,即不能使用额外的矩阵来辅助计算。
方法选择
为了实现原地算法,可以使用矩阵的第一行和第一列作为辅助数组,用来标记哪些行和列需要置零。这样,我们可以避免使用额外的空间,同时完成矩阵的修改。具体步骤如下:
- 标记第一行和第一列:遍历矩阵中的每个元素,如果某个元素为零,便将其所在行的第一个元素和列的第一个元素置为零。
- 处理内层矩阵:根据第一行和第一列的标记,遍历矩阵并设置相应位置的元素为零。
- 处理第一行和第一列:最后单独处理第一行和第一列,因为它们在标记过程中被修改,且需要特别处理。
解题过程
1. 检查第一行和第一列是否需要清零
首先,遍历矩阵的第一行和第一列,记录它们是否包含零。为了避免修改原矩阵,我们使用两个变量 firstRowZero
和 firstColZero
来标记第一行和第一列是否需要置零。
2. 使用第一行和第一列作为辅助数组
接着,我们遍历矩阵的其他部分,如果遇到值为零的元素,我们将该元素所在行的第一个元素和列的第一个元素设置为零。这样,这些位置会作为标记,指示相应的行和列需要置零。
3. 根据标记清零
再遍历矩阵,通过检查第一行和第一列的标记,如果对应位置的值为零,则将该元素所在行列的值置为零。
4. 处理第一行和第一列
最后,单独处理第一行和第一列,依据之前的标记决定是否将它们置为零。
复杂度
- 时间复杂度: ,需要遍历矩阵多次,每次遍历的复杂度是 。
- 空间复杂度: ,使用常数空间,只依赖输入矩阵本身进行修改。
Code
void setZeroes(int** matrix, int matrixSize, int* matrixColSize) { |
289.生命游戏
Problem: 289. 生命游戏
思路
为了在原地更新矩阵的状态,可以使用 位运算 来编码每个细胞的当前状态和下一状态。我们使用 2 位 来表示每个细胞的状态:
- 00:当前死,下一死
- 01:当前活,下一死
- 10:当前死,下一活
- 11:当前活,下一活
通过这种方式,当前状态和下一状态可以同时存储在同一个变量中,并通过位操作轻松提取。
解题过程
-
遍历每个细胞:
- 对于每个细胞,检查其周围 8 个相邻细胞,计算出其活邻居的数量。
- 根据以下规则更新当前细胞的状态:
- 如果当前是活细胞(
board[i][j] == 1
),且活邻居数为 2 或 3,则细胞保持活。 - 如果当前是死细胞(
board[i][j] == 0
),且活邻居数为 3,则细胞复活。 - 其他情况,细胞死亡。
- 如果当前是活细胞(
-
使用位运算更新状态:
- 我们使用 按位或(|) 运算将当前状态和下一状态结合起来:如果需要改变细胞的状态,就把相应的位设置为 1。
-
提取下一状态:
- 完成遍历后,使用 右移运算(
>> 1
) 将低位提取出,更新细胞的最终状态。
- 完成遍历后,使用 右移运算(
复杂度
- 时间复杂度: ,每个细胞都需要检查其 8 个相邻细胞。
- 空间复杂度: ,我们仅使用常量空间来存储临时的状态。
Code
void gameOfLife(int** board, int boardSize, int* boardColSize) { |
383.赎金信
Problem: 383. 赎金信
思路
本题可以通过统计字符出现次数来解决。我们要判断是否能从 magazine
中取出足够的字符来构成 ransomNote
。为此,可以使用一个大小为 26 的数组来记录 magazine
中每个字符的出现次数,再根据 ransomNote
中的每个字符检查是否能从 magazine
中找到足够的字符。
解题过程
-
统计字符频次:
- 使用一个数组
hash[26]
来存储magazine
中每个字符的频次,其中索引是字符与'a'
的差值(即字符'a'
的映射位置为 0,'b'
为 1,依此类推)。
- 使用一个数组
-
检查
ransomNote
中字符的需求:- 遍历
ransomNote
中的每个字符,检查该字符在magazine
中的剩余数量。如果剩余数量为 0,说明无法构成该字符,返回false
;否则减少相应字符的频次。
- 遍历
-
结束条件:
- 如果遍历完
ransomNote
后没有发现任何不足的字符,则返回true
,表示可以成功构造ransomNote
。
- 如果遍历完
复杂度
- 时间复杂度: ,其中 是
magazine
的长度, 是ransomNote
的长度。我们需要遍历magazine
和ransomNote
两次,分别统计字符频次和验证字符是否足够。 - 空间复杂度: ,我们使用的字符频次数组
hash[26]
大小固定,为常数空间。
Code
bool canConstruct(char* ransomNote, char* magazine) { |
205.同构字符串
Problem: 205. 同构字符串
思路
判断两个字符串是否是同构的。两个字符串 s
和 t
是同构的,当且仅当 s
中的每个字符可以按某种方式映射到 t
中的字符,同时保持字符的顺序一致。映射关系是双向的,即每个字符只能映射到一个唯一的字符,并且每个字符只能映射一次。
解题过程
使用两个哈希表来实现字符映射的判断:
map_s_to_t
用于记录从s
到t
的映射关系。map_t_to_s
用于记录从t
到s
的映射关系。
遍历字符串 s
和 t
,对于每个字符:
- 如果
s[i]
已经在map_s_to_t
中映射到其他字符,且不等于t[i]
,说明映射冲突,返回false
。 - 如果
t[i]
已经在map_t_to_s
中映射到其他字符,且不等于s[i]
,也说明映射冲突,返回false
。 - 如果没有冲突,就继续进行映射,保持双向一致。
通过这两个哈希表的双向映射判断,我们可以确保字符串 s
和 t
是否同构。
复杂度
- 时间复杂度: ,其中 是字符串
s
和t
的长度。我们只需要遍历一次字符串并进行常数时间的哈希操作。 - 空间复杂度: ,使用了两个哈希表来存储字符映射关系,最坏情况下需要 的空间。
Code
func isIsomorphic(s string, t string) bool { |
290.单词规律
Problem: 290. 单词规律
思路
和上一道题类似,区别在于这里需要对应的是字符串。
题目要求判断字符串 s
是否遵循规律 pattern
,即字符串 s
中的每个单词和 pattern
中的每个字符之间有一一对应的映射关系。我们需要检查:
pattern
中的字符是否一一对应到s
中的每个单词。- 每个字符映射到的单词要唯一,且每个单词映射到的字符也要唯一,保持双向映射关系。
解题过程
- 首先使用
strings.Fields(s)
来将字符串s
按照空格分割成单词,并存储在words
数组中。 - 然后利用两个哈希表来建立双向映射:
pattern_map
用来记录pattern
中字符到单词的映射。words_map
用来记录words
中单词到字符的映射。
- 遍历
pattern
和words
,检查每个字符和单词的对应关系:- 如果某个字符已经映射到一个单词,并且与当前单词不匹配,则返回
false
。 - 如果某个单词已经映射到一个字符,并且与当前字符不匹配,也返回
false
。
- 如果某个字符已经映射到一个单词,并且与当前单词不匹配,则返回
- 如果遍历完后没有冲突,说明
s
遵循规律pattern
,返回true
。
复杂度
- 时间复杂度: ,其中 是
pattern
和s
的长度。我们需要遍历一次pattern
和words
。 - 空间复杂度: ,我们使用了两个哈希表来存储映射关系,最坏情况下需要 的空间。
Code
func wordPattern(pattern string, s string) bool { |
截止至2024.12.11,更新了42题,打算坑了。
因为有些题太简单,不值得单独去发题解。
往后会单独开一个精选贴,记录我认为有价值的题目