LeetCode刷题笔记（一）

本文按题目排序，每期10题。

本期内容多以排序为主，出现了滑动窗口等算法，学习到了python对于数组的一些操作。

数组

2. 两数相加

next函数：返回迭代器的下一个项目

.next函数：

python3 中的 ->，出现在函数定义中尤其的多：

• 用于标记返回函数注释

• 指示函数返回的类型

• 常常出现在python函数定义的函数名后面，为函数添加元数据，描述函数的返回类型，从而方便开发人员使用：

  def add(x,y) -> int:
      return x+y

  这里面，元数据表明了函数的返回值为int类型

本题提供了ListNode的类，应当学会使用

• val一般是value的意思吧

• 怎样实例化一个类？

  class add:
      type = 'add'
      def __init__(self, name, sex, leg):
          self.name = name
          self.sex = sex
          self.leg = leg
          
  cat = animal('cat', 'male', 4)

• 这里的ListNode类很巧妙，用的时候要注意

  解题思路：leecode第二题python解法

3. 无重复字符的最长子串

问题1：str变量有索引吗？似乎没有

• subscriptable 可下标的，也就是可索引的

问题2：如何把字符串转化为列表（有序）

# 字符串用 split() 转化为列表
a = 'ab,cd,ef'
print(a.split(','))

# 列表转化为字符串
l = ['a', 'b']
print(''.join(l))

可是如果没有,' '逗号、空格之类的呢？

额，醉了

s = 'abc'
list(s)
>>> ['a', 'b', 'c']

这道题还是有点难度的，并不是说都是从第一位开始来算的

有可能从中间开始计算，那么这个时候该怎么办呢？

首先移动到第 i 位，比较 该位之前所有位，是否与它相同

记录位置，选最近的哪个

几种特殊情况：

只有一个重复的，1

空字符串，0

字符串是空格：

• 怎样区分空格和空，是一个问题

len(str) == 0 # 这是字符串为空
str.isspace() == True # 这是字符串为空格

随之而来另一个问题：

• 将字符串转为列表，空格是怎么处理的？

这个我自己做了一个实验：

空格还是空格，还是放在那里的

而且它的布尔值也是True

与此同时，空字符串的bool值是False

只有两个字符：au，怎么进行判断，那就是没有重复项，因此的话，需要直接把整个字符串的长度计算进来，也就是说到目前这个量都是对的

现在的问题是pwwkew为什么结果是5而不是3

开始流动，到了w，开始那个是1，最后这个，j=1或2，都会给list_lit增加一项

比如说到k了，lit是空的，这个时候头已经变了，不再是从头开始了！

设计一个num记录当前无重复的最大数值

那么循环就应该从num开始

这个题涉及的语言方法还是比较多的，我用的str方法

题解中有用enumerate方法的，还有用C++中的指针方法的

提到最多的还是“滑动窗口”

其实倒也没有错，我的方法其实也是为了实现一个滑动窗口，并且记录窗口的长度，但是问题是空格该怎么算

4. 寻找两个正序数组的中位数

读题：本题的要求是：

给的两个数列（list）顺序是好的

但是最后要找的，是两个数组合并到一块，然后取中位数

那么合并后的数组，要进行排序（或者不用排序了，使用一些算法来寻找中位数），这就是问题所在了

数组怎么排序呢？

list.sort()方法可以进行排序，默认是升序

如果列表中有字符串，字符串是按照首字母顺序来的

没有返回值

本题中是正序数组

本题还对复杂度进行了要求：

本题核心：找第k小的数

用到了递归的方法

我们比较了 第 k/2 个数的大小情况，然后cut掉一部分

最后把一边消耗完，返回另一边最小的哪个数字

还有一种很巧妙的计算奇偶两个数列中位数的一个方法

k1 = (len(nums1) + len(nums2) + 1) // 2
k2 = (len(nums1) + len(nums2) + 2) // 2

如果两个数列一奇一偶：

k1 = k2

如果两个数列都是奇数，或者都是偶数

k1 是中间左边，k2是中间右边

17. 电话号码的字母组合

九键输入法中，2-9每个数字对应着一些字母

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合（顺序可以任意）

本来来说，应该要给一个字典存放以下，以便记录每个数字都对应哪些字母

但是实际上也有一定的规律，大多三个，有两个是四个，而且是连续的

分析：

输入是字符串，可以进行索引，然后找对应的字母

• 每个数字 =》 对应几个字母
• 下一个数字 =》 对应几个字母
• 还需要做排列组合

不过，这样的话，岂不是要做3-4层循环？而且还要逐个遍历

感觉容易超时

不对呀，我不是很好控制循环的层数，加之，组合出来的字符串实在有点多

可以这样思考：

如果你已经有了各数字对应的字母

你会如何得到最后的字符串呢？

直接两两组合

这个两两组合还是会使用循环

组合出的是字符串，组合的结果会放在列表里面

