查看: 31697| 回复: 673
跳转到指定楼层
上一主题 下一主题
收起左侧

刷题记录帖子

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
自己开一个帖子, 激励自己,刷题记录。

今天准备明天的报告,只刷了一题, LC 299 Bulls and Cows。

比较简单,说白了就是通过一次遍历,这个时候你一定是位置 match 的,因为你之检测一个位置。所以现在,内容 Match 的就是 Bulls,如果内容不 Match 那么你就记录下来,用一个【0~9】的数组,因为后面只需要比较这里的【0,9】各自在两个数组出现了多少次,然后取每个数字少的那个,当然初始话要都是 0.
时间复杂度 O(n) + 9 其实就是 O(n) 遍历数组的时间,空间复杂度,不算原来的数组,其实只要 O(1)两个长度为 10 的数组记录各相同位置不同内容数字的总体出现次数。

评分

参与人数 1大米 +25 收起 理由
14417335 + 25 给你点个赞!

查看全部评分


上一篇:公共卫生的CPH考试有人考过吗?求经验!
下一篇:打卡开始
 楼主| Myron2017 2020-3-28 00:38:52 | 只看该作者
全局:
本帖最后由 Myron2017 于 2020-3-28 00:52 编辑

LC 442 Find All Duplicates in an Array

The idea is we do a linear pass using the input array itself as a hash to store which numbers have been seen before. We do this by making elements at certain indexes negative.
  1. class Solution:
  2.     def findDuplicates(self, nums: List[int]) -> List[int]:
  3.         # HashMap is an obvious solution, we will not check it
  4.         # Try to solve it in O(n) time without extra space
  5.         # so we must use space in the array itself
  6.         # Then we will cancel each other if possible
  7.         res = []
  8.         for item in nums:
  9.             if nums[abs(item) - 1] < 0:
  10.                 res.append( abs(item) )
  11.             else:
  12.                 nums[abs(item) - 1] *= -1
  13.         return res
复制代码


回复

使用道具 举报

 楼主| Myron2017 2020-4-4 02:51:49 | 只看该作者
全局:
53. Maximum Subarray

这道题目真是很经典,推荐几个视频还是做的很不错的。https://blog.ihuxu.com/xiaoxu-ex ... 3-maximum-subarray/

https://www.youtube.com/watch?v=7J5rs56JBs8

https://www.youtube.com/watch?v=2MmGzdiKR9Y

(1)暴力 n 平方的方法搜索
(2)一维 dp,记住 dp 的含义,这里是 到第 i 位元素的时候最大的 sum, 如果 sum 不足够大那么还不如,不 包括之前的元素,直接自己成为答案
(3)divide and conquer, 分成三部分,左半部分,右半部分,和 如果包含中间元素的解法。

回复

使用道具 举报

 楼主| Myron2017 2020-10-4 09:23:47 | 只看该作者
全局:
39. Combination Sum

DFS 解决,但是如何去重 和 加速求解非常值得学习,这里记录下解法,https://maxming0.github.io/2020/10/02/Combination-Sum/

答案真是巧妙,通过两个调节比较

核心是,每次比较的时候判断是不是需要加入, 首先是排序

显然,
(1) num 大于 target 就没必要加入了, 甚至后面的都不用加入了
(2) 其次是,num 必须比已经加入答案的最后那个元素 大,否则,如果这个 num 加入就会算入了 更小的那个答案,这里必须加入以去重!


回复

使用道具 举报

 楼主| Myron2017 2020-10-5 22:51:54 | 只看该作者
全局:
1009. Complement of Base 10 Integer

这道题目做过,结果还是没做出来,最好的方法其实是 用 11111 mask 和 原数 取 XOR,这样就可以保留下 complment 的要求。

记忆!

回复

使用道具 举报

 楼主| Myron2017 2020-10-7 06:55:47 | 只看该作者
全局:
701 Insert into a Binary Search Tree

啊啊啊啊啊啊啊啊啊啊啊,居然忘记了 BST 的 insert。

其实错误就发生在写法上,最简洁的方法是 如果 遇到null node 就是插入的 node,这个时候确实是需要新建 node 但是也相应的丢掉了,新建 node 的 parent。所以解决方法就是层层 递归的时候层层赋值

回复

使用道具 举报

 楼主| Myron2017 2020-10-9 23:07:00 | 只看该作者
全局:
449 Serialize and Deserialize BST

其实题目还是很经典,很实用的。但是如何简单高效地实现就是考验功力的地方。

