专栏首页机器学习入门算法细节系列(16):深度优先搜索

算法细节系列(16):深度优先搜索

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/71630857

算法细节系列(16):深度优先搜索

详细代码可以fork下Github上leetcode项目,不定期更新。

题目均摘自leetcode: 1. 329 Longest Increasing Path in a Matrix 2. 488 Zuma Game 3. 417 Pacific Atlantic Water Flow 4. 332 Reconstruct Itinerary

329 Longest Increasing Path in a Matrix

Problem:

Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [ [9,9,4], [6,6,8], [2,1,1] ] Return 4 The longest increasing path is [1,2,6,9]

Example 2:

nums = [ [3,4,5], [3,2,6], [2,2,1] ] Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

求图中不断递增的最大路径长度,采用DFS暴力搜索,代码如下:

public int longestIncreasingPath(int[][] matrix) {

        row = matrix.length;
        if (row == 0) return 0;
        col = matrix[0].length;
        if (col == 0) return 0;

        max = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                count = 1;
                dfs(matrix,i,j);
            }
        }
        return max;
    }

    static int count = 1;
    static int max = 0;
    static int row,col;
    static final int[][] direction = {{-1,0},{1,0},{0,-1},{0,1}};


    private void dfs(int[][] matrix, int cx, int cy){
        for (int i = 0; i < 4; i++){
            int nx = cx + direction[i][0];
            int ny = cy + direction[i][1];
            max = Math.max(max, count);
            if (nx >= 0 && nx < row && ny >=0 && ny < col && matrix[nx][ny] > matrix[cx][cy]){
                count++;
                dfs(matrix, nx, ny);
                //注意状态还原
                count--;
            }
        }
    }

代码TLE了,原因很简单,该代码没有记录已经搜索完毕的路径长度,而我们知道,从一个起点出发或许能够抵达某个已经搜过的路径上,所以优化代码如下:

public int longestIncreasingPath(int[][] matrix) {

        int row = matrix.length;
        if (row == 0) return 0;
        int col = matrix[0].length;
        if (col == 0) return 0;

        int[][] cache = new int[row][col];

        int max = 1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int len = dfs(matrix, i, j, row, col, cache);
                max = Math.max(len, max);
            }
        }
        return max;
    }

    final static int[][] direction = {{-1,0},{1,0},{0,-1},{0,1}};

    private int dfs(int[][] matrix, int i , int j, int row, int col, int[][] cache){
        if (cache[i][j] != 0) return cache[i][j];
        int max = 1;
        for (int[] dir : direction){
            int nx = i + dir[0], ny = j + dir[1];
            if (nx < 0 || nx >= row || ny < 0 || ny >= col || matrix[nx][ny] <= matrix[i][j]) continue;
            int len = 1 + dfs(matrix, nx, ny, row, col, cache);
            max = Math.max(max, len);
        }
        return cache[i][j] = max;
    }

DFS带返回值的特点,天然的能够进行一些状态还原,所以不需要像第一版代码一样,在DFS后加入count--

488 Zuma Game

Problem:

Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand. Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed. Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output -1.

Examples:

Input: “WRRBBW”, “RB” Output: -1 Explanation: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW Input: “WWRRBBWW”, “WRBRW” Output: 2 Explanation: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty Input:”G”, “GGGGG” Output: 2 Explanation: G -> G[G] -> GG[G] -> empty Input: “RBYYBBRRB”, “YRBGB” Output: 3 Explanation: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty

Note:

  • You may assume that the initial row of balls on the table won’t have any 3 or more consecutive balls with the same color.
  • The number of balls on the table won’t exceed 20, and the string represents these balls is called “board” in the input.
  • The number of balls in your hand won’t exceed 5, and the string represents these balls is called “hand” in the input.
  • Both input strings will be non-empty and only contain characters ‘R’,’Y’,’B’,’G’,’W’.

小时候玩的泡泡龙游戏,遇到三个以上颜色相同的球就消除,直到为空。

思路: 明确搜索对象,此处对象有两个【手中的球】和【桌上的球】,此处以桌上的球为遍历对象,因为我们知道在桌上,出现的球总共就两种情况,每种颜色要么只出现一次,要么只出现连续两次,只要手中的球足以填补成三个,我们就进行消除。遍历所有情况求得一个最小的步数,即为答案。代码如下:

public int findMinStep(String board, String hand) {
        int[] handCount = new int[32];
        for (int i = 0; i < hand.length(); i++){
            handCount[hand.charAt(i)-'A']++; //顺序无关
        }
        int min_step = helper(board + "#", handCount);
        return min_step == 6 ? -1 : min_step;
    }

    private int helper(String board, int[] handCount){
        String s = removeConsecutive(board);
        if (s.equals("#")) return 0;
        char[] cc = s.toCharArray();
        int min_step = 6;
        for (int i = 0, j = 0; j < s.length(); j++){
            int step = 0;
            if (cc[i] == cc[j]) continue;
            // j - i = 1 or 2
            int need = 3- (j - i);
            if (need <= handCount[cc[i]-'A']){
                step += need;
                handCount[cc[i]-'A'] -= need;
                min_step = Math.min(min_step,step + helper(s.substring(0, i) + s.substring(j), handCount));
                handCount[cc[i]-'A'] += need;
            }
            i = j;
        }
        return min_step;
    }

    private String removeConsecutive(String board) {
        char[] cc = board.toCharArray();
        for (int i = 0, j = 0; j < cc.length; j++){
            if (cc[i] == cc[j]) continue;
            if (j - i >= 3) return removeConsecutive(board.substring(0, i) + board.substring(j));
            else i = j;
        }
        return board;
    }