# 移动到某一位
# 当前位与之前的字符串进行各种组合
# 把组合出的字符串重新加入字符列表

【9月3日】现在的方法是，判断列表是不是空的

如果是空的，说明是第一个数字，那么此时，就需要填入单个的字符，但是这个字符又不能直接加到最后的内容中

如果不是空的，这时已经不是第一个数字了

所以我引入了一个新的列表，是上一个列表的copy

122. 买卖股票的最佳时机 II

给一个数组，第i个元素表示第i天的价格

可以多次交易，但是购买前需要出售掉之前的股票，设计算法让利润最大

（1）利润也就是价差，主要是卖的时候的价差

（2）最多买i/2次，卖也是

（3）应该是低价买进，高价卖出，找差价最大的两天？

     所以应该先找最低点，买进，然后找其后的最高点（跌之前卖出）

跳出股票的场景，其实是在求数组中数的差值，上升过程中，找最大差值卖出，跌到最低，应当买入

1. 滑动窗口，移动到当前值，判断大小：

   小于上一个值，小于下一个值，此时应该买进

   小于上一个值，大于下一个值，观望，下一个值（或之后）应该买进

   大于上一个值，小于下一个值，观望，上一个值（或之前）应该买进

   大于上一个值，大于下一个值，卖出

2. 所以需要有一个股票计数君，记录当前手里有没有股票

   没有才能买

   有才能卖

3. 还有一个利润君，计算利润

手里有股票：

• 价格

# 未完
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        stock = 0
        i = 1
        while i < len(prices):
            if stock:   # 手里有股票，应当卖出
                # 观察价格，应当是最高点卖出
                while prices[i] < prices[i+1] and i+1 < len(prices):
                    i += 1
                # 股票卖出
                stock -= 1
                i += 1
            else：      # 手里没有股票，应该买进
                # 观察价格，最低点买入
                while prices[i] < prices[i-1] and i < len(prices):
                    i += 1
                # 股票买入
                stock += 1
        return profit

我怎么觉得是一个滑动窗口的问题

试看一个窗口：

如果手里还没有股票：

• 此时如果是 ab，a<b，则在a买入
• 如果ba，则观望

如果手里已经有了股票：

• 此时如果是ba，则在b卖出
• 如果ab，则观望
• 如果已经到结尾了，直接卖出

也就是说总是第一个点交易，除非已到结尾

这种方法是可以的，效果也还不错

看别人的题解，有一种很秀的方法，是我这种方法的进化：

直接求下一个数-本数的差值（也就是利润）

如果是正的，就加上，如果是0或者负的，就跳过

至于连续上涨交易日，等价于每天都在买卖

136. 只出现一次的数字

哈希表问题

一个非空整数数组中：

• 只有一个元素只出现了一次
• 其余每个元素都出现了两次

找出这个只出现了一次的元素

额外要求：线性时间复杂度，不使用额外空间

# 在有限能力范围内，我的想法是
class solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 首先给数组去重排序
        # 然后遍历循环，找出数组中数字的索引位置
        # 如果索引位置只有1个，那么就是只出现了一次

问题是：我要怎么分析它的时间复杂度是不是线性的，数组去重排序本身所用的时间就比较多，python中仅一句代码

列表的去重

（1）set方法，起始时转化成了元组，所以之后需要再转化成list，优点是索引值不变

（2）itertools.groupby

（3）fromkeys

（4）添加到新的列表

（5）列表的sort方法可以做到排序

# 再思考，去重排序其实是多此一举的
class solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 遍历循环
        # 找数组中有没有和它一样的
        # 因为是从前往后的，已经遍历过的不算，已经配好对的也不能再遍历了

还是要排一下序，不然不好找

continue和break

continue仅停止本次循环

break跳出本层循环体

NB的解法：

（1）一个小神的解法是：由于全是数字，直接去重，然后double，减去原来的，得到的差就是唯一一个单个的数字；

（2）另一种解法是python中的异或：

符号是^

相同的数异或为0

0和任何数异或，结果都是这个数本身

所以，依次异或就可以，剩下来的一定是只出现一次的数

（3）还有一种解法是：Collections.Counter() 函数，这是一个计数器

202.快乐数

一个正整数，每一次将该数替换为它每个位置上的数字的平方和，不断重复这个过程

如果最终能够变成1，那么就是快乐数

如果不能变成1，那么就不是快乐数

其实变成1，就必须是一个1，和多个0

# 另写一个函数，用来计算平方和
# 其中，首先需要把上一个数字拆成单个数字的组合，把数字变成列表
# 然后计算平方和并相加

把数字，拆成一个个单个数字的列表，可以先转换成字符串，然后再转换为列表

关键问题是，如何判断它不是快乐数？

一次循环，不行，两次循环不行，要多少次循环呢？

无限循环始终变不到1，但是我不可能真的无限循环，要有判断吧！

尝试251，发现，会有重复！如果出现重复，那么肯定是不可以了

