Algorithm
这周做的是一道 腾讯精选练习 50 题 中的简单题 有效的括号,这题非常简单:使用一个栈存储左括号,遇到右括号时弹栈,看是否是匹配的左括号,处理完输入的字符串以后,如果栈是空的说明字符串是题目中定义的有效的。
class Solution { |
Personal Notes
这周做的是一道 腾讯精选练习 50 题 中的简单题 有效的括号,这题非常简单:使用一个栈存储左括号,遇到右括号时弹栈,看是否是匹配的左括号,处理完输入的字符串以后,如果栈是空的说明字符串是题目中定义的有效的。
class Solution { |
这周做了一道 腾讯精选练习 50 题 中的简单题 整数反转,这题很简单,但还是有两点需要注意:
1 负数取模的结果还是负数:-1 % 2 == -1
2 溢出的判断还有两种情况, 因为一定不会成立,故省略:
(1) result == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10
(2) result == Integer.MIN_VALUE / 10 && digit < Integer.MIN_VALUE % 10
class Solution { |
这周做了一道 腾讯精选练习 50 题 中的简单题 Nim 游戏,刚开始我在想是否可以用贪心或者动态规划的思想来解,但是想了半天都没有抽取出子问题,然后我从 5 开始寻找规律,发现 5 到 12 中除了 4 的倍数 8 和 12,先手都是可以获胜的,所以一个简单的结论就是:只要石头总数不能被 4 整除先手就能获胜。仔细想想,这个游戏可以切分成以 4 块石头为一个单位,先手的人无论拿几块(1 到 3 块),最后 1 块都是对方的,所以总数如果是 4 的倍数一定是对方获胜;相反,如果总数不是 4 的倍数,先手的人一定可以通过拿 1 到 3 块使得剩下的石头数量是 4 的倍数,那对方就要输了。
class Solution { |
这周做了一道 腾讯精选练习 50 题 中的中等题 LRU 缓存机制,容易想到的一个方案是:用一个 HashMap 存储数据 key 和 value,再用一个 LinkedList 放数据的 key,访问过的 key 移动到链表的头部(删除然后重新插入),满了就删除链表尾部的元素,但是这种方案由于移动到链表头部需要线性搜索,时间复杂度是 O(n)。其实有一种简单的时间复杂度是 O(1) 的解法:HashMap 仍然存储数据的 key,但是其 value 存储的是 LinkedList 节点的引用,LinkedList 的节点中存储数据的 key 和 value,这样移动到头部的操作就可以在 O(1) 时间完成了,我模仿 Java 的 LinkedList 实现了一个自己的 MyLinkedList,题解如下:
这周做了 3 道 腾讯精选练习 50 题 中的简单题,第 1 道是 合并两个有序链表,刚开始用的解法是比较传统的顺序遍历,看题解中有人提到了递归,又尝试了下相对优雅的递归解法:
/** |