LeetCode算法训练


leetcode漫漫求索路……🛣,进行日常算法训练,就当强身健体了😢,燥起来吧……

从排序数组中删除重复项

示例 1:

1
2
3
4
5
给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

1
2
3
4
5
给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

这道题目很简单,关键词有三个:排序数组,原地删除,返回新数组长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
'''
- 排序数组
- 原地删除
- 返回新数组长度
'''
if not nums:
return 0
length=len(nums)
idx=count=0
while count<length:
if nums[count]>nums[idx]:
idx+=1
nums[idx]=nums[count]
count+=1
return idx+1

买卖股票的最佳时机

注意:你不能在买入股票前卖出股票。

示例 1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
  • 分析

    题目中要求最多允许完成一次交易,并且得到最大的收益,这是一个很明显的动态规划问题,我们可以将问题进行拆解,会发现在整个输入序列中,相邻元素之间如果后者大于前者则存在收益;否则没有收益,并且我们要的是最大的收益,那么就需要比较当前这一步的收益和之前得到的所以之间取大值,即

    $profit$为获得的收益,$sale$为卖出交个,$buy$为买入价格,由于限制了单次交易,那么买入的价格应该选择最低的价格,而卖出应该选择比上次的收益更大的价格,代码如下

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
# 边界条件
if not prices: return 0
benefit=0
# 给定一个买入的初始值
buy=prices[0]
for sale in prices[1:]:
# 找到买入的价格
buy=min(buy,sale)
# 收益为上次的计算的收益和当前的收益中最大的
benefit=max(benefit,sale-buy)
return benefit

买卖股票最佳时机 II

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

1
2
3
4
5
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
  • 分析:根据题意,求解的是累计总收益,实际上在leetcode中有一个类似的求解收益的问题是,求解的是单次投资的最大收益,那个使用动态规划的思路求解,也就是上面那道题,说到本题目,有两种思路。
    • 方法一:直接根据题意和例子进行分析,遍历价格列表,假设初始价格为a,也就是prices[0]=a,当前价格如果大于初始价格并且大于当前的下一个价格,则认为是卖出点,获得收益;如果当前价格小于初始价格,那么对初始价格进行更新,更新为当前的价格
    • 方法二:利用加法交换律,D-A=(D-C)+(C-B)+(B-A),这样思考的话就不用具体考虑当前价格和初始价格的关系,只管比较当前价格和前一个价格之间的关系,如果当前价格大于之前一个的价格,则获得收益,使用迭代的方法,遍历到价格列表最后就可获得总收益
  • 代码:将两种方法的写在了一个代码段之中,并使用注释隔开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
'''
减法交换律
c-a=(c-b)+(b-a)
'''
profit=0
# 第一种低效方法,直接题意入手
# 给定另个指针count,idx,
# 如果idx大于count并且idx大于idx+1,产生利润
# 如果idx+1,count,对count向前移动
# 所说的idx和count为对应的prices相应位置的值
'''
count=idx=0
length=len(prices)
if not prices:
return profit
while idx<length-1:
if prices[idx]>prices[count] and prices[idx]>prices[idx+1]:
profit+=prices[idx]-prices[count]
count=idx+1
elif prices[idx+1]<prices[count]:
count=idx+1
idx+=1
profit+=prices[idx]-prices[count]
'''
# 第二种高效方法,利用加法交换律
for i in range(1,len(prices)):
if prices[i-1]<prices[i]:
profit+=prices[i]-prices[i-1]
return profit

最佳买卖股票时机含冷冻期

  • 原题链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/comments/

  • 题解:

    给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

    • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
    • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
  • 示例

1
2
3
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
  • 分析

    整个购买过程包含买入,卖出和冷冻,可以创建三个数组分别表示在第i天时候对应的是买入,卖出和冷冻状态下的收益状况buy,sale,cold

    • 第i天为买入状态下的收益情况buy[i]
      • 前一天不持有股票,也就是为冷冻状态,那么今天买入得到的收益为cold[i-1]-pirces[i]
      • 前一天持有股票,那么肯定前一天为买入状态,那么今天买入得到的收益为buy[i-1]
      • 取两种情况下的最大收益情况为今天买入的收益状况
    • 第i天为卖出状态下的收益情况sale[i]
      • 前一天不持有股票,也就是前一天股票就是卖出状态,那么今天的卖出收益为sale[i-1]
      • 前一天持有股票,那么前一天为买入状态,由此,今天的卖出收益为buy[i-1]+prices[i]
    • 第i天为冷冻状态下的收益情况cold[i]
      • 前一天刚卖出,今天冷冻的收益为sale[i-1]
      • 前一天就已经冷冻,今天的冷冻收益为cold[i-1]

    最终得到的最大收益,最后一天的状况应该是卖出

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices: return 0

length=len(prices)
sale,buy,cold=[0]*length,[0]*length,[0]*length
buy[0]=-prices[0]
for i in range(1,length):
buy[i]=max(cold[i-1]-prices[i],buy[i-1])
sale[i]=max(buy[i-1]+prices[i],sale[i-1])
cold[i]=max(sale[i-1],cold[i-1])
return sale[-1]

