2019-08-31

leetcode / Medium

4 分钟读完 (大约 586 个字)

is-graph-bipartite

题目描述

给定一个无向图graph，当这个图为二分图时返回true。如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

题目分析

题目比较容易理解，我们只需要使用深搜或者广搜，将节点分成两部分，如果找到某个节点必须在两部分中同时出现，即该图不可二分。

算法

深度优先遍历（Depth-first-Search）

代码

class Solution {
    public boolean isBipartite(int[][] graph) {
        Queue<Integer> queue = new LinkedList<>();
        int[] colors = new int[graph.length];   // 三色标记法，0表示该节点未划分，-1表示该节点在partA，1表示该节点在partB
        for (int i = 0; i < graph.length; i++) {
            // 遍历所有节点，对未划分的节点分入partB（因为该节点和之前划分的节点没有边相连，即无所谓partA和partB，这里选partB）
            if (colors[i] == 0 && !validColor(graph, colors, 1, i)) return false;
        }
        return true;
    }
    
    public boolean validColor(int[][] graph, int[] colors, int color, int node) {
        if (colors[node] != 0) {
            // 剪支，如果当前节点已经归类，则判断他是不是需要在两部分同时出现
            return colors[node] == color;
        }
        colors[node] = color;
        for (int j : graph[node]) {
            // 找到反例立刻返回
            if (!validColor(graph, colors, -color, j)) return false;
        }
        return true;
    }
    
    
}

宽度优先遍历（优化）（Breadth-first-Search）

代码

class Solution {
    public boolean isBipartite(int[][] graph) {
        Queue<Integer> queue = new LinkedList<>();
        int[] colors = new int[graph.length];
        
        for (int i = 0; i < graph.length; i++) {
            if (colors[i] != 0) continue;   // 以染色节点，迅速返回
            queue.offer(i);
            colors[i] = 1;  // 无所谓1或-1，这里选1
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int j : graph[cur]) {
                    // 一条边上另个节点和当前节点分类相同，即非二分图
                    if (colors[j] == colors[cur]) return false;
                    if (colors[j] == 0) {
                        colors[j] = -colors[cur];
                        queue.offer(j);
                    }
                }
            }
        }
        return true;
    }
}

2019-08-24

leetcode / Medium

5 分钟读完 (大约 807 个字)

find-eventual-safe-states

题目链接：find-eventual-safe-states

题目描述

在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。现在, 如果我们最后能走到终点，那么我们的起始节点是最终安全的。更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。哪些节点最终是安全的？结果返回一个有序的数组。该有向图有 N 个节点，标签为 0, 1, …, N-1, 其中 N 是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表，满足 (i, j) 是图的一条有向边。

题目分析

题目意思即找出非闭环的所有节点

我们可以从终点开始，即先找出那些没有出去的边的节点，即出度为0，这些节点一定符合条件，然后，反向搜索，找出他的上游，如果他的上游的所有出去的边都是在这些节点当中，则他的上游节点也是安全的。
我们还可以采用深搜的方式，对每个节点的所有出去的边进行搜索，如果他的所有下游节点都是安全的，则他也是安全的。

算法

反向边（Graph)

代码

class Solution {
    
    public List<Integer> eventualSafeNodes(int[][] G) {
        List<Set<Integer>> graph = new ArrayList<>();       // 正向边图
        List<Set<Integer>> rgraph = new ArrayList<>();      // 反向边图
        Queue<Integer> queue = new LinkedList<>();          // 安全节点队列
        List<Integer> result = new ArrayList<>();           // 返回结果集
        boolean[] safe = new boolean[G.length];             // 标记安全节点（因为返回结果要有序的，这里用空间换时间）
        
        // 图的初始化
        for (int i = 0; i < G.length; i++) {
            graph.add(new HashSet<Integer>());
            rgraph.add(new HashSet<Integer>());
        }
        for (int i = 0; i < G.length; i++) {
            for (int j : G[i]) {
                graph.get(i).add(j);
                rgraph.get(j).add(i);
            }
            if (G[i].length == 0) queue.offer(i);
        }

        while (!queue.isEmpty()) {
            // 安全节点集非空，出队并标记
            int i = queue.poll();
            safe[i] = true;
            for (int j : rgraph.get(i)) {
                // 移除上游节点到安全节点的边，如果上游节点的所有边都是到安全节点（即graph.get(j).isEmpty()），则入队
                graph.get(j).remove(i);
                if (graph.get(j).isEmpty()) queue.offer(j);
            }
        }
        // 读取标记，返回结果
        for (int i = 0; i < G.length; i++) {
            if (safe[i]) result.add(i);
        }
        return result;
    }
}

