Leetcode记录1

发表于
字数统计 740 | 阅读时长 3

建议使用英文，遇到不会的题目，社区会有很多讨论者给出答案，而中文版的较少，而且锻炼自己对于英文编程题目的理解。

这里不对每道题都做记录。

  • 13题， Roman to Integer，用了一个字典，苦恼于如何分情况写规则，看了评论区，用了两个字典，妙啊，真香。
  • 14题，Longest Common Prefix，查看列表中的所有元素，一个all，骚气啊
1
all([s[i] == strs[0][i] for s in strs])
  • 20题，Valid Parentheses，利用了堆栈后进先出，开始有点难理解，以后解决对称问题都可以借鉴
  • 58题，length Of LastWord，判断字符串是否全为空格，s.isspace()
  • 66题，Plus One，得到一个任意长度整数的各个位
1
2
3
4
5
6
result = [] 
while num:
result.append(num % 10)
num = num // 10 #取整除 - 返回商的整数部分（向下取整）
# 逆序，按正常的顺序返回
result.reverse()
  • 67题，Add Binary，将两个只有0和1的字符串进行二进制相加
1
2
3
4
# int(x, base=10)x - - 字符串或数字;base - - 进制数，默认十进制
# bin(x)x - - int或者long int数
# 结果包含0bxxxx，所以从第二位开始
return str(bin(int(a, 2) + int(b, 2)))[2:]
  • 69题，Sqrt(x)，计算开方，返回整数部分，不能引入math库，所以sqrt()不能使用
1
return int(pow(x, .5))
  • 70题， climbStairs，递归：对于n阶台阶，可以看成走了n-1阶基础上再跨1阶 + 走了n-2阶基础上再跨2阶，即f(n)=f(n−1)+f(n−2)，f(0)=1，f(1)=1
1
2
3
4
5
6
7
def climbStairs(self, n: int) -> int:
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n >= 3:
        return self.climbStairs(n-1)+self.climbStairs(n-2)

但是太费时，n比较大时Time Limit Exceeded，相同思路使用数组实现

1
2
3
4
5
6
7
result = [0] * n
result[0] = 1
if n >= 2:
    result[1] = 2
for i in range(2, n):
    result[i] = result[i-1] + result[i-2]
return result[n-1]
  • 83题，Remove Duplicates from Sorted List， 移除给定有序链表的重复项 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        currentNode = head
        while currentNode is not None and currentNode.next is not None:
            if currentNode.val == currentNode.next.val:
                currentNode.next = currentNode.next.next
            else:
                currentNode = currentNode.next
        return head

思路比较简单， 遍历这个链表，每个结点和其后面的结点比较，如果结点值相同了，只要将前面结点的 next 指针跳过紧挨着的相同值的结点，指向后面一个结点。 重点是借此回顾一下链表。

  • 100题，Same Tree，比较两棵树是否完全相同，使用递归比较简单，这里想记录的是看到别人代码中非常漂亮的一段
1
2
3
4
# if one of the nodes is null
if not p or not q:
    # if both nodes are null then we need to return True
    return p == q

很巧妙的判断了p为空或q为空或都为空应该返回的值。

注：转载文章请注明出处，谢谢~