一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 1868|回复: 15
收起左侧

[其他] 我的刷题摸索贴

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎

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

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

x
【目标】遇到面试的题目,最少要有大致的方向
刷题方式】按类型刷题、注重思考、讲解、15分钟medium、20分钟hard
【计划】三个月时间, 2-5月,连续刷三个月
【参考】
1. 花花酱(进入千题时代如何刷题) https://space.bilibili.com/98803 ... =530415000051444285 https://www.youtube.com/c/huahualeetcode
https://zxi.mytechroad.com/blog/
2. grokking-the-coding-interview https://www.educative.io/courses ... -interview?aff=K7qB
3. 每个类型的经典题目:https://zhuanlan.zhihu.com/p/89392459
4. 平时可看:https://leetcode.com/discuss/gen ... r-in-Review%3A-2019
5. 参加每周 weekly leetcode.com contests


评分

参与人数 8大米 +10 收起 理由
Britneyajulie + 1 很有用的信息!
johnson139 + 2 给你点个赞!
kittytok + 1 很有用的信息!
tensorboy + 1 赞一个!
Erik_ + 1 赞一个
14417335 + 2
stowe + 1 给你点个赞!
cherryyoon + 1 赞一个

查看全部评分


上一篇:Sudoku Solver和valid Sudoku这两道题
下一篇:找最小生成树的算法思路

本帖被以下淘专辑推荐:

我的人缘0
杨幂的老公 2020-2-5 00:36:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   41% (37)
 
 
58% (52)    👎
每周参加leetcode比赛?
你急需参加这个群
https://www.1point3acres.com/bbs/thread-581507-1-1.html
回复

使用道具 举报

我的人缘0
 楼主| hahaha6.1 2020-2-5 23:29:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
杨幂的老公 发表于 2020-2-5 00:36
每周参加leetcode比赛?
你急需参加这个群
https://www.1point3acres.com/bbs/thread-581507-1-1.html

好的,多谢提醒,我研究一下
回复

使用道具 举报

我的人缘0
 楼主| hahaha6.1 2020-2-6 00:05:57 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
2020.2.5
从新更新LC session,从0开始计数
按类型复习:动态规划(爬台阶 70、三角形最小路径和120、乘积最大子序列152、股票买卖 121/122/123/309/188/714 ),注意初始条件设定,自底向上推理
刷题7道:421、5、 53、62、63、64、70
421. 最大XOR值 要求O(n)
    需要剪枝,缩小状态空间;从O(n^2)=>O(n),另外一个n由固定大小的K代替,比如整数的位数32位
方法一、trie树,对每个数,用从高到低位与字典中的数抑或,利用 x ^ 1 = y的方式求y满足条件的数字(在trie上获取/筛选有效候选数字集合),如果没有,则 x ^ 0 = y, x=y, 使用当前数字的bit位
方法二、直接利用 a_prefix ^ max_xor_prefix = b_prefix, 假设有max_xor_prefix,寻找 <a_prefix, b_prefix>, 十分巧妙

5. longest palindromic substring
   dp(i, j) = {1, i == j;
                  dp(i-1, j -1), s[i]==s[j];
                  0, s[i]!=s[j]}
    i: 起始点;j: 结束点

53. maximum subarray 最大连续子数组和
   dp(i, j, 1)=max(dp(i, j-1, 1)+s[j], s[j])
   dp(i, j, 0) = max(dp(i, j-1, 0), dp(i, j-1, 1))
   return max(dp(i, n-1, 1), dp(i, n-1, 0))
    简化算法为:记录全局最大值,每次计算dp(j)=max(dp(j-1)+s[j], s[j]), 显而易见,若dp(j-1)>0,取前者,否则,用后者

62. unique paths
    方法一、数字排列组合法 C(n-1, m+n-2), 有乘积溢出风险
    方法二、动态规划 dp(i,j) = dp(i-1,j) + dp(i, j -1)

63. unique paths 2
    有障碍,需要对路径数做条件判断

64. minimum path sum
    dp(i, j) = {  g[i][j], i = 0 & j = 0;
                      dp(i-1, 0) + g[i][0], j == 0;
                      dp(0, j-1) + g[0][j], i == 0;
                      min(dp(i-1, j) , dp(i, j-1)) + g[i][j],  i>0&j>0;
                   }

70. climbing stairs
      dp(i) = dp(i-1) +dp(i-2), dp(0)=0,dp(1)=1,dp(2)=2
回复

使用道具 举报

我的人缘0
niyanwen212 2020-2-6 05:54:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (115)
 
 
1% (2)    👎
支持一下lz~~~~~
回复

使用道具 举报

我的人缘0
 楼主| hahaha6.1 2020-2-6 17:46:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎

多谢支持~
回复

使用道具 举报

我的人缘0
 楼主| hahaha6.1 2020-2-7 23:12:20 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
2020.2.6
按类型复习:动态规划(零钱兑换、编辑距离、最长连续上升序列)
刷题6道:股票买卖类 Best Time to Buy and Sell Stock  121/122/123/309/188/714
121 一次交易,算法:从后向前遍历,记录当前最大值-当前值=当前值最大收益,更新最大收益,返回
122 允许多次交易,算法:从前向后遍历,只要比前者大,profit +=p[i]-p[i-1], 返回profit(利用连续上涨,则等同于最大值-最小值)
123 交易2次
188 交易k次
    dp[i,k,j], 第i天、第k次交易、状态j:0非持有/1持有
    dp[i,k, 0] = max(dp[i-1,k,1]+p[i], dp[i-1,k,0])
    dp[i,k,1]=max(dp[i-1, k, 0] - p[i]], dp[i-1,k,1] )
309 允许多次交易,交易一次后第二天禁止买入
    dp[i,j] 第i天、状态j: 0非持有/1持有/2cooldown
    dp[i,2]=max(dp[i-1,0], dp[i-1,2])
    dp[i,1]=max(dp[i-1,2]-p[i], dp[i-1,1])
    dp[i,0]=max(dp[i-1,1] + p[i], dp[i-1,0])
714 允许多次交易, 有交易费
     dp[i,j] 第i天、状态j: 0非持有/1持有
    dp[i,1]=max(dp[i-1,0]-p[i], dp[i-1,1])
    dp[i,0]=max(dp[i-1,1] + p[i]-fee, dp[i-1,0])
回复

使用道具 举报

我的人缘0
 楼主| hahaha6.1 2020-2-7 23:20:07 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
2020.2.7
刷题3道
300        Longest Increasing Subsequence  
dp[i] = max(dp[i-k]) +1 , if s[i] > s[i-k]

322 coin change
dp[i, len]=min(dp[i, len-1],dp[i-coins[len], len-1];

518. coin change II
方法数=不包含第len个coin+包含len个coin的方法数
dp[len, i] = dp[len-1, i] + dp[len, i-coins[len]]
回复

使用道具 举报

我的人缘0
maxmonlt 2020-2-9 23:28:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
佩服佩服,坚持就是胜利。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-4-1 12:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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