AC24. 机器人的运动范围

// 学习如何处理C++的pair<int, int> 

import java.util.*;

public class Main {
    public static void main (String[] args) 2{ 
        // int k = 7, m = 4, n = 5; // 20
        int k = 18, m = 40, n = 40; // 1484
        int res = movingCount(k, m, n);
        System.out.println(res);  // 20
    }

    public static int movingCount(int threshold, int rows, int cols) {
        int res = 0;
        if (cols == 0 || rows == 0) return 0;
        boolean[][] st = new boolean[rows][cols];

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0));
        while (!q.isEmpty()) {
            Node t = q.poll();
            if (get_sum(t) > threshold || st[t.first][t.second]) continue;
            res ++;
            st[t.first][t.second] = true;
            for (int i = 0; i < 4; i ++) {
                int x = t.first + dx[i], y = t.second + dy[i];
                if (x >= 0 && x < rows && y >= 0 && y < cols) q.add(new Node(x, y));
            }
        }

        return res;
    }

    public static int get_sum(Node p) {
        return get_single_sum(p.first) + get_single_sum(p.second);
    }

    public static int get_single_sum(int x) {
        int s = 0;
        while (x != 0) {
            s += x % 10;
            x /= 10;
        }

        return s;
    }

    public static class Node {
        int first;
        int second;

        public Node(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};
}

LC39. 组合总和

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        /*
        7 
        2 2 3 
        */

        // int[] candidates = {2, 3, 5};
        // int target = 8;
        /*
        3 5 
        2 3 3 
        2 2 2 2 
        */

        List<List<Integer>> res = combinationSum(candidates, target);

        for (List<Integer> r : res) {
            for (int i : r) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> ans = new ArrayList<>();;
    public static List<Integer> path = new ArrayList<>();;

    public static List<List<Integer>> combinationSum(int[] c, int target) {
        dfs(c, 0, target);
        return ans;
    }

    public static void dfs(int[] c, int u, int target) {
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            // 注意这里不可写成 ans.add(path); 也不能是new ArrayList<List<Integer>>(path)
            return ;
        }

        if (u == c.length) return ;
        for (int i = 0; c[u] * i <= target; i ++) {
            dfs(c, u + 1, target - c[u] * i);
            path.add(c[u]);
        }

        for (int i = 0; c[u] * i <= target; i ++) {
            path.remove(path.size() - 1);
        }

    }
}

LC40. 组合总和 II

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        /*
        2 6 
        1 7 
        1 2 5 
        1 1 6  
        */

        // int[] candidates = {2, 5, 2, 1, 2};
        // int target = 5;
        /*
        5 
        1 2 2 
        */

        List<List<Integer>> res = combinationSum2(candidates, target);

        for (List<Integer> r : res) {
            for (int i : r) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> ans = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();

    public static List<List<Integer>> combinationSum2(int[] c, int target) {
        Arrays.sort(c);
        dfs(c, 0, target);
        return ans;
    }

    public static void dfs(int[] c, int u, int target) {
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            // 注意这里不可写成 ans.add(path); 也不能是new ArrayList<List<Integer>>(path)
            return ;
        }

        if (u == c.length) return ;
        int k = u + 1;
        while (k < c.length && c[k] == c[u]) k ++;
        int cnt = k - u;

        for (int i = 0; c[u] * i <= target && i <= cnt; i ++) {
            dfs(c, k, target - c[u] * i);
            path.add(c[u]);
        }

        for (int i = 0; c[u] * i <= target && i <= cnt; i ++) {
            path.remove(path.size() - 1);
        }

    }
}

LC46. 全排列

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 2, 3};
        /*
        1 2 3 
        1 3 2 
        2 1 3 
        2 3 1 
        3 1 2 
        3 2 1 
        */
        List<List<Integer>> res = permute(nums);

        for (List<Integer> r : res) {
            for (int i : r) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> ans = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();
    public static boolean[] st;

    public static List<List<Integer>> permute(int[] nums) {
        st = new boolean[nums.length + 1];
        dfs(nums, 0);
        return ans;
    }

    public static void dfs(int[] nums, int u) {
        if (u == nums.length) {
            ans.add(new ArrayList<>(path));
            // 注意这里不可写成 ans.add(path); 也不能是new ArrayList<List<Integer>>(path)
            return ;
        }
        for (int i = 0; i < nums.length; i ++) 
            if (!st[i]) {
                st[i] = true;
                path.add(nums[i]);
                dfs(nums, u + 1);
                st[i] = false;
                path.remove(path.size() - 1);
            }

    }
}