深度优先搜索（Depth-first-Search）

代码

import java.util.*;

class Solution {
    // white表示未搜索，
    // black表示安全节点，
    // grey表示搜索中的节点或不安全节点
    enum Color {
        WHITE,
        BLACK,
        GREY,
    }
    
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> result = new ArrayList<>();
        if (graph.length == 0) return result;
        Color[] color = new Color[graph.length];
        Arrays.fill(color, Color.WHITE);
        for (int i = 0; i < graph.length; i++) {
            if (dfs(graph, i, color)) result.add(i);
        }
        return result;
    }
    
    public boolean dfs(int[][] graph, int i, Color[] color) {
        if (color[i] != Color.WHITE) return color[i] == Color.BLACK;        // 节点i被搜索过，剪支，快速返回
        color[i] = Color.GREY;          // 标记节点i在搜索中
        for (int child : graph[i]) {
            if (!dfs(graph, child, color)) return false;       
        }
        color[i] = Color.BLACK;         // 标记节点i安全
        return true;
    }
}

2019-08-18

leetcode / Medium

5 分钟读完 (大约 704 个字)

decode-string

题目链接：decode-string

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

题目分析

基本上，我们可以理解为只用三种情况

字母字符串，直接返回
数字字符串，后边跟了各’[‘，将他的下层返回的字符字符串加倍存储。
‘]’一层结束的标志，返回字符字符串。

算法

栈（Stack）

代码

import java.util.*;

class Solution {
    public String decodeString(String s) {
        StringBuilder result = new StringBuilder();
        LinkedList<String> stack = new LinkedList<String>();
        int index = 0;
        while (index < s.length()) {
            if (Character.isLetter(s.charAt(index))) {
                // 字母字符串
                StringBuilder cur = new StringBuilder();
                while(index < s.length() && Character.isLetter(s.charAt(index))) {
                    cur.append(s.charAt(index));
                    index++;
                }
                stack.push(cur.toString());
            } else if (Character.isDigit(s.charAt(index))) {
                // 数字字符串
                int j = index;
                while (Character.isDigit(s.charAt(j))) j++;
                stack.push(s.substring(index, j));
                index = j + 1;
            } else {
                while (index < s.length() && s.charAt(index) == ']') {
                    // 一层结束
                    StringBuilder tmp = new StringBuilder();
                    String s2 = stack.pop();
                    String s1 = stack.pop();
                    if (Character.isDigit(s1.charAt(0))) {
                        // 将栈里最后两个字符串合并（数字 * 字母）
                        int k = Integer.parseInt(s1);
                        while (k-- > 0) {
                            tmp.append(s2);
                        }
                        index++;
                    } else {
                        // 有可能同一层里套了多个子层，所以，有可能是两个字符串，需要先合并如 "2[3[a]2[b]]"， 我们
                        // 在完成2[b]合并的同时，栈里是[2, aa, bb],我们需要将aa也合并，直到栈里的前一个字符串是数字。
                        tmp.append(s1);
                        tmp.append(s2);
                    }
                    stack.push(tmp.toString());
                }
            }
        }
        // 最外一层合并，如例子 "3[a]2[bc]"
        while (!stack.isEmpty()) {
            result.append(stack.removeLast());
        }
        return result.toString();
    }
}

深度优先遍历（Depth-first-Search）

事实上，感觉这题不是经典的深搜，更加符合stack的标签，不过理解为深搜也没毛病。

代码

class Solution {
    public String decodeString(String s) {
        StringBuilder result = new StringBuilder();
        dfs(s.toCharArray(), 0, result);
        return result.toString();
    }
    