先序遍历tree,然后存下来,注意 int 变成 str 之后必须指定 seperator 不然你不知道怎么切割。
然后,直接在建立树的时候带入,左右子树的范围,开始是 -inf 到 +inf。

具体讲解在这儿, https://maxming0.github.io/2020/ ... nd-Deserialize-BST/

回复

使用道具 举报

 楼主| Myron2017 2020-10-10 22:38:18 | 只看该作者
全局:
452 Minimum Number of Arrows to Burst Balloons

经典的 greedy 题。

https://maxming0.github.io/2020/ ... -to-Burst-Balloons/

回复

使用道具 举报

 楼主| Myron2017 2020-10-13 09:12:07 | 只看该作者
全局:
316 Remove Duplicate Letters AND 1081. Smallest Subsequence of Distinct Characters

真是经典题目,删除当前已经有的 char 的条件是,新加入的 char 更小,同时 后面还有想删除的字符,同时 stack 不为 空。
stack 为空,则直接加入即可。

Leetcode 会出现重复题目,比如这道题就是 316, 1081 完全是相同的题目,充分说明 核心题目在大约 500 道 左右。

回复

使用道具 举报

 楼主| Myron2017 2020-10-14 04:16:22 | 只看该作者
全局:
148 Sort List

真是经典题,虽然是用 merge sort 做,但是还是有很多细节要记忆,比如如何找到 linked list 的中间点。

回复

使用道具 举报

 楼主| Myron2017 2021-7-8 11:50:57 | 只看该作者
全局:
89         Gray Code        Medium

镜像法