LC47. 全排列 II

// 只需要在LC46. 全排列 加两行代码 即可。

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 1, 2};
        /*
        1 1 2 
        1 2 1 
        2 1 1 
        */
        List<List<Integer>> res = permute(nums);

        for (List<Integer> r : res) {
            for (int i : r) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> ans = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();
    public static boolean[] st;

    public static List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums); // 1. 这里新加的
        st = new boolean[nums.length + 1];
        dfs(nums, 0);
        return ans;
    }

    public static void dfs(int[] nums, int u) {
        if (u == nums.length) {
            ans.add(new ArrayList<>(path));
            return ;
        }
        for (int i = 0; i < nums.length; i ++) 
            if (!st[i]) {
                if (i != 0 && nums[i - 1] == nums[i] && !st[i - 1]) continue; // 2. 这里新加的 
                st[i] = true;
                path.add(nums[i]);
                dfs(nums, u + 1);
                st[i] = false;
                path.remove(path.size() - 1);
            }

    }
}

LC51. N 皇后

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int k = 4;

        /*
        .Q.. 
        ...Q 
        Q... 
        ..Q. 
        ----------
        ..Q. 
        Q... 
        ...Q 
        .Q.. 
        ----------
        */
        List<List<String>> res = solveNQueens(k);

        for (List<String> r : res) {
            for (String s : r) {
                System.out.print(s);
                System.out.println(" ");
            }

            System.out.println("----------");
        }
    }

    public static List<List<String>> ans = new ArrayList<>();

    public static int N = 20;
    public static boolean[] col = new boolean[N];
    public static boolean[] dg = new boolean[2 * N];
    public static boolean[] udg = new boolean[2 * N];
    public static char[][] path = new char[N][N];

    public static int n;

    public static List<List<String>> solveNQueens(int _n) {
        n = _n;
        for (int i = 0; i < n; i ++) 
            for (int j = 0; j < n; j ++) 
                path[i][j] = '.';

        dfs(0);
        return ans;
    }

    public static void dfs(int u) {
        if (u == n) {
            List<String> t = new ArrayList<>();
            for (int i = 0; i < n; i ++) {
                String temp = "";
                for (int j = 0; j < n; j ++) temp += path[i][j];
                t.add(temp);
            }

            ans.add(t);
            return ;
        }
        for (int i = 0; i < n; i ++) {
            if (!col[i] && !dg[u - i + n] && !udg[u + i]) {
                col[i] = dg[u - i + n] = udg[u + i] = true;
                path[u][i] = 'Q';
                dfs(u + 1);
                path[u][i] = '.';
                col[i] = dg[u - i + n] = udg[u + i] = false;
            }
        }

    }
}

LC52. N皇后 II

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        // int k = 4; // 2
        // int k = 8; // 92
        int k = 5; // 10

        int res = totalNQueens(k);
        System.out.println(res);
    }

    public static int N = 20;
    public static boolean[] col = new boolean[N];
    public static boolean[] dg = new boolean[2 * N];
    public static boolean[] udg = new boolean[2 * N];

    public static int n;

    public static int totalNQueens(int _n) {
        n = _n;
        return dfs(0);
    }

    public static int dfs(int u) {
        if (u == n) return 1;

        int res = 0;

        for (int i = 0; i < n; i ++) {
            if (!col[i] && !dg[u - i + n] && !udg[u + i]) {
                col[i] = dg[u - i + n] = udg[u + i] = true;
                res += dfs(u + 1);
                col[i] = dg[u - i + n] = udg[u + i] = false;
            }
        }
        return res;
    }
}

