193. 有效电话号码

给定一个包含电话号码列表（一行一个电话号码）的文本文件 file.txt，写一个 bash 脚本输出所有有效的电话号码。

你可以假设一个有效的电话号码必须满足以下两种格式： (xxx) xxx-xxxx 或 xxx-xxx-xxxx。（x 表示一个数字）

你也可以假设每行前后没有多余的空格字符。

示例:

假设 file.txt 内容如下：

1
2
3
987-123-4567
123 456 7890
(123) 456-7890

你的脚本应当输出下列有效的电话号码：

1
2
987-123-4567
(123) 456-7890

代码如下:

1
grep '^\(([0-9]\{3\}) \|[0-9]\{3\}-\)[0-9]\{3\}-[0-9]\{4\}$' file.txt

195. 第十行

给定一个文本文件 file.txt，请只打印这个文件中的第十行。

示例:

假设 file.txt 有如下内容：

1
2
3
4
5
6
7
8
9
10
Line 1
Line 2
Line 3
Line 4
Line 5
Line 6
Line 7
Line 8
Line 9
Line 10

你的脚本应当显示第十行：

1
Line 10

说明:

  1. 如果文件少于十行，你应当输出什么？
  2. 至少有三种不同的解法，请尝试尽可能多的方法来解题。

代码如下:

1
awk 'NR==10{print $0}' file.txt

或者:

1
2
3
if [ `cat file.txt | wc -l` -ge "10" ]; then
    head -n 10 file.txt | tail -n 1
fi

或者:

1
sed -n '10p' file.txt

196. 删除重复的电子邮箱

编写一个 SQL 查询，来删除 Person 表中所有重复的电子邮箱，重复的邮箱里只保留 Id 最小 的那个。

1
2
3
4
5
6
7
8
+----+------------------+
| Id | Email            |
+----+------------------+
| 1  | john@example.com |
| 2  | bob@example.com  |
| 3  | john@example.com |
+----+------------------+
Id 是这个表的主键。

例如，在运行你的查询语句之后，上面的 Person 表应返回以下几行:

1
2
3
4
5
6
+----+------------------+
| Id | Email            |
+----+------------------+
| 1  | john@example.com |
| 2  | bob@example.com  |
+----+------------------+

只要在where里添加一个and p1.Id > p2.Id即可,代码如下:

1
2
delete p1 from Person p1 ,Person p2
where p1.Email = p2.Email and p1.Id > p2.Id

当然也可以复杂一点:

1
2
3
delete from Person where id not in 
(select min(id) from 
	(select * from Person) p group by Email);

197. 上升的温度

当前的SQL架构为:

1
2
3
4
5
6
Create table If Not Exists Weather (Id int, RecordDate date, Temperature int)
Truncate table Weather
insert into Weather (Id, RecordDate, Temperature) values ('1', '2015-01-01', '10')
insert into Weather (Id, RecordDate, Temperature) values ('2', '2015-01-02', '25')
insert into Weather (Id, RecordDate, Temperature) values ('3', '2015-01-03', '20')
insert into Weather (Id, RecordDate, Temperature) values ('4', '2015-01-04', '30')

给定一个 Weather 表，编写一个 SQL 查询，来查找与之前（昨天的）日期相比温度更高的所有日期的 Id。

1
2
3
4
5
6
7
8
+---------+------------------+------------------+
| Id(INT) | RecordDate(DATE) | Temperature(INT) |
+---------+------------------+------------------+
|       1 |       2015-01-01 |               10 |
|       2 |       2015-01-02 |               25 |
|       3 |       2015-01-03 |               20 |
|       4 |       2015-01-04 |               30 |
+---------+------------------+------------------+

例如，根据上述给定的 Weather 表格，返回如下 Id:

1
2
3
4
5
6
+----+
| Id |
+----+
|  2 |
|  4 |
+----+

代码如下:

1
2
3
4
select w2.Id as Id
from Weather w1, Weather w2
where datediff(w2.RecordDate,w1.RecordDate)=1 and 
	w1.Temperature < w2.Temperature

也可以使用自连接,代码如下:

1
2
3
4
select Weather.id as `Id` from 
	Weather join Weather w
	on DATEDIFF(Weather.RecordDate,w.RecordDate) = 1
		AND Weather.Temperature > w.Temperature

或者:

1
2
3
4
SELECT w2.id from 
	Weather w1 INNER JOIN Weather w2 
	on w1.RecordDate = DATE_SUB(w2.RecordDate,INTERVAL 1 DAY) AND	
		w1.Temperature < w2.Temperature;

经验:==日期差使用datediff函数==

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

1
2
3
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

1
2
3
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

我的代码:使用动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 比较前一天的钱之和
# 和
# 前两天的钱之和加上今天的钱

# 比如今天26号,那么今天最多能偷的钱就是
# max(25号最多能偷的钱,24号最多能偷的钱+26号能偷的钱)
class Solution(object):
    def rob(self, nums):
        if not nums:
            return 0
        elif len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums[0],nums[1])
        else:
            # two_day_ago:到前天为止总共能偷的最多的钱
            # yesterdat  :到昨天为止总共能偷的最多的钱
            res = two_day_ago = nums[0]
            yesterday = max(nums[0],nums[1])

            for idx in range(2,len(nums)):
                res = max(yesterday,two_day_ago + nums[idx])
                # 准备下一天的计算:昨天变成前天,今天变成昨天
                two_day_ago = yesterday
                yesterday = res
            return res

其实可以没有前天这个变量的:

1
2
3
4
5
6
7
class Solution(object):
    def rob(self, nums):
        # rob1表示这一家偷了的最大收益，rob2表示这一家不偷的最大收益
        rob1, rob2 = 0,0
        for num in nums:
            rob1, rob2 = rob2 + num, max(rob1, rob2)
        return max(rob1, rob2)

也可以这么写:

1
2
3
4
5
6
7
8
class Solution(object):
    def rob(self, nums):
        # last代表昨天的最大利益,now表示今天的最大利益
        last = now = 0 
        for i in nums: 
            # now = max(last + i, now):今天偷还是不偷
            last, now = now, max(last + i, now)
        return now

动态规划中当前的状态往往依赖于前一阶段的状态和前一阶段的决策结果。例如我们知道了第i个阶段的状态Si以及决策Ui，那么第i+1阶段的状态Si+1也就确定了。所以解决动态规划问题的关键就是确定状态转移方程，一旦状态转移方程确定了，那么我们就可以根据方程式进行编码。

不妨把状态转移方程理解为递归关系。就是如何从已知求得未知的表达式。
比如找一列数中最大的一个数，如果你知道了前n个数中最大，记做Max_n
那么当你遇到第n+1个数x_n+1的时候，前n+1个数中最大值是什么呢，就是拿这个新x去和之前那个max比，然后留下较大的一个，对吧，写下来就是
Max_n+1 = (x_n+1 > Max_n) ? x_n+1 : Max_n
这就是一个状态转移方程，就是一个递归关系。

202. 快乐数

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

示例: 

1
2
3
4
5
6
7
输入: 19
输出: true
解释: 
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

这道题当然可以使用存缓来做:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def isHappy(self, n):
        cache = []
        while n != 1:
            tmp = 0
            for each in str(n):
                tmp += int(each)**2
            n = tmp
            if not n in cache:
                cache.append(n)
            else:
                return False
        return True

就算是使用存缓,上面代码的6-8行的效率不高,应该如下使用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def isHappy(self, n):
        if n == 1:
            return True
        numlist = []
        while True:
            temp = 0
            # 代替上面代码的6-8行
            while n != 0:
                n,remain = divmod(n,10)
                temp += remain**2
            if temp == 1:
                return True
            if temp in numlist:
                return False
            numlist.append(temp)
            n = temp

经验:==取出数的各位数字,永远用的都是不断的求余==:

1
2
while n != 0:
    n,remain = divmod(n,10)

而不是:

1
2
3
for each in str(n):
    tmp += int(each)**2
    n = tmp

正确的代码是使用反例:
所有不快乐数的数位平方和计算，最後都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def isHappy(self, n):
        unhappy = [4,16,37,58,89,145,42,20]
        happy = [1,10,100,1000]
        while n not in unhappy and n not in happy:
            total = 0
            while n:
                n,remain = divmod(n,10)
                total += remain**2
            n = total
        return n in happy

203. 移除链表元素

删除链表中等于给定值 val 的所有节点。

示例:

1
2
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def removeElements(self, head, val):
        #因为有可能头结点会被删除,所以将头结点放到最后最后处理
        newhead = head
        while head:
            if head.next and head.next.val==val:
                head.next = head.next.next
            else:                
                head = head.next
        #最后处理头结点的的情况
        if newhead and newhead.val == val:
            newhead = newhead.next
        return newhead

