Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]刷题记录 2021.01

Posted on 2022-10-23 10:14 Uriel 阅读(32) 评论(0)  编辑 收藏 引用 所属分类: 闲来无事重切Leet Code

2021.01.18

AC:

Easy 1,7,9,13,14


2021.01.20

AC:

Easy 20


2021.01.21

AC

Easy 21,26,27,28,29,38,53,58,66,67,69,70,83,88


2021.01.23

AC

Easy 100


2021.01.24

AC

Easy 101,104


2021.01.25

AC

Easy 107,108,110,111


2021.01.26

AC

Easy 112,118,119,121,122,125,136


2021.01.27

AC

Easy 141,155,160,167


2021.01.28

AC

Easy 168,169,171


2021.01.30

AC

Easy

172,278


2021.01.31

AC

Easy

283,290,303,326,342,344



题目分类

1 Two Sum 简单数学题,二重循环看是否有两个数之和等于要求的数


7 Reverse Integer 简单字符串处理,不超过int上下限就翻转字符串(加一些特判)


9 Palindrome Number 简单字符串处理,判断回文数(直接python字符串翻转判断)


13 Roman to Integer 简单字符串处理,要特殊处理IV这种(如果后一个字母代表的数字比前一个大,加特判)


14 Longest Common Prefix 简单字符串处理,一堆字符串的最长公共前缀(以第一个字符串为开始与之后的字符串匹配,匹配不到就不断递减长度)


20 Valid Parentheses 简单模拟,栈操作


21 Merge Two Sorted Lists 简单操作,合并有序链表


26 Remove Duplicates from Sorted Array 数组去重,python的list pop操作


27 Remove Element 数组去除指定值的元素,python的list pop操作


28 Implement strStr() 字符串查找


35 Search Insert Position 寻找有序数组的插入点


38 Count and Say 简单模拟


53 Maximum Subarray 最大连续子序列


58 Length of Last Word 句子中最后一个单词长度,注意特判(输入只有一堆宫格,或者最后一个单词后面还有空格,或者空串)


66 Plus One 大数加法模拟(+1)(颠倒字符串先)


67 Add Binary 二进制加法模拟(颠倒字符串先)


69 Sqrt(x) 求sqrt,精确到整数(二分0~x,注意特判x=1)


70 Climbing Stairs n级台阶,每次爬1 或2层,问一共几种爬法,dp[n]=dp[n-1]+dp[n-2],因为只要记录过去的两个值,可以用两个变量记录,不用开dp[n]数组


83 Remove Duplicates from Sorted List 链表去重if p.next.val == p.val: p.next = p.next.next


88 Merge Sorted Array 合并有序数组,需要插入时把数组某个值之后的值后移


100 Same Tree 判断两棵二叉树是否一样,简单递归,注意类中函数自我调用self.,注意空树的特判

if p == None and q != None:

            return False

        if p != None and q == None:

            return False

        if p != None and q != None and p.val != q.val:

            return False

        if p != None and q != None:

            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

        return True


101 Symmetric Tree 判断二叉树是否对称,同时DFS,一个从左到右,一个从右到左,注意python类变量的使用self.xx


104 Maximum Depth of Binary Tree 计算二叉树深度,简单DFS

    max_depth = 1

    def DFS_Tree(self, root, depth):

        self.max_depth = max(self.max_depth, depth)

        if root.left != None:

            self.DFS_Tree(root.left, depth + 1)

        if root.right != None:

            self.DFS_Tree(root.right, depth + 1)

        return

    def maxDepth(self, root):

        """

        :type root: TreeNode

        :rtype: int

        """

        if root == None:

            return 0

        self.DFS_Tree(root, 1)

        return self.max_depth


107 Binary Tree Level Order Traversal II 按照深度输出二叉树每一层的所有值,BFS


108 Convert Sorted Array to Binary Search Tree DFS,每次从中间等分,创造两棵子树


110 Balanced Binary Tree 判断是否是二叉平衡树,DFS


111 Minimum Depth of Binary Tree 计算二叉树最小叶子的深度(两个儿子都没有才是叶子),DFS or BFS


112 Path Sum 二叉树是否有一条path只和等于给定值,DFS,注意一直要加到叶子结点,以及注意判断空树


118 Pascal's Triangle 上一行相邻元素求和,一行行往下算,注意判0


119 Pascal's Triangle II 与118一样,但只要输出第k行的值,并且只能额外使用O(k)Memory,只要记住前一行的值就行