注意一些细节,因为顺序无关,所以我们可以直接用一个map进行计数。防止特殊情况j == s.length(),所以在board后多了一个字符'#'removeConsecutive()该方法针对单独连续的字符串www将返回www而不是空串,需注意。对连续的相同字符串计数的代码可以研究研究,挺不错的一个小技巧。

417 Pacific Atlantic Water Flow

Problem:

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges. Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower. Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

  • The order of returned grid coordinates does not matter.
  • Both m and n are less than 150.

Example:

Given the following 5x5 matrix: Pacific ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 * * * * * * Atlantic Return: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

思路: 可以沿着山峰顺流而下,但得保证每次下降都是流向更低的地方,如果算法不满足,就会出错。在实际编写代码时,发现这种想法较难实现,于是用了一种逆流而上的做法,分别从大西洋和太平洋出发,寻找更高的山峰,只增不减。这样,如果太平洋和大西洋都能抵达某个山峰,该山峰就是我们所求的解。代码如下:

public List<int[]> pacificAtlantic(int[][] matrix) {
        int row = matrix.length;
        if (row == 0) return new ArrayList<int[]>();
        int col = matrix[0].length;
        if (col == 0) return new ArrayList<int[]>();

        List<int[]> ans = new ArrayList<>();
        boolean[][] a = new boolean[row][col];
        boolean[][] p = new boolean[row][col];

        for (int i = 0; i < row; i++){
            dfs(matrix, i, 0, Integer.MIN_VALUE, a);
            dfs(matrix, i, col-1, Integer.MIN_VALUE, p);
        }

        for (int j = 0; j < col; j++){
            dfs(matrix, 0, j, Integer.MIN_VALUE, a);
            dfs(matrix, row-1, j, Integer.MIN_VALUE, p);
        }


        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                if (a[i][j] && p[i][j]){
                    ans.add(new int[]{i,j});
                }
            }
        }
        return ans;
    }

    int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
    private void dfs(int[][] matrix, int i, int j, int height, boolean[][] visited){
        int row = matrix.length, col = matrix[0].length;
        if (i < 0 || i >= row || j < 0 || j >= col || matrix[i][j] < height || visited[i][j]){
            return;
        }
        visited[i][j] = true;
        for (int[] d : dir){
            dfs(matrix, i+d[0], j+d[1], matrix[i][j], visited);
        }
    }

332 Reconstruct Itinerary

Problem:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

  • If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].
  • All airports are represented by three capital letters (IATA code).
  • You may assume all tickets form at least one valid itinerary.

Example 1:

tickets = [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] Return [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”].

Example 2:

tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]] Return [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]. Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]. But it is larger in lexical order.

思路: 数据结构采用Map和优先队列来建立邻接矩阵,路径的寻找采用贪心,所以只要DFS而不需要BFS,遍历结束后,从底自上把答案添加到LinkedList中去,算法与数据结构的完美结合,证明暂略。代码如下:

public List<String> findItinerary(String[][] tickets) {
        Map<String, PriorityQueue<String>> targets = new HashMap<>();
        for (String[] ticket : tickets)
            targets.computeIfAbsent(ticket[0], k -> new PriorityQueue<String>()).add(ticket[1]);
        visit("JFK",targets);
        return route;
    }

    List<String> route = new LinkedList<String>();
    private void visit(String airport, Map<String, PriorityQueue<String>> targets) {
        while (targets.containsKey(airport) && !targets.get(airport).isEmpty())
            visit(targets.get(airport).poll(), targets);
        route.add(0, airport);
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 挑战程序竞赛系列(30):3.4矩阵的幂

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 挑战程序竞赛系列(36):3.3线段树和平方分割

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 挑战程序竞赛系列(32):4.5 A*与IDA*

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • POJ 1985 Cow Marathon(树的直径)

    Description After hearing about the epidemic of obesity in the USA, Farmer John...

    attack
  • 「POJ - 2318」TOYS (叉乘)

    有一个玩具盒,被n个隔板分开成左到u右n+1个区域,然后给每个玩具的坐标,求每个区域有几个玩具。

    饶文津
  • Noip 2016 Day1 题解

    老师让我们刷历年真题, 然后漫不经心的说了一句:“你们就先做做noip2016 day1 吧” 。。。。。。 我还能说什么,,,,,老师你这是明摆着伤害我们啊2...

    attack
  • Python3 基础学习之数值进制转换

        这个函数在上篇里表示强转,并没有输入n这个参数。当n不输入的时候默认是n=10。

    ZY_FlyWay
  • poj-------(2240)Arbitrage(最短路)

    Arbitrage Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 156...

    Gxjun
  • Codeforces Round #186 (Div. 2)A、B、C、D、E

    Ilya得到了一个礼物,可以在删掉银行账户最后和倒数第二位的数字(账户有可能是负的),也可以不做任何处理。

    xindoo
  • 2019 CCPC 重现赛 1006 基环树

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2965768

扫码关注云+社区

领取腾讯云代金券