Nim游戏

  • 原题链接:https://leetcode-cn.com/problems/nim-game/

  • 题目:

    你和你的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

    你们是聪明人,每一步都是最优解。 编写一个函数,来判断你是否可以在给定石头数量的情况下赢得游戏。

  • 示例

    1
    2
    3
    4
    输入: 4
    输出: false
    解释: 如果堆中有 4 块石头,那么你永远不会赢得比赛;
    因为无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。
  • 分析

    这是一个easy级别的题目,轮流拿掉1-3个,每次都是最优解而不是随便拿的,通过示例的分析,将二人每那一次作为一组,在一组中,买这时候对应着最少2个石头,最多6个石头,每次都是最优解,因此先拿的人肯定是要拿最少的石子,而第二个人要想胜利必须拿更多的石子,由此可以得出,只要组中的石子是4的倍数,那么肯定是先手的人输,推广到整个n中同样如此。

    1
    2
    3
    4
    5
    6
    7
    class Solution:
    def canWinNim(self, n):
    """
    :type n: int
    :rtype: bool
    """
    return False if n%4==0 else True

旋转数组

  • 原题链接:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/23/

  • 题解:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    示例 1:

    1
    2
    3
    4
    5
    6
    输入: [1,2,3,4,5,6,7] 和 k = 3
    输出: [5,6,7,1,2,3,4]
    解释:
    向右旋转 1 步: [7,1,2,3,4,5,6]
    向右旋转 2 步: [6,7,1,2,3,4,5]
    向右旋转 3 步: [5,6,7,1,2,3,4]

    示例 2:

    1
    2
    3
    4
    5
    输入: [-1,-100,3,99] 和 k = 2
    输出: [3,99,-1,-100]
    解释:
    向右旋转 1 步: [99,-1,-100,3]
    向右旋转 2 步: [3,99,-1,-100]

    说明:

    • 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
    • 要求使用空间复杂度为 O(1) 的原地算法。
  • 分析:

    这个题目很简单,右侧移动k步,如果移动的步数和数组的长度相等,那么得到的数组和原来的数组相等。可以对k于数组长度进行取余计算,数组实际移动的步数就是取余之后的结果。

    • 方法1:一次移动一个,数组左侧进行插入insert,右侧进行删除del,每次都把数组的最后一个移动0位置,删除新数组的最后一个元素
    • 方法2:使用切片移动,利用extend命令,如果取余结果为m,那么把数组的前length-m个元素添加到数组的后面构成新数组,之后删除新数组的前length-m个元素
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution:
    def rotate(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    if k<=0:
    return
    length=len(nums)
    step=k%length
    ## 方法1:
    # 后面元素向前移动,一个一个移动,移动之后删除最后一个元素
    # for i in range(step):
    # nums.insert(0,nums[-1])
    # del nums[-1]
    ## 方法2
    # 使用元素切片,把前面的整体移动到后面之后删除前面部分
    nums.extend(nums[:length-step])
    del nums[:length-step]

存在重复

  • 原题链接:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/24/

  • 题意:给定一个整数数组,判断是否存在重复元素。

    如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

    示例 1:

    1
    2
    输入: [1,2,3,1]
    输出: true

    示例 2:

    1
    2
    输入: [1,2,3,4]
    输出: false

    示例 3:

    1
    2
    输入: [1,1,1,3,3,4,3,2,4,2]
    输出: true
  • 分析:这道题真的太太太简单了,感觉是考察元组的性质,元组内部元素只能出现一次,根据这个特性直接写出代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution:
    def containsDuplicate(self, nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    ## 一步到位,直接比较元组的长度和原始列表长度,如果相等,则没有重复元素,返回False,否则返回True
    # return not len(set(nums))==len(nums)

    ## 麻烦一些,思路大体一致
    new=set()
    for i in nums:
    if i in new:
    return True
    new.add(i)
    return False

只出现一次的数字

  • 原题:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/25/

  • 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    说明:

    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

    示例 1:

    1
    2
    输入: [2,2,1]
    输出: 1

    示例 2:

    1
    2
    输入: [4,1,2,1,2]
    输出: 4
  • 分析:很简单,也是两种方法。

    • 只有一个数出现一次,其余都出现了两次,可以利用元组的性质,进行求解,该方法更好理解
    • 使用按照位进行异或运算,因为除了出现一次的其余的全部出现两次,所以出现两次的元素进行异或运算最后都会变为0,只有出现一次的会保留下来,也就是所求的结果
  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
## 方法1
## (2x+y)=sum1; x+y=sum2;可以得到y=2*sum2-sum1
return 2*sum(list(set(nums)))-sum(nums)
## 方法2
## 转化二进制,按照位异或运算
out=0
for i in nums:
out^=i
return out

两个数组的交集 II

  • 原题链接:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/26/

  • 题意:给定两个数组,编写一个函数来计算它们的交集。

    示例 1:

    1
    2
    输入: nums1 = [1,2,2,1], nums2 = [2,2]
    输出: [2,2]

    示例 2:

    1
    2
    输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出: [4,9]

    说明:

    • 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
    • 我们可以不考虑输出结果的顺序。
  • 分析:要求不用考虑输出结果的顺序,那么直接求在两个数组中的元素

  • 代码:两种思路:

      1. 直接按照题意,找出长度较短的数组,查看内部元素是否在长数组中,时间复杂度$n^2$
      1. 使用字典的方式,存储一个数组中的值以及对应出现的次数,之后另一个数组查看是否在该字典中,如果存在,字典中该key对应的value减去1。时间复杂度$nlog(n)$
      2. 利用字典形式,将nums1和num2都出现的次数都存储在字典中,字典的value为列表形式,时间复杂度为$log(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution:
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
'''
方法1:
直接按照题意,遍历长度短的数组,
看内部元素是否在短的数组内,如果存在,删除长的数组内的该元素
'''

# out=[]
# length1=len(nums1)
# length2=len(nums2)
# if length1<length2:
# sm=nums1
# bi=nums2
# else:
# sm=nums2
# bi=nums1
# for i in sm:
# if i in bi:
# out.append(i)
# bi.remove(i)
# return out


'''
方法2:
使用字典
'''
# dire={}
# out=[]
# for i in nums1:
# if i not in dire:
# dire[i]=0
# dire[i]+=1

# for i in nums2:
# if i in dire and dire[i]>0:
# dire[i]-=1
# out.append(i)
# return out
'''
方法3:
排名前列的算法,同样是利用字典的方法,不过非常巧妙
'''
maps={}
out=[]
for i in nums1:
if i not in maps:
maps[i]=[1,0]
else:
maps[i][0]+=1

for i in nums2:
if i in maps:
maps[i][1]+=1
for i in maps:
if maps[i][1]>0:
howmany=min(maps[i])
for j in range(howmany):
out.append(i)
return out

加一

  • 原题链接:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/27/

  • 题意:给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

    最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。

    你可以假设除了整数 0 之外,这个整数不会以零开头。

    示例 1:

    1
    2
    3
    输入: [1,2,3]
    输出: [1,2,4]
    解释: 输入数组表示数字 123。

    示例 2:

    1
    2
    3
    输入: [4,3,2,1]
    输出: [4,3,2,2]
    解释: 输入数组表示数字 4321。
  • 分析:两种思路

    1. 直接在数组上进行操作,进行输入数组原地修改,空间复杂度$O(1)$时间复杂度$O(n)$,更优选择

    2. 把数组转换成数字,进行+1操作之后再转换回去,空间O2,时间On

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution:
    def plusOne(self, digits):
    """
    :type digits: List[int]
    :rtype: List[int]
    """
    ##方法1 直接按照加法法则从后向前移动,
    length=len(digits)
    count=1
    for idx in range(-1,-length-1,-1):
    s=digits[idx]+count
    cur,res=s%10,s//10
    count=res
    digits[idx]=cur

    if count:
    digits.insert(0,1)
    return digits
    ## 方法2
    ## 把数组转换成字符串
    # ori=int(''.join(str(i) for i in digits))
    # ori+=1
    # out=str(ori)
    # return list(int(i) for i in out)

移动零

  • 原题链接:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/28/

  • 题意:给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

    示例:

    1
    2
    输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]

    说明:

    1. 必须在原数组上操作,不能拷贝额外的数组。
    2. 尽量减少操作次数。
  • 分析:遍历整个数组,遍历的次数为数组的长度,当遇到为0时,append一个0,并且删除当前值,并且继续从当前值遍历

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution:
    def moveZeroes(self, nums):
    """
    :type nums: List[int]
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    '''
    count表示遍历的次数,index代表数组的索引,如果不添加遍历次数的限制,会出现死循环情况
    '''
    idx=0
    count=0
    while count<len(nums):
    if nums[idx]==0:
    nums.append(0)
    del nums[idx]
    else:
    idx+=1
    count+=1

两数之和

  • 原题链接:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/29/

  • 题意:给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

    你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

    示例:

    1
    2
    3
    4
    给定 nums = [2, 7, 11, 15], target = 9

    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
  • 分析:两数之和为target,可以认为一个为a,另一个为target-a

    • 使用哈希的方式,假设当前值为cur,key为(target-cur),对应的value为idx
  • 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 哈希方法
maps={}
out=[]
for idx in range(len(nums)):
if nums[idx] not in maps:
maps[target-nums[idx]]=[idx]
else:
maps[nums[idx]].append(idx)
return maps[nums[idx]]

两数相加

  • 原题链接https://leetcode-cn.com/problems/add-two-numbers/

  • 题解:给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

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

示例:

1
2
3
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
  • 分析:该题一目了然,使用链表的形式模拟了十进制加法运算。根节点代表低位,next代表了高位,直至给定的两个链表全部加完,即next为none。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
tmp = ListNode(0) # 创建链表,初始值为0
out=tmp # out为要返回链表
count=0
'''
while 遍历解释:
终止条件:给定的l1,l2全部结束
遍历过程:
逐位遍历,当前为初始值为0,根据l1,l2是否存在决定是否当前为是否加和
对当前进行10的取余“%”运算和取整“//”运算,取余所得为当前位的值,取整所得为下一位的初始值
依次遍历,直至l1,l2全部结束
'''
while l1 or l2:
sum_cur=count
if l1:
sum_cur+=l1.val
l1=l1.next
if l2:
sum_cur+=l2.val
l2=l2.next
cur=(sum_cur)%10
count=(sum_cur)//10
out.next=ListNode(cur)
out=out.next
'''
判断当l1,l2遍历完之后剩余是否为1,如果是则为out加上1
'''
if count:
out.next=ListNode(1)
# 如果没有下面语句,返回的out只会剩下循环之后的最后一位
out=tmp.next
return out


最小栈

  • 原题链接 https://leetcode-cn.com/problems/min-stack/

  • 题意

    设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

    • push(x) — 将元素 x 推入栈中。
    • pop() — 删除栈顶的元素。
    • top() — 获取栈顶元素。
    • getMin() — 检索栈中的最小元素。
  • 示例

    1
    2
    3
    4
    5
    6
    7
    8
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin(); --> 返回 -3.
    minStack.pop();
    minStack.top(); --> 返回 0.
    minStack.getMin(); --> 返回 -2.
  • 分析

    这道题目考察的堆栈的理解,对于堆栈结构使用的是先进后出的策略,类似于摞盘子,先放的盘子是在最下面,后方的盘子在最上面,取盘子的时候先取的都是最后放的,

    • push操作

      将元素压入栈中,也就是为栈append一个元素

    • pop操作

      删除栈顶的元素,也就是对栈进行pop操作,删除最后添加的元素

    • top

      获取栈顶匀速,也就是返回栈中最后添加的元素

    • getMin

      获取栈的最小元素,并且是在常数时间内,也就是不能说那个min()的方式,因为这种方式的时间复杂度为$O(n)$,题目要求的是$O(1)$,基于此,可以创建一个临时数组只用来存储最小的元素,当进行getMin操作的时候,返回该临时数组的最后一个元素

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class MinStack:

def __init__(self):
"""
initialize your data structure here.
"""
self.data=[]
self.min_stack=[]

def push(self, x):
"""
:type x: int
:rtype: void
"""
self.data.append(x)

if not self.min_stack:
self.min_stack.append(x)
else:
if x<self.min_stack[-1]:
self.min_stack.append(x)
else:
self.min_stack.append(self.min_stack[-1])


def pop(self):
"""
:rtype: void
"""

self.data.pop()
self.min_stack.pop()


def top(self):
"""
:rtype: int
"""
return self.data[-1]

def getMin(self):
"""
:rtype: int
"""

return self.min_stack[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

Note

这里有一个要注意的地方,实际上对于使用数组结构模拟栈的结构形式,有两种实现方式

  • insert,del

    对于push操作,使用insert(0,x)进行,也就是新元素插入数组的顶部

    对于pop操作,删除的是最近添加的元素,使用del data[0]

  • Apped,pop

    对于push操作,使用append(X),将新元素添加到数组的尾部

    对于pop操作,直接使用data.pop()

比较这两种方法,对于第一种的insert+del的方式,元素压入和删除元素,数组中的其他元素都要顺序后移或前移一位,而第二中的append+pop的方式则不会这样,因此在操作时间上,第二种方法是更优的。对于数组结构,都要优先使用尾部添加或删除的方式。

3的幂

  • 原题链接 https://leetcode-cn.com/problems/power-of-three/

  • 题意

    给定一个整数,写一个函数来判断它是否是 3 的幂次方。

  • 示例

    示例 1:

    1
    2
    输入: 27
    输出: true

    示例 2:

    1
    2
    输入: 0
    输出: false

    示例 3:

    1
    2
    输入: 9
    输出: true

    示例 4:

    1
    2
    输入: 45
    输出: false
  • 进阶:
    你能不使用循环或者递归来完成本题吗?

  • 分析

    • 递归方法

      简单易行,每次当前数字和3取余

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isPowerOfThree(self, n):
"""
:type n: int
:rtype: bool
"""

while n>1:
if n%3!=0:
break
n/=3
return n==1

二叉树的坡度

  • 原题链接 https://leetcode-cn.com/problems/binary-tree-tilt/

  • 题意

    给定一个二叉树,计算整个树的坡度。

    一个树的节点的坡度定义即为,该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。

    整个树的坡度就是其所有节点的坡度之和。

  • 示例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    输入: 
    1
    / \
    2 3
    输出: 1
    解释:
    结点的坡度 2 : 0
    结点的坡度 3 : 0
    结点的坡度 1 : |2-3| = 1
    树的坡度 : 0 + 0 + 1 = 1
  • 注意:

  1. 任何子树的结点的和不会超过32位整数的范围。
  2. 坡度的值不会超过32位整数的范围。
  • 分析

    根据每个节点的坡度的定义,对于某个节点当前节点和左右子树之和为left+right+root.val,依次为递归的返回式,进行后续遍历

    1
    2
    3
    4
    5
    def find_sum(root):
    left=find_sum(root.left)
    right=find_sum(root.right)
    out+=abs(left-right)
    return root.val+left+right

    通过该遍历得到每个节点计算得到的left-right之和,得到的out即为所求,因此,整个代码可以为

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    # Definition for a binary tree node.
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None

    class Solution:
    def findTilt(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    self.out = 0
    def find_sum(root):
    if not root: return 0
    left = find_sum(root.left)
    right = find_sum(root.right)
    # 计算坡度,左右节点相减
    self.out += abs(left - right)
    # 返回以当前的节点为根节点的所有节点之和,进入下一步的递归
    # root.val + left + right构成一个完成的节点
    return root.val + left + right
    find_sum(root)
    return self.out

寻找两个有序数组的中位数

  • 原题链接 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

  • 题意

    给定两个大小为 m 和 n 的有序数组 nums1nums2

    请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))

    你可以假设 nums1nums2 不会同时为空。

  • 示例

    示例 1:

    1
    2
    3
    4
    nums1 = [1, 3]
    nums2 = [2]

    则中位数是 2.0

    示例 2:

    1
    2
    3
    4
    nums1 = [1, 2]
    nums2 = [3, 4]

    则中位数是 (2 + 3)/2 = 2.5
  • 分析

    先说中位数的定义

    對於有限的數集,可以通過把所有觀察值高低排序後找出正中間的一個作爲中位數。如果觀察值有偶數個,則中位數不唯一,通常取最中間的兩個數值的平均數作爲中位數。

    由此可以看到,对于中位数,针对数组长度的奇偶数不同而计算方法不同

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
l1 = len(nums1)
l2 = len(nums2)
Length = int(l1 + l2)

nums = nums1 + nums2
nums.sort()

# 如果合并数组为偶数,那么中位数就是中间位置的两个数之和/2
if (Length % 2) == 0:
out = (nums[int(Length/2)] + nums[int((Length / 2) - 1)]) / 2
else:
# 如果长度为奇数,中位数对应的索引为长度/2
out = nums[int((Length - 1) / 2)]
return out

复原ip地址

  • 原题链接:https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1044/

  • 题意

    给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。

  • 示例

    1
    2
    输入: "25525511135"
    输出: ["255.255.11.135", "255.255.111.35"]
  • 分析

    本体考察的是图搜索算法,分为广度优先搜索和深度优先搜索

    对于ip的格式

    • ip分为4断格式,每段之间数字为0–255之间的数字
    • 数字不能以0开头,除了0本身

    对于该判断可以得到条件函数

    1
    2
    3
    4
    def isvalid(s):
    if str(int(s))==s and 0<=int(s)<=255:
    return True
    return False

    对于每个字段之间,可能的数字数量为为1,2,3,将符合条件字符串分段存储,如果最后将给定的字符串分割完毕并且满足条件的分段字符串为4段,可以得到满足条件的一个分割ip地址,使用递归的方式进行依次调用查找函数。

  • 代码

    • 递归方式
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    class Solution:
    def restoreIpAddresses(self, s):
    """
    :type s: str
    :rtype: List[str]
    """
    # 边界条件,大于12个或者小于4个无法构成有效ip地址
    if len(s) > 12 or len(s)<4:
    return []
    res = []
    dfs(s, [], res)
    return res

    def isvalid(s):
    if 0<=int(s)<=255 and str(int(s))==s:
    return True
    return False

    def dfs(s, path, res):
    # 剪枝条件,如果剩余的有效的ip字符段数量无法满足最大的字符数量条件退出该条路径
    if len(s) > (4 - len(path)) * 3 or len(s)<4-len(path):
    return
    # 如果s被查找完毕并且找的ip字符段数量满足收敛条件,添加到res中
    if not s and len(path) == 4:
    res.append('.'.join(path))
    return
    # 每个ip字段有可能为1,2,3个
    for i in range(1, 4):
    # 判断剩余的s是否满足条件
    if i > len(s):
    continue
    # 是否满足ip格式
    if isvalid(s[:i]):
    # 如果满足条件,path中存储满足条件的字符段并重复调用寻找函数path+[s[:i]]
    # 寻找区间缩小为剩余的字符串s[:i]
    dfs(s[i:],path+[s[:i]],res)

    • 对于递归的方式,由于需要重复对函数本身进行调用,因此容易造成内存溢出,将递归的方式修改成迭代方式,更加直白,类似于暴力搜索的方式
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution:
    def restoreIpAddresses(self, s):
    """
    :type s: str
    :rtype: List[str]
    """
    def isvalid(s):
    if s and 0<=int(s)<=255 and str(int(s))==s:
    return True
    return False

    res=[]
    for i in range(1,4):
    f1=s[:i]
    if not isvalid(f1):
    continue
    for j in range(i+1,i+4):
    f2=s[i:j]
    if not isvalid(f2):
    continue
    for k in range(j+1,j+4):
    f3,f4=s[j:k],s[k:]
    if not isvalid(f3) or not isvalid(f4):
    continue
    res+=[f1+'.'+f2+'.'+f3+'.'+f4]
    return res

反转字符串的单词

  • 链接:https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1011/

  • 题意

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

  • 示例

    1
    2
    输入: "the sky is blue",
    输出: "blue is sky the".
  • 说明

    • 无空格字符构成一个单词。
    • 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
    • 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
  • 进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。

  • 分析

    对于python来说,直接进行字符串分割,然后反转列表输出字符串

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
# 一步步来
# s=s.strip() # 去除字符串前后声明符合
# s=s.split() # 分割字符串
# s.reverse() # 反转列表
# s=' '.join(s) # 生成字符串
# return s

# 一步到位
return ' '.join(reversed(s.strip().split()))

搜索旋转排序数组

  • 题意

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

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

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

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

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

  • 示例

    1
    2
    3
    4
    5
    输入: nums = [4,5,6,7,0,1,2], target = 0
    输出: 4

    输入: nums = [4,5,6,7,0,1,2], target = 3
    输出: -1
  • 分析

    时间复杂度是$O(\log n)$首先想到的就是二分查找法,对于该题目,由于涉及两个查找,首先是对单调递增区间的查找,之后是在单调区间内的查找

    • 对于单调递增权健的查找

      实际上就是找到两个单调区间的临界点,该临近点的右侧是单调递增区间并且,该临界点大于右侧区间的所有点,该临界点的左侧也是单调递增区间,同样,该临界点也大于左侧的区间内的左右点,使用二分查找的方式确定该临界点,确定右侧的单调区间,设置left,right对应右侧单调区间的起始索引,

      • 如果中值大于右侧的值,那么右侧区间在在中值的更右侧,此时left=mid+1
      • 如果中值小于右侧的值,那么该中值的位置位于右侧的单调区间内,此时,right=mid
    • 找到单调区间之后可以使用标准的二分查找方式确定目标值的索引

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
# log(n)标准的二分查找
def binarysearch(tar,num):
index=-1
lf=0
rg=len(num)-1
while lf <=rg:
mid=(rg+lf)//2
if tar>num[mid]:
# 如果中间值小于目标值,搜索中间值右侧区间,left=mid+1
lf=mid+1
elif tar<num[mid]:
# 如果中间值大于目标值,搜索中间值左侧的区间,rigjt=mid-1
rg=mid-1
else:
index=mid
break
return index

# 边界条件
if not nums:
return -1
if len(nums)==1:
if nums[0]==target:
return 0
else:
return -1
# 查找右侧单调区间起始索引点
left = 0
right = len(nums) -1
while left <right:
mid=(right+left)//2
# 反转之后右侧是递增的,找到右侧的单调区间的起始索引值left
if nums[mid]>nums[right]:
left=mid+1
else:
right=mid
turned=left
find_para=nums[:turned]
res=binarysearch(target,find_para)
#在左侧区间没找到
if res==-1:
res=binarysearch(target,nums[turned:])
if res!=-1:
res+=turned
return res

第k个排列

  • 原题链接 https://leetcode-cn.com/problems/permutation-sequence/

  • 题意

    给出集合 [1,2,3,…,*n*],其所有元素共有 n! 种排列。

    按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

    1. "123"
    2. "132"
    3. "213"
    4. "231"
    5. "312"
    6. "321"

    给定 nk,返回第 k 个排列。

  • 说明:

  • 给定 n 的范围是 [1, 9]。

  • 给定 k 的范围是[1, n!]。

示例 1:

1
2
输入: n = 3, k = 3
输出: "213"

示例 2:

1
2
输入: n = 4, k = 9
输出: "2314"
  • 分析

    参考https://cloud.tencent.com/developer/article/1335755

    本题目考察的也是一种回溯法,但是直接使用递归的方法计算全排列然后再拿到全排列数组中的第k个元素会存在超时的问题,对于得到字符串全排列的方法为

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution:
    def getPermutation(self, n, k):
    """
    :type n: int
    :type k: int
    :rtype: str
    """
    s=''.join(str(i) for i in list(range(1,n+1)))
    # 迭代方法
    self.res=[s]
    def Permutation(ss):
    res=[]
    if len(ss) <= 1:
    return ss
    for i in range(len(ss)):
    # 使用map和lambda函数
    # 递归的计算ss[:i] + ss[i+1:]
    for n in map(lambda x:ss[i] + x, Permutation(ss[:i] + ss[i+1:])):
    res.append(n)
    return res
    self.res=Permutation(s)
    return self.res[k-1]

    对于递归的方法计算复杂度是在是太高,可以稍微修改一下为

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution:
    def getPermutation(self, n, k):
    """
    :type n: int
    :type k: int
    :rtype: str
    """
    s=''.join(str(i) for i in list(range(1,n+1)))

    def helper(ss, res, path):
    if not ss:
    # 如果ss为空,那么将前面得到的path存入到res中
    res.append(path)
    else:
    for i in range(len(ss)):
    # 将当前字符串添加入path中,并递归计算剩余的元素
    helper(ss[:i] + ss[i+1:], res, path + ss[i])
    self.res=[]
    helper(s, self.res, '')
    return self.res[k-1]

    上面两个是基于先计算字符串的全排列然后再返回所有全排列的第k-1个元素的思路,这两种方法都会存在运算超时的问题,肯定是有问题的。

    重新分析,

    • 对于n个数字,范围是1-9,那么全排列的可能性为n!

    • 加入给定n=4,那么数字为1234,并且要求的k是得到的所有排列从小到大排列之后的第k个元素

      • 1开头+(2,3,4)全排列
      • 2开头+(1,3,4)全排列
      • 。。。
        • 12开头+(3,4全排列)
        • 13开头+(2,4)全排列

      可以逐位计算得到最终的字符串

    • 第一位元素对应着(k/(n-1)!),第二位对应着(k%(n-1)!)/(n-2)!,以此类推

    代码如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    class Solution:
    def getPermutation(self, n, k):
    """
    :type n: int
    :type k: int
    :rtype: str
    """
    # n个数字存在n!全排列
    # 每个数字开头,存在(n-1)!种全排列
    nums = list(range(1, n+1))
    if k == 1:
    return "".join(str(i) for i in nums)
    fact = 1
    # 对于第一个个字开头的情况存在着n-1种全排列
    for i in range(2, n):
    fact *= i

    _round = n - 1
    # 求的是第k个元素,对于列表中对应着k-1的索引
    k -= 1
    Res = []
    # 找到排列中的n个元素
    # 对于每个元素,根据k的值进行计算
    # 第一个元素,对应着(n-1)!种全排列可能,使用int(k/(n-1)!)得到第一位的元素对应的nums中的位置
    # 第二个元素,对应着(n-2)!种全排列可能,使用int(k/(n-2)!)得到第二位元素对应的nums中的位置
    # 由此,一次类推,逐渐求出每位的元素
    while _round >= 0:
    index = int(k / fact)
    # 对k取余,得到下一位对应的排列可能的数量
    k %= fact
    # 当前位元素在nums中的位置,并删除nums中的这个元素
    Res.append(nums[index])
    nums.remove(nums[index])
    # 如果还有下一位要进行计算,那么对fact进行更新,上一位存在(n-1)!种可能
    # 那么下一位存在(n-2)!种可能
    if _round > 0:
    fact /= _round
    _round -= 1
    return "".join(str(i) for i in Res)

朋友圈

  • 原题链接 https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1036/

  • 题意

    班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。

    给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

  • 示例

    1
    2
    3
    4
    5
    6
    7
    输入: 
    [[1,1,0],
    [1,1,0],
    [0,0,1]]
    输出: 2
    说明:已知学生0和学生1互为朋友,他们在一个朋友圈。
    第2个学生自己在一个朋友圈。所以返回2。
    1
    2
    3
    4
    5
    6
    输入: 
    [[1,1,0],
    [1,1,1],
    [0,1,1]]
    输出: 1
    说明:已知学生0和学生1互为朋友,学生1和学生2互为朋友,所以学生0和学生2也是朋友,所以他们三个在一个朋友圈,返回1。
  • 注意

    1. N 在[1,200]的范围内。
    2. 对于所有学生,有M[i][i] = 1。
    3. 如果有M[i][j] = 1,则有M[j][i] = 1。
  • 分析

    对于本题来说,有三种解体方法,

    • DFS
    • BFS
    • 查并集

    对于这种搜索的问题,要优先考虑图搜索的相关算法,在图搜索中包含深度优先搜索DFS,广度优先搜索BFS。

    • 广度优先搜索

      BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问,则算法中止。
      BFS属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

      1
      2
      3
      4
      5
      算法流程:
      1.首先将根节点放入队列中。
      2.从队列中取出第一个节点,并检验它是否为目标。如果找到目标,则结束搜寻并回传结果。否则将它所有 尚未检验过的直接子节点加入队列中。
      3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
      重复步骤2。
    • 深度优先搜索

      它沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

      1
      2
      3
      4
      算法流程
      1.访问顶点v;
      2.依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
      3.若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶 点均被访问过为止。

    在图论中,能使用BFS的一般也能使用DFS。

    • DFS代码

    对于本题目,一共存在n个人,使用深度优先搜索的方法,首先设置一个状态列表,从每个节点出发,如果这个节点不再状态列表内,那么查找该人的朋友圈,关于该人朋友圈的查找方法为,如果这个人不在已经状态列表中,并且这个人和查找的节点的人存在朋友关系,那么把这个人加入到状态信息中并且继续查找这个人对饮的朋友信息。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution:
    def findCircleNum(self, M):
    """
    :type M: List[List[int]]
    :rtype: int
    """
    cnt, N = 0, len(M)
    vset = set()
    def dfs(n):
    for x in range(N):
    if M[n][x] and x not in vset:
    vset.add(x)
    dfs(x)
    for x in range(N):
    if x not in vset:
    cnt += 1
    dfs(x)
    return cnt
    • BFS代码

    如果是广度优先搜索的方法,需要借助一个队列来协助,遍历

    (1)可以先找到一个人,把这个人的所有朋友都入队。
    (2)然后依次出队,把朋友的朋友都入队,已经入过队列的,则不再入队。
    (3)直到不再有朋友入队,而且已经出队完成,说明现在已经组成了一个朋友圈。
    (4)然后把剩下的没被分到朋友圈里面的,同学,再次入队,进行下一个朋友圈的计算,依次循环直到结束。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution:
    def findCircleNum(self, M):
    """
    :type M: List[List[int]]
    :rtype: int
    """
    cnt, N = 0, len(M)
    vset = set()
    # bfs搜索算法
    def bfs(n):
    # 将该人添加到队列中
    q = [n]
    while q:
    # 依次出队,第一次出队的是节点本身
    # 找到和该节点满足朋友关系的人之后再找这些朋友的朋友
    n = q.pop(0)
    # 找到该节点人对应的所有朋友,
    # 将朋友关系的添加到队列中,此外在将此添加到状态列表中
    for x in range(N):
    # 如果满足朋友关系但是该人已经在状态列表中,那么这个人不再入队列
    # 目的是剪枝去重,如果a和bc都是朋友关系,那么不再查找bc之间的关系
    if M[n][x] and x not in vset:
    vset.add(x)
    q.append(x)

    for x in range(N):
    if x not in vset:
    cnt += 1
    # 对该人进行bfs搜索
    bfs(x)

    return cnt
    • 查并集
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution:
    def findCircleNum(self, M):
    """
    :type M: List[List[int]]
    :rtype: int
    """
    N = len(M)
    # 假设每个人是相互独立的
    f = list(range(N))

    def find(x):

    while f[x] != x:
    x = f[x]
    return x

    for x in range(N):
    # 向前搜索
    for y in range(x + 1, N):
    # 如果满足朋友关系
    if M[x][y]:
    # 满足朋友关系的话,将f中的x的节点的值进行更新
    # 更新为与其为朋友关系的人值
    # 更新之后,如果是一个朋友圈的,那么在f中的值是相同的
    f[find(x)] = find(y)
    return sum(f[x] == x for x in range(N))

最长回文子串

  • 原题链接:https://leetcode-cn.com/explore/interview/card/tencent/221/array-and-strings/896/

  • 题意:

    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

  • 示例 1:

    1
    2
    3
    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。

    示例 2:

    1
    2
    输入: "cbbd"
    输出: "bb"
  • 分析

    • 暴力搜索

    这是一道经典题目,直接暴力搜索肯定可以完成,遍历整个字符串,以当前位置为中心进行前后查找,判断前后位置对应的字符是否相等,直到找到不相同的字符,跳出循环;此外还要判断当前位置的字符和前后位置的字符是否为连续相同的字符,直到遍历完整个字符串,时间复杂度为$O(n^3)$

    • Manacher算法

    参考链接 https://segmentfault.com/a/1190000003914228

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if not s or len(s)==1: return s
l = len(s)
max_length = 0
palindromic = ''
for i in range(l):
x = 1
# 以当前点为中心前后寻找
while (i - x) >= 0 and (i + x) < l:
if s[i + x] == s[i - x]:
x += 1
else:
break
# 找到不满足条件的点之后当前已经进行了x+1操作,当前步减去1
x -= 1
# 更新长度和返回的回文子串
if 2 * x + 1 > max_length:
max_length = 2 * x + 1
palindromic = s[i - x:i + x + 1]
# 有可能相邻两位相同,这个时候要进行要进行特殊移动,前移动也行后移动也行的
# 例如字符串为abbc,如果当前位对应着第一个b,那么前后分别为ba,不满足上面的条件,
# 上面的方法可以提取技术哥相同的相邻数字
# 使用下面的条件判定,一直找到不同的数字,对于偶数个相同的相邻数字使用下面的方法提取
x = 0
if i + 1 < l:
while (i - x) >= 0 and (i + 1 + x) < l:
# 当前为为i,右侧为i+1+x,左侧为x
if s[i + 1 + x] == s[i - x]:
x += 1
else:
break
x -= 1
#
if 2 * x + 2 > max_length:
max_length = 2 * x + 2
palindromic = s[i - x:i + x + 2]
if palindromic == '':
palindromic = s[0]
return palindromic
  • Manacher 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
s='#'+'#'.join(s)+'#'

RL=[0]*len(s)
MaxRight=0
pos=0
MaxLen=0
out=""
for i in range(len(s)):
if i<MaxRight:
RL[i]=min(RL[2*pos-i], MaxRight-i)
else:
RL[i]=1
#尝试扩n展,注意处理边界
while i-RL[i]>=0 and i+RL[i]<len(s) and s[i-RL[i]]==s[i+RL[i]]:
RL[i]+=1
#更新MaxRight,pos
if RL[i]+i-1>MaxRight:
MaxRight=RL[i]+i-1
pos=i
#更新最长回文串的长度
# MaxLen=max(MaxLen,RL[i])
# return MaxLen-1
if RL[i]>MaxLen:
MaxLen=RL[i]
out=s[i-RL[i]+1:i+RL[i]]
return out.replace('#','')

m个苹果n个盒子

这是一个经典的算法题,本题的前提假设是,苹果是相同的,盒子是相同的,并且允许有的盒子空置,问有多少种分法

迭代方法

  • 如果苹果数量>=盒子的数量,以有盒子为空为分界,有两种情况

    • 至少一个盒子为空,那么find(m,n-1)
    • 没有盒子为空,那么先在所有的盒子里各放置一个苹果,这个不会影响分配结果,将剩余的苹果分配给这m个盒子,那么find(m-n,n)
  • 如果苹果的数量<盒子的数量

    肯定至少会有一些盒子是空的,又因为盒子的相同的,那么先去掉一些盒子(n-m),并不会影响分配方案,也就是将这些苹果分配给剩下的这些盒子,那么对应find(m,m)

  • 边界条件

    • 当剩下的盒子数量为1时,不管剩下多少盒子,剩下的这些苹果必须全部放在这个盒子里面,也就是对应着1中分配方案
    • 当剩下的苹果数量为0时,这个时候已经没有苹果了,也是一种分配方案
1
2
3
4
5
6
7
def find(m,n):
if m==0 or n==1:
return 1
if m<n:
return find(m,m)
else:
return find(m-n,n)+find(m,n-1)

m个苹果n个人

本题是上一个题目”m个苹果n个盒子”的升级版。

苹果相同,人是不同的,并且允许有的人拿不到苹果,问多少种分法

分析

假设存在m个苹果,n个人来分,先给一个人拿一个苹果,那么剩下的m-1个苹果,由剩下的人来分,剩下了可能是n个人,也可能是n-1个人;直到剩下的苹果全部分完,在递归过程中,每次当前的人分的一个苹果,在查看剩下的m-1个苹果别的分配情况,苹果分完之后,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def nums(m,n):

result=[]
out=[0]*n

def find(m,n,p):

if m==0:
print('out:',out)
# result.append(out)
# print(result)
return

for i in range(p,n):
out[i]=out[i]+1
find(m-1,n,i)
out[i]=out[i]-1

find(m,n,0)
return result

res=nums(3,3)
赏杯咖啡!