ARTS 第 2 周 - AWS 云服务之 Glue

发表于 May 30 2020

Algorithm

这周仍然是腾讯精选练习 50 题列表中的一道简单题：爬楼梯，可以拆解出子问题，即爬到第 n 阶台阶有两种方式：从第 n - 1 阶爬 1 个台阶，或者从第 n - 2 阶爬 2 个台阶，所以：f(n) = f(n - 1) + f(n -2)。我的题解使用了一种带缓存的递归，时间复杂度是 O(n)：

class Solution {
    private Map<Integer, Integer> cache = new HashMap<>();
    public int climbStairs(int n) {
        cache.put(1, 1);
        cache.put(2, 2);
        return f(n);
    }

    private int f(int n) {
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        int y = f(n - 1) + f(n - 2);
        cache.put(n, y);
        return y;
    }
}

阅读全文 »

ARTS 第 1 周 - Huffman 编码

发表于 May 24 2020

Algorithm

因为很久没做算法题了，刚开始选择了腾讯精选练习 50 题这个列表中较为简单的一题：反转链表，一个简单的解法是：在遍历的过程中记录当前节点的前后节点，然后进行指针（引用）的变更即可，我的题解代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}