LC77. 组合

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int n = 4, k = 2;
        /*
        1 2 
        1 3 
        1 4 
        2 3 
        2 4 
        3 4 
        */
        List<List<Integer>> res = combine(n, k);

        for (List<Integer> r : res) {
            for (int i : r) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> ans = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();

    // 第一种方法：可以少写一个参数， k：当前还需要选几个数
    public static List<List<Integer>> combine(int n, int k) {
        dfs(n, k, 1);
        return ans;
    }

    public static void dfs(int n, int k, int start) {
        if (k == 0) { // 少写一个参数
            ans.add(new ArrayList<>(path));
            return ;
        }

        for (int i = start; i <= n; i ++) {
            path.add(i);
            dfs(n, k - 1, i + 1);
            path.remove(path.size() - 1);
        }
    }


    /* 
    // 第二种方法：u表示当前选了几个数，start：当前可以从第start个数开始选
    public static List<List<Integer>> combine(int n, int k) {
        dfs(0, 1, n, k);
        return ans;
    }

    public static void dfs(int u, int start, int n, int k) {
        if (u == k) {
            ans.add(new ArrayList<>(path));
            return ;
        }

        for (int i = start; i <= n; i ++) {
            path.add(i);
            dfs(u + 1, i + 1, n, k);
            path.remove(path.size() - 1);
        }

    }
    */
}

LC78. 子集

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 2, 3};
        /*

        3 
        2 
        2 3 
        1 
        1 3 
        1 2 
        1 2 3 
        */
        List<List<Integer>> res = subsets(nums);

        for (List<Integer> r : res) {
            for (int i : r) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> ans = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();

    public static List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return ans;
    }

    public static void dfs(int[] nums, int u) {
        if (u == nums.length) { // 少写一个参数
            ans.add(new ArrayList<>(path));
            return ;
        }

        dfs(nums, u + 1);
        path.add(nums[u]);
        dfs(nums, u + 1);
        path.remove(path.size() - 1);
    }

}

LC90. 子集 II

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 2, 2};
        /*

        2 
        2 2 
        1 
        1 2 
        1 2 2 
        */
        List<List<Integer>> res = subsetsWithDup(nums);

        for (List<Integer> r : res) {
            for (int i : r) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

    public static List<List<Integer>> ans = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();

    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(nums, 0);
        return ans;
    }

    public static void dfs(int[] nums, int u) {
        if (u == nums.length) {
            ans.add(new ArrayList<>(path));
            return ;
        }

        int k = u;
        while (k < nums.length && nums[k] == nums[u]) k ++;

        dfs(nums, k);
        for (int i = u; i < k; i ++) {
            path.add(nums[i]);
            dfs(nums, k);
        }

        for (int i = 1; i <= k - u; i ++) path.remove(path.size() - 1);
    }

}

LC130. 被围绕的区域

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        char[][] board = {
            {'X', 'X', 'X', 'X'},
            {'X', 'O', 'O', 'X'},
            {'X', 'X', 'O', 'X'},
            {'X', 'O', 'X', 'X'},
        };

        solve(board);

        for (int i = 0; i < board.length; i ++) {
            for (int j = 0; j < board[0].length; j ++) {
                System.out.print(board[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }

        /*
        X X X X 
        X X X X 
        X X X X 
        X O X X 
        */
    }

    public static int n, m;
    public static char[][] board;

    public static int[] dx = new int[]{-1, 0, 1, 0};
    public static int[] dy = new int[]{0, -1, 0, 1};


    public static void solve(char[][] _board) {
        n = _board.length;
        if(n == 0) return ;
        m = _board[0].length;

        board = new char[n][m];
        board = _board;
        for (int i = 0; i < n; i ++) {
            if (board[i][0] == 'O') dfs(i, 0);
            if (board[i][m - 1] == 'O') dfs(i, m - 1);
        }

        for (int i = 0; i < m; i ++) {
            if (board[0][i] == 'O') dfs(0, i);
            if (board[n - 1][i] == 'O') dfs(n - 1, i);
        }

        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++)
                if (board[i][j] == '#') board[i][j] = 'O';
                else board[i][j] = 'X';

        _board = board;
    }

    public static void dfs(int x, int y) {
        board[x][y] = '#';
        for (int i = 0; i < 4; i ++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && board[a][b] == 'O') dfs(a, b);
        }
    }

}

