LeetCode题解（2020-10-23）

Dear 丶 2022-12-17 08:54 60阅读 0赞

从今天开始，有空就开始做题，主要不想让脑子太迟钝，先从简单的题目开始。

# 题1：重塑矩阵 #

## 题目描述 ##

在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。

给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

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

## 解题思路 ##

numpy中不是有reshape函数么，何不直接调用

## 提交代码 ##

class Solution(object):
        
        def matrixReshape(self, nums, r, c):
            """
            :type nums: List[List[int]]
            :type r: int
            :type c: int
            :rtype: List[List[int]]
            """
            import numpy as np
            nums_np = np.array(nums)
            if r * c != nums_np.shape[0] * nums_np.shape[1]:
                return nums
            else:
                return nums_np.reshape(r,c).tolist()

## 提交情况 ##

![在这里插入图片描述][20201023112012208.png_pic_center]

# 题2：分糖果 #

## 题目描述 ##

给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

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

## 解题思路 ##

用set函数删除重复值，判断非重复集合长度与原列表长度一半的大小

## 提交代码 ##

class Solution(object):
        def distributeCandies(self, candies):
            """
            :type candies: List[int]
            :rtype: int
            """
            hf = len(candies)/2
            c = set(candies)
            if len(c) > hf:
                return hf
            else:
                return len(c)

## 提交情况 ##

![在这里插入图片描述][20201023113329466.png_pic_center]

# 题3:检查单词是否为句中其他单词的前缀 #

## 题目描述 ##

给你一个字符串 sentence 作为句子并指定检索词为 searchWord ，其中句子由若干用 单个空格 分隔的单词组成。

请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。

如果 searchWord 是某一个单词的前缀，则返回句子 sentence 中该单词所对应的下标（下标从 1 开始）。  
如果 searchWord 是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标）。  
如果 searchWord 不是任何单词的前缀，则返回 -1 。  
字符串 S 的 「前缀」是 S 的任何前导连续子字符串。

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

## 解题思路 ##

split函数将字符串转为列表，然后在列表中遍历搜索判断是否存在searchWord

## 提交代码 ##

class Solution(object):
        def isPrefixOfWord(self, sentence, searchWord):
            """
            :type sentence: str
            :type searchWord: str
            :rtype: int
            """
            s = sentence.split(' ')
            for i in range(len(s)):
                if s[i][:len(searchWord)] == searchWord:
                    return i + 1
            return -1

## 提交情况 ##

![在这里插入图片描述][20201023115421336.png_pic_center]

# 题4：统计有序矩阵中的负数 #

## 题目描述 ##

给你一个 m \* n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。

请你统计并返回 grid 中 负数 的数目。

## 解题思路 ##

遍历就行了

## 提交代码 ##