121 Best Time to Buy and Sell Stock 给定每天的股价,问何日买进何日卖出最划算,每次记录从1~i-1的股价最大值,尝试第i日卖出是否更好


122 Best Time to Buy and Sell Stock II 给定每天的股价,可以多次买入/卖出,问一共最多赚多少,相邻元素相减,大于零就加上(大于零相当于多在手上拿一天,否则就是中间卖掉再次买入,贪心)


125 Valid Palindrome 判断字符串是否对称(字母数字以外的字符不算)。去掉其他字符,大写都变为小写之后颠倒字符串看是否一样(有更好解法)


136 Single Number 一堆数里面只有一个出现一次,其他都出现两次,找出出现一次的,所有数全部异或一遍,最后的值即为所求


141 Linked List Cycle 判断单向链表中是否有环,开两个指针,一个一次跳一步,一个一次跳两步,如果两个指针相遇则有环


155 Min Stack 模拟栈,注意getMin()需要在O(1)返回结果,所以每次入栈的时候顺便记录当前栈中的最小值


160 Intersection of Two Linked Lists 判断两条单向链表是否从某一点开始合成同一个链表,两个指针从两个开头开始找,如果一个找完了就从另一条开始(相当于两个指针交换位置重新找),如果在某个点两个指针重合了,那就是两个链表有合并

theadA = headA

        theadB = headB

        while theadA != theadB:

            #print(theadA.val)

            #print(theadB.val)

            if theadA != None:

                theadA = theadA.next

            else:

                theadA = headB

            if theadB != None:

                theadB = theadB.next

            else:

                theadB = headA

        return theadA


167 Two Sum II - Input array is sorted 在给定的递增数列中找两个数,之和等于给定值(保证有解)

解法一:两个游标,分别从头和尾向中间游动,和比给定值小左侧加一,否则右侧加一

解法二,左侧游标从1-n遍历,右侧用二分,时间和解法一差不太多,注意二分写法

    l = i + 1

            r = len(numbers)

            while l < r:

                mid = (l + r) // 2

                if numbers[i] + numbers[mid] == target:

                    return [i + 1, mid + 1]

                if numbers[i] + numbers[mid] < target:

                    l = mid + 1

                else:

                    r = mid


168 Excel Sheet Column Title 将数字转成excel的A-AA-。。。ZZZ这个的格式,不断取模再转换


169 Majority Element 求数组中出现次数超过半数的数字

解法一:直接sort,返回中间的数字

解法二:哈希表,python的dict

解法三:bit voting

解法四:分治

解法五:C++ nth_element() 


171 Excel Sheet Column Number 将excel的A-AA-。。。ZZZ这个的格式转为数字,建个dict存字母到数字的映射,从第一个字符开始不断*26+值

PS:python的ord()函数可以 直接返回ascii码值


172. Factorial Trailing Zeroes,算n的阶乘末尾0的数量,即计算1-n中5的数量

        t = 0

        while n >= 5:

            n = n // 5

            t = t + n

        return t


278. First Bad Version,1-n个版本,从第m个开始后面都是bad,每次可以调用isBadVersion(i)判断I是不是好的,问从第几个开始是bad,简单二分

        l = 1

        r = n

        if n == 1:

            return 1

        while l <= r:

            mid = (l + r) // 2

            #print mid

            if isBadVersion(mid):

                if mid == 1 or isBadVersion(mid - 1) == False:

                    return mid

                r = mid

            else:

                l = mid + 1


283. Move Zeroes 把数字串中的0挪到末尾,利用python的list操作

        l = len(nums)

        nums[:]=[i for i in nums if i != 0]

        nums += [0]*(l - len(nums))


290. Word Pattern 判断字符串是否符合某种pattern,python的dict操作,注意如下两种的区别

Input: pattern = "abba", s = "dog cat cat dog"

Output: true

Input: pattern = "abba", s = "dog dog dog dog"

Output: false


292. Nim Game n个石子,轮流取,每次1-3颗,问给定n是否能赢,n若是4(3+1)的倍数必输,其他都赢


303. Range Sum Query - Immutable 区间求和,多次query,预处理0-i的和,return self.sums[j + 1] - self.sums[i]


326. Power of Three 判断一个数是否是3的某次方

解法一,不断除3

解法二,n > 0 and math.ceil(log10(n) / log10(3)) == int(log10(n) / log10(3))


342. Power of Four 判断一个数是否是4的某次方,同326


344. Reverse String 字符串翻转

解法一,str.reverse()

解法二,左右两个游标



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理