LC200. 岛屿数量

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        char[][] grid = {
            {'1', '1', '1', '1', '0'},
            {'1', '1', '0', '1', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '0', '0', '0'}
        }; // 1


     /*   
        char[][] grid = {
            {'1', '1', '0', '0', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '1', '0', '0'},
            {'0', '0', '0', '1', '1'}
        }; // 3
    */
        int res = numIslands(grid);
        System.out.println(res);
    }



    // 方法一：dfs遍历
    public static char[][] g;

    public static int[] dx = new int[]{-1, 0, 1, 0};
    public static int[] dy = new int[]{0, 1, 0, -1};

    public static int numIslands(char[][] grid) {
        int n = grid.length;
        if (n == 0) return 0;
        int m = grid[0].length;
        g = new char[n][m];
        g = grid;

        int cnt = 0;
        for (int i = 0; i < n; i ++) 
            for (int j = 0; j < m; j ++) 
                if (g[i][j] == '1') {
                    dfs(i, j);
                    cnt ++;
                }
        return cnt;
    }

    public static void dfs(int x, int y) {
        g[x][y] = 0;
        for (int i = 0; i < 4; i ++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < g.length && b >= 0 && b < g[a].length && g[a][b] == '1')
                dfs(a, b);
        }
    }

    /*
    // 方法二：bfs遍历

    public static boolean[][] st;
    public static int[] dx = new int[]{0, 0, -1, 1};
    public static int[] dy = new int[]{1, -1, 0, 0};


    public static int numIslands(char[][] grid) {
        int n = grid.length;
        if (n == 0) return 0;
        int m = grid[0].length;

        st = new boolean[n][m];
        int res = 0;
        for (int i = 0; i < n; i ++) 
            for (int j = 0; j < m; j ++) 
                if (!st[i][j] && grid[i][j] == '1') {
                    res ++;
                    bfs(i, j, grid);
                }
        return res;
    }

    public static void bfs(int x, int y, char[][] g) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x, y));
        st[x][y] = true;
        while (!q.isEmpty()) {
            Node t = q.poll();
            for (int i = 0; i < 4; i ++) {
                int a = t.first + dx[i], b = t.second + dy[i];
                if (a < 0 || a >= g.length ||
                    b < 0 || b >= g[a].length ||
                    g[a][b] == '0' || st[a][b]) continue;
                st[a][b] = true;
                q.add(new Node(a, b));
            }
        }

    }

    public static class Node {
        int first;
        int second;

        public Node(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    */
}

LC216. 组合总和 III

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int k = 3, n = 7;
        /*
        1 2 4 
        */
        int k = 3, n = 9;
        /*
        1 2 6 
        1 3 5 
        2 3 4 
        */

        List<List<Integer>> res = combinationSum3(k, n);

        for (List<Integer> r : res) {
            for (int i : r) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
        }

    }

    public static List<List<Integer>> ans = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();

    public static List<List<Integer>> combinationSum3(int k, int n) {
        dfs(1, k, n);
        return ans;
    }

    public static void dfs(int start, int k, int n) {
        if (n == 0)  
            if (k == 0) 
                ans.add(new ArrayList<>(path));

        for (int i = start; i <= 9; i ++)
            if (n >= i) {
                path.add(i);
                dfs(i + 1, k - 1, n - i);
                path.remove(path.size() - 1);
            }

    }


    /* div代码
    public static List<List<Integer>> ans = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();

    public static List<List<Integer>> combinationSum3(int k, int n) {
        dfs(0, k, 1, 0, n);
        return ans;
    }

    public static void dfs(int u, int k, int start, int s, int n) {
        if (u == k) {
            if (s == n) ans.add(new ArrayList(path));
            return ;
        }

        for (int i = start; i <= 9; i ++) {
            path.add(i);
            dfs(u + 1, k, i + 1, s + i, n);
            path.remove(path.size() - 1);
        }

    }
    */
}