发表于

Algorithm

这周做的是一道 腾讯精选练习 50 题 中的简单题 有效的括号，这题非常简单：使用一个栈存储左括号，遇到右括号时弹栈，看是否是匹配的左括号，处理完输入的字符串以后，如果栈是空的说明字符串是题目中定义的有效的。

class Solution {
    private final static Map<Character, Character> MAPPING = new HashMap();
    static {
        MAPPING.put(')', '(');
        MAPPING.put('}', '{');
        MAPPING.put(']', '[');
    }
    public boolean isValid(String s) {
        if (s == null || s.isEmpty()) {
            return true;
        } 
        Deque<Character> stack = new ArrayDeque<>();
        for (Character c: s.toCharArray()) {
            if (MAPPING.keySet().contains(c)) {
                Character expected = MAPPING.get(c);
                Character actual = stack.pollFirst();
                if (!expected.equals(actual)) {
                    return false;
                }
            } else {
                stack.offerFirst(c);
            }
        }
        return stack.isEmpty();
    }
}
阅读全文 »

发表于

Algorithm

这周做了一道 腾讯精选练习 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 {
    public int reverse(int x) {
        int result = 0;
        while (x != 0) {
            int digit = x % 10;
            if (result > Integer.MAX_VALUE / 10 || result < Integer.MIN_VALUE / 10) {
                return 0;
            }
            result = result * 10 + digit;
            x /= 10;
        }
        return result;
    }
}
阅读全文 »

发表于

Algorithm

这周做了一道 腾讯精选练习 50 题 中的简单题 Nim 游戏，刚开始我在想是否可以用贪心或者动态规划的思想来解，但是想了半天都没有抽取出子问题，然后我从 5 开始寻找规律，发现 5 到 12 中除了 4 的倍数 8 和 12，先手都是可以获胜的，所以一个简单的结论就是：只要石头总数不能被 4 整除先手就能获胜。仔细想想，这个游戏可以切分成以 4 块石头为一个单位，先手的人无论拿几块（1 到 3 块），最后 1 块都是对方的，所以总数如果是 4 的倍数一定是对方获胜；相反，如果总数不是 4 的倍数，先手的人一定可以通过拿 1 到 3 块使得剩下的石头数量是 4 的倍数，那对方就要输了。

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}
阅读全文 »

发表于

Algorithm

这周做了一道 腾讯精选练习 50 题 中的中等题 LRU 缓存机制，容易想到的一个方案是：用一个 HashMap 存储数据 key 和 value，再用一个 LinkedList 放数据的 key，访问过的 key 移动到链表的头部（删除然后重新插入），满了就删除链表尾部的元素，但是这种方案由于移动到链表头部需要线性搜索，时间复杂度是 O(n)。其实有一种简单的时间复杂度是 O(1) 的解法：HashMap 仍然存储数据的 key，但是其 value 存储的是 LinkedList 节点的引用，LinkedList 的节点中存储数据的 key 和 value，这样移动到头部的操作就可以在 O(1) 时间完成了，我模仿 Java 的 LinkedList 实现了一个自己的 MyLinkedList，题解如下：

阅读全文 »

发表于

Algorithm

这周做了 3 道 腾讯精选练习 50 题 中的简单题，第 1 道是 合并两个有序链表，刚开始用的解法是比较传统的顺序遍历，看题解中有人提到了递归，又尝试了下相对优雅的递归解法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}
阅读全文 »
0%