经验:==为了减少判断条件的数量,涉及链表移动,一律使用while head,这样,就只需处理只有一个头节点的问题==:

1
2
3
while head:
    if head.next and head.next.val == val:
        head.next = head.next.next

所以,后续使用下面代码处理:

1
2
if newhead and newhead.val == val:
    newhead = newhead.next

其实还有一种方法,就是==自己新建一个dummyhead==:

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def removeElements(self, head, val):
        # 自己新建一个头节点dummyhead
        pa=source=ListNode(0)
        pa.next=head
        while(pa):
            while(pa.next and pa.next.val==val):
                pa.next=pa.next.next
            pa=pa.next
        return source.next

204. 计数质数

统计所有小于非负整数 n 的质数的数量。

示例:

1
2
3
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

当然可以使用暴力求解法:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def isPrimes(self,n):
        for num in range(2,n//2+1):
            if n % num == 0:
                return False
        return True
    def countPrimes(self, n):
        res = 0
        for each in range(2,n):
            if self.isPrimes(each):
                res += 1
        return res

这时该采用厄拉多塞筛法.
想要得到一个不大于N的数所有素数，可以先找到不超过根号N的所有素数，设2 = p1 < p2 < ……<pk ≤√N，然后在2,3,4……N里面进行下面的操作：

  1. 留下p1 = 2，把p1的倍数全部划掉，
  2. 再留下p2 ，把p2 的倍数全部划掉，
  3. 继续这一过程，直到留下pk，把pk的倍数全部划掉，
  4. 最后留下来就是不超过N的全体素数。

比如说求20以内质数的个数,首先0,1不是质数.2是第一个质数,然后把20以内所有2的倍数划去.2后面紧跟的数即为下一个质数3,然后把3所有的倍数划去.3后面紧跟的数即为下一个质数5,再把5所有的倍数划去.以此类推.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def countPrimes(self, n):
            if n < 3:
                return 0     
            else:
                # 首先生成了一个全部为1的列表
                output = [1] * n
                # 因为0和1不是质数,所以列表的前两个位置赋值为0
                output[0],output[1] = 0,0
                 # 此时从index = 2开始遍历,output[2]==1,即表明第一个质数为2,然后将2的倍数对应的索引
                 # 全部赋值为0. 此时output[3] == 1,即表明下一个质数为3,同样划去3的倍数.以此类推.
                for i in range(2,int(n**0.5)+1): 
                    if output[i] == 1:
                        output[i**2:n:i] = [0] * len(output[i**2:n:i])
             # 最后output中的数字1表明该位置上的索引数为质数,然后求和即可.
            return sum(output)

这里需要注意的是第14行的代码:

1
output[i**2:n:i] = [0] * len(output[i**2:n:i])

14行的代码其实本该是:

1
output[i*2:n:i] = [0] * len(output[i*2:n:i])

14行表示去除i的倍数:
假设i=13,那么该去除的就是2乘13,3乘13,4乘13…也就是output[i*2:n:i],但是注意到2乘13是2的倍数,早就被2去除了,同理3乘13是3的倍数,被3去除.4乘13被2去除,5乘13被5去除…
简单来说,对于2,3,4,5,6,7,8,9,10,11,12乘以13这11种情况,如果是合数早就被2去除了,如果是质数,那么早就被13前面的质数去除了.所以可以直接从平方开始.

下面的代码比较好理解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def countPrimes(self, n):
        if n <= 1:
            return 0
        
        nums = [None] * n
        nums[0] = False
        nums[1] = False
        
        for i in range(n):
            if nums[i] == None:
                nums[i] = True
                
                for j in range(i + i, n, i):
                    nums[j] = False
        return sum(nums)

经验:注意有时候可以使用列表法

205. 同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

1
2
输入: s = "egg", t = "add"
输出: true

示例 2:

1
2
输入: s = "foo", t = "bar"
输出: false

示例 3:

1
2
输入: s = "paper", t = "title"
输出: true

说明:
你可以假设 s 和 t 具有相同的长度。

我写的垃圾代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def temp(self, s, t):
        hashmap = {}
        for idx in range(len(s)):
            if not s[idx] in hashmap :
                hashmap[s[idx]] = t[idx]
            else:
                if not t[idx] == hashmap[s[idx]]:
                    return False
        return True
    def isIsomorphic(self,s,t):
        a,b = self.temp(s,t),self.temp(t,s)
        res = True if a==b==True else False
        return res

上面temp函数有一个漏洞,就是当输入’aa’,’ab’时,temp会返回True,但是输入’ab’,’aa’却返回False.所以使用上面isIsomorphic函数12行调换t和s的位置,一旦有False就就是False,只有两个都是True的情况才是True

为了防止上面说的情况,我们可以对比字典的值:(注意第9行)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def isIsomorphic(self, s, t):
        temp = {}
        for i in range(len(s)):
            if s[i] not in temp:
                temp[s[i]] = t[i]
                # 当输入'ab','aa'是,temp为{'a':'a','b':'a'}
                # 这样就保证了不会有多个键映射到同一个值
                if len(temp.values()) != len(set(temp.values())):
                    return False
            if temp[s[i]] != t[i]:
                return False
        return True

还可以使用两个哈希表,以空间换时间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 两个哈希表,空间换时间
def isIsomorphic(self, s, t):
        dictionary_s = dict()
        dictionary_t = dict()

        for i in range(len(s)):
            if s[i] not in dictionary_s:
                dictionary_s[s[i]] = t[i]
            elif s[i] in dictionary_s:
                if dictionary_s[s[i]] != t[i]:
                    return False
                    
            if t[i] not in dictionary_t:
                dictionary_t[t[i]] = s[i]
            elif t[i] in dictionary_t:
                if dictionary_t[t[i]] != s[i]:
                    return False
                    
        return True

有一种很巧妙的方式:==使用zip表示映射关系==

1
2
3
4
5
6
class Solution(object):
    def isIsomorphic(self, s, t):
        # zip(s, t)其实就是每个单词的映射
        # len(zip(s, t))==len(set(t)),说明映射的长度等于全部的长度
        # 说明这是一一映射的关系
        return len(set(s)) == len(set(t)) == len(set(zip(s, t)))

经验:

  1. 如果要==保证不会有多个键映射到同一个值==,可以使用len(temp.values()) != len(set(temp.values()))
  2. 可以==使用zip表示映射关系==.
  3. 复杂的映射关系可以==使用两个哈希表==,以空间换时间.

206. 反转链表

反转一个单链表。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

我的垃圾代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 新建一条链表,重新连接(头插法)
class Solution(object):
    def reverseList(self, head):
        if not head:
            return None

        NewList = ListNode(head.val)
        while head.next:
            newNode = ListNode(head.next.val)
            newNode.next = NewList

            NewList = newNode
            head = head.next
        return NewList

因为是反转,所以可以使用stack:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 尾插法
class Solution:
    def reverseList(self, head):
        if not head:
            return None

        stack = []
        while head:
            stack.append(head.val)
            head = head.next

        dummy = newList = ListNode(stack.pop())
        while stack:
            newNode = ListNode(stack.pop())
            newList.next = newNode
            newList = newList.next
        return dummy

使用栈,不能新建节点来连接:效率太低,在stack里直接存入节点,而不是存入结点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def reverseList(self, head):
	    if not head:
	        return None
	        
	    stack = []
	    node = head
	    while node:
            # 在stack里直接存入节点
	        stack.append(node)
	        node = node.next
	    new_head = stack.pop()
	    node = new_head
	    while stack:
	        node.next = stack[-1]
	        node = stack.pop()
	    node.next = None

	    return new_head

可以不使用stack,直接尾插:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 头插法.
# 思路:将原链的头节点p设置为最后一个节点,然后head节点不断头插入p中,最后返回head
class Solution(object):
    def reverseList(self, head):
        p = head
        if p is None:
            return p
		# s节点用于遍历整个原链表
        s = head.next
        # p的节点设置为空,变成尾节点
        # 因为使用头插法,p变成初始节点
        p.next = None
        while s:
        	# head为头插的节点(头节点)
            head = s
            s = s.next

            # 将head头插入p中
            head.next = p
            p = head
        return head

假设传入的head为1–>2–>3–>4–>5–>None,
当while s:执行第一次后,链表变成**None<–1<–2**–>3–>4–>5–>None
所以说,上面代码是使用头插法,将1作为初始节点,==一边遍历链表一边修改节点next的方向==.

下面的代码也是头插法,但是是把5作为初始节点:

1
2
3
4
5
6
7
8
9
10
class Solution:
    def reverseList(self, head):
        if not head or not head.next:
            return head

        result = self.reverseList(head.next)
        # 转换两个节点next的方向
        head.next.next = head
        head.next = None
        return result

假设传入的head为1–>2–>3–>4–>5–>None,
等第二次递归结束,链表变成1–>2–>3–>(None<–)4<–5<–None.
上面的意思就是3的next节点是4,但是4的next节点是None

单链表有两个插法:头插法和尾插法.

  1. 头插法: 在链表的开头插入一个新的节点，也就是，必须使得链表头Head指向新节点，该新节点指向原来是表头的第一个节点。代码1使用的就是头插法.
  2. 尾插法: 在链表的尾部插入一个节点。尾插法是比较容易理解并令大家习惯的插入形式，生成一个新节点后直接插入链表的微端，也就是让原来最后一个节点指向该新节点。代码2使用的就是尾插法.

经验:

  1. 遇到反转,第一个要想到的就是stack
  2. 反转链表的时候可以使用头插法和尾插法.
    当使用头插法的时候注意,可以将头节点作为初始节点,也可以将尾节点作为初始节点.

217. 存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

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

示例 2:

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

示例 3:

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

当然可以使用语言特性,使用set:

1
2
3
class Solution(object):
    def containsDuplicate(self, nums):
    	return len(nums) != len(set(nums))

或者先排序,然后判断相邻元素

1
2
3
4
5
6
7
class Solution:
    def containsDuplicate(self, nums):
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i - 1] == nums[i]:
                return True
        return False

