辞职许久了,思考了很久,觉得自己是不是不太适合当程序员了?最近看算法,刷 leetcode,简单的基本都会(相信在做的各位也没几个不会的),遇到最优解的,动态规划的,基本一个都不会了(哭。。。)
然后昨天今天特意看了下 01 背包问题,我发现我居然看不懂了。。。
今天看到一个简单的零钱兑换问题。只会用回溯法。。。我是不是没救了。。。
附代码
private int change0(int[] arr, int target) {
Arrays.sort(arr);
ArrayDeque<Integer> stack = new ArrayDeque<>();
int index = arr.length-1;
while (!stack.isEmpty() || index >= 0) {
if (index < 0) {
if (stack.isEmpty()) return -1; //找不到
int last = stack.pop();
target += arr[last];
index = last-1;
continue;
}
if (arr[index] == target) {
return stack.size()+1;
} else if (arr[index] > target) {
index--;
} else {
target -= arr[index];
stack.push(index);
}
}
return -1;
}
1
hubahuba 2020-11-16 12:17:02 +08:00 1
cao
|
2
guixiexiezou OP 而且代码还是错误的.........哎😔
|
3
v2webdev 2020-11-16 12:26:48 +08:00 1
矫情的话,去一亩三分地上吧,V 站不适合。
|
4
crclz 2020-11-16 12:29:14 +08:00 1
0-1 背包,不要试着去理解它,去感受它。
多做几个变形题(做不出来看题解也行),自然就理解了。 |
5
darklowly 2020-11-16 12:30:46 +08:00 13
写程序有两大条路
1 系统类 2 算法类 系统类,不需要那么多的算法,简单的数据,链表,树,hash 就够了。其他的就是计算机系统方面的知识。例如,组成原理,操作系统,设计模式,架构模式。这条路适合智力正常范围的人,因为智力正常的人,更容易感受到困难,就更容易设计简单的系统,反而对设计有好处。 算法类,侧重点就是数学,适合智力好一点的人,反而这类人不容易感受到困难,设计的系统会违反常人的直觉,反而是不好的设计。当然也有很多智商不够,自以为很够的人,既设计不好算法,又搞的很复杂。 所以不要灰心。 |
6
BBCCBB 2020-11-16 12:35:07 +08:00 1
你要有点基础后就好了, 别气馁.. 刚开始时都是这样, 不停的刷, 总结, 系统的学.
0-1 背包可以看看这个 https://www.cnblogs.com/labuladong/p/12455089.html |
7
guixiexiezou OP @v2webdev 可能是太久没工作了吧,心又静不下来。多谢指点
|
8
guixiexiezou OP @darklowly 嗯嗯,多谢指点。我也觉得我如果继续 coding 下去,最多最多还是只能走工程这条路,也就是所谓的用别别人的轮子
|
9
guixiexiezou OP @BBCCBB 多谢,我去看看
|
10
guixiexiezou OP @crclz 我再感受 2 天吧,说不定真就领悟了
|
11
rodrick 2020-11-16 12:59:14 +08:00
不要灰心,换个角度想想,你如果转行了又怎么知道自己更适合另外一行呢
|
12
deepall 2020-11-16 13:19:40 +08:00 7
这不是凡尔赛人?
|
14
a62527776a 2020-11-16 13:30:04 +08:00
太牛了(吹捧一波
|
15
keymao 2020-11-16 13:32:38 +08:00
这不就是凡尔赛人
|
16
guchengyehai1 2020-11-16 13:38:02 +08:00 via Android
回溯再加个记忆就和 dp 差不多了
|
17
Mac 2020-11-16 13:38:45 +08:00 via Android 1
我只会百度谷歌,其它的一概不会
|
18
shubo83 2020-11-16 13:42:45 +08:00
可以先当不会算法的野生程序员,比如我
|
19
leido 2020-11-16 13:45:33 +08:00
|
20
wph95 2020-11-16 13:47:40 +08:00 1
|
21
gitgabige 2020-11-16 13:48:22 +08:00
讲道理,我最近也在看(复习)这个。也就看了下简单的 0-1 背包,后面更复杂的就不想看了。我觉得吧,主要是面试公司需要这些,真正工作中用到的凤毛麟角。所谓面试造火箭,工作拧螺丝。
|
22
wph95 2020-11-16 13:51:08 +08:00
动归这问题不要慌,这东西是反正常人思路的。不像回溯符合正常人的思维。
得靠多做题才能逐渐掌握的 (大神除外) 背包 dp 记忆化搜索 区间 DP 稍微能知道是个啥就足够了 |
23
cccp2020 2020-11-16 13:54:11 +08:00
动态规划是高阶的算法题了,先学简单的,慢慢再看动态规划,开局就打 boss 绝对是被虐
|
24
gadsavesme 2020-11-16 14:01:30 +08:00
不至于啊,不就是多看多练么,我好多题目都是当时花了半天全部参透,写完提交美滋滋,然后过了几个月回来依旧不大记得。但是有的题反复写的多了,基本就忘不掉了。别怀疑自己毕竟都是普通人,那种看过就会,刷一篇就精通的大佬实在是比不来。
|
25
axex 2020-11-16 14:09:40 +08:00
刷了过几个月忘了
|
26
Gwzlchn 2020-11-16 14:11:41 +08:00 4
楼主您好~我是来鼓励你的 hhh
我这学期刚选了我们学校的算法课(卜东波教授),实际上,老师上课也会说,DP 、贪心算法的每个细微的策略并不是那么显然的,我们不可能对每道题都背诵算法的策略,重要的是我们应该如何从问题的特点构造出来一种合适的策略。 举个例子,我看楼上有说“九讲背包”这个文档不错,那么我对下面这句话问几个问题希望楼主思考一下:为什么我们要在状态方程中使用“前 i 个物品”这种定义状态转移的策略?如果用“前 i 个”这种表述,那么我们对物品集合进行排序了吗(注意,集合是无序的,所以你不能对一个集合说“前 i 个”)?如果是排序的,那么我们应该用什么样的定序方法? 或者考虑这种更新子问题的策略:我们每步都考虑物品集合中的每个物品是否能放入背包中,然后下一步进行同样的策略呢?这种方法可不可行呢? “用子问题定义状态:即 F[i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是:F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci] + Wi} ” 你看,这个 01 背包物品问题真的每步都不是那么显然成立的,所以觉得难是正常的。如果你觉得简单,而并没有仔细思考这些问题只能说明你是背会的答案,而不是理解会的,那又有什么意义呢? 总而言之:觉得难是好事,这会促进我们思考算法中每个不那么显然的地方。 |
27
dk7952638 2020-11-16 14:46:31 +08:00
如果谷歌和栈溢出不能解决问题,那就去 github 里问候作者
|
28
dk7952638 2020-11-16 14:47:38 +08:00 1
其实绝大多数 IT 从业者从事的并不是软件开发,而是代码焊接工
|
29
QingchuanZhang 2020-11-16 15:08:47 +08:00
我一开始也不会,别担心,可能只是教程不合适
|
30
westtide 2020-11-16 15:16:09 +08:00
可以看 mooc 上的算法课?这些问题在算法课上一般都有讲,还有形式化证明。考研的时候看了北大屈婉玲老师的《算法设计与分析》,讲的很透彻和深刻。
|
31
luckcul 2020-11-16 15:27:03 +08:00
多看 多想 多写
孰能生巧 |
32
SWALLOWW 2020-11-16 16:49:19 +08:00
我司软件和算法是分开的,各司其职,不难为程序员搞数学
|
33
Martox 2020-11-16 16:54:51 +08:00
我都快要忘记我应该刷算法这件事情了
|
34
zzzain46 2020-11-16 19:06:49 +08:00
哈哈哈当年学 运筹学 的时候也觉得动态规划和背包问题是有点难的,多学几遍就好,先手动模拟原理和方法,再写代码会好很多
|
35
wowodavid 2020-11-16 20:04:03 +08:00
你要搞明白那些人是“会”了,还是“学会”了,又不是自己想明白的,不就是比你早两天看书看会了吗,有啥好优越的,闻道有先后而已。
|
36
impl 2020-11-16 21:50:56 +08:00 via iPad
多刷题,不懂的话背下来,找张纸默写几遍,总会有理解的时候
|
37
lithbitren 2020-11-16 22:08:53 +08:00
动态规划题型太多,背包只是基础,遇到没见过的 DP 题型,除了顶尖大神,剩下基本不可能在面试的时候做出来,所以面试的时候一般就算考动归也是基础动归,多刷刷题就好了
|
39
raaaaaar 2020-11-16 22:37:19 +08:00 via Android
垃圾算法,毁我青春
|
40
RedBeanIce 2020-11-16 22:40:52 +08:00 1
凡尔赛。
|
41
QingchuanZhang 2020-11-16 23:01:38 +08:00
|
42
yekern 2020-11-17 07:31:49 +08:00 1
刷波数据结构以后在去刷 leetcode
|
43
b00tyhunt3r 2020-11-17 08:47:11 +08:00
马一个
|
44
dingyaguang117 2020-11-17 09:20:58 +08:00 via iPhone
题目做多了就有感觉了 和数学一样
|
45
guixiexiezou OP 认真看了下每个回复,感谢鼓励。昨晚研究了一晚上,终于把基础的 01 背包看懂了,但在二维数组变换成一维数组又看不懂了。关于算法这个,工作中用的概率确实太低太低了(可能和我职业层次位置相对低下有关,之前做游戏服务端,无论是路径计算,技能伤害计算还是常规业务处理,上面的算法我一个都用不到)
|
46
user8341 2020-11-17 10:06:58 +08:00
@guixiexiezou 路径计算是不是也要用到算法啊?
|
47
lewis89 2020-11-17 10:45:37 +08:00
@guixiexiezou #45 本来这些算法的意义就不大,至少在 N 很小的时候就没什么卵用,有这个功夫去实现这样花俏的算法,还不如直接全部暴力枚举,你搞一堆剪枝 递推 打表 结果发现 N 很小,维护这个代码的成本远比优化带来的收益高得多,而恰恰大部分场景 N 都很小,所以实际场景 DP 没什么人去用,极少我觉得暴力枚举比 DP 可靠,而且实现容易 测试简单。
|
48
lewis89 2020-11-17 10:46:50 +08:00
@user8341 #46 路径有专门的最短路径算法 还有 R* 这些都是现成的套路算法,只要把游戏里面的地图 弄好成邻接矩阵就行了
|
50
gongshishao126 2020-11-17 10:48:52 +08:00
@rodrick 杀人诛心呐~
|
51
lewis89 2020-11-17 10:55:52 +08:00
@Gwzlchn #26 关键是 N 很小的时候,费这么大的劲去搞递推公式的意义真的不大,大部分时候 N 都很小,没必要去实现这样花俏 难以维护的算法,与其这样 为啥不直接暴力枚举?
|
53
Chenamy2017 2020-11-17 11:01:28 +08:00
话说作为十年老程序员的我,还没看过 01 背包问题,你钻牛角尖了,程序员有很多方面的,不要揪着算法深入,算法无穷尽,基本的掌握了就可以做业务了。有几个程序员是算法大牛的,市场也不需要那么多的算法大牛。
|
54
justest123 2020-11-17 11:01:55 +08:00
是我对凡尔赛的理解有偏差么?为什么这种吐槽+半诉苦的帖子都会有人刷凡尔赛?有病吧
数学思维或者说逻辑思维不是非常好,这类算法题一样也是感觉头大,倒是没怀疑自己没救了,大概还是看开点,什么能力做什么事,难为自己干嘛呢 |
55
Phariel 2020-11-17 11:05:58 +08:00 via iPhone
自信点 我有些 easy 也做不到最优解 你太魔怔了🐶
|
56
Felldeadbird 2020-11-17 11:14:12 +08:00
CURD 也是一件快活牛逼的事情。写软件又不是时刻用到算法。
|
57
vevlins 2020-11-17 11:24:55 +08:00 1
不会算法的程序员多的是。
程序员的三个方向:性能的极致优化、业务的极致理解、系统的极致设计。做到一个就可以了。 |
58
coderunI 2020-11-17 11:31:22 +08:00
看不起,代码焊接工吗?
|
59
learningman 2020-11-17 11:33:05 +08:00
看不起,手上没几块 ICPC World Final Gold 配写代码? NOI 国集估计也就勉强写写 CURD 吧
|
60
cumshot 2020-11-17 11:42:53 +08:00
不能
|
61
tianhualefei 2020-11-17 13:49:40 +08:00 via Android
背包问题在力扣( leetcode )属于中等难度。你这既没有正确认识问题的难度,也没正确认识自己的水平。
|
62
totoro52 2020-11-17 13:54:48 +08:00
这里也有凡尔赛人?
|
63
guixiexiezou OP @tianhualefei 我看了下,确实是属于中等难度。也就是说这就是我思维的极限了。
|
64
ochatokori 2020-11-17 14:07:37 +08:00 via Android
我只会快排,我应该转行吗
|
65
guixiexiezou OP @totoro52 当你所有视频面(中大厂级别)都挂了的时候,也许你就不会这么认为了,反而会从另外一个角度思考问题,无论是牛角尖也好,还是感悟人生也好
|
66
guixiexiezou OP @user8341 寻路一般都用改进版 A 星算法,一般都用现成的库例如 LIBGDX 等,也会用上一代人遗留的代码,直接调用接口。需要自己完整实现的场景不多
|
67
jay4497 2020-11-17 14:52:25 +08:00
哪条路上都有各种级别的人,大神都那么多了,咱就不去凑那个热闹了,安心做个菜鸡。。。
说不适合这条路那不至于不至于。。。 |
68
billma 2020-11-17 16:45:17 +08:00
你这让只会 vb 的我情何以堪...
|
69
calabash519 2020-11-17 16:53:17 +08:00
建议转行
|
71
1039460820 2020-11-17 18:14:12 +08:00
小白前来为楼主加油,随便看看大佬们的推荐,V2ex 万岁!
|
72
CoderGeek 2020-11-17 18:21:40 +08:00
用过就忘 老被说 公司里经常被人怼 不是会个啥算法就怎么样,然后离职换下家又得温习一遍 哈哈哈
|
73
hejw19970413 2020-11-17 18:28:18 +08:00
先会学会抄,后会学,然后是理解,这是一个痛苦的过程
|
74
darklowly 2020-11-17 22:00:58 +08:00
@leido 和算法高不高级么关系的,重要是两条不同的方向。不信的话,你可以调研一下绝大部分工程师,工作中用过动态规划吗?
绝大部份工程师职业瓶颈根本就不在算法上面,是在设计上面,能够用简单优美的方法解决问题,比算法更重要。 我观察过很多工程师,智力正常,投资很多时间去搞算法,结果是,算法也搞不好,代码也写不好,这种情况在国内非常普遍。甚至很多工程师工作 10 年以上,分解一个函数都分解不好。 go 语言有一个开源的 web 框架:beego,在国内受到了大量的追捧,里面的代码写得非常差,设计也非常潦草。如果你仔细去思考这个问题,会非常有意思: 1 为什么一个喜欢技术的程序员写出了非常差的代码,还好意思公开发表?并且还出书教人? 2 为什么大量的用户会去追捧这样一个很差的框架?这些用户里面大量是小白,没有鉴别能力,可以理解,为什么很多很有经验的工程师也没有鉴别能力?如果连基本的鉴别能力都不具备,设计能力就更不具备了。 他们缺乏的是算法能力吗?还是基本的设计能力和鉴别能力? 这些设计和鉴别能力,应该怎么才能学到呢?无非就是去多学习经典的设计方法。而这些设计方法大多在第一条路上面学习。 PS:基本的数据结构和算法是需要的。 |
75
gy0624ww 2020-11-20 14:26:28 +08:00
特么的,今天我才知道凡尔赛人是啥意思,我以为你们讨论的是一道 leetcode 题目叫凡尔赛人呢
|