也是，全部是100以内的加减法，所以第一次运算之后也不会大于3位

三位数的组合，能够实现快乐数的

所以这里有一个问题，三位数，计算平方数，用循环显然不是很经济，取位才是更经济的方法

递归似乎是有上限的，先后遇到两个问题：

（1）maximum recursion depth exceeded while getting the str of the object 超出了最大递归深度，估计大概递归不到1000次就超出了

python中if 条件的非是：if not

没错，看了题解，我基本发现真相了

就是判断有没有重复，然后再判断是不是1就可以了

所以，需要一个之来存放已经出现过的值：

set() 元组，特点是无序不重复，可以进行关系测试，计算交集、差集、并集等等

724. 寻找数组的中心索引

如果一个数组（python中是list）中，某个数的左侧数字之和 = 右侧数字之和，那么这个数就是中心数，返回索引值

我的方法就是，先求出总和

然后看左边的数字之和，是不是等于（总和-当前数字）/ 2

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        i = 0
        list_sum = sum(nums)
        while i < len(nums):
            left_sum = sum(nums[0:i])
            if (list_sum - nums[i])/2 == left_sum:
                return i
            i += 1
        return -1

一把过。

筛法

204. 计数质数

这个题居然难度是简单？

给一个n，统计小于n的质数的数量

问题1：是不是得计算一下一个数是不是质数？

• 质数，除了1和它本身，不能被其他数整除，但是这个其他数也要进行遍历吗？余数为0的检验

问题2：计算资源的使用

• 从1到n循环
• 从1到n做除数，观察余数
• 所以复杂度在$O(n^2)$级别

最后要的只是数量，而没有要具体是哪些

其实按照双循环的思路，做出来并不难，难的是速度，一下子就写出了代码，但是总是有超时问题，这个问题也很严重了！

class Solution:
    def countPrimes(self, n: int) -> int:
        count = 0
        i = 1
        # 判断每个数是不是质数
        while i < n:
            if self.is_primes(i):
                # 如果是质数，则计数君加1
                count += 1
            i += 1
        return count

    # 判断一个数是不是质数
    def is_primes(self, num: int) -> bool:
        if num == 1:
            return False
        elif num == 2:
            return True
        else:
            k = 2
            while (k * k) <= num:
                if num % k == 0:
                    return False
                else:
                    k += 1
            return True

理论上，已经除过的数的倍数也不能再作为除数了

但是这个筛选听起来就很麻烦

从解答来看

1. i不需要遍历到n，而只需要到sqrt(n)即可

   因为，如果不是素数，在sqrt(n)之后的乘数其实就是前面的反过来

   

   这样的话，复杂度降到了$O(\sqrt n)$

2. 其实也不是非要有一个判断质数的函数

   的确，比如3，没有必要从2开始除，这就是在白费力气

   所以应该使用排除法

   2是素数，2的倍数都不可能是素数

   3也是素数，3的倍数

   4因为是2的倍数，所以已经不是素数了

   5仍然是素数，倍数

   6是2的倍数，也是3的倍数

   7仍然素数

   8，2的倍数

   9，3的倍数

   这个方法确实很妙！！

昂拉多塞筛法：

由于给出的数是n，不妨给出一个有n个1的列表：方法是：list =[1] * n

如果我们找出合数，然后把它的倍数所在位置的值标记为0:

• 这个也是极妙
• 如果2是素数，其倍数从2*2=4开始，到n结束，间隔都是2
• 如果3是素数，其倍数从3*3=9开始（因为3x2已经是2的倍数了，就可以略过），到n结束，间隔都是3
• 如果5是素数，其倍数从5*5=25开始······
• 实在是很妙，所以就是 从 i*i 开始，到 n 结束，间隔为 i

这要到最后，这个列表中为1的地方就是所有素数的索引位置了！

纯粹筛法，不用仔细计算！

其他

面试题16.08 整数的英文表示

有点意思

这个题中：

首先看数字长度：

3位：hundred

4位：thousand

5位：xxty xx thousand（这个地方可能会比较难）

6位： million

9位：billion

高于9位，还是billion

每过一个点看3位数字

用函数嵌套会比较好一点

另外两位数：

10-19有特殊的表示

如果是0x一类的

三位数：

xxx hundred xxty xx

顺序：正向还是反向？

正向可能会好一点

如果是反向的话，那么两位数的情况可能不是很通用

问题一：python中，int没有长度，所以要先转化成list

方法是，先从int转为str，然后从str转为list，或者str也是有长度的可以直接用

参考：python中str,int,list,list(str),list(int)的相互转换

这道题说实在的，道理就是这么多，每三位读取一次

看位数，不停进行查找就可以了

但是从一个题解来看，还是有可学习之处的，那就是怎么样把数字的写法写的更简洁

其实除了 thousand、million、billion之外，其他部分的写法还是很通用的

---

OK！本期10题就先到这里了，期待下一个10题快点到来！