219. 存在重复元素 II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

示例 1:

1
2
输入: nums = [1,2,3,1], k = 3
输出: true

示例 2:

1
2
输入: nums = [1,0,1,1], k = 1
输出: true

示例 3:

1
2
输入: nums = [1,2,3,1,2,3], k = 2
输出: false

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def containsNearbyDuplicate(self, nums, k):
        nums_len = len(nums)
        if nums_len <= 1:
            return False
        nums_dict = {}

        for i in range(nums_len):
            if nums[i] in nums_dict:
                if i - nums_dict[nums[i]] <= k:
                    return True
            # 因为是从左到右扫描,所以每次都要更新字典
            nums_dict[nums[i]] = i
        return False

上面代码可以简化如下:

1
2
3
4
5
6
7
8
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        d={}
        for index,value in enumerate(nums):
            if value in d and index-d[value]<=k:
                return True
            d[value]=index
        return False

经验:==一般遇到高复杂度的情况都是用空间换时间,一般都是用字典,可以更换O(n)的时间==

225. 用队列实现栈

使用队列实现栈的下列操作：

  • push(x) – 元素 x 入栈
  • pop() – 移除栈顶元素
  • top() – 获取栈顶元素
  • empty() – 返回栈是否为空

注意:

  • 你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
  • 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
  • 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
class MyStack(object):
    def __init__(self):
        # 使用列表模拟dequeue
        self.dequeue = []
    def push(self, x):
        self.dequeue.append(x)
    def pop(self):
        return self.dequeue.pop()
    def top(self):
        return self.dequeue[-1]
    def empty(self):
        return self.dequeue == []

使用双向队列固然简单,如果使用queue的话就需要旋转队列了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MyStack(object):
    def __init__(self):
        self.queue = []
    def push(self, x):
    	# 列表尾部作为队列的头部
        self.queue.append(x)
    def pop(self):
    	for _ in range(len(self.que1)-1):
    		# 旋转队列
    		self.queue.append(self.queue.pop(0))
    	return self.queue.pop(0)
    def top(self):
        return self.queue[-1]
    def empty(self):
        return not self.que1

也可以使用内置的collections模块:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MyStack(object):
	def __init__(self):
	    from collections import deque
	    self.stack = deque()
	def push(self, x):
	    self.stack.appendleft(x)
	def pop(self):
	    n = len(self.stack)
        # 需要旋转整个队列(其实就是翻转)
	    self.stack.rotate(n-1)
	    return self.stack.pop()
	def top(self):
	    return self.stack[0]
	def empty(self):
	    return not self.stack

经验:==手动旋转列表:不断的append(pop(0))==

