LeetCode 刷题笔记

Borris 的个人博客 / 0 / 0 / 创建于 5年前 / 更新于 5年前

目的#

从 Amazon OA 高频题开始#

总结每一道做过的题目，先总结一下思路，然后记录从中获取的新知识。题目顺序不是按照序号顺序的，而是题目在真实面试中出现的频率排序。由于之前已经做过一些了，所以那些题目暂时还没有更新上去。等重新做的时候加上吧。目前的目标是每天争取记录两题在这个博文里面。

146. LRU Cache#

解法一#

这是一个比较偷懒的解法。
这道题可以使用 LinkedHashMap 的特性来完成，因为 LinkedHashMap 内置特有的方法 protected boolean removeEldestEntry(Map.Entry eldest)。put 和 putAll 将调用这个方法，移除 LinkedHashMap 中最旧的那个元素，也就是这道题所要求的。

protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_ENTRIES;
}

本题中我们只需将 MAX_ENTRIES 替换为我们所要求的 capacity 即可。其他的 put 和 get 方法可以直接调用 LinkedHashMap 内置的方法。
实现代码：

class LRUCache {
    private int capacity;
    private LinkedHashMap<Integer, Integer> cache;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            return cache.get(key);
            }
        else {
            return -1;
        }
    }

    public void put(int key, int value) {
        cache.put(key, value);
    }
}
/*
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

解法二#

利用构建 HashMap 和 DoubleLinkedList。每次 HashMap 更新一堆键值对，双向链表也要相应更新，把更新的值添加到头结点，而最早添加的结点自然来到了链表的末尾。

class LRUCache {
    private class Node {
        int key, value;
        Node prev, next;
        Node() {
            this(0, 0);
        }
        Node(int k, int v) {
            this.key = k;
            this.value = v;
        }
    }

    private int capacity, count;
    private Map<Integer, Node> map;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        map = new HashMap<Integer, Node>();
        // 定义头结点和尾节点
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (null == n) return -1;
        update(n);
        return n.value;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if (null == n) {
            n = new Node(key, value); // 没有这个值，直接新建就行
            map.put(key, n );
            add(n);
            ++count;
        }
        else {
            n.value = value; // 用新值替换
            update(n);
        }
        if (count > capacity) {
            Node toDel = tail.prev;
            remove(toDel);
            map.remove(toDel.key);
            --count;
        }
    }

    private void update(Node node) {
        remove(node);
        add(node); // 将 node 加到头结点之后
    }

    private void add(Node node) {
        Node after = head.next;
        head.next = node; // 头结点后是 node
        node.prev = head; // node 前是 head;
        node.next = after; // node 后是 after;
        after.prev = node; // after 前是 node;
    }

    // Double Linked List remove a node
    private void remove(Node node) {
        // Get the previous node and the after node. 
        Node before = node.prev, after = node.next;
        // assign the next pointer of before node pointing to after; and the after node previous pointer points to before thus caneeling the connection of the node.
        before.next = after;
        after.prev = before;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Takeaway
- 查阅了 LinkedHashMap 在题中的定义方式，了解到 LinkedHashMap 初始默认容量为 16，默认加载因子为 0.75。关于加载因子，如果实际容量达到了加载因子乘以设定的容量，那么容量就将翻倍。如 16x0.75=12, 那么实际容量到达了 12，设定容量会达到 16x2 = 32。
- 双向链表 (Double LinkedList) 构建中，add 和 remove 方法都是通过改变节点指针指向来实现再增删的。初始化双向链表时，注意要把头结点的 next 指向尾结点，尾节点的 prev 指向头结点。所有链表也要有直接前驱和直接后继的定义。

42. Trapping Rain Water#

此题求积水量，可以按列来求。根据木桶效应，每一列积水量等于左边最大高度和右边最大高度中较小的那个减去当前列的高度（当前列高需要小于最大高度的较小值）。这是求解此题的关键。

解法一: Brute Force#

对每一列，都求出左边做大高度和右边最大高度。index = 0 没有最大左边界，index = height.length 没有最大有边界。

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        for (int  i = 1; i < height.length; i++) {
            int maxLeft = 0;
            for (int j = i -1; j >= 0; j--) {
                if (height[j] > maxLeft) {
                    maxLeft = height[j];
                }
            }

            int maxRight = 0;
            for (int k = i + 1; k < height.length; k++) {
                if (height[k] > maxRight) {
                    maxRight = height[k];
                }
            }

            if (height[i] < Math.min(maxLeft, maxRight)) {
                sum += Math.min(maxLeft, maxRight) - height[i];
            }
        }

        return sum;
    }
}

时间复杂度：O (n^2), 空间复杂度 O (1)

解法二：动态规划#

第二题中，对于每一列我们都进行了遍历。其实可以使用两个数组将每一列左边右边最大的值储存起来。这样在求和时直接调用数组中的值进行计算即可。

class Solution {
    public int trap(int[] height) {
        int[] maxLeft = new int[height.length];
        int[] maxRight = new int[height.length];

        for (int i = 1; i < height.length; i++) {
            // 这里的 trick 是求第 i 列的左边最大值时，只需将第 i-1 列的左边最大值和它的高进行比较即可。
            maxLeft[i] = Math.max(maxLeft[i -1], height[i-1]); 
        }

        for (int i = height.length -2; i >= 0; i--) {
            maxRight[i] = Math.max(maxRight[i + 1], height[i+1]);
        }

        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] < Math.min(maxLeft[i], maxRight[i])) {
                sum += Math.min(maxLeft[i], maxRight[i]) - height[i];
            }
        }

        return sum;
    }
}

时间复杂度：O (n), 空间复杂度 O (n)

解法三：双指针#

这个看了解答还是没有太弄明白。明天再看一看吧。

200. Number of Islands#

解法一: DFS#

这道题如果能想到 DFS, 那么问题就变得很简单了。遍历集合中所有的点，如果含有 ‘1’，那么进行一次 DFS, 这个 DFS 的退出条件是：只要达到边界，或者达到 '0'，就退出。

class Solution {
    public int numIslands(char[][] grid) {
        // 处理空数组，防止溢出
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int row = grid.length;
        int col = grid[0].length;
        int numIsland = 0;
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (grid[r][c] == '1') {
                    numIsland++; // 遇到 1 就进行一次 DFS, 那么必然有一个岛。
                    dfs(grid, r, c);
                }
            }
        }
        return numIsland;
    }

    private void dfs(char[][] grid, int r, int c) {
        int row = grid.length;
        int col = grid[0].length;
        // 边界条件
        if (r < 0 || c < 0 || r >= row || c >= col || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0'; // 标记查找过的点为 0
        // 查找四个方向
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }
}

解法二: BFS#

稍后更新

Takeaway
- 我们在本题中不需要用另外数组来记录 visited points，把访问过的点直接置零即可，因为 DFS 的退出条件之一就是访问到 '0' 这个点。
- 需要注意的是题中 grid 是 char 类型的二维数组，并非数字！如果给点赋值数字会造成 DFS 无法退出死循环。

819. Most Common Words#

个人认为这是一道相当恶心的题目，因为有些 Test Case 实在是想不到。可能是经验少了吧。
整个题目我的思路就是，把输入的 paragraph 字符串转换为字符串数组形式，然后除了在 Banned Lists 里面的字符串外全部添加进 HashMap 中。如果字符为重复的，value (就是字符出现的次数) 加一；如果该字符串第一次出现，次数记为 1。
全部字符串录入完毕后，遍历找出出现最多的字符串。

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        /*
        Create a HashMap to store every word.
        */
        HashMap<String, Integer> map = new HashMap<>();
        String str = paragraph + ".";
        // 这里的 trick 是，对于 “a, c, b,b,b, e” 这样的 test case, 先替换逗号会造成三个 'b' 连在一起，所以先替换', ' (逗号及空格) 为 ',' 再替换 ',' 为空格。这样一来语句的格式就正确了。不过居然有人会想出这样的 test case 实在是太恶心了。。
        String[] newStr = paragraph.replaceAll("\\, ",",").replaceAll("\\,"," ").replaceAll("\\.","").replaceAll("\\!","").replaceAll("\\?","").replaceAll("\\'","").replaceAll("\\;","").split(" ");
        // 对字符串数组进行遍历，如果在 banned list 中就不加入 HashMap 里，不在的话就转换成小写后加入。
        // 如果是第一次加入，就令 value 为 1；否则 value 加一。
        for (String s : newStr) {
            boolean containBanned = false;
            for (String b : banned) {
                if (s.toLowerCase().equals(b)) {
                    containBanned = true;
                }
            }
            if (map.containsKey(s.toLowerCase()) && !containBanned) {
                int value = map.get(s.toLowerCase());
                map.put(s.toLowerCase(), value+1);
            }
            else if (!containBanned)
            {
                map.put(s.toLowerCase(), 1);
            }
        }
        // Loop for the HashMap to find out the most frequent word (Not in the banned String lists).
        Set<Map.Entry<String, Integer>> set = map.entrySet();
        int max = 0;
        String maxKey = "";
        for (Map.Entry<String, Integer> s : set) {
            if (s.getValue() >= max) {
                max = s.getValue();
                maxKey = s.getKey();
            }
        }
        return maxKey;
    }
}

