一、多数元素
题目描述
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例
示例 1： 输入：[3,2,3] 输出：3 示例 2： 输入：[2,2,1,1,1,2,2] 输出：2
解题
from collections import Counter class Solution: def majorityElement(self, nums: List[int]) -> int: count_result = Counter(nums) return count_result.most_common(1)[0][0]
用到了中collections库的Counter，这是一个计数器，我们可以用来方便的统计出一些元素出现的次数
，比如String、List、Tuples等等。
most_common(1)方法，可以查出最常见的N个元素，这里查出最常见的1个元素。返回是一个[(2,1)]，对应
列表中的元组，第一个是元素，第二个是这个元素出现的次数。
所以，最终返回的值count_result.most_common(1)[0][0]。
二、最长公共前缀
题目描述
编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。
示例
示例 1： 输入：strs = ["flower","flow","flight"] 输出："fl" 示例 2： 输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
解题
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: result = "" for i in zip(*strs): temp_set = set(i) if len(temp_set) == 1: result += i[0] else: break return result
利用中的zip()函数可以巧妙的解决此题。
比如测试输入strs = ["flower", "flow", "flight"]，那么for循环下zip(*strs)，看下内容输出：
strs = ["flower", "flow", "flight"] new = zip(*strs) for i in new: print(i)
输出
('f', 'f', 'f') ('l', 'l', 'l') ('o', 'o', 'i') ('w', 'w', 'g')
可以看到相当于把strs中的每个元素'解压'一样，再打包装载tuple里，循环的次数取决字符最短的元素"flow"。
到这里解题思路就有了：
- 声明一个
result变量，为一个空字符串，后面存字符使用。 - for循环出
zip(*strs)的每个元素i。 - 然后将遍历出来的元素i，转化为set()，去重。
- 去重后，判断set()的长度，如果为1，那么说明遍历出来的元素i，里面的字符都是一样的，符合公共前缀，
添加到result字符串中。 - 继续遍历，当set()的长度不等于1，说明里面有不一样的字符，
break循环，返回结果result。
三、只出现一次的数字
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例
示例 1: 输入: [2,2,1] 输出: 1 示例 2: 输入: [4,1,2,1,2] 输出: 4
解题
from collections import Counter class Solution: def singleNumber(self, nums: List[int]) -> int: result = None count_dict = dict(Counter(nums)) for k, v in count_dict.items(): if v == 1: result = k return result
这里再次使用到了collections的Counter。
比如，测试输入是nums=[4,1,2,1,2]，那么Counter(nums)结果是Counter({1: 2, 2: 2, 4: 1})。
这时候，解决思路就有了：
- 将
Counter结果转化为dict，应该是{4: 1, 1: 2, 2: 2}。 - 遍历dict，判断当
value==1的时候，return对应的key。
四、整数反转
题目描述
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。 假设环境不允许存储 64 位整数（有符号或无符号）。
示例
示例 1： 输入：x = 123 输出：321 示例 2： 输入：x = -123 输出：-321 示例 3： 输入：x = 120 输出：21 示例 4： 输入：x = 0 输出：0
解题
class Solution: def reverse(self, x: int) -> int: str_x = str(x) if str_x[0] != "-": str_x = str_x[::-1] x = int(str_x) else: str_x = str_x[:0:-1] x = int(str_x) x = -x if (-2**31) < x < (2**31-1): return x else: return 0
思路是将int转为str，然后进行切片反转，但是要考虑正负数情况，以及(-2**31) < x < (2**31-1)。
- 输入的int转为str，
str_x = str(x)。 - 判断是否是负数，
str_x[0] != "-"。
如果是正数，直接逆序切片[::-1]，然后转回int类型。
如果是负数，注意负号'-'是不要的，所以切片[:0:-1]，然后转回int类型。
*最后，判断下题目给出的条件，(-2**31) < x < (2**31-1)，满足才返回x，否则返回0。
五、最大子序和
题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例
示例 1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 示例 2： 输入：nums = [1] 输出：1 示例 3： 输入：nums = [0] 输出：0 示例 4： 输入：nums = [-1] 输出：-1 示例 5： 输入：nums = [-100000] 输出：-100000
解题
class Solution: def maxSubArray(self, nums: List[int]) -> int: temp = nums[0] _max = temp for i in range(1, len(nums)): if temp > 0: temp += nums[i] _max = max(_max, temp) else: temp = nums[i] _max = max(_max, temp) return _max
暴力解法，声明2个变量，一个当前的和temp，一个最大的和_max。
通过遍历数组，比较两者，将大的赋值给_max。
但是要注意的是，如果temp(当前和)加上下一个元素还小于0，说明最大和子序列肯定不会是
从temp开始节点起始的，例如nums = [-5，-3，-2]， temp = -8, -8 +（-2）< 0 ，
所以最大和的子序列肯定不会是从-5开始，然后就让temp=-2，从该节点再往后找。