不然也可以使用如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
def rev(Alist):
	if len(Alist) % 2 == 1:
		for idx in range(len(Alist)//2+1):
			idx2 = (len(Alist)//2 - idx) * 2 + idx
			Alist[idx],Alist[idx2] = Alist[idx2],Alist[idx]
	else:
		for idx in range(len(Alist)//2+1):
			idx2 = (len(Alist)//2 - idx) * 2 + idx - 1
			Alist[idx],Alist[idx2] = Alist[idx2],Alist[idx]
	return Alist

print(rev([0,1,2,3,4,5]))    # [5, 4, 2, 3, 1, 0]
print(rev([0,1,2,3,4,5,6]))  # [6, 5, 4, 3, 2, 1, 0]

226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

1
2
3
4
5
     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

1
2
3
4
5
     4
   /   \
  7     2
 / \   / \
9   6 3   1

备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

这是我的初始代码(是错的)

1
2
3
4
5
6
7
class Solution(object):
    def invertTree(self, root):
        if not root or (not root.left and not root.right):
        	return root
        else:
        	root.left,root.right = root.right,root.left
        	return self.invertTree(root.left) and self.invertTree(root.right)

上面代码确实能翻转二叉树,但是不能返回翻转后的二叉树.例如传入[4,2,7,1,3,6,9],返回的是[1].而题目要求返回[4,7,2,9,6,3,1]

所以这里存在一个问题,如何return出正确的东西.答案==想想这个函数是干什么的,最后应该返回什么==,把递归函数看成是普通的函数,这里已经翻转了左右子树,那么最后就应该return root

正确代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def invertTree(self, root):
        if not root or (not root.left and not root.right):
        	return root
        else:
            # 主要逻辑在这里
        	root.left,root.right = root.right,root.left
            # 当主要逻辑写完之后才考虑如何递归
        	self.invertTree(root.left)
        	self.invertTree(root.right)
            # 想想这个函数本身应该return什么,这里就应该return什么
        	return root

同理,递归函数应该在哪里写主要递归逻辑问题,==先把递归函数考虑成普通函数,普通函数结束后才考虑递归问题==

经验:==先把递归函数考虑成普通函数,普通函数结束后才考虑递归问题==,这样就能解决:

  1. 递归计数问题.
  2. 递归主要逻辑放在哪里问题.
  3. 递归return出错问题.

这道问题也可以使用遍历:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def invertTree(self, root):
        trees = []
        trees.append(root)
        while trees:
            node = trees.pop()
            if not node:
                continue
            node.left,node.right = node.right,node.left
            trees.append(node.left)
            trees.append(node.right)
        return root

可以使用多元赋值:

1
2
3
4
5
6
7
class Solution(object):
    def invertTree(self, root):
        if not root :
            return root
        else:
            root.left,root.right = self.invertTree(root.right),self.invertTree(root.left)
            return root

经验:==对于树而言,如果要使用遍历,一般都是设置一个数组来存放root.left和root.right的==

或者:

1
2
3
4
5
6
7
8
9
class Solution(object):
    def invertTree(self, root):
        if root:
            root.right,root.left = root.left,root.right
            if root.left:
                self.invertTree(root.left)
            if root.right:
                self.invertTree(root.right)
            return root

231. 2的幂

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

示例 1:

1
2
3
输入: 1
输出: true
解释: 2^0 = 1

示例 2:

1
2
3
输入: 16
输出: true
解释: 2^4 = 16

示例 3:

1
2
输入: 218
输出: false

我的代码:

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def isPowerOfTwo(self, n):
        # 特殊情况:0
    	if not n:
    		return False
        while n != 1:
        	n,remain = divmod(n,2)
        	if remain != 0:
        		return False
        return True

其实这道题应该使用位运算:

1
2
3
class Solution:
    def isPowerOfTwo(self, n):
        return n > 0 and not (n & (n - 1))

解释:
&运算，同1则1
2的幂次方在二进制下，只有1位是1，其余全是0。例如:8—00001000。所以,当n是2次方的时候,n & (n - 1),按位相与,全为0.(eg:4的二进则为100,3的二进则为011,则位运算4&3(=000)=0)

也可以使用下面的代码:

1
2
3
class Solution:
    def isPowerOfTwo(self, n):
        return n > 0 and (n & -n)==n

解释:
负数的在计算机中二进制表示为补码(原码->正常二进制表示，原码按位取反(0-1,1-0)，最后再+1(eg:-8就是8的按位取反再加一:00001000–>111101111,再加1得:11111000)。然后两者进行与操作，得到的肯定是原码中最后一个二进制的1。例如8&(-8)->00001000 & 11111000 得 00001000，即8。

经验:关于与运算判断2的幂次方的两种方法

  1. return n&(n-1) == 0
  2. return (n&(-n)) == n

232. 用栈实现队列

使用栈实现队列的下列操作：

  • push(x) – 将一个元素放入队列的尾部。
  • pop() – 从队列首部移除元素。
  • peek() – 返回队列首部的元素。
  • empty() – 返回队列是否为空。

示例:

1
2
3
4
5
6
7
MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

  • 你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

我的代码(不合题意):

1
2
3
4
5
6
7
8
9
10
11
12
13
class MyQueue(object):
    def __init__(self):
        self.stack = []
    def push(self, x):
        self.stack.append(x)
        for _ in range(len(self.stack)-1):
            self.stack.append(self.stack.pop(0))
    def pop(self):
        return self.stack.pop()
    def peek(self):
        return self.stack[-1]
    def empty(self):
        return not self.stack

上面代码测试通过,但是完全不符合题意啊,你一个stack怎么能append又能pop(0)呢?既能在弹出首元素还能直接在栈底添加元素?

正确的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MyQueue:
    def __init__(self):
    	# 列表尾作为栈顶
        self.input = []
        self.output = []
    def push(self, x):
        self.input.append(x)
    def pop(self):
        self.peek()
        return self.output.pop()
    def peek(self):
        while not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]
    def empty(self):
        return not self.input and not self.output

解释:思路：

  • 用两个堆栈 input 和 output 来模拟队列
  • 入队列时：向 input 中压入元素
  • 出队列时：将 input 中的元素依次弹出堆栈，并压入 output 中，最后弹出 output 的栈顶元素

234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

1
2
输入: 1->2
输出: false

示例 2:

1
2
输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

最简单的肯定是使用列表存放整个链表了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def isPalin(self,alist):
        if len(alist) == 0:
            return True
        left = 0
        right = len(alist) - 1
        while left < right:
            if alist[left] != alist[right]:
                return False
            left += 1
            right -= 1
        return True
    def isPalindrome(self, head):
        alist = []
        while head:
            alist.append(head.val)
            head = head.next
        return self.isPalin(alist)

如果要O(n) 时间复杂度和 O(1) 空间复杂度,使用双指针+反转链表:

下面是我的代码(是错的):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def reversed(self,head):
        if not head or not head.next:
            return head
        pre = head.next
        head.next = None
        while pre:
            tmp = pre.next
            pre.next = head
            pre = tmp
        return head

    def isPalindrome(self, head):
    	dummy = head
        revHead = self.reversed(dummy)
        while head:
            if head.val != revHead.val:
                return False
            head = head.next
            revHead = revHead.next
        return True

这里确实是使用了反转链表和双指针,但是,问题是这是原地反转,所以16-20行就变成了同一条链的双指针了,没有意义.

有一个解决方法那就是:==让链表从中间原地反转==

我的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def reversed(self,head):
        if not head or not head.next:
            return head
        pre = head.next
        head.next = None
        while pre:
            tmp = pre.next
            pre.next = head
            head = pre
            pre = tmp
        return head

    def isPalindrome(self, head):
    	if not head or not head.next:
    		return True

    	slow = fast = head
    	while fast and fast.next:
    		slow = slow.next
    		fast = fast.next.next
    	print(slow.val)
    	
        slow = self.reversed(slow)
        while slow:
        	print(head.val,slow.val)
        	if head.val != slow.val:
        		return False
    		head = head.next
    		slow = slow.next
    	return True

可以简化如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isPalindrome(self, head):
        fast = slow = head
        # 找到中点
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        # 反转链表，可参考leetcode206
        node = None
        while slow: 
            slow.next, node, slow = node, slow, slow.next
		# 双指针
        while node:
            if node.val != head.val:
                return False
            node = node.next
            head = head.next
        return True

经验:

  1. ==使用快慢双指针来寻找链表的中点==.
  2. 回文链表的判断使用==中间原地反转链表+双指针==

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

img

示例 1:

1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

这种题需要利用二叉搜索树的特性对其进行寻找,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def lowestCommonAncestor(self, root,p,q):
        if not root:
            return None
        num1, num2 = p.val, q.val
        return self.getResult(root,num1,num2)
        
    def getResult(self, root, num1, num2):
        # 父节点的值一定介于num1和num2中(闭区间)
        if (root.val-num1) * (root.val-num2) <= 0:
            return root
        elif root.val > num1 and root.val > num2:
            return self.getResult(root.left,num1,num2)
        else:
            return self.getResult(root.right,num1,num2)

代码可以更简洁:

1
2
3
4
5
6
7
class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if max(p.val,q.val) < root.val:
            return self.lowestCommonAncestor(root.left,p,q)
        if min(p.val,q.val) > root.val:
            return self.lowestCommonAncestor(root.right,p,q)
        return root

还可以使用迭代:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root == None:
            return None
        while root:
            if root.val > q.val and root.val > p.val:
                root = root.left
            elif root.val < q.val and root.val < p.val:
                root = root.right
            else:
                return root

总结本题:

  1. 基线条件是父节点的值介于num1和num2中(闭区间),
    即(root.val-num1) * (root.val-num2) <= 0
  2. 递归条件是从根节点开始,大了往左走,小了往右走
  3. 注意:==因为是从根节点开始走的,所以第一个节点一定就是目标节点==

237. 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 – head = [4,5,1,9]，它可以表示为:

img

示例 1:

1
2
3
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

1
2
3
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明:

  • 链表至少包含两个节点。
  • 链表中所有节点的值都是唯一的。
  • 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
  • 不要从你的函数中返回任何结果。

这个题目和我们平时解题的思路不一样，给我们的这个node就是链表的一部分，直接在上面操作就可以了，不要纠结为什么没有head。

1
2
3
4
5
# 将node的val修改为后继结点的val,然后让node的后继结点当自己的替死鬼
# 简单来说就是:让下一个节点直接死掉，自己替代它
class Solution:
    def deleteNode(self, node): 
        node.val,node.next = node.next.val,node.next.next

这种解法有一个限制:
题目是建立在删除的节点不是末尾节点的，如果是末尾节点，则不能使用该题解了，需要从头遍历到尾去删除指定的节点。

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。

示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
输入: s = "rat", t = "car"
输出: false

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

最简单的代码肯定是使用字典:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def isAnagram(self, s, t):
        if len(s) != len(t):
            return False
        s_dict = {each:0 for each in s}
        t_dict = {each:0 for each in t}
        for idx in range(len(s)):
            s_dict[s[idx]] += 1
            t_dict[t[idx]] += 1

        if s_dict != t_dict:
            return False
        else:
            return True

当然也可以使用集合和count函数:

1
2
3
4
5
6
class Solution(object):
    def isAnagram(self, s, t):
        for each in set(s)|set(t):
        	if s.count(each) != t.count(each):
        		return False
        return True

甚至直接导入Counter

1
2
3
4
from collections import Counter
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s)==Counter(t)

或者直接排序:

1
2
3
class Solution(object):
	def isAnagram(self, s, t):
		return sorted(s) == sorted()

注意字典的get方法:

1
2
3
4
5
6
7
8
9
class Solution(object):
    def isAnagram(self, s, t):
        dict1,dict2 = {},{}
        
        for item in s:
            dict1[item] = dict1.get(item,0) + 1
        for item in t:    
            dict2[item] = dict2.get(item,0) + 1
        return dict1 == dict2

经验:==使用字典的dict1.get(item,0) + 1方法实现新key的插入和val的递增==

257. 二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

1
2
3
4
5
6
7
8
输入:
   1
 /   \
2     3
 \
  5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def binaryTreePaths(self, root):
        if not root:
            return root
        result = []
        self.binaryTreePath(root, '', result)
        return result
    # DFS:传入result作为参数
    def binaryTreePath(self, root, path, result):
        # 如果是叶节点
        if not root.left and not root.right:
            # 每到一个叶节点就将路径append到result列表中
            result.append(path + str(root.val))
        if root.left:
            self.binaryTreePath(root.left,path+str(root.val)+'->',result)
        if root.right:
            self.binaryTreePath(root.right,path+str(root.val)+'->', result)

经验:

  1. ==在递归里,如果要返回扁平的列表,基本上都要新建一个函数,并且该函数传入该列表作为参数.==这种做法利用了列表的可变性.
  2. 如果要串联字符串的话,一样是要将字符串当成参数传入递归函数.因为字符串是不变,所以传入的实参是变化的.
  3. ==如果需要记录递归中的信息,那么就需要将该信息设置为函数的参数,如果该参数的数据类型是可变的,那么传入的实参就是不变的,如果传入的数据类型是不变的,那么传入的实参就是可变的==.

258. 各位相加

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

示例:

1
2
3
输入: 38
输出: 2 
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？

我的代码:

1
2
3
4
5
6
7
8
9
class Solution(object):
    def addDigits(self, num):
        while num > 9:
        	res = 0
        	while num:
        		num,remain = divmod(num,10)
        		res += remain
        	num = res
        return num

进阶代码:

1
2
3
4
5
6
7
8
class Solution:
    def addDigits(self, num):
        if num == 0:
            return 0
        elif num % 9 == 0:
            return 9
        else:
            return num % 9

也可以写成:

1
2
3
4
5
class Solution:
    def addDigits(self, num):
        if num % 9 == 0 and num != 0:
            return 9
        return num % 9

或者:

1
2
3
4
5
6
7
# 1-9对应输出1-9，这个很容易看出来10 -18对应输出1-9
# 总结一下发现，1-无穷 是循环输出1-9
class Solution(object):
    def addDigits(self, num):
        if num==0:
            return 0
        return (num-1)%9+1

263. 丑数

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

1
2
3
输入: 6
输出: true
解释: 6 = 2 × 3

示例 2:

1
2
3
输入: 8
输出: true
解释: 8 = 2 × 2 × 2

示例 3:

1
2
3
输入: 14
输出: false 
解释: 14 不是丑数，因为它包含了另外一个质因数 7。

说明：

  1. 1 是丑数。
  2. 输入不会超过 32 位有符号整数的范围: [−2^31^, 2^31^ − 1]。

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def isUgly(self, num):
        # 特殊情况
        if num == 0:
            return False

        while num%2 == 0:
            num //= 2
        while num%3 == 0:
            num //= 3
        while num%5 == 0:
            num //= 5

        return num == 1

还可以使用递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isUgly(self, num: int) -> bool:
	    if num <= 0:
	        return False
	    if num%2 == 0:
	        return self.isUgly(num//2)
	    if num%3 == 0:
	        return self.isUgly(num//3)
	    if num%5 == 0:
	        return self.isUgly(num//5)
	    if num == 1:
	        return True
	    else: 
	        return False

268. 缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

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

示例 2:

1
2
输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

我的代码:

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def missingNumber(self, nums):
        a = (len(nums)+1) / 2 * len(nums)
        tot = 0
        for each in nums:
            tot += each
        # 如果缺最大数
        if (len(nums)-1) / 2 * len(nums) - tot == len(nums):
            return len(nums)
        return int(a-tot)

题目要求使用常数空间来实现,这里仅用了O(1),这代码体现了python的语言优势:真除法.

也可以或使用下面代码:

1
2
3
4
class Solution:
    def missingNumber(self, nums):
        t=len(nums)
        return sum(range(t+1))-sum(nums)

进阶的代码是使用异或:

1
2
3
4
5
6
7
8
9
# 4 ^ 4 = 0
# 0 ^ 4 = 4
class Solution:
    def missingNumber(self, nums):
        res = len(nums)
        for i in range(len(nums)):
            res ^= i
            res ^= nums[i]
        return res

写成下面的比较好理解:

1
2
3
4
5
6
7
class Solution:
    def missingNumber(self, nums):
        res = len(nums)
        for i in range(len(nums)):
            # 不断的(i^nums[i])就能找出缺少的值
            res ^= (i^nums[i])
        return res

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

1
2
3
4
5
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

代码一如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):
class Solution:
    def firstBadVersion(self, n):
        left = 1
        right = n
        mid = int(left+(right-left)/2)
        while left <= right:
            if isBadVersion(mid):
                right = mid-1
            else:
                left = mid+1
            mid = int(left+(right-left)/2)
        return left

代码二如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def firstBadVersion(self, n):
        # 头元素
        low = 1
        # 伪元素
        high = n
        # 没有等号,等号成立的时候就退出循环
        while low < high:
            mid = (low + high) //2
            if isBadVersion(mid):
                # 高不加
                high = mid
            else:
                # 低加一
                low = mid + 1
        # 此时low==high,所以可以二选一
        return low

新时代的二分法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def firstBadVersion(self, n):
        left = 1
        # 利用左闭右开的特性，所以右端点加1，
        # 好处是当while loop终止时，right、mid、left三者取值相同
        # 不用思考需要返回哪一个，返回哪一个都是正确的
        right = n+1
        while(left<right):
            # 注意这里的mid取值
            mid = left + (right-left)//2
            if(isBadVersion(mid)==False):
                left = mid + 1
            else:
                right = mid
        return right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def searchInsert(self, nums, target) -> int:
        low = 0
        # 左闭右开
        # 唯一注意:这里是len(nums),不是len(nums)-1
        high = len(nums)
        while low < high:
            # # 注意这里的mid取值
            mid = low + (high - low)//2
            if nums[mid] > target:
                high = mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                return mid
        return low

经验:对于二分法

  1. 使用==high=mid,low=mid+1==,这样while low<high退出的时机一定是low=high.不要再使用high=mid-1,low=mid+1,这样很不好控制.
  2. ==使用左闭右开的区间==用于查找.这样的好处是，当while loop终止时(提前break出来的不算)，left、right、mid三个索引取值全相同
  3. 使用==mid = low + (high - low) // 2==,这样就保证了left、right一致.

二分法练习:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# chars为***###,找出第一个#的索引
def find_char(chars):
    left = 0
    # 左闭右开
    right = len(chars)

    while left < right:
        # 使用mid = low + (high - low) // 2
        mid = left + (right - left) // 2
        if chars[mid] == '#':
            # right不加一
            right = mid
        else:
            left = mid + 1
    return left

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

1
2
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  1. 必须在原数组上操作，不能拷贝额外的数组。
  2. 尽量减少操作次数。

我的代码:

1
2
3
4
5
6
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        for each in nums[::-1]:
            if each == 0:
                nums.remove(each)
                nums.append(0)

但是这是删除后添加,而不是移动,而且上面的代码效率较低.正确的代码如下:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def moveZeroes(self, nums):
        k = 0
        # 此次遍历的目的:将不为0的元素复制到前面,记录复制了多少个元素
        for i in nums:
            if i != 0:
                nums[k] = i
                k += 1
		# 既然有k个不为零的元素,并且这些元素都移动到了前面,那么后面元素都是0
        for i in range(k,len(nums)):
            nums[i] = 0

上面的代码很不好理解
思路:使用一个变量k记录位置，我们通过遍历nums数组，将不为0的元素依次复制到nums的前面，并且记录我们复制了多少个元素，对len(nums)-k的元素置0即可。
最难理解就是第7行的nums[k]=i:
k指出某个非零元素是第几个非零元素,而i是这个非零元素的索引.所以整句就是将这个元素复制到前面去.

还有一种写法:

1
2
3
4
5
6
7
8
9
# 交换非零元素和零元素
class Solution:
    def moveZeroes(self, nums):
        # k记录非零元素应该换到第几个位置
        k = 0
        for i, num in enumerate(nums):
            if num != 0:
                nums[i], nums[k] = nums[k], nums[i]
                k += 1

经验:
注意这种设置一个标记变量,在迭代中记录标记的思路.

290. 单词模式

给定一种 pattern(模式) 和一个字符串 str ，判断 str 是否遵循相同的模式。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式。

示例1:

1
2
输入: pattern = "abba", str = "dog cat cat dog"
输出: true

示例 2:

1
2
输入:pattern = "abba", str = "dog cat cat fish"
输出: false

示例 3:

1
2
输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false

示例 4:

1
2
输入: pattern = "abba", str = "dog dog dog dog"
输出: false

说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def wordPattern(self, pattern, str):
        pattern_dict = {}
        str_dict = {}
        str_list = str.split(' ')

        if len(str_list) != len(pattern):
            return False

        for idx in range(len(str_list)):
            if str_list[idx] not in str_dict:
                str_dict[str_list[idx]] = pattern[idx]
            else:
                if str_dict[str_list[idx]] != pattern[idx]:
                    return False

            if pattern[idx] not in pattern_dict:
                pattern_dict[pattern[idx]] = str_list[idx]
            else:
                if pattern_dict[pattern[idx]] != str_list[idx]:
                    return False
        return True

292. Nim游戏

你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

1
2
3
输入: 4
输出: false 
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

代码如下:只要不是4的倍数就是我赢

1
2
3
4
5
class Solution:
    def canWinNim(self, n: int) -> bool:
        if n % 4 == 0:
            return False
        return True

或者:

1
2
3
class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

这道题可以找规律:可知当n等于4的时候我输.也就是说当n=4的时候后手赢.所以只要n=4的时候我是后手就赢了.所以当n=5,6,7的时候,我能保证n=4的时候我是后手.
相反,当n=8的时候对手能保证当n=4的时候自己是后手,所以n=8时我就输了.所以说当n=8的时候后手赢

这其实是巴什博奕，n%(m+1) != 0时，先手总是会赢的(两个顶尖聪明的人在玩游戏，有个n石子，每人可以随便拿1到m个石子，不能拿的人为败者，问谁会胜利)

303. 区域和检索 - 数组不可变

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

示例：

1
2
3
4
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明:

  1. 你可以假设数组不可变。
  2. 会多次调用 sumRange 方法。

正常思路:

1
2
3
4
5
class NumArray:
    def __init__(self, nums):
        self.nums=nums      
    def sumRange(self, i, j):
        return sum(self.nums[i:j+1])

但是这样会超级慢,正确的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class NumArray:
    def __init__(self, nums):
        self.res = nums
        # 从1开始
        for i in range(1, len(nums)):
            # 每个位置的值，代表当前位置之前所有值的和
            self.res[i] += self.res[i-1]

    def sumRange(self, i, j):
        if i == 0:
            return self.res[j]
        else:
            # 包含两端边界
            return self.res[j] - self.res[i-1]

上面代码其实就是动态规划,不过是在原地修改数值,也可以不原地修改:

1
2
3
4
5
6
7
8
9
10
11
class NumArray:
    def __init__(self, nums: List[int]):
        # 多设置一个值
        self.dpl = [0]*(len(nums)+1)
        self.dpl[0] = 0

        for i in range(1,len(nums)+1):
            self.dpl[i] = self.dpl[i-1] + nums[i-1]

    def sumRange(self, i: int, j: int) -> int:
        return self.dpl[j+1]-self.dpl[i]

326. 3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。

示例 1:

1
2
输入: 27
输出: true

示例 2:

1
2
输入: 0
输出: false

示例 3:

1
2
输入: 9
输出: true

示例 4:

1
2
输入: 45
输出: false

进阶：
你能不使用循环或者递归来完成本题吗？

第一想法肯定是:

1
2
3
4
5
6
7
8
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n == 0:
            return False
            
        while n % 3 == 0:
            n //= 3
        return n == 1

其实这道题不是为python准备的,因为整数有大小范围限制，可以找出整数的最大的3次幂的值,

1
2
3
public boolean isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

当然python可以使用对数:

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        import math
        if n <= 0:
            return False
        else:
            # 求以3为底的对数
            a = math.log(n,3)
            # 注意精度问题
            return abs(a - round(a)) < 0.000000000001

如果是精度问题,更适合这种写法:

1
2
3
4
5
6
7
8
9
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        import math
        if n <= 0:
            return False
        else:
            a = math.log(num, 3)
            # 使用a==int(a)
            return a == int(a)

342. 4的幂

给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

示例 1:

1
2
输入: 16
输出: true

示例 2:

1
2
输入: 5
输出: false

进阶：
你能不使用循环或者递归来完成本题吗？

代码和上一题一样:

1
2
3
4
5
6
7
8
class Solution:
    def isPowerOfFour(self, num: int) -> bool:
        if num == 0:
            return False
            
        while num % 4 == 0:
            num //= 4
        return num == 1

有意思的解法:

1
2
3
4
5
# 4的幂一定是2的幂，二进制表示都只有一个1，
# 且4的幂二进制表示里其唯一的1位一定在奇数位上，2的幂反之
class Solution:
    def isPowerOfFour(self, num: int) -> bool:
        return bin(num)[2:].count("0") % 2 == 0 and bin(num)[2:].count("1") == 1 and num > 0

或者:

1
2
3
4
5
6
# 4的幂次减一 一定是3的倍数
class Solution(object):
    def isPowerOfFour(self, num):
        if num < 0 or num & (num-1):
            return False
        return (num - 1) % 3 == 0

或者:

1
2
3
class Solution:
    def isPowerOfFour(self, num):
        return num > 0 and not (num & (num - 1)) and len(bin(num)) % 2 == 1

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

1
2
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

1
2
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

最直接的想法肯定是:

1
2
3
class Solution:
    def reverseString(self, s: List[str]) -> None:
        s.reverse()

第二个想法肯定是双指针:

1
2
3
4
5
6
7
8
class Solution:
    def reverseString(self, s: List[str]) -> None:
        left = 0
        right = len(s) -1
        while left < right:
            s[left],s[right] = s[right],s[left]
            left += 1
            right -= 1

当然你也可以这么写:

1
2
3
4
5
class Solution:
    def reverseString(self, s: List[str]) -> None:
        a = len(s) - 1
        for i in range(len(s)//2):
            s[i],s[a-i]=s[a-i],s[i]

345. 反转字符串中的元音字母

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1:

1
2
输入: "hello"
输出: "holle"

示例 2:

1
2
输入: "leetcode"
输出: "leotcede"

说明:
元音字母不包含字母”y”。

我的代码:还是使用双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def reverseVowels(self, s: str) -> str:
        s = list(s)
        x = ['a','e','i','o','u','A','E','I','O','U']
        left = 0
        right = len(s) - 1

        while left < right:
            while s[left] not in x and left < right:
                left += 1
            while s[right] not in x and left < right:
                right -= 1

            s[left],s[right] = s[right],s[left]
            left += 1
            right -= 1

        return ''.join(s)

349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

1
2
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

1
2
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:

  • 输出结果中的每个元素一定是唯一的。
  • 我们可以不考虑输出结果的顺序。

第一想法肯定是:

1
2
3
class Solution:
    def intersection(self,nums1:List[int], nums2:List[int])->List[int]:
        return list(set(nums1) & set(nums2))

一般来说dict速度是最快的:

1
2
3
4
5
6
7
8
9
10
class Solution:
    def intersection(self, nums1, nums2):
        a = {}
        for i in nums1:
            if i in a:
                a[i] += 1
            else:
                a[i] = 0
        r = [each for each in nums2 if each in a]
        return list(set(r))

350. 两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

1
2
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:

1
2
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：

  • 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。

进阶:

  • 如果给定的数组已经排好序呢？你将如何优化你的算法？
  • 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
  • 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

代码如下:

1
2
3
4
5
6
7
8
class Solution(object):
    def intersect(self, nums1, nums2):

        inter = set(nums1) & set(nums2)
        l = []
        for i in inter:
            l += [i] * min(nums1.count(i), nums2.count(i))  
        return l

或者使用dict:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def intersect(self,nums1, nums2):
        """使用hash"""
        d1 = {}
        d2 = {}
        for each in nums1:
            d1[each] = d1.get(each,0) + 1
        for each in nums2:
            d2[each] = d2.get(each,0) + 1

        inners = []
        # 同时遍历两个字典
        for key in (d1.keys() if len(d1)<len(d2) else d2.keys()):
            if d1.get(key) != None and d2.get(key) != None:
                inners.extend([key]*min(d1.get(key),d2.get(key)))
        return inners

经验:

  1. ==同时遍历两个字典使用if d1.get(key) and d2.get(key):==
  2. 注意for key in (d1.keys() if len(d1)<len(d2) else d2.keys())的用法

当然也可以使用最普通的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        d={}
        res=[]
        for i in nums1:
            if i in d:
                d[i]+=1
            else:
                d[i]=1
        for i in nums2:
            if i in d and d[i]>0:
                res.append(i)
                d[i]-=1
        return res

367. 有效的完全平方数

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

说明：不要使用任何内置的库函数，如 sqrt。

示例 1：

1
2
输入：16
输出：True

示例 2：

1
2
输入：14
输出：False

耍赖的做法:

1
2
3
4
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        a = num**0.5
        return int(a) == a

还可以使用:

1
2
3
class Solution(object):
    def isPerfectSquare(self, num):
        return num **0.5 % 1 == 0

经验:判断一个数是不是整数有两种方法:

  1. ==int(a) == a==
  2. ==a % 1 == 0==

当然可以使用二分法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left = 0
        right = num + 1

        while left < right:
            mid = left + (right - left) // 2
            if mid**2 > num:
                right = mid
            elif mid**2 < num:
                left = mid + 1
            else:
                return True
        return False

正确方法是使用牛顿逼近法:
从函数意义上理解：我们是要求函数f(x) = x²，使f(x) = num的近似解，即x² - num = 0的近似解。
从几何意义上理解：我们是要求抛物线g(x) = x² - num与x轴交点（g(x) = 0）最接近的点。
我们假设g(x0)=0，即x0是正解，那么我们要做的就是让近似解x不断逼近x0，这是函数导数的定义：

$f’(x_0) = \lim_{x\to x_0}\frac{f(x)-f(x0)}{x-x_0}$

可以由此得到

$x_0 = x-\frac{f(x)}{f’(x)}​$

得到:

$x_{n+1} = x_n-\frac{f(x_n)}{f’(x_n)}​$

1
2
3
4
5
6
7
8
9
10
11
#  牛顿逼近法本来就是求方程近似解的，
#  题目本来就是f(x)=x*x - num = 0，有整数解。
#  不断逼近整数解的Xn = Xm - f(Xm) / f'(Xm)。
#  如果能得到这个Xn就可以返回True了。 f'(X)是f(X)的导数，为2x，
#  因此Xn=(Xm - num / Xm) / 2 持续迭代下去就好了。
class Solution(object):
    def isPerfectSquare(self, num):
        r = num
        while r*r > num:
            r = (r + num/r) / 2
        return r*r == num

371. 两整数之和

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1:

1
2
输入: a = 1, b = 2
输出: 3

示例 2:

1
2
输入: a = -2, b = 3
输出: 1

a ^ b是无进位的相加；
a&b得到每一位的进位；
让无进位相加的结果与进位不断的异或， 直到进位为0；

代码如下:

1
2
3
4
5
class Solution:
    def getSum(self, a, b):
        if a&b==0:
            return a|b
        return self.getSum(a^b,(a&b)<<1)

374. 猜数字大小

我们正在玩一个猜数字游戏。 游戏规则如下：
我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。
每次你猜错了，我会告诉你这个数字是大了还是小了。
你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）：

1
2
3
-1 : 我的数字比较小
 1 : 我的数字比较大
 0 : 恭喜！你猜对了！

示例 :

1
2
输入: n = 10, pick = 6
输出: 6

使用二分法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num):
class Solution(object):
    def guessNumber(self, n):
        left = 1
        right = n + 1
        while left < right:
            mid = left + (right - left) // 2
            if guess(mid) == 1:
                left = mid + 1
            elif guess(mid) == -1:
                right = mid
            else:
                return mid
        return left

383. 赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)
简单来说:只要是ransomNote的每个字符包含于magazine就好啦。

注意：

你可以假设两个字符串均只含有小写字母。

1
2
3
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

代码如下:

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        d = {}
        for i in magazine:
            d[i] = d.get(i, 0) + 1
        for i in ransomNote:
            d[i] = d.get(i, 0) - 1

            if d[i] < 0:
                return False
        return True

经验:==字典计数问题可以先后使用d[i] = d.get(i, 0) + 1,d[i] = d.get(i, 0) - 1然后判断d[i]的大小==

还可以使用count函数

1
2
3
class Solution:
    def canConstruct(self, ransomNote, magazine):
        return all([magazine.count(i) >= ransomNote.count(i) for i in set(ransomNote)])

387. 字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

案例:

1
2
3
4
s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.

注意事项：您可以假定该字符串只包含小写字母。

我的代码:

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def firstUniqChar(self, s):
        count_dict = {}
        for each in s:
            count_dict[each] = count_dict.get(each,0) + 1
        
        y = [key for key,value in count_dict.items() if value == 1]
        for idx in range(len(s)):
            if s[idx] in y:
                return idx
        return -1

第7行新开辟了空间,不太好:

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def firstUniqChar(self, s):
        hash_map = dict()
        for char in s:
            hash_map[char] = hash_map.get(char,0) + 1
        for i in range(len(s)):
            char = s[i]
            # 不开辟空间,直接使用
            if char in hash_map and hash_map[char] == 1:
                return i
        return -1

可以用空间换时间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def firstUniqChar(self, s):
        # 用于记录所有字母的次数  eg:{a:9}
        count_dict = {}
        # 用于记录第一个字母的idx eg:{a:1}
        idx_dict = {}

        for idx in range(len(s)):
            if not s[idx] in idx_dict:
                idx_dict[s[idx]] = idx
            count_dict[s[idx]] = count_dict.get(s[idx],0) + 1

        x = [idx_dict[char] for char,count in count_dict.items() if count == 1]
        return min(x)if x else -1

当然也可以这么用:

1
2
3
4
class Solution(object):
    def firstUniqChar(self, s):
        l = [each for each in s if s.count(each) == 1]
        return 0 if l else -1

上面的复杂度高到报表,真正的代码:

1
2
3
4
5
class Solution:
    def firstUniqChar(self, s):
        # 从左向右找==从右向左找
        l = [s.find(i) for i in set(s) if s.find(i)==s.rfind(i)]
        return min(l) if l else -1

下面的代码速度也很快:

1
2
3
4
5
class Solution:
    def firstUniqChar(self, s):        
        letters='abcdefghijklmnopqrstuvwxyz'
        index=[s.index(l) for l in letters if s.find(l) != -1 and s.find(l) == s.rfind(l)]
        return min(index) if len(index) > 0 else -1

上面两个代码,一个使用了set(s),另一个使用letters.速度差不多.

经验:==找出只有一个的元素==可以使用:

  1. s.find(i)==s.rfind(i)
  2. s.count(i)==1
  3. 异或:数字与自身异或结果为0

389. 找不同

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例:

1
2
3
4
5
输入：
s = "abcd"
t = "abcde"
输出：e
解释：'e' 是那个被添加的字母。

我的代码:

1
2
3
4
5
class Solution(object):
    def findTheDifference(self, s, t):
        for each in set(t):
            if s.count(each) != t.count(each):
                return each

或者使用dict:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def findTheDifference(self, s, t):
        dict_s = {}
        dict_t = {}
        for each in s:
            dict_s[each] = dict_s.get(each,0) + 1
        for each in t:
            dict_t[each] = dict_t.get(each,0) + 1

        for each in dict_t:
            if dict_t.get(each) != dict_s.get(each):
                return each

真正的做法,应该使用位运算:==数字与自身异或结果为0==

1
2
3
4
5
6
class Solution:
    def findTheDifference(self, s, t):
        ret = 0
        for c in s + t:
            ret ^= ord(c)
        return chr(ret)

经验:==每次要找唯一元素的时候就应该考虑异或==

400. 第N个数字

在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …中找到第 n 个数字。

注意:
n 是正数且在32为整形范围内 ( n < 2^31^)。

示例 1:

1
2
输入:3
输出:3

示例 2:

1
2
3
输入:11
输出:0
说明:第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。

解释一下题意，
当变量n为11时,这个字符串就是1234567891011,然后问这个字符串的第11位是什么数字,为0
当变量n为12时,这个字符串就是123456789101112,然后问这个字符串的第12位是什么数字,为1

1
2
3
4
个位数：1-9，一共9个,共计1*9=9个数字
2位数：10-99,一共90个，共计2*90=180个数字
3位数：100-999，一共900个，共计3*900=2700个数字
4位数，1000-9999，一共9000个，共计4*9000=36000个数字

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 第一步确定n是在几位数里，第二步是确定在几位数的第几位数字的第几位
class Solution(object):
    def findNthDigit(self, n):
        # 第一步
        # 位数
        digit = 1 
        while n > digit*9*10**(digit-1):
            n -= digit*9*10**(digit-1)
            digit += 1

        # 第二步
        # 得到几位数的第几位数字
        a = int((n-1)/digit) 
        # 得到几位数的第几位数字的第几位
        b = int((n-1)%digit)
        # 得到第几位数字是多少
        num = 10**(digit-1)+a
        # 数字转字符再转列表把第几位数的第几位切出来
        res = list(str(num))[b:b+1]
        # 列表转字符再转数字
        return int(''.join(res))

或者:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findNthDigit(self, n):
        if n < 10:
            return n
        # 多少位数
        i = 1
        while n > 9 * 10 **(i - 1) * i:
            n -= 9 * 10 **(i - 1) * i
            i += 1
        
        if n % i == 0:
            return int(str(10 ** (i - 1) + n // i - 1)[-1])
        else:
            return int(str(10 ** (i - 1) + n // i)[n%i-1])

或者:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def findNthDigit(self, n):
        # 多少位数
        w = 1
        # 某位数有多少个数字(如w=2时k=9*10=90)
        k = 9
        while n > k * w:
            n -= k * w
            k *= 10
            w += 1
        tmp = 10 ** (w - 1) + (n - 1) / w 
        return int(str(tmp)[(n - 1) % w])

401. 二进制手表

二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。

每个 LED 代表一个 0 或 1，最低位在右侧。

img

例如，上面的二进制手表读取 “3:25”。

给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。

案例:

1
2
输入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

注意事项:

  • 输出的顺序没有要求。
  • 小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
  • 分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。

代码如下:暴力求解

1
2
3
4
5
6
7
8
9
class Solution:
    def readBinaryWatch(self, num):
        ret = []
        for hour in range(12):         
            for minute in range(60):
                # hours和mins的二进制位数和等于num
                if (bin(hour) + bin(minute)).count('1') == num:
                    ret.append('%d:%02d' % (hour, minute))               
        return ret

404. 左叶子之和

计算给定二叉树的所有左叶子之和。

示例：

1
2
3
4
5
6
7
    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

代码如下:

1
2
3
4
5
6
7
8
9
class Solution:
    def sumOfLeftLeaves(self, root):
        if not root:
            return 0
        # root.left存在,root.left不存在左右节点,说明root.left就是左叶子
        if root.left and not root.left.left and not root.left.right:
            return root.left.val + self.sumOfLeftLeaves(root.right)
        else:
            return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

405. 数字转换为十六进制数

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

注意:

  1. 十六进制中所有字母(a-f)都必须是小写。
  2. 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
  3. 给定的数确保在32位有符号整数范围内。
  4. 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

示例 1：

1
2
输入:26
输出:"1a"

示例 2：

1
2
输入:-1
输出:"ffffffff"

码位复习:

  1. 设计原码,反码,补码就是为了让符号位也参与计算.
  2. 一个数的最高位存放符号,正数为0,负数为1.
  3. 机器数是带符号的二进制数,真值就是将符号位当成正常数字的二进制数.
    (eg:机器数10000011是-3,真值10000011是131)
  4. 原码就是第一位表示符号,其余为表示值.
  5. 正数的反码是本身,负数的反码是符号位不变,其余按位取反.
    (所以说反码还是依靠符号位来判断数字的正负)
  6. 正数的补码是本身,负数的补码是符号位不变,其余按位取反,最后+1.

我的代码:(没有写当num是负数的情况)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def toHex(self, num):
        hashmap = '0123456789abcdef'
        if num > 0:
            res = ''
            while num:
                num,remain = divmod(num,16)
                res = hashmap[remain] + res
            return res
        elif num < 0:
            ...
        else:
            return '0'

上面11行缺的代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
if num < 0:   # 求补码 
    begin=1   # 初始标记位
    add = 0   # 进位标志
    num = abs(num)
    
    while num != 0:
        x = num % 16
        
        if begin: # 首位计算
            if x==0:
                add=1
            else:
                x = 16-x # 取补
            begin = 0
        else:
            if x == 0 and add==1:
                x=x
            else:
                x = 15-x+add # 取反
                add = 0

        rslt = dic[x]+rslt
        num = num>>4
    # 补位     
    rslt = 'f'*(8-len(rslt))+rslt
return rslt

正确的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
# 使用位运算，每4位，对应1位16进制数字。
# 使用0xf(00...01111b)获取num的低4位。
# >>算数位移，其中正数右移左边补0，负数右移左边补1。!
class Solution(object):
    def toHex(self, num):
        result = ''
        alpha = '0123456789abcdef'
        if num == 0:
            return '0'
        while num != 0 and len(result) < 8:
            result += alpha[num & 0xf]
            num = num >> 4
        return result[::-1]

409. 最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。

示例 1:

1
2
3
输入:"abccccdd"
输出:7
解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 如果一个字符出现偶数次，那么它必定对于构造回文串有帮助，
# 如果一个字符出现奇数次，那么它的（奇数次 - 1）也可以用于构造回文串
# 如果一个数出现一次，那么它可以用于放在中间。
class Solution:
    def longestPalindrome(self, s: str) -> int:
        d = {}
        for each in s:
            d[each] = d.get(each,0) + 1

        res = 0
        has_alone = False
        for count in d.values():
            if count % 2 == 1:
                res += (count - 1)
                has_alone = True
            else:
                res += count
        return res + 1 if has_alone else res

还有高端洋气的做法:

1
2
3
class Solution:
    def longestPalindrome(self, s: str) -> int:
        return len(s) - max(0,sum([s.count(i)%2 for i in set(s)])-1)

412. Fizz Buzz

写一个程序，输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是3的倍数，输出“Fizz”；

  2. 如果 n 是5的倍数，输出“Buzz”；

  3. 如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = 15,
返回:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

最无脑的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        res = []
        for each in range(1,n+1):
            if each % 15 == 0:
                res.append('FizzBuzz')
            elif each % 3 == 0:
                res.append('Fizz')
            elif each % 5 == 0:
                res.append('Buzz')
            else:
                res.append(str(each))
        return res

可以合并这些代码:

1
2
3
4
5
6
class Solution:
    def fizzBuzz(self, n):
        res = []
        for i in range(1,n+1):
            res.append('Fizz'[i%3*len('Fizz')::]+'Buzz'[i%5*len('Buzz')::] or str(i))
        return res

414. 第三大的数

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1:

1
2
3
输入: [3, 2, 1]
输出: 1
解释: 第三大的数是 1.

示例 2:

1
2
3
输入: [1, 2]
输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .

示例 3:

1
2
3
输入: [2, 2, 3, 1]
输出: 1
解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。存在两个值为2的数，它们都排第二。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        first,second,third= float('-inf'),float('-inf'),float('-inf')
        for num in nums:
            if num > first:
                first,second,third = num,first,second
            elif second < num < first:
                second,third = num,second
            elif third < num < second:
                third = num
        return third if third != float('-inf') else first

经验:==对于这种第n大的问题,都可以使用这种推挤的方式==

或者:

1
2
3
4
5
6
7
8
9
10
class Solution:
    def thirdMax(self, nums):
        # 先转为set
        nums1 = list(set(nums))
        if len(nums1) < 3:
            return max(nums1)
        else:
            nums1.remove(max(nums1))
            nums1.remove(max(nums1))
            return max(nums1)

415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意：

  1. num1 和num2 的长度都小于 5100.
  2. num1 和num2 都只包含数字 0-9.
  3. num1 和num2 都不包含任何前导零。
  4. 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def addStrings(self, num1, num2):
        # 首先反转
        num1_r = num1[::-1]
        num2_r = num2[::-1]
        
        carry, ret, i = 0, '', 0
        while i < len(num1_r) or i < len(num2_r):
            a = 0 if i >= len(num1_r) else int(num1_r[i])
            b = 0 if i >= len(num2_r) else int(num2_r[i])
            ret += str((a+b+carry)%10)
            carry = (a+b +carry) // 10
            i += 1
        if carry: ret += '1'
        return ret[::-1]

427. 建立四叉树

我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。网络中每一格的值只会是真或假。树的根结点代表整个网络。对于每个结点, 它将被分等成四个孩子结点直到这个区域内的值都是相同的.

每个结点还有另外两个布尔变量: isLeaf 和 val。isLeaf 当这个节点是一个叶子结点时为真。val 变量储存叶子结点所代表的区域的值。

你的任务是使用一个四叉树表示给定的网络。下面的例子将有助于你理解这个问题：

给定下面这个8 x 8 网络，我们将这样建立一个对应的四叉树：

img

由上文的定义，它能被这样分割：

img

对应的四叉树应该像下面这样，每个结点由一对 (isLeaf, val) 所代表.

对于非叶子结点，val 可以是任意的，所以使用 * 代替。

img

提示：

  1. N 将小于 1000 且确保是 2 的整次幂。
  2. 如果你想了解更多关于四叉树的知识，你可以参考这个 wiki 页面。

题意为，将一个大区域划分为若干个小区域（要求每个小区域中的val全部一致），每次都是将一个大区域划分为4份（直到小区域val全部一致，终止）。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for a QuadTree node.
# class Node:
#     def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
#         self.val = val
#         self.isLeaf = isLeaf
#         self.topLeft = topLeft
#         self.topRight = topRight
#         self.bottomLeft = bottomLeft
#         self.bottomRight = bottomRight
class Solution:
    def construct(self, grid):
        if not grid:
            return None
        if self.is_leaf(grid):
            return Node(grid[0][0] == 1, True, None, None, None, None)
        n = len(grid)
        return Node("*", False, self.construct([row[:n // 2] for row in grid[:n // 2]]),
            self.construct([row[n // 2:] for row in grid[:n // 2]]),
            self.construct([row[:n // 2] for row in grid[n // 2:]]),
            self.construct([row[n // 2:] for row in grid[n // 2:]])
            )

    def is_leaf(self,grid):
        # print(grid)
        vals = set()
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                vals.add(grid[i][j])
                if len(vals) > 1:
                    return False
        return True

或者:

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def construct(self, grid):
        def Tree(grid,x,y,length):
            for i in range(x,x+length):
                for j in range(y,y+length):
                    if grid[i][j] != grid[x][y]:
                        return Node(False,False,Tree(grid,x,y,length/2),Tree(grid,x,y+length/2,length/2),
                                   Tree(grid,x+length/2,y,length/2),Tree(grid,x+length/2,y+length/2,length/2))
            return Node(grid[x][y]==1,True,None,None,None,None)
        return Tree(grid,0,0,len(grid))