注意空间换时间

当复杂度太高的时候,总是应该考虑以空间换时间

比较多个序列

如果比较数组for循环的两个each,可以考虑是不是只需比较最长和最短的两个.
如果是在不行,可以取出数组的第一个值,然后使用for循环.

先获取idx后截取 和 滑动窗口

模仿find函数可以使用类似于滑动窗口的设计

也就是说,对于序列,我们不一定要当场截取,可以获取需要的idx,最后再来截取:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。
# 如果不存在最后一个单词，请返回 0 
class Solution:
    def lengthOfLastWord(self, s):
        tail = len(s) - 1

        while tail >= 0 and s[tail] == ' ':
            tail -= 1

        head = tail

        while head >= 0 and s[head] != ' ':
            head -= 1

        return tail - head

进位的相加问题

相加问题都要想到设置进位变量up,并且在最后出了循环后还要检查up

正常操作是:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def plusOne(self, digits):
        up = 1

        for idx in range(len(digits)-1,-1,-1):
            up,digits[idx] = divmod(digits[idx] + up,10)
            
            if up != 1:
                return digits

        if up == 1:
            digits.insert(0,1)
        return digits

  • quo,remain = divmod((string1[idx] + string2[idx] + up) ,进制)一样可以用于进制转换

    1
    up,num = divmod(int(a[idx]) + int(b[idx]) + up,2)

链表的常用操作

新建链表的时候都要设置dummyHead,然后最后return dummyHead.next

链表遍历最常使用

1
while(pre and pre.next)

或者:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def removeElements(self, head, val):
        pre = head
        # 使用while pre
        while pre:
            # 使用pre.next
            if pre.next and pre.next.val == val:
                pre.next = pre.next.next
            else:
                pre = pre.next
        # 处理头节点
        if head and head.val == val:
            return head.next
        else:
          7  return head

使用动态规划的思路

使用动态规划要确保每走一步都要调整状态转移方程.
前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
# 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

# 前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
class Solution:
    def maxProfit(self, prices):
        min_p = float('inf')
        res = 0
        
        for i in range(len(prices)):
            # 求出前i天最低价
            min_p = min(min_p, prices[i])：
            # 前i天的最高收益
            res = max(res, prices[i] - min_p)
        return res

s = Solution()
print(s.maxProfit([7,1,5,3,6,4]))  # 5

做动态规划题,总是要想到前一位的情况证明解,或者左边的情况怎么解

动态规划的设计思路:

  1. 首先，把我们面对的局面表示为x。这一步称为设计状态。
  2. 对于状态x，记我们要求出的答案(e.g. 最小费用)为f(x).我们的目标是求出f(T).
    找出f(x)与哪些局面有关（记为p），
  3. 写出一个式子（称为状态转移方程），通过f(p)来推出f(x).

动态规划:

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def maxSubArray(self, nums):
        # 阶段性求和
        tot = 0
        result = nums[0]

        for num in nums:
            tot += num
            result = max(result,tot)
            tot = max(tot,0)
        return result

常用形式就是:

  • tot阶段性状态
  • result最终状态
  • 我们就是在一系列阶段性状态中选出最终状态

同时遍历两棵树

同时遍历两颗树,那么这个函数就要接受两个参数,两个参数分别传入两个左子树和两个右子树

判断两棵树相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>class Solution:
   def isSameTree(self, p, q):
       # 如果不存在p,q(基线条件1)
       if not p and not q:
           return True
       # 如果pq都存在(递归条件)
       elif p and q :
           # 如果子树的根节点相同,就判断左右子树是否相同
           if p.val == q.val:
               return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
           else:
               return False
       # pq其中一者存在(基线条件2)
       else:
           return False

树的按层次索引

树的按层次索引类似于广度优先遍历 : 不需要使用递归

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
# 主要思路:将每层的节点倒序填充进res,然后将下一次要迭代的节点放入stack
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:   
        if not root: return []
        
        # 使用stack存放每层节点
        stack = [root]
        # 将来会倒序填充res
        res = []
        
        while len(stack) != 0:
            # 使用tmp存放每层节点的左右子节点
            tmp = []
            # res_each用于存放每一层的元素
            res_each = []
            for i in stack:
                # 将节点的值放入res_each中
                res_each.append(i.val)
                if i.left:
                    tmp.append(i.left)
                if i.right:
                    tmp.append(i.right)
            # 将下次要迭代的节点放入stack
            stack = tmp
            # 每次都在res头部添加
            res.insert(0,res_each)
            
        return res

寻找递归的基线条件要从传入的参数考虑

寻找递归的基线条件要从传入的参数考虑

同时迭代多个序列要使用zip

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def getRow(self, rowIndex):
        if rowIndex == 0:
            return [1]

        temp = [1]
        count = 0
        
        while count != rowIndex:
            temp = [1] + [a+b for a,b in zip(temp[1:],temp[:-1])] + [1]
            count += 1
        return temp

s = Solution()
print(s.generate(10))

摩尔投票算法

该算法用于解决寻找一个含有$n$个元素的数列${an}$中出现超过$\frac{1}{K}$(即大于$\frac{n}{K}$次)的元素（假设满足要求的元素存在）。满足要求的元素最多有$(k−1)$个。

摩尔投票算法可以快速的计算出一个数组中出现次数过半的数即大多数（majority），算法核心思想是同加，异减

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 这里的众数是指在数组中出现次数大于n/2的元素。
# 从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，
# 减到0就重新换个数开始计数，总能找到最多的那个
class Solution:
    def majorityElement(self, nums):
        count = result = 0
        for num in nums:
            # count等于零就换人
            if count == 0:
                result = num
	# 与result不相等就count-1,相等就count+1
            if result != num:
                count -= 1
            else:
                count += 1
                
        return result

s = Solution()
print(s.majorityElement([2,1,1,1,2,2,2]))

反转链表需要维护三个变量

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

        p = head
        s = head.next
        p.next = None

        while s:    
            head = s
            s = s.next
            head.next = p
            p = head

        return head

二叉树的搜索

  1. 递归条件是从根节点开始,大了往左走,小了往右走
  2. 注意 : 因为是从根节点开始走的,所以第一个节点一定就是父节点

列表的按序移动

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

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

通过遍历nums数组，将不为0的元素依次复制到nums的前面，并且记录我们复制了多少个元素，对len(nums)-k的元素置0即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def moveZeroes(self, nums):
        search_idx = 0
        insert_idx = 0
        while search_idx < len(nums):
            if nums[search_idx] != 0:
                nums[insert_idx] = nums[search_idx] 
                insert_idx += 1
            search_idx += 1

        for i in range(insert_idx,len(nums)):
            nums[i] = 0
        return nums

s = Solution()
print(s.moveZeroes([0,1,0,3,12]))

反转列表

使用双指针:

1
2
3
4
5
6
7
8
9
10
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
        return s

使用字典计数的最佳实践

1
2
for each in alist:
    adict[each] = adict.get(each,0) + 1

要找唯一元素时应该考虑异或

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。

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)

判断左子树

root.left存在,root.left不存在左右节点,说明root.left就是左叶子

1
if (root.left) and (not root.left.left) and (not root.left.right):

122