    public int dfs(char[] cc, int start, StringBuilder str) {
        while (start < cc.length) {
            if (Character.isDigit(cc[start])) {
                int count = 0;
                while (Character.isDigit(cc[start])) {
                    count = count * 10 + cc[start] - '0';
                    start++;
                }
                StringBuilder inner = new StringBuilder();      // 将下一层解析的字符串结果带回来
                int end = dfs(cc, start + 1, inner);
                while (count-- > 0) str.append(inner.toString());   // 合并 数字 * 字符串
                start = end;
            } else if (Character.isLetter(cc[start])) {
                // 存储连续的字符串
                while (start < cc.length && Character.isLetter(cc[start])) {    
                    str.append(cc[start]);
                    start++;
                }
            } else {
                // ‘]'字符，返回这层结束后的下一个index
                return start + 1;
            }
        }
        return start;
    }
}

2019-08-17

leetcode / Medium

5 分钟读完 (大约 765 个字)

loud-and-rich

题目链接：loud-and-rich

题目描述

在一组 N 个人（编号为 0, 1, 2, …, N-1）中，每个人都有不同数目的钱，以及不同程度的安静（quietness）。为了方便起见，我们将编号为 x 的人简称为 “person x “。如果能够肯定 person x 比 person y 更有钱的话，我们会说 richer[i] = [x, y] 。注意 richer 可能只是有效观察的一个子集。另外，如果 person x 的安静程度为 q ，我们会说 quiet[x] = q 。现在，返回答案 answer ，其中 answer[x] = y 的前提是，在所有拥有的钱不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）

题目分析

直观上看，对每个人，我们需要找出比他有钱或者和他一样有钱（他自己）的人，然后比较找出这些人（包括他自己）中最安静的一个作为结果。（解法1）
事实上，在寻找结果过程中，我们没必要找出所有比他有钱的人，比如A比B有钱，C比A有钱，在查找过程中，对于B，我们没有必要同时比较A、B、C三个人的安静值，我们可以先比较A、C的安静值，将min(A, C)结果存起来，然后再比较min(min(A, C), B)的值，即得出比B有钱且最安静的人。（解法2）

算法

深度优先遍历（Depth-first-Search）

代码

import java.util.*;

class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int N = quiet.length; 
        Map<Integer, Set<Integer>> map = new HashMap<>(); // value值存的是比key值更有钱的人
        for (int[] r : richer) {
            Set<Integer> tmp = map.getOrDefault(r[1], new HashSet<>());
            tmp.add(r[0]);
            map.put(r[1], tmp);
        }
        for (int i = 0; i < N; i++) {
            // 遍历深搜，对每个人，找出比他更有钱的人
            Set<Integer> tmp = new HashSet<>();
            dfs(map, tmp, i);
            map.put(i, tmp);
        }

        int[] result = new int[N];
        for (int i = 0; i < N; i++) {
            // 比较，对每个人，从比他更有钱的人找出最安静的人
            result[i] = i;
            for (int p : map.get(i)) {
                if (quiet[result[i]] > quiet[p])
                    result[i] = p;
            }
        }
        return result;
    }
    
    public void dfs(Map<Integer, Set<Integer>> map, Set<Integer> cur, int j) {
        Set<Integer> tmp = new HashSet<>(map.getOrDefault(j, new HashSet<>()));
        for (int richer : tmp) {
            if (!cur.contains(richer)) {
                cur.add(richer);
                dfs(map, cur, richer);                
            }
        }
    }    
}

深度优先遍历（优化）（Depth-first-Search）

代码

import java.util.*;

class Solution {
    List<Integer>[] graph; // 同解法1map,graph[i]表示比i更有钱的人（不完全集合）
    int[] result;
    int[] quiet;
    
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int N = quiet.length; 
        graph = new ArrayList[N];
        result = new int[N];
        this.quiet = quiet;
        
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<Integer>();
            result[i] = -1;
        }
        for (int[] edge : richer) {
            graph[edge[1]].add(edge[0]);
        }
        for (int node = 0; node < N; node++) {
            dfs(node);
        }
        return result;
    }
    
    // 返回比node更有钱或同样有钱（包括他自己）的人中最安静的人的编号
    public int dfs(int node) {
        if (result[node] == -1) {
            result[node] = node;
            for (int child : graph[node]) {
                int cand = dfs(child);
                if (quiet[cand] < quiet[result[node]]) {
                    result[node] = cand;
                }
            }
        }
        return result[node];
    }    
}

2019-08-17

leetcode / Medium

4 分钟读完 (大约 643 个字)

house-robber-iii

题目链接：house-robber-iii

题目描述

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

题目分析

不相邻的节点和最大值，让我们可以分成两种情况：

