YoungForest's blog

发表于 更新于 分类于 Disqus：
本文根据LeetCode上的教程 Introduction to Algorithms - Recursion I 整理而成。目的在于帮助笔者自己更熟悉“递归”这一重要的编程概念，如果能够同时对他人产生帮助，那更好不过了。 本文的结构和LeetCode上的完全相同，分为 简介、递归原则、复现关系、备忘录、复杂度分析、总结 6个部分。 简介 本Card的目的，回答以下问题： 1. 什么是递归？递归如何工作？ 2. 如何递归地解决一个问题？ 3. 如何分析一个递归算法的时间复杂度和空间复杂度？ 4. 如何以一种更好的方式应用递归？ 递归的原理 每次递归函数调用自身，都将给定问题
阅读全文 »

发表于 更新于 分类于 Disqus：
本次比赛是春节后的第一次。 989. Add to Array-Form of Integer 思路：模拟笔算过程，一位一位地相加。（Solution中有个很形象的名字：Schoolbook Addition） 时间复杂度：O(max(N, M)), 其中N, M分别表示A，K的长度。 空间复杂度：O(M-N), 即deque所用的空间。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: vector addToArrayForm(v
阅读全文 »

发表于 更新于 分类于 Disqus：
由于宅在家里过节，竟然忘记了每天是星期几，只知道农历腊月几日。今天才发现已经到了周一了，错过了每周一度的weekly contest。在此除夕之夜，和家人一起看春晚之前，Forest携全家人一起祝大家新年快乐！快些刷完这4道比赛题目，好安心吃年夜饭。 由于比赛不能用官方的Notes, 写在blog上还是蛮方便的一种替代品。 985. Sum of Even Numbers After Queries 第一题直接模拟即可。每个query有2个动作： 1. add val to A[index]; 2. sum the even values of A. 模拟的时间复杂度为： O(K
阅读全文 »

发表于 更新于 分类于 Disqus：
今天放假回家，下午3点半的火车。不过我还是百忙之中抽出时间参加了每周例行的weekly contest。 结果因为回家不够专注，效果很差，只做出一道签到题。第二题TLE(结果把一个变量改成引用就可以了，也算是吸取了教训，能用引用就用引用)，第3题没有足够的时间完成了(直到下午坐上火车，心无旁骛地终于独立完成了第三题。其实思路从一开始就是对的，只不过没有时间调试细节)。第四题干脆连题干都没有时间看完。 984. String Without AAA or BBB Intution: 由于不能出现连续的a或b，我们可以试着直接构造出符合要求的字符串。多的字符出现2次，即插入一个少的字符，当剩余
阅读全文 »

发表于 更新于 分类于 Disqus：
本周和好友“女声男”同时参加weekly contest。有同学共同竞争还是挺有压力的。因为我练习算法题已经有半年时间了，他还是新手，如若最后还败北了，岂不丢人。不过结果还好，没有丢自己的人。我在离比赛结束还有10min时全部AC，而且所有题目都是一遍过，略胜一筹。不得不说，这次的题比往届简单不少，之前我的水平一直维持在只做出2道题目，ranking 800左右，而本次ranking 为 356 / 3870。从排名上看有所进步。 下面我分享一下四道题目的思路。 977. Squares of a Sorted Array 给定一个数组，返回各个元素的平方数组，该数组是排好序的。直接br
阅读全文 »

发表于 更新于 分类于 Disqus：
这次contest做的比较惨，排名大致是1486 / 3845。出现的问题有： * 第二题，比较简单。由于是easy的题目，直接brute force了，结果TLE一次。之前由于粗心，for循环条件中的变量还写错了一次。导致2次罚时。 * 第三题，也不是很难，但最后并没有想到O(n)的解法。只想到了O(n ^ 2)的。想到了要算前缀和，也注意到了divisible这一关键词。但并没有联想到前缀和相等就可以这一关键点。 * 第四题，想到了dp。卡在了"找寻后面数组中刚刚大一点的数"这步，即没想到用TreeMap解决。归根结底是因为对基础的数据结构不熟悉。 973. K Closest
阅读全文 »

发表于 更新于 分类于 Disqus：
一周一度的LeetCode weekly contest 开始啦。本周着实比之前有所进步，首先是对C++更加熟悉了，之前都是用Python写的。答题过程也更流畅了，差点做出来3道题目。 970. Powerful Integers 第一题只有3分，而且无法从算法上就行优化，brute approach即可。 需要注意的是corner case, 当x == 1 or y == 1时，1^n = 1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public:
阅读全文 »

发表于 更新于 分类于 Disqus：
今天参加LeetCode weekly contest 117, 采取了不同的策略：边做题边写博客总结。期望这样可以真实地记录所思所想，提高写博客的效率。因为之前2次，事后写博客总是耽误几天时间才写完。 965. Univalued Binary Tree 一道很简单、很弱智的题目，直接DFS/BFS即可。因为BFS在遇到异常节点的时候可以直接返回，更方便。我选择了BFS实现。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 # Definition for a binary tree node. # cl
阅读全文 »

发表于 更新于 分类于 Disqus：
又到周末LeetCode weekly contest的时候了，这次战果不佳。原因主要是，二三题都想做出来，结果都没有做出来。如果把时间都集中于第二题，应该也还是能AC的。 961. N-Repeated Element in Size 2N Array 这道题总觉得之前在LeetCode上已经做过了，还记得solution的方向。 思路是这样的，既然有一半的元素是一样的，我们随机抽取2个元素，判断是否相等就可以了。从概率上来讲，虽然有永远算不出来的概率，但在实际应用中效果很好。 1 2 3 4 5 6 7 8 9 10 11 12 import random class Solu
阅读全文 »

发表于 更新于 分类于 Disqus：
有些日子没有参加LeetCode的weekly contest了，最近由于准备一月末的Google电话面试，需要重新把算法捡起来。复习算法书是一部分，另一手就是准备刷题啦。由于时间有限，LeetCode的weekly contest不失为一个更好的选择。因为contest有时间限制，和实际面试更像。 weekly contest时长为1个半小时，4道不同难度的题目，每周末10点半开始(之前是9点半，可能是因为美国冬令时的原因，所以后沿了一小时)。 和之前一样，只完成了2道题目，第三道题有些思路(后来证明不对)，第四题看了下题目，果断放弃。 下面分享4道题目的思路和Solution，当然后2道是
阅读全文 »
0%