六十六、Leetcode数组系列（中篇）
@Author：Runsen
@Date：2020/6/8
人生最重要的不是所站的位置，而是内心所朝的方向。只要我在每篇博文中写得自己体会，修炼身心；在每天的不断重复学习中，耐住寂寞，练就真功，不畏艰难，奋勇前行，不忘初心，砥砺前行，人生定会有所收获，不留遗憾 （作者：Runsen ）
作者介绍：Runsen目前大三下学期，专业化学工程与工艺，大学沉迷日语，Python， Java和一系列数据分析软件。导致翘课严重，专业排名中下。.在大学60%的时间，都在CSDN。决定今天比昨天要更加努力。前面文章，点击下面链接
我的Python教程，不断整理，反复学习
今日，我决定继续更新Python教程，今天就见识下刷Leetcode的快乐。
Runsen先打开Pycharm，
剑指 Offer 系列 面试题03.：数组中重复的数字
先来一个简单的，见面礼。题目来源于 LeetCode 上的剑指 Offer 系列 面试题03. 数组中重复的数字。
题目链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
#找出数组中重复的数字。
#在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
#
# 示例 1：
#
# 输入：
#[2, 3, 1, 0, 2, 5, 3]
#输出：2 或 3
#
# 限制：
# 2 <= n <= 100000
# Related Topics 数组 哈希表
先进行数据的排序，然后看相邻元素是否有相同的，有直接return。不过很慢，时间O(nlogn)了，空间O(1)，但是代码很简单。
'''
@Author：Runsen
@微信公众号： 润森笔记
@博客：https://blog.csdn.net/weixin_44510615
@Date：2020/6/10
'''
def findRepeatNumber(nums):
nums.sort()
for i in range(len(nums) -1):
if nums[i] == nums[i+1]:
return nums[i]
nums = [2, 3, 1, 0, 2, 5, 3]
print(findRepeatNumber(nums))
2
如果用哈希表，就是字典，遍历整个数组,当这个数字没有出现过字典的时候将其加入进去,如果在哈希表中则直接返回即可。时间复杂度O(n)，空间复杂度O(n)
def findRepeatNumber1(nums):
dict = {}
for i in nums:
if i not in dict:
dict[i] = 0
else:
return i
nums = [2, 3, 1, 0, 2, 5, 3]
print(findRepeatNumber1(nums))
2
LeetCode 第 5 题：最长回文子串
题目链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
#给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
#
# 示例 1：
#
# 输入: "babad"
#输出: "bab"
#注意: "aba" 也是一个有效答案。
# 示例 2：
#
# 输入: "cbbd"
#输出: "bb"
定义一个判读回文子串的方法 遍历字符串比较回文子串的长度
比如说字符串abacd，反过来是dcaba，它俩的最长公共子串是aba，也就是最长回文子串。
但是这个思路是错误的，比如说字符串aacxycaa，反转之后是aacyxcaa，最长公共子串是aac，但是最长回文子串应该是aa。
算法一：枚举s所有子串，满足回文的同时，满足最长 结果：
，同学请你出门右转
算法二：遍历s的每个字符，（奇数）以该字符为中心，向左向右同时遍历，（偶数）以两个字符为中心，向左向右同时遍历，当不满足回文时停止，最终筛选最长回文串 结果：
，嗯，还可以，那你完整写出来吧
算法三：Manacher算法，为最长回文子串而生，O（N），了解一下就放弃。
回文中心的两侧互为镜像。因此，回文可以从他的中心展开，并且只有2n-1个这样的中心(一个元素为中心的情况有n个，两个元素为中心的情况有n-1个)。
# 回文的长度是奇数还是偶数的情况，如果是奇数形回文，就以当前字符为中心左右两边寻找，例如回文"bab"；如果是偶数形回文，需要两个字符，并且这两个字符是相等的，则需要以当前字符和其相邻的字符为中心向左右两边寻找，例如回文"abba"。
def longestPalindrome(s):
res = ""
for i in range(len(s)):
# 奇数形回文, like "aba"
tmp = helper(s, i, i)
if len(tmp) > len(res):
res = tmp
# 偶数形回文, like "abba"
tmp = helper(s, i, i + 1)
if len(tmp) > len(res):
res = tmp
return res
def helper(s, l, r):
# 中心扩散
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return s[l + 1:r]
if __name__ == '__main__':
longestPalindrome('abasfggttg')
LeetCode 第 53 题：最大子序和
#给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
#
# 示例:
#
# 输入: [-2,1,-3,4,-1,2,1,-5,4],
#输出: 6
#解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
定义当前子序和以及最大子序和为数组的一个元素；
遍历整数数组，比较当前子序和的值及当前遍历的值，取较大值重置赋值给当前子序和 cur_sum；
同时比较当前子序和及最大子序和的值，取较大值重置赋值给最大子序和 max_sum；
遍历结束，返回最大子序和的值 max_sum。
def maxSubArray( nums):
'''查找连续子数组的最大和
'''
# 比较当前子序和，最大子序和，返回最大值
# 定义当前子序和以及最大子序和为第一个元素
cur_sum = max_sum = nums[0]
# 遍历整数数组
for x in range(1, len(nums)):
# 比较当前值和当前子序和的值，取较大值
cur_sum = max(nums[x], cur_sum + nums[x])
# 比较当前值和定义的最大子序和值，将最大值重置赋值给 max_sum
max_sum = max(cur_sum, max_sum)
return max_sum
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))
6
LeetCode 第88题 :合并两个有序数组
#给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
# 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
# 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
# 输入:
#nums1 = [1,2,3,0,0,0], m = 3
#nums2 = [2,5,6], n = 3
#
#输出: [1,2,2,3,5,6]
合并两个列表再排序，简单。
def merge(nums1, nums2):
nums1[:] = sorted(nums1[:m] + nums2[:n])
因为本身就是有序，通过 双指针法 达到
的时间复杂度。
最直接的算法实现是将指针p1 置为 nums1的开头， p2为 nums2的开头，在每一步将最小值放入输出数组中。
由于 nums1 是用于输出的数组，需要将nums1中的前m个元素放在其他地方，也就需要
的空间复杂度。
def merge(nums1,m, nums2,n):
# Make a copy of nums1.
nums1_copy = nums1[:m]
nums1[:] = []
# Two get pointers for nums1_copy and nums2.
p1 = 0
p2 = 0
# Compare elements from nums1_copy and nums2
# and add the smallest one into nums1.
while p1 < m and p2 < n:
if nums1_copy[p1] < nums2[p2]:
nums1.append(nums1_copy[p1])
p1 += 1
else:
nums1.append(nums2[p2])
p2 += 1
# if there are still elements to add
if p1 < m:
nums1[p1 + p2:] = nums1_copy[p1:]
if p2 < n:
nums1[p1 + p2:] = nums2[p2:]
return nums1
nums1 = [1,2,3,0,0,0]
nums2 = [2,5,6]
print(merge(nums1,3,nums2,3))
[1, 2, 2, 3, 5, 6]
LeetCode 第118题 :杨辉三角
#给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
# 在杨辉三角中，每个数是它左上方和右上方的数的和。
#
# 示例:
#
# 输入: 5
#输出:
#[
# [1],
# [1,1],
# [1,2,1],
# [1,3,3,1],
# [1,4,6,4,1]
#]
# Related Topics 数组
第一行第二行都是1，每行第一个和最后一个都为1，假设任意一个位置的数x，索引坐标是(m,n)，则x就是该数 正上方的数 和 左上方那个数 之和。即(m-1,n),(m-1,n-1)两数和。
def generate(numRows):
if numRows == 0: return []
triangle = [[1]]
if numRows == 1: return triangle
for i in range(1, numRows):
tmp = [1]
for j in range(1, i):
tmp.append(triangle[i - 1][j - 1] + triangle[i - 1][j])
tmp.append(1)
triangle.append(tmp)
return triangle
print(generate(5))
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
如果本文对你有帮助，大家可以点赞转发一波，有错误大家可以评论指出，感谢！
腾讯云开发者