该节点值 + 他的间接子树最大值的和
他的直接子树最大值的和

算法

深度优先遍历（Depth-first-Search）

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        return dfs(root);
    }
    
    public int dfs(TreeNode root) {
        if (root == null) return 0;
        int result = root.val;
        if (root.left != null) result += dfs(root.left.left) + dfs(root.left.right);    // 该节点左间接子树和最大值
        if (root.right != null) result += dfs(root.right.left) + dfs(root.right.right); // 该节点右间接子树和最大值
        result = Math.max(result, dfs(root.left) + dfs(root.right));    // 比较选择包含该节点还是不包含该节点的和最大值
        return result;
    }
}

深度优先遍历（优化）（Depth-first-Search）

在上一解法中，明显可以发现，我们在寻找当前树的最大值时，还需要寻找子树的子树最大值，而在寻找子树的最大值时，我们已经查找过了子树的子树的最大值，即有很多计算是重复的。因此，在深搜过程中，同时返回包含该节点和最大值和不包含该节点和最大值可以给我们运行时间上带来不少优化。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }
    
    // [0] => 包含该节点的和最大值
    // [1] => 不包含该节点的和最大值
    public int[] dfs(TreeNode root) {
        if (root == null) return new int[]{0, 0};
        int result = root.val;
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        return new int[] {
            root.val + l[1] + r[1], Math.max(l[0], l[1]) + Math.max(r[0], r[1])
            };
    }
}

2019-08-10

leetcode / Medium

6 分钟读完 (大约 948 个字)

all-nodes-distance-k-in-binary-tree

题目链接：all-nodes-distance-k-in-binary-tree

题目描述

给定一个二叉树（具有根结点 root），一个目标结点 target ，和一个整数值 K 。返回到目标结点 target 距离为 K 的所有结点的值的列表。答案可以以任何顺序返回。

题目分析

距离给定节点距离为K的节点有两种情况：第一种是他的子节点，这种情况比较容易通过遍历得到。第二种是他的祖先节点的其他子树，对于这种情况，我们需要能找到节点的祖先节点的方法。
找到某节点父节点的方法可有两种，一种是深搜回退到他的父节点，一种是建立子节点到父节点的映射。

算法

深度优先遍历（Depth-first-Search）

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> result;
    int k;

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        result = new ArrayList<>();
        k = K;
        dfs(root, target);
        return result;
    }

    public int dfs(TreeNode cur, TreeNode target) {
        if (cur == null) {
            return -1;            // 返回-1表示在当前子树没有找到目标节点
        }
        if (cur == target) {
            subtreeAdd(cur, 0); // 找到目标节点了，对目标节点子树进行查找
            return 1; // 返回他的父节点到目标节点距离
        } else {
            int d = dfs(cur.left, target);
            if (d != -1) {
                // 目标节点在左子树
                if (d == k) {
                    // 当前节点符合到目标节点距离，添加到结果集
                    result.add(cur.val);                    
                }
                subtreeAdd(cur.right, d + 1);  // 寻找当前节点右子树符合条件的节点
                return d + 1; // 返回当前节点父节点到目标节点的距离
            } else {
                d = dfs(cur.right, target);
                if (d != -1) {
                    // 目标节点在右子树
                    if (d == k) {
                        // 当前节点符合到目标节点距离，添加到结果集
                        result.add(cur.val);    
                    }
                    subtreeAdd(cur.left, d + 1);    // 寻找当前节点左子树符合条件的节点
                    return d + 1;   // 返回当前节点父节点到目标节点的距离
                }
            }
            return -1;  // 目标节点在当前子树不存在
        }
    }

    // 查找当前子树符合到目标节点距离的值，保存结果
    public void subtreeAdd(TreeNode cur, int d) {
        if (cur == null || d > k) {
            return;
        }
        if (k == d) {
            result.add(cur.val);            
        }
        subtreeAdd(cur.left, d + 1);
        subtreeAdd(cur.right, d + 1);
    }
}

