当前位置: 首页 > > 天 方 夜 “谈” 第10期 | leetcode实战

天 方 夜 “谈” 第10期 | leetcode实战

发表于:2020-03-18 20:47 作者: 方滨兴班 阅读数(6379人)

对于一个计算机专业学生(俗称码农)来说,数据结构和算法十分重要,所以这一期来一些实战的例子,选取的是leetcode其中的十道题目,从解题思路、代码展示和改进思路三方面对这十道题目进行分析。

1 整数反转

题目描述:

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123
输出: 321

示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

注意:

假设我们的环境只能存储 32 位的有符号整数,则其数值范围为 [−231,  231 − 1]。根据这个假设,如果反转后整数溢出那么就返回 0。


解题思路:

  1. 先取数字的绝对值,方便后续统一处理

  2. 将数字转化为字符串,将数字的个十百千等位输出为一个反序的列表

  3. 将列表翻转,每一位对应的数字*(10^列表下标)

  4. 根据输入数字正负判断输出数字正负

  5. 判断是否溢出

代码展示:


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

知识点:

  1. 类和函数的使用方法

  2. 数字取绝对值abs()

  3. 列表生成式的使用

  4. 列表翻转的几种方法

    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] #反向输出
  5. 列表元素删除的几种方法

    a=[1, 2, 3, 4, 2, 3, 4]
    a.remove(2) #删除单个元素,删除首个符合条件的元素,按值删除

    a.pop() #按位删除(根据索引删除),默认从列表尾部弹出

    del a[-2:] #del完全删除时时删除变量
  6. 数字与字符串的相互转换


2 回文数

题目描述:

判断一个整数是否是回文数,其中回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
解释: 从左向右读,  -121  从右向左读,  121- 。因此它不是一个回文数。

示例 3:

输入: 10
输出: false
解释: 从右向左读,  01 。因此它不是一个回文数。

解题思路:

  1. 将数字转化为字符串

  2. 迭代判断字符串的“首尾”是否相等

代码展示:


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. 个位数全部是回文数

    2. 负数直接可以判定不为回文数

3 最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀,如果不存在公共前缀,返回空字符串 ""

示例 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)

知识点

  1. 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(*)相当于解压,只是两者的输入不同而已
  2. set集合:集合中不会存在相同的元素;

  3. max()和min()函数执行时,如果对象为空,必须指定参数default(用来返回默认值);

  4. find()函数如果查到:返回查找的第一个出现的位置,否则返回-1;

  5. os.path.commonprefix(list),返回list(多个路径)中,所有path共有的最长的路径。

4 有效的括号

题目描述:

给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。

注意:空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

解题思路:

  1. 括号之间只要左括号数目=右括号数目(先不在意位置),那么括号之间是可以完全匹配的;

  2. 先判断首位是否是右括号;

  3. 利用栈的思想,扫描字符串,遇到左括号就压缩到栈中;

  4. 遇到右括号就与栈顶元素比较;

代码展示:


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

5 合并两个有序链表

题目描述:

将两个有序链表合并为一个新的有序链表并返回,新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

输入: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


6 买卖股票的最佳时机

题目描述:

给定一个数组,它的第 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。

解题思路:

  1. 暴力法:直接嵌套两次循环,比较两值之间的大小;

  2. 动态规划:

    1. 将min赋予一个很大的数,max赋予一个很小的数;

    2. 将min与数组开始比较,如果(min>数组值),将数组值赋给min;

    3. 如果不大于,那么判断(数组值-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

改进思路:

就是暴力法-->动态规划。

知识点:

  1. for循环中enumerate()函数的使用,可以显示下表;

  2. 字典中对于键值对的操作;


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)

7 买卖股票的最佳时机2

题目描述:

给定一个数组,它的第 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。

解题思路:

  1. 观察功能需求,当确定有最小值s[i]时(买入的时候),只要确定s[i+1]>s[i+2],那么就可以认定为在i时买入,(i+1)时卖出,之后都是如此;

  2. 简单地说就是找波峰波谷,每一个波峰波谷之间都需要计算;

  3. 为了避免超出列表长度,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)

知识点:

  1. zip()函数在计算相邻之间数的时候,操作很方便;

  2. 对于列表的长度,一定要考虑清楚,很容易就会超出长度;

  3. 对于i也要多考虑考虑,本次学到一种转化的方法,将i取值减小,比较当前位和下一位,之后进行i++操作,将下一位的值赋予变量;

  4. and/or/not的使用。

8 只出现一次的数字

题目描述:

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次,找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

解题思路:

  1. 观察题目,只存在一个只出现一次的数字,其他数字都出现两次;

  2. 遍历数组,单独出现的时候放到一个列表中,如果再次出现,将该数弹出;

  3. 这个方法只需要遍历一次,但是使用了额外的空间,所以使用异或运算;

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

知识点:

  1. find()函数只能使用在字符串的查找中,找到返回第一个位置的索引,否则返回-1(可进行切片操作);

  2. pop()函数默认弹出列表最后一个元素,也可以指定弹出位置的元素;

  3. remove()按照指定元素进行删除;

  4. index()返回第一个位置的索引值,可用于字符串和列表;

  5. 异或运算很有意思,对于这些比较经典的运算需要灵活应用。


9 存在重复元素

题目描述:

给定一个整数数组,判断是否存在重复元素。如果任何值在数组中出现至少两次,函数返回 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))


10 2的幂次方

题目描述:

给定一个整数,编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 20 = 1

示例 2:

输入: 16
输出: true
解释: 24 = 16

示例 3:

输入: 218
输出: false

解题思路:

  1. 设计一个循环,依次将2^i与n进行比较;

  2. 比较中一旦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二进制做与运算,结果等于本身

知识点:

  1. 对于正数,特别是2的倍数,那么它的二进制表示是有一定规律的。比如这道题目,只可能在某一位上为1其他都是0;该数与其相反数进行与操作得到本身;

  2. 对于2的倍数,还可以进行左移或者右移,那么就是放大或缩小2倍;

  3. 当碰到(2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0),可以使用二进制进行运算:111111=1000000-1;

关于 天 方 夜 “谈”

天方夜谈原意讲不切实际的东西,而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。

方班人有自己的浪漫,

我们探讨知识,谈论理想,

采摘科研的繁星,

脚下是星辰大海。

天:代表我们的理想犹如天空般浩荡

方:代表方班

夜:代表代码人的冷静与静谧

谈:代表方班愿与您,就领域内的经典思想和前沿成果“秉烛夜谈”