对于一个计算机专业学生(俗称码农)来说,数据结构和算法十分重要,所以这一期来一些实战的例子,选取的是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->4
class 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;
关于 天 方 夜 “谈”
天方夜谈原意讲不切实际的东西,而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。
方班人有自己的浪漫,
我们探讨知识,谈论理想,
采摘科研的繁星,
脚下是星辰大海。
天:代表我们的理想犹如天空般浩荡
方:代表方班
夜:代表代码人的冷静与静谧
谈:代表方班愿与您,就领域内的经典思想和前沿成果“秉烛夜谈”