宽度优先搜索（Breadth-first-Search）

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        Map<TreeNode, TreeNode> child2parent = new HashMap<>();
        dfs(root, null, child2parent);  // 建立子节点到父节点的映射

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(target);
        queue.offer(null);  // 以null为到目标节点距离相同的节点集分割点

        HashSet<TreeNode> seen = new HashSet<>();   // 标记查找过的节点，保证入队节点距离目标节点的距离是逐渐增加的
        seen.add(target);
        seen.add(null);

        List<Integer> result = new ArrayList<>();   // 保存结果
        while (!queue.isEmpty()) {
            TreeNode tmp;
            if (K == 0) {
                // 到目标节点距离为K，将当前队列中所有节点集保存到结果，null节点是分割点
                while ((tmp = queue.poll()) != null) {
                    result.add(tmp.val);
                }
            } else {
                while ((tmp = queue.poll()) != null) {
                    // 遍历当前距离目标节点距离相等的所有节点，分别将他的父节点、左子节点、右子节点
                    // 入队（如果这些节点没有被标记过，即他们离目标节点的距离都是+1）
                    if (!seen.contains(tmp.left)) {
                        seen.add(tmp.left);
                        queue.offer(tmp.left);
                    }
                    if (!seen.contains(tmp.right)) {
                        seen.add(tmp.right);
                        queue.offer(tmp.right);
                    }
                    if (!seen.contains(child2parent.get(tmp))) {
                        seen.add(child2parent.get(tmp));
                        queue.offer(child2parent.get(tmp));
                    }
                }
                queue.offer(null); // null入队分割下次循环
                K--; // 目标距离-1
            }
        }
        return result;
    }
    
    public void dfs(TreeNode cur, TreeNode parent, Map<TreeNode, TreeNode> child2parent) {
        if (cur != null) {
            child2parent.put(cur, parent);
            dfs(cur.left, cur, child2parent);
            dfs(cur.right, cur, child2parent);
        }
    }
}

2019-08-04

leetcode / Medium

7 分钟读完 (大约 992 个字)

shopping-offers

题目链接：shopping-offers

题目描述

在LeetCode商店中，有许多在售的物品。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。任意大礼包可无限次购买。

说明:

最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
你不可以购买超出待购清单的物品，即使更便宜。

题目分析

首先，改题目明显具有最有子结构的特征，因此可以采用动态规划算法。
最优值，如果采用深搜，明显具有可以剪枝特征。

算法

深度优先遍历（Depth-first-Search）

代码

public class Solution {
    public int shoppingOffers(List < Integer > price, List < List < Integer >> special, List < Integer > needs) {
        return dfs(price, special, needs, 0);
    }
    
    public int dfs(List < Integer > price, List < List < Integer >> special, List < Integer > needs, int offerIndex) {
        if (offerIndex == special.size()) {
            // 不采用套餐
            int cost = 0;
            for (int i = 0; i < needs.size(); i++) cost += price.get(i) * needs.get(i);
            return cost;
        }
        
        int cost = Integer.MAX_VALUE;
        // 采用当前套餐
        List<Integer> offer = special.get(offerIndex);
        if (check(offer, needs)) {
            for (int i = 0; i < needs.size(); i++) {
                needs.set(i, needs.get(i) - offer.get(i));
            }
            cost = Math.min(cost, 
                            offer.get(price.size()) + dfs(price, special, needs, offerIndex));     // 继续采用当前套餐
            cost = Math.min(cost,
                            offer.get(price.size()) + dfs(price, special, needs, offerIndex + 1)); // 采用下一个套餐
            // 将当前需要商品数还原
            for (int i = 0; i < needs.size(); i++) {
                needs.set(i, needs.get(i) + offer.get(i));
            }
        }
        // 不采用当前套餐
        cost = Math.min(cost,
                        dfs(price, special, needs, offerIndex + 1));
        return cost;
    }
    
    
    // 检验当前套餐是否可用
    private boolean check(List<Integer> offer, List<Integer> needs) {
        for (int i = 0; i < needs.size(); i++) {
            if (offer.get(i) > needs.get(i)) return false;
        }
        return true;
    }

}

深度优先遍历+剪枝（Depth-first-Search+Pruning）

代码