位移法, i ^ (i//2)
回复

使用道具 举报

 楼主| Myron2017 2021-7-14 16:41:18 | 只看该作者
全局:
295        Find Median from Data Stream        Hard        5        Classic Using Two Heap for Partion

  1. class MedianFinder(object):

  2.     def __init__(self):
  3.         """
  4.         initialize your data structure here.
  5.         """
  6.         # small to large
  7.         # pop large by multiplying -1
  8.         self.Heap1 = []
  9.         # large to small
  10.         # pop small
  11.         self.Heap2 = []

  12.     def addNum(self, num):
  13.         """
  14.         :type num: int
  15.         :rtype: None
  16.         """
  17.         heappush(self.Heap1, -num)
  18.         heappush(self.Heap2, -heappop(self.Heap1))
  19.         
  20.         if len(self.Heap2) > len(self.Heap1):
  21.             heappush(self.Heap1, -heappop(self.Heap2))

  22.     def findMedian(self):
  23.         """
  24.         :rtype: float
  25.         """
  26.         if len(self.Heap1) != len(self.Heap2):
  27.             return -self.Heap1[0]
  28.         else:
  29.             return (self.Heap2[0]-self.Heap1[0]) / 2


  30. # Your MedianFinder object will be instantiated and called as such:
  31. # obj = MedianFinder()
  32. # obj.addNum(num)
  33. # param_2 = obj.findMedian()
复制代码
回复

使用道具 举报

推荐
 楼主| Myron2017 2026-2-13 22:52:44 | 只看该作者
全局:
夏日柠檬红茶 发表于 2026-2-12 21:35
支持一下楼主。看到你2020年就开始刷了。
现在AI大行其道,其实这挺影响我刷题的热情的[捂脸]

我也不喜欢刷题,但是没办法,面试还没改革,那就得继续刷。加油!
回复

使用道具 举报

推荐
 楼主| Myron2017 2020-12-21 14:16:49 | 只看该作者
全局:
880 Decoded String at Index

正向做是常规思路,但是会 TLE,所以 backward 做是最好的。官方解析很好,https://leetcode.com/problems/decoded-string-at-index/solution/



一个优化是,直接 break 累加,参考这个帖子,https://maxming0.github.io/2020/12/20/Decoded-String-at-Index/

回复

使用道具 举报

推荐
 楼主| Myron2017 2020-8-8 03:47:14 | 只看该作者
全局:
LeetCode 987 Vertical Order Traversal of a Binary Tree

Sorting a List of Elements by the First element but if Equal sort by the second == > Forming a tuple and range them by order
  1. tmp = sorted(res[i], key=lambda tup: (-1 * tup[1],tup[2]))
复制代码


MaxMing 的讲解很好, https://maxming0.github.io/2020/ ... l-of-a-Binary-Tree/

当然我的做法就是慢慢来解决,当然代码不太清晰但是还是可以看出功能。

回复

使用道具 举报

🔗
 楼主| Myron2017 2020-3-28 00:09:05 | 只看该作者
全局:
补下昨天的,104 Maximum Depth of Binary Tree

出现了低级失误,居然没做出来。

其实很简单就是递归,先看root,再 left, 再 right,最后对于该节点做一个归纳,决定怎么输出。

List all scenarios of what a binary tree could be like:

1. when a binary tree is null, simply return maximum depth as 0
2. when a binary tree just have a root node, return maximum depth as 1
3. when a binary tree has a root node and child nodes, maximum depth would be the depth of the bigger side between left and right subtrees plus 1.

回复

使用道具 举报

🔗
 楼主| Myron2017 2020-3-28 02:09:52 | 只看该作者
全局:
LC 806. Number of Lines To Write String

还是很简单的题目,其实可以很容易看懂思路,设置两个变量然后不断检查当前的字符。
回复

使用道具 举报

🔗
jf2891 2020-3-28 03:01:37 | 只看该作者
全局:
赞一个,楼主讲解的很详细!加油!
回复

使用道具 举报

🔗
 楼主| Myron2017 2020-3-28 12:36:56 | 只看该作者
全局:
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

这个题目其实我不知道为什么要给 old tree 完全是冗余条件,但是其实就是纯粹的traverse tree 然后你比较 value 并且记录当前的 treeNode。
回复

使用道具 举报

🔗
 楼主| Myron2017 2020-3-29 02:49:04 | 只看该作者
全局:
今天复习 双指针 topic, 参照这个 Github 帖子, 双指针

167. Two Sum II - Input array is sorted 非常直接双指针使用,直接两头夹逼出答案

633. Sum of Square Numbers 需要注意的是,这个是从 0 开始的,换句话说 0**2 + 2**2 == 4 是符合平方和要求的。

345. Reverse Vowels of a String 首先是如何从 Python String 转 List,其次是从 List 转回 String,因为 String 在 Python 中不可变。 其次是需要考虑字符串的大小写问题。最后是其实写判断条件的时候,时刻注意两个 Pointer 的范围,越界是比较讨厌的问题。同时双指针满足条件,交换了内容之后别忘记更新指针。
回复

使用道具 举报

🔗
 楼主| Myron2017 2020-3-29 11:52:22 | 只看该作者
全局:
1108       
Defanging an IP Address     太简单,就是简单的字符串操作练习,没啥提高。
回复

使用道具 举报

🔗
 楼主| Myron2017 2020-3-31 04:42:08 | 只看该作者
全局:
本帖最后由 Myron2017 于 2020-3-31 05:03 编辑

LC 1395. Count Number of Teams 周六比赛的时候暴力求解,现在看到花花的视频,还可以用压缩解法,对于 O(n^3) 的算法,肯定确实是如果超过300就不太暴力做了。
学习了,其实就是变第二趟遍历的时候,可以统计出可能的状态数,这样简单乘法计算即可,而不用一个个检测。代码快了接近 30 倍。

  1. class Solution:
  2.     def numTeams(self, rating: List[int]) -> int:
  3.         totalN = len(rating)
  4.         """
  5.         This time we use the j th ratings to cut the array into two parts
  6.         then i is choosen from the left part,
  7.              j is choosen from the right part,
  8.              so i < j < k
  9.         Since unique rating values in ratings
  10.         Then (1) for rating[i] < rating[j] < rating[k]
  11.              we can count how many elements in j left part is smaller than j which is the possible value of i saying it is numL
  12.              (2) for rating[i] > rating[j] > rating[k]
  13.              total number of all elements in j th left part is j, so the number of elements that is larger than j th is ( j - numL )
  14.         """

  15.         res = 0
  16.         for j in range(1,totalN-1):
  17.             # Both numL and numR are for smaller cases
  18.             numL = 0
  19.             numR = 0
  20.             for i in range(0, j):
  21.                 if rating[i] < rating[j]:
  22.                     numL += 1
  23.             for k in range(j+1,totalN):
  24.                 if rating[j] < rating[k]:
  25.                     numR += 1
  26.             # print("%d , %d"%(numL, numR))
  27.             res = res + numL * numR + (j - numL) * (totalN - j - numR - 1)
  28.             # print(res)
  29.         return res
  30.             
  31.             
复制代码






回复

使用道具 举报

🔗
 楼主| Myron2017 2020-4-1 10:53:22 | 只看该作者
全局:
1295. Find Numbers with Even Number of Digits 把数字转换成字符串再用字符串长度 %2 计算。 其实可以用位运算。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表