LeetCode题解（2020-11-03至2020-11-05）

傷城~ 2022-11-22 03:06 92阅读 0赞

这几天事情太多，只能抽空来做几题，加之随机做筛选出来的简单题都感觉好难（我怀疑力扣官网对简单是不是有啥误解），所以几天都没法写解题思路，好吧，停更一周了，总算凑够了几个题，继续更，继续记录

# 题1：单调数列 #

## 题目描述 ##

如果数组是单调递增或单调递减的，那么它是单调的。

如果对于所有 i <= j，A\[i\] <= A\[j\]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A\[i\]> = A\[j\]，那么数组 A 是单调递减的。

当给定的数组 A 是单调数组时返回 true，否则返回 false。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/monotonic-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 解题思路和代码 ##

这是个简单的排序题，不过要分正序和逆序，如果直接用Python中sort和reverse函数将会很简单

class Solution:
        def isMonotonic(self, A: List[int]) -> bool:
            B = A.copy()
            C = A.copy()
            B.sort()
            C.sort()
            C.reverse()
            if A == B or A == C:
                return True
            return False

唯一要注意的是，sort和reverse函数会改变原始数组，所以最好用深拷贝  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center]  
成绩还可以

# 题2：单词规律 #

## 题目描述 ##

给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = “abba”, str = “dog cat cat dog”  
输出: true  
示例 2:

输入:pattern = “abba”, str = “dog cat cat fish”  
输出: false  
示例 3:

输入: pattern = “aaaa”, str = “dog cat cat dog”  
输出: false

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/word-pattern  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 解题思路和代码 ##

通过这题恶补了一下Python的又一个基础知识  
我的想法是将pattern中每个字母第一次出现的位置放入一个列表，又将str中每个单词第一次出现的位置放入另一个列表，如果两个列表相等，那就返回True。  
我想用index函数，index函数我只用过对列表数据索引，所以第一步是将字符串转为列表。那么如何将列表中每个元素第一次出现的位置获取到呢，可以用映射器map函数来处理  
说来这个map函数还真是经常用到，我平时也常会使用，但还真没领悟到这个函数的精髓，这次算是搞明白了  
下面引自菜鸟教程：

> Python map() 函数  
> Python 内置函数 Python 内置函数  
> 描述  
> map() 会根据提供的函数对指定序列做映射。  
> 第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的新列表。  
> 语法  
> map() 函数语法：  
> map(function, iterable, …)  
> 参数  
> function – 函数  
> iterable – 一个或多个序列  
> 返回值  
> Python 2.x 返回列表。  
> Python 3.x 返回迭代器。  
> 实例  
> 以下实例展示了 map() 的使用方法：
> 
> > def square(x) : \# 计算平方数  
> > return x \*\* 2
> 
> > map(square, \[1,2,3,4,5\]) \# 计算列表各个元素的平方  
> > \[1, 4, 9, 16, 25\]
> 
> > > map(lambda x: x \*\* 2, \[1, 2, 3, 4, 5\]) \# 使用 lambda 匿名函数  
> > > \[1, 4, 9, 16, 25\]  
> > > \#提供了两个列表，对相同位置的列表数据进行相加
> 
> > map(lambda x, y: x + y, \[1, 3, 5, 7, 9\], \[2, 4, 6, 8, 10\])  
> > \[3, 7, 11, 15, 19\]

就是说，map函数的第一个参数应该是个函数名（不需要带参数），后面第二个参数才是这个函数要处理的参数。map函数返回的是个map object，需要转成list  
好吧，挺难解释清楚，不过看上面的代码应该能理解个八九分  
下面我直接写这题的代码

class Solution:
        def wordPattern(self, pattern: str, s: str) -> bool:
            pattern = list(pattern)
            s = s.split()
            lp = list(map(pattern.index, pattern))
            ls = list(map(s.index, s))
            return lp == ls

首先我将输入的两个参数都转为列表，然后用列表对应的index函数获取每个元素第一次出现的索引，也就是map(pattern.index, pattern)这个方法  
看看成绩：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center 1]  
感觉还不错，好吧，终于明白怎么用map了，希望不是过几天又忘了