class Solution {
    int total = Integer.MAX_VALUE;  // 总花费
    
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        dfs(price, special, needs, 0, 0);
        return total;
    }
    
    private void dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int offerIndex, int cost) {
        if (cost >= total) return;  // 剪枝
        if (offerIndex == special.size()) {
            // 不采用套餐
            for (int i = 0; i < needs.size(); i++) cost += price.get(i) * needs.get(i);
            total = Math.min(total, cost);
            return;
        }

        // 采用当前套餐
        List<Integer> offer = special.get(offerIndex);
        if (check(offer, needs)) {
            for (int i = 0; i < needs.size(); i++) {
                needs.set(i, needs.get(i) - offer.get(i));
            }
            dfs(price, special, needs, offerIndex, cost + offer.get(price.size()));     // 继续采用当前套餐
            dfs(price, special, needs, offerIndex + 1, cost + offer.get(price.size())); // 采用下一个套餐
            for (int i = 0; i < needs.size(); i++) {
                needs.set(i, needs.get(i) + offer.get(i));
            }
        }

        // 不采用当前套餐
        dfs(price, special, needs, offerIndex + 1, cost);
    }
    
    // 检验当前套餐是否可用
    private boolean check(List<Integer> offer, List<Integer> needs) {
        for (int i = 0; i < needs.size(); i++) {
            if (offer.get(i) > needs.get(i)) return false;
        }
        return true;
    }
    
}

动态规划（Dynamic-Programming）

代码

class Solution {
    
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        dp(price, special, needs, map);
        int key = hashcode(needs);
        return map.get(key);
    }
    
    private void dp(List<Integer> price, List<List<Integer>> special, List<Integer> needs, Map<Integer, Integer> map) {
        int code = hashcode(needs);
        if (map.get(code) != null) return;  // 已被解决的子问题，剪枝
        
        int result = 0;
        // 不采用套餐
        for (int i = 0; i < needs.size(); i++) {
            result += price.get(i) * needs.get(i);
        }
        
        for (List<Integer> offer : special) {
            if (check(offer, needs)) {
                List<Integer> temp = new ArrayList<>();
                for (int i = 0; i < needs.size(); i++) temp.add(needs.get(i) - offer.get(i));
                dp(price, special, temp, map);
                result = Math.min(result, map.get(hashcode(temp)) + offer.get(price.size()));       // 此时，子问题一定已经被解决，直接从map中获取
            }
        }
        map.put(code, result);  // 将当前最优解放入map中
    }
    
    // 检验当前套餐是否可用
    private boolean check(List<Integer> offer, List<Integer> needs) {
        for (int i = 0; i < needs.size(); i++) {
            if (offer.get(i) > needs.get(i)) return false;
        }
        return true;
    }
    
    // 将当前需要转化成一个hash值，因为说明最多买6中商品
    private int hashcode(List<Integer> needs) {
        int result = 0;
        for (int need : needs) result = result * 6 + need;
        return result;
    }
}

2019-08-03

leetcode / Medium

5 分钟读完 (大约 717 个字)

pyramid-transition-matrix

题目链接：pyramid-transition-matrix

题目描述

现在，我们用一些方块来堆砌一个金字塔。每个方块用仅包含一个字母的字符串表示，例如 “Z”。使用三元组表示金字塔的堆砌规则如下：(A, B, C) 表示，“C”为顶层方块，方块“A”、“B”分别作为方块“C”下一层的的左、右子块。当且仅当(A, B, C)是被允许的三元组，我们才可以将其堆砌上。初始时，给定金字塔的基层 bottom，用一个字符串表示。一个允许的三元组列表 allowed，每个三元组用一个长度为 3 的字符串表示。如果可以由基层一直堆到塔尖返回true，否则返回false。

题目分析

首先，看完题目，我们可以很清楚的知道，我们需要将每层的各种可能性组合起来，然后不断往金字塔顶部迭代（递归），找到一种可能性。
由于每层的方块数都不一致，因此，我们不能以层作为递归条件，而且，可能有好多层，for循环次数不一致。应该以每个块作为递归条件，在每次递归中，再加以判断是不是应该换层。

算法

深度优先遍历（Depth-first-Search）

代码

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, List<Character>> map = new HashMap<>(); // 可堆砌块的映射
        for (String s : allowed) {
            String key = s.substring(0, 2);
            List<Character> vals = map.getOrDefault(key, new ArrayList<Character>());
            vals.add(s.charAt(2));
            map.put(key, vals);
        }
        return dfs(bottom, map, "");
    }
    
    private boolean dfs(String bottom, Map<String, List<Character>> map, String path) {
        if (bottom.length() == 1) return true;  // 到达金字塔顶端，返回true
        if (bottom.length() == path.length() + 1) return dfs(path, map, "");    // 当前一个层完成，进入下一层
        String key = bottom.substring(path.length(), path.length() + 2);
        for (Character c : map.getOrDefault(key, new ArrayList<Character>())) {
            if (dfs(bottom, map, path + c)) return true; // 递归遍历，每个砖块
        }
        return false;
    }
    
}

