我是靠谱客的博主 难过美女,这篇文章主要介绍LeetCode题解(2020-10-23)题1:重塑矩阵题2:分糖果题3:检查单词是否为句中其他单词的前缀题4:统计有序矩阵中的负数题5 根据数字二进制下 1 的数目排序题6:有多少小于当前数字的数字题7:生成每种字符都是奇数个的字符串题8:矩阵中的幸运数,现在分享给大家,希望可以做个参考。

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

题1:重塑矩阵

题目描述

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

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

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

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

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

解题思路

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

提交代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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()

提交情况

在这里插入图片描述

题2:分糖果

题目描述

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

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

解题思路

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

提交代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
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)

提交情况

在这里插入图片描述

题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

提交代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
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

提交情况

在这里插入图片描述

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

题目描述

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

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

解题思路

遍历就行了

提交代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
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

提交情况

在这里插入图片描述

思考

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

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

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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来设定排序规则。

提交代码

复制代码
1
2
3
4
5
6
7
8
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))

提交情况

在这里插入图片描述

题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函数来索引排序列表的位置。

提交代码

复制代码
1
2
3
4
5
6
class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: numsNew = nums.copy() numsNew.sort() return [numsNew.index(i) for i in nums]

提交情况

在这里插入图片描述

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

题目描述

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

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

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

解题思路

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

提交代码

复制代码
1
2
3
4
5
6
7
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哈哈~)

提交代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

提交情况

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

思考

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

复制代码
1
2
3
4
5
6
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基础不牢固,很多函数还不熟练。

今天就到这里吧。

最后

以上就是难过美女最近收集整理的关于LeetCode题解(2020-10-23)题1:重塑矩阵题2:分糖果题3:检查单词是否为句中其他单词的前缀题4:统计有序矩阵中的负数题5 根据数字二进制下 1 的数目排序题6:有多少小于当前数字的数字题7:生成每种字符都是奇数个的字符串题8:矩阵中的幸运数的全部内容,更多相关LeetCode题解(2020-10-23)题1:重塑矩阵题2:分糖果题3:检查单词是否为句中其他单词的前缀题4:统计有序矩阵中的负数题5内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(84)

评论列表共有 0 条评论

立即
投稿
返回
顶部