@Author：Runsen

@Date：2020/6/8

人生最重要的不是所站的位置，而是内心所朝的方向。只要我在每篇博文中写得自己体会，修炼身心；在每天的不断重复学习中，耐住寂寞，练就真功，不畏艰难，奋勇前行，不忘初心，砥砺前行，人生定会有所收获，不留遗憾 （作者：Runsen ）

作者介绍：Runsen目前大三下学期，专业化学工程与工艺，大学沉迷日语，Python， Java和一系列数据分析软件。导致翘课严重，专业排名中下。.在大学60%的时间，都在CSDN。决定今天比昨天要更加努力。 前面文章，点击下面链接

我的Python教程，不断整理，反复学习

今日，我决定继续更新Python教程，今天就见识下刷Leetcode的快乐。

剑指 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?

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?

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]]

如果本文对你有帮助，大家可以点赞转发一波，有错误大家可以评论指出，感谢！

之前的文章点击下面即可。