深度优先遍历+位运算（Depth-first-Search + Bit-Manipulation）

代码

class Solution {
    int N = 7;  // 题目里只有7中方块
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        int[][] blocks = new int[N][N];
        for (String s : allowed) {
            blocks[s.charAt(0) - 'A'][s.charAt(1) - 'A'] |= (1 << (s.charAt(2) - 'A')); // 类似上一解法中的map
        }
        int[][] pyramids = new int[bottom.length()][];
        for (int i = 0; i < bottom.length(); i++) {
            pyramids[i] = new int[bottom.length() - i]; // 第i层砖块长度
            pyramids[0][i] = bottom.charAt(i) - 'A'; // 初始层砖块
        }
        return dfs(pyramids, blocks, 1, 0);
    }
    
    private boolean dfs(int[][] pyramids, int[][] blocks, int level, int pos) {
        if (level == pyramids.length) return true;  // 金字塔构建完成
        if (pos == pyramids[level].length) return dfs(pyramids, blocks, level + 1, 0);  // 进入下一层
        
        int mask = blocks[pyramids[level - 1][pos]][pyramids[level - 1][pos + 1]];  // 当前两个砖块可以堆叠的全部可能性
        for (int i = 0; i < N; i++) {
            if ((mask & (1 << i)) != 0) {
                pyramids[level][pos] = i;
                if (dfs(pyramids, blocks, level, pos + 1)) return true;
            }
        }
        return false;
    }
}

2019-07-27

leetcode / Medium

3 分钟读完 (大约 468 个字)

friend-circles

题目链接：friend-circles

题目描述

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

题目分析

要求返回的是朋友圈总数，即不相连的朋友圈数量，典型深搜和并查集题目。

算法

深度优先遍历（Depth-first-Search）

代码

class Solution {
    public int findCircleNum(int[][] M) {
        int result = 0;
        for (int row = 0; row < M.length; row++) {
            // 遍历每个学生
            result += dfs(M, row);
        }
        return result;
    }
    
    public int dfs(int[][] M, int row) {
        if (M[row][row] == 0) return 0; // 该学生已经被深搜遍历过
        for (int col = 0; col < M.length; col++) {
            if (M[row][col] == 1) {
                // row, col表示两个人，他们是朋友，从row遍历到col
                M[row][col] = 0;
                M[col][row] = 0;
                dfs(M, col);
            }
        }
        return 1;
    }
    
}

并查集（Union-Find）

代码

class Solution {
    public int findCircleNum(int[][] M) {
        UnionFind uf = new UnionFind(M.length);
        for (int row = 0; row < M.length; row++) {
            for (int col = 0; col < M.length; col++) {
                if (M[row][col] == 1) uf.union(row, col);   // 两人是朋友，合并朋友圈
            }
        }
        return uf.count;
    }
    
    class UnionFind {
        int[] parents;
        int count;  // 统计parents[id] == id的数量
        
        UnionFind(int n) {
            parents = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parents[i] = i;
            }
        }
        
        public int find(int p) {
            while (parents[p] != p) {
                parents[p] = parents[parents[p]];
                p = parents[p];
            }
            return p;
        }
        
        public void union(int p, int q) {
            if (find(p) != find(q)) {
                // 两者合并，parents[id] == id的数量减1
                count--;
                parents[find(p)] = find(q); 
            }
        }
    }
        
}

2019-07-27

leetcode / Medium

5 分钟读完 (大约 792 个字)

minesweeper

题目链接：minesweeper

题目描述

让我们一起来玩扫雷游戏！
给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷，’E’ 代表一个未挖出的空方块，’B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（’1’ 到 ‘8’）表示有多少地雷与这块已挖出的方块相邻，’X’ 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中（’M’或者’E’）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：

如果一个地雷（’M’）被挖出，游戏就结束了- 把它改为 ‘X’。
如果一个没有相邻地雷的空方块（’E’）被挖出，修改它为（’B’），并且所有和其相邻的方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（’E’）被挖出，修改它为数字（’1’到’8’），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。