Takeaway
- 编程中出现了一些错误，比如忘记了所有的字符串比较存储都应该是在先转换成小写字符的前提下的。另外，Entry 是在 Map 下的，所以得使用这种调用方式: Map.Entry。还有就是要时刻记住给变量赋值时两边类型应该一样！！

发现如果所有题都写在一篇里篇幅就太长了，所以后面的题打算每一题都另起炉灶。#

leetcode

本作品采用《CC 协议》，转载必须注明作者和本文链接

Borris

课程读者 150 声望

暂无个人描述~

0 人点赞

讨论数量: 0

(=￣ω￣=)··· 暂无内容！

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

LeetCode 刷题笔记

目的#

从 Amazon OA 高频题开始#

146. LRU Cache#

解法一#

解法二#

42. Trapping Rain Water#

解法一: Brute Force#

解法二：动态规划#

解法三：双指针#

200. Number of Islands#

解法一: DFS#

解法二: BFS#

819. Most Common Words#

发现如果所有题都写在一篇里篇幅就太长了，所以后面的题打算每一题都另起炉灶。#

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

LeetCode 刷题笔记

目的#

从 Amazon OA 高频题开始#

146. LRU Cache#

解法一#

解法二#

42. Trapping Rain Water#

解法一: Brute Force#

解法二：动态规划#

解法三：双指针#

200. Number of Islands#

解法一: DFS#

解法二: BFS#

819. Most Common Words#

发现如果所有题都写在一篇里篇幅就太长了，所以后面的题打算每一题都另起炉灶。#

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录