class Solution(object):
        def countNegatives(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            s = 0
            for i in grid:
                for j in i:
                    if j < 0:
                        s += 1
            return s

## 提交情况 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center]

## 思考 ##

显然我提交的代码不是最优解，这么简单个题目时间复杂度居然是O(n^2)，肯定不合适。当然博主本身没学过算法，只能看看那些大神都是怎么写的了。  
下面是别人的解题思路：

> 充分利用非递增条件，遇到小于0的数便停止循环，直接加上(n-j)\*(m-i)的数。

class Solution:
        def countNegatives(self, grid: List[List[int]]) -> int:
            res = 0
            m = len(grid)
            n = len(grid[0])
            for i in range(m):
                for j in range(n):
                    if grid[i][j] < 0:
                        res += (n-j)*(m-i)
                        n = j
                        break
            return res

感觉也没啥优化，就是利用了一个非递增条件，时间复杂度和我的一样。

# 题5 根据数字二进制下 1 的数目排序 #

## 题目描述 ##

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

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

## 解题思路 ##

1.  首先十进制数组要转成二进制，bin(arr)可以实现；
2.  根据二进制数据中数字1的个数排序，count函数可以统计字符串、数字中某个数出现的次数；
3.  排序用sorted函数，引入匿名函数，用参数key来设定排序规则。

## 提交代码 ##

class Solution(object):
        def sortByBits(self, arr):
            """
            :type arr: List[int]
            :rtype: List[int]
            """
            return sorted(arr, key=lambda x: (bin(x).count('1'), x))

## 提交情况 ##

![在这里插入图片描述][2020102314104620.png_pic_center]

# 题6：有多少小于当前数字的数字 #

## 题目描述 ##

给你一个数组 nums，对于其中每个元素 nums\[i\]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums\[i\] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums\[j\] < nums\[i\] 。

以数组形式返回答案。

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

## 解题思路 ##

肯定要排序，那少不了sort函数，然后可以用index函数来索引排序列表的位置。

## 提交代码 ##

class Solution:
        def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
            numsNew = nums.copy()
            numsNew.sort()
            return [numsNew.index(i) for i in nums]

## 提交情况 ##

![在这里插入图片描述][20201023143831682.png_pic_center]

# 题7：生成每种字符都是奇数个的字符串 #

## 题目描述 ##

给你一个整数 n，请你返回一个含 n 个字符的字符串，其中每种字符在该字符串中都恰好出现 奇数次 。

返回的字符串必须只含小写英文字母。如果存在多个满足题目要求的字符串，则返回其中任意一个即可。

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

## 解题思路 ##

刷到这题，让我觉得我的智商受到了侮辱

## 提交代码 ##

class Solution:
        def generateTheString(self, n: int) -> str:
            if n % 2 == 1:
                return 'a'*n
            else:
                return 'a'*(n-1)+'b'

## 提交情况 ##

我甚至不想描述

# 题8：矩阵中的幸运数 #

## 题目描述 ##

给你一个 m \* n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。

幸运数是指矩阵中满足同时下列两个条件的元素：

在同一行的所有元素中最小  
在同一列的所有元素中最大

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

## 解题思路 ##

这题乍一看，感觉又在侮辱我智商，仔细一想，好像不是那么回事儿，感觉不好写，看看我的暴力解法（也叫憨憨解法，O(∩\_∩)O哈哈~）

## 提交代码 ##

class Solution:
        def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
            import numpy as np
            matrix_np = np.array(matrix)
            mi = []
            for i in range(len(matrix)):
                mi.append([min(matrix[i][:]), matrix[i][:].index(min(matrix[i][:]))])
        
            ma = []
            for j in mi:
                if j[0] == max(matrix_np[:, j[1]]):
                    ma.append(j[0])
            return ma

## 提交情况 ##

我都有点不好意思贴上来。。。  
![在这里插入图片描述][20201023153945379.png_pic_center]  
简直战五渣。。

## 思考 ##

这么写肯定不是一个程序员或者搞算法的人应该写出来的程序，虽然我只是个编程爱好者，但也不能接受。有没有啥更好的思路，动态规划？分治算法？  
看了看官方的解释，原来还可以这么写。。

class Solution:
        def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
            mins = {
        min(rows) for rows in matrix}
            maxes = {
        max(columns) for columns in zip(*matrix)}
            return list(mins & maxes)

主要还是Python基础不牢固，很多函数还不熟练。

今天就到这里吧。

[20201023112012208.png_pic_center]: /images/20221122/9cd7efb9bb8f4c4e825d222fcb293fa3.png
[20201023113329466.png_pic_center]: /images/20221122/81b834dd46a044069e07b9bff8324b6a.png
[20201023115421336.png_pic_center]: /images/20221122/156a860d377e48f8b4d8fc83a9ea9499.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI4NDgzMDQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/93ecb71e2b024b8aab494bfd82fb3199.png
[2020102314104620.png_pic_center]: /images/20221122/66003bb04aa24e98b2da10bb3c1eac20.png
[20201023143831682.png_pic_center]: /images/20221122/16b39397f477444990ef7e4a4e00d109.png
[20201023153945379.png_pic_center]: /images/20221122/0cfdf46336e949c3b963a50a52ef780d.png