题目分析

这里的相邻是上下左右和四个对角线，注意不是只有上下左右

算法

深度优先遍历（Depth-first-Search）

代码

class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int row = click[0];
        int col = click[1];
        if (board[row][col] == 'M') board[row][col] = 'X';  // 踩雷直接返回
        else dfs(board, row, col);
        return board;
    }
    
    private void dfs(char[][] board, int row, int col) {
        if (isOutOfBoundary(board, row, col) || board[row][col] != 'E') return; // 越界或已经遍历过
        int mines = getNumOfMinesAround(board, row, col);
        if (mines == 0) {
            // 周围地雷数量为0，才会递归遍历
            board[row][col] = 'B';
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    dfs(board, row + i, col + j);
                }
            }
        } else {
            board[row][col] = (char)('0' + mines);
        }
    }
    
    // 获取周围地雷数量
    public int getNumOfMinesAround(char[][] board, int row, int col) {
        int result = 0;
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if ((i == j && i == 0) || isOutOfBoundary(board, row + i, col + j)) continue;
                if (board[row+i][col+j] == 'M') result++;
            }
        }
        return result;
    }
    
    // 判断是否越界
    public boolean isOutOfBoundary(char[][] board, int row, int col) {
        return row < 0 || row >= board.length || col < 0 || col >= board[0].length;
    }
}

广度优先遍历（Breadth-first-Search）

代码

class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int row = click[0];
        int col = click[1]; 
        if (board[row][col] == 'M') {
            // 踩雷直接返回
            board[row][col] = 'X';
            return board;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(click);
        while (!queue.isEmpty()) {
            click = queue.poll();
            row = click[0];
            col = click[1];
            if (isOutOfBoundary(board, row, col) || board[row][col] != 'E') continue;   // 越界或已经遍历过
            int mines = getNumOfMinesAround(board, row, col);
            if (mines == 0) {
                // 周围地雷数量为0，入队遍历
                board[row][col] = 'B';
                for (int i = -1; i <= 1; i++) {
                    for (int j = -1; j <= 1; j++) {
                        queue.offer(new int[]{row + i, col + j});
                    }
                }
            } else {
                board[row][col] = (char)('0' + mines);
            }    
        }
        return board;
    }
    
    // 获取周围地雷数量
    public int getNumOfMinesAround(char[][] board, int row, int col) {
        int result = 0;
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if ((i == j && i == 0) || isOutOfBoundary(board, row + i, col + j)) continue;
                if (board[row+i][col+j] == 'M') result++;
            }
        }
        return result;
    }
    
    // 判断是否越界
    public boolean isOutOfBoundary(char[][] board, int row, int col) {
        return row < 0 || row >= board.length || col < 0 || col >= board[0].length;
    }
}

文章

分类

标签

关注我

题目描述

题目分析

算法

深度优先遍历（Depth-first-Search）

代码

宽度优先遍历（优化）（Breadth-first-Search）

代码

题目描述

题目分析

算法

反向边（Graph)

代码

深度优先搜索（Depth-first-Search）

代码

题目描述

题目分析

算法

栈（Stack）

代码

深度优先遍历（Depth-first-Search）

代码

题目描述

题目分析

算法

深度优先遍历（Depth-first-Search）

代码

深度优先遍历（优化）（Depth-first-Search）

代码

题目描述

题目分析

算法

深度优先遍历（Depth-first-Search）

代码

深度优先遍历（优化）（Depth-first-Search）

代码

题目描述

题目分析

算法

深度优先遍历（Depth-first-Search）

代码

宽度优先搜索（Breadth-first-Search）

代码

题目描述

题目分析

算法

深度优先遍历（Depth-first-Search）

代码

深度优先遍历+剪枝（Depth-first-Search+Pruning）

代码

动态规划（Dynamic-Programming）

代码

题目描述

题目分析

算法

深度优先遍历（Depth-first-Search）

代码

深度优先遍历+位运算（Depth-first-Search + Bit-Manipulation）

代码

题目描述

题目分析

算法

深度优先遍历（Depth-first-Search）

代码

并查集（Union-Find）

代码

题目描述

题目分析

算法

深度优先遍历（Depth-first-Search）

代码

广度优先遍历（Breadth-first-Search）

代码

分类

标签云

最新文章

归档

标签

最新文章

归档

标签