对于一个计算机专业学生（俗称码农）来说，数据结构和算法十分重要，所以这一期来一些实战的例子，选取的是leetcode其中的十道题目，从解题思路、代码展示和改进思路三方面对这十道题目进行分析。
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321示例 2:
输入: -123
输出: -321示例 3:
输入: 120
输出: 21注意:
假设我们的环境只能存储 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。根据这个假设，如果反转后整数溢出那么就返回 0。
先取数字的绝对值，方便后续统一处理
将数字转化为字符串，将数字的个十百千等位输出为一个反序的列表
将列表翻转，每一位对应的数字*（10^列表下标）
根据输入数字正负判断输出数字正负
判断是否溢出
class Solution: def reverse(self, x: int) -> int: """ function： 整数翻转 parameters： para1：输入的整数 return： 输出翻转后的整数 """ self.x = x y = 0 x_abs = abs(self.x) #取绝对值，避免因为负数带有字符导致统计数字长度出错 num_len = len(str(x_abs)) num_list = [] for i in range(num_len): rem = x_abs % 10 x_abs = x_abs // 10 num_list.append(rem) #将绝对值每一个逆向输出为一个列表 num_list = num_list[::-1] #将列表翻转，有利于后续计算 for i in range(len(num_list)): y = y + num_list[i] * (10**i) if self.x < 0: #判断是否要添加符号 y = -y if (y >= -(2**31) and y <= (2**31)-1): #判定是否会溢出 return y else: return 0a = Solution()a.reverse(560)直接利用字符串的翻转实现：
class Solution: def reverse(self, x: int) -> int: """ function： 整数翻转 parameters： para1：输入的整数 return： 输出翻转后的整数 """ self.x = x flag = -1 if self.x<0 else 1 y = flag * int(str(abs(self.x))[::-1])# y = self.x // max(1, abs(self.x)) * int(str(abs(self.x))[::-1]) return y if (-2**31<y<2**31-1) else 0类和函数的使用方法
数字取绝对值abs()
列表生成式的使用
列表翻转的几种方法
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
b = list(reversed(a)) #reversed()函数返回的是一个迭代器，而不是一个List，需要再使用List函数转换一下。
c=sorted(a, reverse=True) #sort()函数是将列表重新排序，reverse=True是按降序排列，reverse=False是按照升序排列
d=a[::-1] #反向输出列表元素删除的几种方法
a=[1, 2, 3, 4, 2, 3, 4]
a.remove(2) #删除单个元素，删除首个符合条件的元素，按值删除
a.pop() #按位删除(根据索引删除),默认从列表尾部弹出
del a[-2:] #del完全删除时时删除变量数字与字符串的相互转换
判断一个整数是否是回文数，其中回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。将数字转化为字符串
迭代判断字符串的“首尾”是否相等
class Solution: def isPalindrome(self, x: int) -> bool: """ function: 判定一个数字是否是回文数 parameters: para1:一个整数 return: 布尔值 """ self.x = x x_str = str(self.x) temp = 0 if (len(x_str) == 1): #个位数全部都是回文数 return True else: for i in range(len(x_str)//2): #长度为偶数时，比较一半的次数，长度为奇数时，比较[一半]的次数 if (x_str[i] == x_str[-(i+1)]): temp += 1 #给定一个标志，用于接下来判定是否为回文数 if temp == len(x_str)//2: return True else: return False a = Solution() print(a.isPalindrome(10000021))直接将字符串进行反转，也就是上一个问题的思路，然后比较反转前后的字符串是否相等即可。
class Solution: def isPalindrome(self, x: int) -> bool: """ function: 判定一个数字是否是回文数 parameters: para1:一个整数 return: 布尔值 """ self.x = x if self.x < 0: return False else: if str(self.x) == str(self.x)[::-1]: #反转字符比较 return True else: return Falsea = Solution()print(a.isPalindrome(10000021))更简单的代码：
class Solution: def isPalindrome(self, x: int) -> bool: """ function: 判定一个数字是否是回文数 parameters: para1:一个整数 return: 布尔值 """ self.x = x return str(self.x) == str(self.x)[::-1]a = Solution()print(a.isPalindrome(10000021))在思考问题时一定要全面，特别是特殊情况的时候，比如这道题目：
个位数全部是回文数
负数直接可以判定不为回文数
编写一个函数来查找字符串数组中的最长公共前缀，如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。说明:
所有输入只包含小写字母 a-z 。
1、看到题目最开始想的是将字符串数组内的每个字符串切割出来，然后比较每个字符串的相对于字符，但是遇到一个问题，如果字符串数组很长，那就必须设置很多个变量，这点比较难以实现。
2、使用zip函数将字符串数组内的每个字符串对应位置集合起来变成一个元组。
3、利用set集合判定元组内元素是否一样。
4、判断set集合长度即可得知每个字符串对应位置的字符是否一致。
class Solution: def longestCommonPrefix(self, strs) -> str: """ function: 判定一个字符串列表中最长的公共前缀，没有输出"" parameter: 字符串数组 return： 字符串 """ self.strs = strs res = '' for tmp in zip(*self.strs): #将字符串数组内每个字符串的对应位置重新组合为一个列表（内为元组） tmp_set = set(tmp) if len(tmp_set) == 1: #判定元组内是否有重复 res += tmp[0] else: break return res思路1：python中字符串也是可以比较的，他是按照每个字符的ASCII码进行比较，比如aba，abac，abb中最大的是abb，最小的是aba。
class Solution: def longestCommonPrefix(self, strs) -> str: """ function: 判定一个字符串列表中最长的公共前缀，没有输出"" parameter: 字符串数组 return： 字符串 """ self.strs = strs if self.strs: #首先要评定数组是否为空，如果为空，max()和min()函数无法执行 max_str = max(self.strs) min_str = min(self.strs) for i,x in enumerate(min_str): if x != max_str[i]: return min_str[:i] return min_str else: return ""思路2：利用find()函数，取第一个字符串，依次与后面的字符串比较。
class Solution: def longestCommonPrefix(self, strs) -> str: """ function: 判定一个字符串列表中最长的公共前缀，没有输出"" parameter: 字符串数组 return： 字符串 """ self.strs = strs if not self.strs: #先判定是否为空，因为后面需要对数组经常操作 return "" res = self.strs[0] i = 1 while i < len(self.strs): while self.strs[i].find(res) != 0: #find()函数如果查到：返回查找的第一个出现的位置；否则，返回-1。 res = res[:-1] i += 1 return res思路3：利用os.path.commonprefix(list)，返回list(多个路径)中，所有path共有的最长的路径。
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: return os.path.commonprefix(strs)zip()和zip(*)函数的使用；
x = [1, 2, 3]
y = [4, 5, 6]
z = [7, 8, 9]
xyz = zip(x, y, z) #将三个列表的对应位置元素集合在一个元组内，然后多个元组构成一个列表；如果列表长度不一致，取最短的
print(list(xyz))x = [1, 2, 3]
y = [4, 5, 6]
z = [7, 8, 9]
xyz = zip(x, y, z) #此时xyz为[(1, 4, 7), (2, 5, 8), (3, 6, 9)]
u = zip(*xyz) #zip(*xyz)等价于zip((1, 4, 7), (2, 5, 8), (3, 6, 9))
print (list(u)) #所以u又变成了[(1, 2, 3), (4, 5, 6), (7, 8, 9)]
# 总结一句话，zip()相当于压缩，zip(*)相当于解压，只是两者的输入不同而已set集合：集合中不会存在相同的元素；
max()和min()函数执行时，如果对象为空，必须指定参数default（用来返回默认值）；
find()函数如果查到：返回查找的第一个出现的位置，否则返回-1；
os.path.commonprefix(list)，返回list(多个路径)中，所有path共有的最长的路径。
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意：空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true示例 2:
输入: "()[]{}"
输出: true示例 3:
输入: "(]"
输出: false示例 4:
输入: "([)]"
输出: false示例 5:
输入: "{[]}"
输出: true括号之间只要左括号数目=右括号数目（先不在意位置），那么括号之间是可以完全匹配的；
先判断首位是否是右括号；
利用栈的思想，扫描字符串，遇到左括号就压缩到栈中；
遇到右括号就与栈顶元素比较；
class Solution: def isValid(self, s: str) -> bool: """ function: 判断括号是否正确匹配 parameter: para1:str return: bool """ self.s = s stack = [] match = {')':'(', '}':'{', ']':'['} for char in s: if char in match: if stack: top_element = stack.pop() else: return False if match[char] != top_element: return False else: stack.append(char) return not stack将两个有序链表合并为一个新的有序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: """ function: 合并两个有序链表 parameter: para1:链表1 para2:链表2 return: 合并链表 """ if not l1: return l2 if not l2: return l1 if l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next,l2) return l1 else: l2.next = self.mergeTwoLists(l1,l2.next) return l2给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
暴力法：直接嵌套两次循环，比较两值之间的大小；
动态规划：
将min赋予一个很大的数，max赋予一个很小的数；
将min与数组开始比较，如果（min>数组值），将数组值赋给min；
如果不大于，那么判断（数组值-min）是否大于相差值，大于的话将（数组值-min）赋给max。
class Solution: def maxProfit(self, prices) -> int: """ function: 得到一个数组中相差最大的数（小的在前） parameters: para1:list(int) return: int """ self.prices = prices if not self.prices: return 0 tmp_min = self.prices[0] #f最好设一个较大的值，方便后续比较 res = 0 for key,value in enumerate(self.prices): #在break时，key和value是保留退出时的数 if value < tmp_min: tmp_min = value else: #嵌套关系要清楚 if value - tmp_min > res: res = value - tmp_min return res更简单的代码
class Solution: def maxProfit(self, prices) -> int: """ function: 得到一个数组中相差最大的数（小的在前） parameters: para1:list(int) return: int """ self.prices = prices if not self.prices: return 0 tmp_min = max(self.prices) tmp_max = 0 for key,value in enumerate(self.prices): tmp_min = min(tmp_min, value) tmp_max = max(tmp_max, value-tmp_min) return tmp_max就是暴力法-->动态规划。
for循环中enumerate()函数的使用，可以显示下表；
字典中对于键值对的操作；
dic1 = {'age': 22, 'name': 'xie', 'sex': 'male',}for key in dic1.keys(): print(key)for value in dic1.values(): print(value)for key,value in dic1.items(): print(key,value)给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
观察功能需求，当确定有最小值s[i]时（买入的时候），只要确定s[i+1]>s[i+2]，那么就可以认定为在i时买入，(i+1)时卖出，之后都是如此；
简单地说就是找波峰波谷，每一个波峰波谷之间都需要计算；
为了避免超出列表长度，i只取到len(s)-1,所以最后赋值之前需要进行i++操作，这样就可以避免超出列表长度范围。
class Solution: def maxProfit(self, prices) -> int: """ function: 最大利润 parameters: para1:List[int] return: int """ self.prices = prices if not self.prices: #后面涉及到取数组，所以先判断是否为空 return 0 res = 0 min_price = self.prices[0] max_price = self.prices[0] i = 0 while i < (len(self.prices)-1): while (i < (len(self.prices)-1) and self.prices[i] >= self.prices[i+1]): #再次规定i要小于数组的长度 i += 1 #i加1之后就变成取后者，这也是为了避免超出数组长度范围 min_price = self.prices[i] while (i < (len(self.prices)-1) and self.prices[i] <= self.prices[i+1]): i += 1 max_price = self.prices[i] res += max_price - min_price return res因为观察到的规则是计算每一个波峰波谷之间的差值，但有一种更简单的思路：
比如1,2,5,(2-1)+(5-2) = (5-1)，只要理解为在当天卖出的时候又买入，那么得到的结果是一样的。
class Solution: def maxProfit(self, prices) -> int: """ function: 最大利润 parameters: para1:List[int] return: int """ self.prices = prices res = 0 if not self.prices: #后面涉及到取数组，所以先判断是否为空 return 0 for i in range(1,len(self.prices)): if self.prices[i] > self.prices[i-1]: #判断是否比前面的大，只要更大就相减；比如1,2,5,(2-1)+(5-2) = (5-1) res += self.prices[i] - self.prices[i-1] return res更简单的代码：
class Solution: def maxProfit(self, prices) -> int: """ function: 最大利润 parameters: para1:List[int] return: int """ return sum(b - a for a, b in zip(prices, prices[1:]) if b > a)zip()函数在计算相邻之间数的时候，操作很方便；
对于列表的长度，一定要考虑清楚，很容易就会超出长度；
对于i也要多考虑考虑，本次学到一种转化的方法，将i取值减小，比较当前位和下一位，之后进行i++操作，将下一位的值赋予变量；
and/or/not的使用。
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次，找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
观察题目，只存在一个只出现一次的数字，其他数字都出现两次；
遍历数组，单独出现的时候放到一个列表中，如果再次出现，将该数弹出；
这个方法只需要遍历一次，但是使用了额外的空间，所以使用异或运算；
异或运算：0^a=a, a^a=0。
class Solution: def singleNumber(self, nums) -> int: """ function:输出只出现一次的数字 type:list[int] rtype:int """ self.n = nums res = [self.n[0],] #虽然实现了功能，并且时间复杂度也是O(n)，但是使用了额外空间 for i in range(1, len(self.n)): if self.n[i] in res: res.remove(self.n[i]) else: res.append(self.n[i]) return res[0]虽然实现了功能，并且时间复杂度也是O(n)，但是使用了额外空间。
class Solution: def singleNumber(self, nums) -> int: """ function:输出只出现一次的数字 type:list[int] rtype:int """ self.n = nums res = self.n[0] for i in range(1, len(self.n)): res ^= self.n[i] #异或运算，相同数字异或为0,0与其他数字异或为该数字，所以也不需要使用额外空间，遍历一次 return resA = Solution()A.singleNumber([4,3,4,3,1]) find()函数只能使用在字符串的查找中，找到返回第一个位置的索引，否则返回-1（可进行切片操作）；
pop()函数默认弹出列表最后一个元素，也可以指定弹出位置的元素；
remove()按照指定元素进行删除；
index()返回第一个位置的索引值，可用于字符串和列表；
异或运算很有意思，对于这些比较经典的运算需要灵活应用。
给定一个整数数组，判断是否存在重复元素。如果任何值在数组中出现至少两次，函数返回 true；如果数组中每个元素都不相同，则返回 false。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
直接用set函数判断一下就可以啦。
class Solution: def containsDuplicate(self, nums) -> bool: """ type nums: List[int] rtype:bool """ self.n = nums if not self.n: return False if ( len(self.n)==len(set(self.n)) ): #用set函数判定数组是否存在重复元素 return False else: return True
更简单的代码：
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: """ type nums: List[int] rtype:bool """ return len(self.n) != len(set(self.n))给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例 1:
输入: 1
输出: true
解释: 20 = 1
示例 2:
输入: 16
输出: true
解释: 24 = 16
示例 3:
输入: 218
输出: false
设计一个循环，依次将2^i与n进行比较；
比较中一旦2^i比n大，返回False。
class Solution: def isPowerOfTwo(self, n: int) -> bool: """ :type n: int :rtype: bool """ self.n = n i = 0 while ( n != 2**i): #i循环加一后与n比较即可 if n < 2**i: return False else: i += 1 return True改进思路：
使用位运算：一个正数在计算机中以二进制存储（原码和反码一样），这个数的相反数在计算机中是表示为反码，两个数的反码进行与运算，得到的结果仍然是这个正数的原码。
16 :00010000（原码）
-16:11110000（负数的反码是取反后加一）
16 & -16:00010000（16）
class Solution: def isPowerOfTwo(self, n: int) -> bool: """ :type n: int :rtype: bool """ return ( n > 0 ) and ( n & -n ) == n #位运算，一个正数与自己相反数的A二进制做与运算，结果等于本身对于正数，特别是2的倍数，那么它的二进制表示是有一定规律的。比如这道题目，只可能在某一位上为1其他都是0；该数与其相反数进行与操作得到本身；
对于2的倍数，还可以进行左移或者右移，那么就是放大或缩小2倍；
当碰到（2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0），可以使用二进制进行运算：111111=1000000-1；
关于 天 方 夜 “谈”
天方夜谈原意讲不切实际的东西，而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。
方班人有自己的浪漫，
我们探讨知识，谈论理想，
采摘科研的繁星，
脚下是星辰大海。
天：代表我们的理想犹如天空般浩荡
方：代表方班
夜：代表代码人的冷静与静谧
谈：代表方班愿与您，就领域内的经典思想和前沿成果“秉烛夜谈”
