YoungForest's blog

RankNameScoreFinish TimeQ1 (3)Q2 (4)Q3 (5)Q4 (6)448 / 8571YoungForest141:22:340:07:280:11:43null1:17:34 1最后一题debug耽误了不少时间，最后发现是range函数的cache写错了，修改了函数的参数。以后切记memo时要把参数写成const的。 第三题，没有想到效率比较高的DP解法，一直TLE。 1475. Final Prices With a Special Discount in a Shop 寻找下一个大于的数。使用单调递增栈解决。 时间复杂度: O(N), 空间复杂度: O

RankNameScoreFinish TimeQ1 (3)Q2 (4)Q3 (5)Q4 (6)1854 / 13794YoungForest121:18:350:15:310:12:311:18:35null最近比赛能力有所下降，昨晚的双周赛也是有一道第3题没做出来，现在更是最后一题没做出来。对Q4的树上倍增算法不了解。 1480. Running Sum of 1d Array 签到题，一遍presum求和。 也可以使用STL 中的partial_sum，达到相同的效果。 时间复杂度: O(N), 空间复杂度: O(N). 1 2 3 4 5 6 7 8 9 10 11 12 13

RankNameScoreFinish TimeQ1 (3)Q2 (4)Q3 (5)Q4 (6)374 / 13805YoungForest180:53:480:07:190:07:350:15:000:43:48 2本周的题目不算难，3456手速场，最后1k人AK。 前3题自己手速还算快，最后一题花了比较长的时间，还因为实现问题TLE了2发。本来觉得自己做的还不错，后来看到排名才发现，大家都很强。还需继续努力呀。争取rating进入世界前500. 1470. Shuffle the Array 使用辅助数组，straight forward. 时间复杂度: O(N), 空间复杂度: O

RankNameScoreFinish TimeQ1 (3)Q2 (4)Q3 (5)Q4 (6)231 / 7926YoungForest180:42:160:04:510:10:550:22:31 10:37:16质量还可以的手速场。有些问题值得思考，只有发现本质，才能迅速解决。 1460. Make Two Arrays Equal by Reversing Sub-arrays 由于对reverse操作的数目不限，我们可以采用这样的策略构造将2个array转成相同的array。用类似select sort的思想，每次reverse可以将一个位置排好序。所以问题转化为，2个数组排好序后

RankNameScoreFinish TimeQ1 (3)Q2 (4)Q3 (5)Q4 (7)765 / 13283YoungForest120:27:190:02:160:12:530:27:19null本周最后一题着实比较难，涉及概率和组合数学等知识。恰好触及到我的知识盲区，所以没有做出来。对于数学好的同学应该会好很多。 1464. Maximum Product of Two Elements in an Array 签到题。由于nums.size()比较小，所以暴力即可。 时间复杂度: O(N^2), 空间复杂度: O(1). 1 2 3 4 5 6 7 8 9 10 11

Reference: C++ Standard Library: A tutorial and reference, Second version Chapter 7.9.2: Creating and Controlling unordered Container All solutions I found in Google use XOR to generate hashcode of pair, which is totally bad. see why-is-xor-the-default-way-to-combine-hashes. However, the book has g

今天在做一道AtCoder的题目，有个test case一直TLE。研究这个测试用例和其他用例的区别，苦思不得其解。后来把unordered_map换成map就过了。虽然在小数据集上hashmap和treemap区别不大，但数据量大的话，hashmap还是好些。所以最佳实践是，在不需要排序特性时，就用hashmap。 而且之前也从来没有遇到过hashmap比treemap效果差这么多的原因。最后花了一上午时间，才定位到是我的 pair 的hash函数实现太糟糕了。因为C++ STL中并没有pair的hash特化，所以如果想把pair当作键用在unordered_map中的话，就需要自己实现ha

昨晚老爸帮我掏耳朵，一不小心掏出了血。今天一大早就去地区医院检查，还好并无大碍，只损伤了外耳道，休息一周，自然痊愈就好了。只要不感染，就没问题。开了些阿姆西林吃了。 所以鸽了周赛，赛后补题。 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence C++没有自带的切割字符串的方法，不过可以用自己的模版。通过stringstream实现分割，O(N)的复杂度. 时间复杂度: O(N), 空间复杂度: O(N). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

IDscorerankBike TourBus RoutesRobot Path CodingWandering RobotTimeYoungForest745245 + 710 + 1311 + 1614 + 01:35:18上个月因为Round B结果还不错，收到了Google CN HR的Congraduation邮件。本月再接再厉，为了进入Google的梦想而努力。 A. Countdown One pass. 寻找countdown的模式。由于开始数字一定为K，所以countdown的过程中如果失败了的话，可以直接从失败的位置继续寻找。 时间复杂度: O(N), 空间复杂度:

最近经常打kickstart需要include万能头文件bits/stdc++.h，然而，我喜爱的编辑器vs code总是不能正确地找到该头文件，会有红色波浪线表示错误。作为程序员的我完全不能忍受，所以尝试解决该问题。在网络上搜了很多解决方案，大多数并不能直接地解决我的问题。所以，我总结自己的解决方案于此，方便各位取用。 编程环境: g++ 9.1.0, Mac 10.14.2, vs code 1.45.1 总的思路是: 1. 寻找gcc编译器头文件的路径, 2. 更改VS Code设置，让其用上面的路径可以找到bits/stdc++.h 1 gcc-9 -v -E -x c