# 题3：剑指 Offer 39. 数组中出现次数超过一半的数字 #

## 题目描述 ##

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: \[1, 2, 3, 2, 2, 2, 5, 4, 2\]  
输出: 2

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 解题思路&代码 ##

看起来这题挺简单的，我第一反应想到的是排序和二分查找，但思考半天感觉无从下手。整理一下思路：

1.  对给定列表进行排序；
2.  遍历列表，注意，如果真遍历的话，那肯定也要超时了，因为列表中肯定存在多数元素，因此只需要遍历列表的半数；
3.  排序列表中存在连续超过一半的数，那么就返回这个数。

好了，这样梳理一下，开始写代码

class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            nums.sort()
            for i in range((len(nums) + 1)//2):
                if nums[i:(i+(len(nums)+1)//2)] == [nums[i]]*((len(nums)+1)//2):
                    return nums[i]

在取半数这里有点绕，我们假设nums=\[1, 2, 3, 2, 2, 2, 5, 4, 2\]  
那么nums.sort()后，nums=\[1,2,2,2,2,2,3,4,5\]，nums的长度是9，其中元素‘2’的长度为5，超过半数，应该返回2  
半数应该是(9+1)//2 = 5  
当然，如果nums的长度是10的话，半数也是5，(10+1)//2=5，所以这里一定要加1，这样就不用再来判断列表长度到底是偶数还是奇数了。  
后面就是判断条件了。  
这种算法的时间复杂度应该是O(N/2)也就是O(N)，来看看成绩  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center 2]  
我去，简直不能看，垫底啊大哥。  
那该怎么优化呢？  
我想到了一个点，既然列表中一定存在多数元素，那是不是最中间那个数肯定就是我要返回的数，比如列表长度为9，那么重复数肯定大于等于5个，那么中间那个数也就是第五个数肯定是要返回的那个；列表长度是10，那么重复数肯定大于等于6个，那第五个和第六个数也必定是要返回的那个数，因此这样就简单了。  
看下代码：

class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            nums.sort()
            return nums[((len(nums))//2)] if len(nums) > 1 else nums[0]

看下成绩：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center 3]  
这种解法的时间复杂度应该也是O(N)，因为sort排序了，但计算效率大大提升了，还是得动脑子，唉，一言难尽。  
再看看大佬们的解题思路  
有个摩尔投票

> 算法流程:  
> 初始化： 票数统计 votes = 0 ， 众数 x；  
> 循环： 遍历数组 nums 中的每个数字 num ；  
> 当 票数 votes 等于 0 ，则假设当前数字 num 是众数；  
> 当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1 ；  
> 返回值： 返回 x 即可；  
> 作者：jyd  
> 链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/  
> 来源：力扣（LeetCode）  
> 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

反正我是没理解，看看大佬的代码吧

class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            votes = 0
            for num in nums:
                if votes == 0: x = num
                votes += 1 if num == x else -1
            return x
    
    作者：jyd
    链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

看看成绩

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center 4]  
时间复杂度还是O(N)，空间复杂度有所提升。  
这题就这样吧。。

# 题4：剑指 Offer 40. 最小的k个数 #

## 题目描述 ##

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

## 解题思路&代码 ##

看我被虐这么久，总算来点安慰了

class Solution:
        def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
            arr.sort()
            return arr[:k]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center 5]  
这种写法肯定会被大佬不齿，话说高端操作是用堆排序，快速排序也行，毕竟没专门学过算法，只会用sort  
难受，好多不会，边学变思考吧，算法还是得有基础。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/6338183bc1cf4ea3ab86b9419fa79762.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/768974cbf6ac49eb97ebd9a0c16758fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/629e48a7aed1497faf1d86ae29de915e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/d5a479ff6e8943a4b8b9907bcb68ddd3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/7f2ae693f9bd4f39a4a238411e625758.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/76fef618d58e4470a65969160de13627.png