[Hard]鸡蛋掉落

887. 鸡蛋掉落

你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N  共有 N 层楼的建筑。

每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。

你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?

 

示例 1:

输入:K = 1, N = 2
输出:2
解释:
鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。
否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。
如果它没碎,那么我们肯定知道 F = 2 。
因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2:

输入:K = 2, N = 6
输出:3
示例 3:

输入:K = 3, N = 14
输出:4
 

提示:

1 <= K <= 100
1 <= N <= 10000
class Solution {
   public:
    //方法一:暴力动规(超时),比较好理解
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
        //初始化
        for (int i = 1; i <= K; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = j;
            }
        }
        for (int i = 2; i <= K;) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k < j; k++) {
                    /**
                     * 最坏情况下的最少扔鸡蛋次数
                     * 当前鸡蛋总数为i,楼层总数为j,在第k层楼扔鸡蛋时,鸡蛋碎了往楼下走(dp[i-
                     * 1][k - 1],鸡蛋没碎dp[i][j - k],在第k层扔得算1次
                     */
                    dp[i][j] =
                        min(dp[i][j], max(dp[i - 1][k - 1], dp[i][j - k]) + 1);
                }
            }
        }
        return dp[K][N];
    }

    //方法二:数学动规,重新定义dp
    int superEggDrop2(int K, int N) {
        /**
         * dp[k][m]:当前状态为 k 个鸡蛋,尝试扔 m 次鸡蛋,
         * 返回这个状态下最高的确认楼层数
         */
        vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
        int m = 0;
        while (dp[K][m] < N) {
            m++;
            for (int k = 1; k <= K; k++)
                /**
                 * 1. 鸡蛋没碎: dp[k][m - 1] 就是楼上的楼层数,因为鸡蛋个数 k
                 * 不变,扔鸡蛋次数 m 减一;
                 * 2. 鸡蛋碎了: dp[k - 1][m - 1]
                 * 就是楼下的楼层数,因为鸡蛋个数 k 减一,同时扔鸡蛋次数 m
                 * 减一;
                 * 3.是当前楼层数
                 *
                 */
                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
        }
        return m;
    }
}

 

0

打怪兽

小Q打算穿越怪兽谷,他不会打怪,但是他有钱。

他知道,只要给怪兽一定的金币,怪兽就会一直护送着他出谷。

在谷中,他会依次遇见N只怪兽,每只怪兽都有自己的武力值和要“贿赂”它所需的金币数。

如果小Q没有“贿赂”某只怪兽,而这只怪兽“武力值”又大于护送他的怪兽武力之和,这只怪兽就会攻击他。

小Q想知道,要想成功穿越怪兽谷而不被攻击,他最少要准备多少金币。

输入格式
第一行包含整数N,表示怪兽的数量。

第二行包含N个整数d1,d2,…,dn,表示每只怪兽的武力值。

第三行包含N个整数p1,p2,…,pn,表示收买N只怪兽所需的金币数。

输出格式
输出一个整数,表示所需最小金币数。

https://www.acwing.com/problem/content/description/605/
/**
 * dp[i][j] = max(dp[i-1][j],dp[i-1][j-coin[i]]+force[i]);
 * 其中dp[i][j]表示包含第i个怪兽的情况下,用j个金币所能获得的最大武力值
 * 初始条件:
 * dp[0][j]=0;//0个怪兽始终获得武力0
 * dp[i][0]=-1;//用0个金币贿赂怪兽不可行
 * dp[i][j]=-1;//表示用j个硬币贿赂前i个怪兽不可行。如上面的例子:dp[1][1]=8。dp[3][1]=-1,用1个金币贿赂3个怪兽显然不可行。
 * 答案:
 * 找到第一个不为-1的dp[n][j],这个j即为所求。
 */

int main() {
    int n;//n个怪兽
    cin >> n;
    int force[100];
    int coin[100];
    int dp[101][101];
    for (int i = 1; i <= n; i++)
        cin >> force[i];
    for (int i = 1; i <= n; i++)
        cin >> coin[i];
    memset(dp, -1, sizeof(dp));
    memset(dp[0], 0, sizeof(dp[0]));
//    fill(dp[0], dp[0] + sizeof(dp[0]) / dp[0][0], 0);//0个怪兽始终获得武力0
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= 100; ++j) {
            //只有满足 不用贿赂怪兽i时的最大武力值 > 怪兽i的武力值时,才可以不用贿赂怪兽i,即dp[i-1][j]
            if (dp[i - 1][j] >= force[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);//
            }
            //只有当前金币j大于贿赂怪兽i所需金币coin[i],并且剩余的金币j-coin[i]可以保证足够贿赂i之前的怪兽时才可以贿赂怪兽i,
            // 即dp[i-1][j-coin[i]];
            if (j >= coin[i] && dp[i - 1][j - coin[i]] != -1) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - coin[i]] + force[i]);
            }
        }
    }
    int res = 0;
    for (int j = 1; j <= 100; ++j) {
        if (dp[n][j] != -1) {
            res = j;
            break;
        }
    }
    cout << res << endl;
    return 0;
}

 

0

KMP和朴素匹配BF

  1. KMP和朴素匹配算法BF

class Solution {
public:
    int kmp(string ts, string ps) {
        int i = 0;
        int j = 0;
        vector<int> next(ps.size());
        get_next(ps, next);
        while (i < (int) ts.size() && j < (int) ps.size()) {//string::size()返回的是一个无符号的整数,当与负数比较会出错
            if (j == -1 || ts[i] == ps[j]) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }
        if (j == ps.size())
            return i - j;
        else
            return -1;
    }

    void get_next(string ps, vector<int> &next) {
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < (int) ps.size() - 1) {
            if (k == -1 || ps[j] == ps[k]) {
                next[++j] = ++k;
            } else
                k = next[k];
        }
    }

    int bf(string ts, string ps) {//朴素搜索
        int i = 0;
        int j = 0;
        while (i < (int) ts.size() && j < (int) ps.size()) {
            if (ts[i] == ps[j]) {
                i++;
                j++;
            } else {
                i = i - j + 1;//回溯
                j = 0;
            }
        }
        if (j == (int) ps.size())
            return i - j;
        else
            return -1;
    }
};

2.KMP原理

寻找最长前缀后缀

假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置

  • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;
  • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j – next [j] 位。
    • 换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 – 失配字符对应的next 值,即移动的实际位数为:j – next[j],且此值大于等于1。

字符串查找之KMP

0

C++ size()

vector, string,等的size()返回的都是无符号的整数,跟负数比较会出问题,比如

vector<int> a{1, 4, 3};
int i = -1;
while (i < a.size()) {
    cout << "great" << endl;//并不会输出
    break;
}

#必须改成
while (i < (int)a.size()) {

 

0

DFS

130. 被围绕的区域

给定一个二维的矩阵,包含 'X' 和 'O'(字母 O)。

找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后,矩阵变为:

X X X X
X X X X
X X X X
X O X X
解释:

被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
public class Onehundred_thirty {
    /**
     * dfs
     * 依次将与边界上O相邻的O全部标记为M,表示他们不会被包围;剩下的O一定是被包围的,所以最终将M节点标记为O,O节点标记为X
     */
    private int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0)
            return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1 && board[i][j] == 'O')
                    dfs(i, j, board);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == 'M') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(int i, int j, char[][] board) {
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O')
            return;
        board[i][j] = 'M';
        for (int[] direction : directions) {
            dfs(i + direction[0], j + direction[1], board);
        }
    }
}
class Solution {
private:
    const vector<pair<int, int>> directions{{0,  1},
                                            {0,  -1},
                                            {1,  0},
                                            {-1, 0}};
public:
    void solve(vector<vector<char>> &board) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1 && board[i][j] == 'O')
                    dfs(board, i, j);
            }
        }
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                if (board[i][j] == 'M')
                    board[i][j] = 'O';
            }
        }
    }

    void dfs(vector<vector<char>> &board, int i, int j) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O')
            return;
        board[i][j] = 'M';
        for (auto direction:directions) {
            dfs(board, i + direction.first, j + direction.second);
        }
    }
};

200. 岛屿数量

给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3
package gongel_first;

public class Twohundred {
    /**
     * DFS
     * 极其类似130题
     */
    public void dfs(char[][] grid, int row, int col, int m, int n) {
        if (row >= m || row < 0 || col >= n || col < 0 || grid[row][col] != '1')//一定要加grid[row][col] == '0',避免重复走
            return;
        grid[row][col] = '0';
        dfs(grid, row - 1, col, m, n);//上
        dfs(grid, row + 1, col, m, n);//下
        dfs(grid, row, col - 1, m, n);//左
        dfs(grid, row, col + 1, m, n);//右
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int m = grid.length;
        int n = grid[0].length;
        int numIsland = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {//没有被访问过
                    dfs(grid, i, j, m, n);
                    numIsland++;
                }
            }
        }
        return numIsland;
    }
}
class Solution {
private:
    const vector<pair<int, int>> directions{{0,  1},
                                            {0,  -1},
                                            {1,  0},
                                            {-1, 0}};
public:
    int numIslands(vector<vector<char>> &grid) {
        int num_island = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    num_island++;
                    dfs(grid, i, j);
                }
            }
        }
        return num_island;
    }

    void dfs(vector<vector<char>> &grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != '1')
            return;
        grid[i][j] = '0';
        for (auto direction:directions) {
            dfs(grid, i + direction.first, j + direction.second);
        }
    }
};

695. 岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为0。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11,因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。
public class Sixhundred_ninetyFive {
    /**
     * 和200题几乎完全一样,只是该题需要返回值而已
     */
    private int[][] directions = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1)
                    maxArea = Math.max(maxArea, dfs(grid, i, j));
            }
        }
        return maxArea;
    }

    public int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0)
            return 0;
        int area = 1;
        grid[i][j] = 0;//不用回溯,下次从别的地方也不用再次访问
        for (int[] direction : directions) {
            area += dfs(grid, i + direction[0], j + direction[1]);
        }
        return area;
    }
}
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        if (grid.empty() || grid[0].empty())
            return 0;
        int max_area = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    int temp = 0;
                    dfs(grid, i, j, temp);
                    if (max_area < temp)
                        max_area = temp;
                }
            }
        }
        return max_area;
    }

    void dfs(vector<vector<int>> &grid, int i, int j, int &temp) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1)
            return;
        temp += 1;//temp也不能回溯,因为主程序是全部遍历
        grid[i][j] = 2;//避免再次访问;不能回溯
        dfs(grid, i + 1, j, temp);
        dfs(grid, i - 1, j, temp);
        dfs(grid, i, j + 1, temp);
        dfs(grid, i, j - 1, temp);
    }
};

547. 朋友圈

班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。

给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明:已知学生0和学生1互为朋友,他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:

输入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出: 1
说明:已知学生0和学生1互为朋友,学生1和学生2互为朋友,所以学生0和学生2也是朋友,所以他们三个在一个朋友圈,返回1。
注意:

N 在[1,200]的范围内。
对于所有学生,有M[i][i] = 1。
如果有M[i][j] = 1,则有M[j][i] = 1。
package gongel_first;

public class Fivehundred_fortySeven {
    /**
     * 法一:DFS
     * 求连通图的数量,可以画邻接表
     * 与 200 岛屿问题 有不同的地方,连通图问题和上色问题的区别
     * 本题:[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->1
     * 200题:[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->4
     */
    public void dfs(int[][] M, int i, boolean[] visited) {
        visited[i] = true;
        for (int j = 0; j < M.length; j++) {
            if (!visited[j] && M[i][j] == 1) {
                dfs(M, j, visited);
            }
        }
    }

    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0)
            return 0;
        int m = M.length;
        int circleNums = 0;
        boolean[] visited = new boolean[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i]) {
                    circleNums += 1;
                    dfs(M, i, visited);
                }
            }
        }
        return circleNums;
    }

    /**
     * 法二:并查集:https://gongel.cn/?p=312
     */
    private int findFather(int[] father, int son) {
        while (son != father[son]) {//初始化时自己为自己的父亲,如果现在自己不是自己的父亲, 说明自己找到了真正的父亲,那需要一直循环找到祖先
            son = father[son];
        }
        return son;
    }

    public int findCircleNum2(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0)
            return 0;
        int[] father = new int[200];
        int numFriends = 0;
        //初始化
        for (int i = 0; i < M.length; i++)
            father[i] = i;
        for (int i = 0; i < M.length; i++) {
            for (int j = i + 1; j < M.length; j++) {//只需要考虑上三角矩阵,因为这是无向图----对称矩阵
                if (M[i][j] == 1) {
                    int fatherI = findFather(father, i);
                    int fatherJ = findFather(father, j);
                    if (fatherI != fatherJ)
                        father[fatherI] = fatherJ;
                }
            }
        }
        for (int i = 0; i < M.length; i++) {
            if (father[i] == i)
                numFriends++;
        }
        return numFriends;
    }
}
给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 出发。

说明:

如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前
所有的机场都用三个大写字母表示(机场代码)。
假定所有机票至少存在一种合理的行程。
示例 1:

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2:

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
/**
     * 用DFS回溯需要考虑一堆问题:
     * 1.目的地需要排序
     * 2.使用过的行程不能再使用
     */
    private List<String> ans;
    private Map<String, PriorityQueue<String>> map = new HashMap<>();//保存相同出发地的所有目的地(按字母序)

    public List<String> findItinerary(List<List<String>> tickets) {
        ans = new ArrayList<>();
        if (tickets == null || tickets.size() == 0)
            return ans;
        for (List<String> ticket : tickets) {
            String src = ticket.get(0);
            String dst = ticket.get(1);
            if (!map.containsKey(src)) {
                PriorityQueue<String> pq = new PriorityQueue<>();
                map.put(src, pq);
            }
            map.get(src).add(dst);
        }
        dfs("JFK");
        Collections.reverse(ans);
        return ans;

    }

    private void dfs(String src) {
        PriorityQueue<String> pq = map.get(src);
        if (pq != null) {
            while (!pq.isEmpty()) {
                dfs(pq.poll());
            }
        }
        ans.add(src);
    }
class Solution {
public:
    //欧拉路径(https://www.cnblogs.com/vocaloid01/p/9514023.html)
    vector<string> findItinerary(vector<vector<string>> &tickets) {
        unordered_map<string, multiset<string>> from_to;//multiset相当于小根堆
        for (auto ticket:tickets)
            from_to[ticket[0]].insert(ticket[1]);
        vector<string> ans;
        dfs("JFK", from_to, ans);
        return vector<string>(ans.rbegin(), ans.rend());

    }

    void dfs(string from, unordered_map<string, multiset<string>> &from_to, vector<string> &ans) {
        while (from_to[from].size() != 0) {
            string next = *from_to[from].begin();
            from_to[from].erase(from_to[from].begin());//可能存在相同的地点,所以只能erase迭代器
            dfs(next, from_to, ans);
        }
        ans.push_back(from);//一定倒着存,将孤立节点放在最后访问。题目保证一定会有路径
    }
};

79. 单词搜索

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
public boolean exist2(char[][] board, String word) {
//和695、200差不多
        boolean result;
        boolean[][] visited=new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    result = dfs2(board, word, i, j, 0,visited);
                    if (result) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private static boolean dfs2(char[][] board, String word, int i, int j, int index,boolean[][] visited) {
        if (index == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length|| visited[i][j]) {
            return false;
        }
        if (board[i][j] != word.charAt(index)) {
            return false;
        }

        boolean result;
        visited[i][j]=true;//标记已经访问:不会回溯
        result = dfs2(board, word, i - 1, j, index + 1,visited)
                || dfs2(board, word, i + 1, j, index + 1,visited)
                || dfs2(board, word, i, j - 1, index + 1,visited)
                || dfs2(board, word, i, j + 1, index + 1,visited);
        visited[i][j]=false;//恢复未访问
        return result;
    }
class Solution {
public:
    bool exist(vector<vector<char>> &board, string word) {
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == word[0])
                    if (dfs(board, word.substr(0), i, j, visited))
                        return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>> &board, string word, int i, int j, vector<vector<bool>> &visited) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || word[0] != board[i][j] || visited[i][j])
            return false;
        if (word.size() == 1 && word[0] == board[i][j])
            return true;
        visited[i][j] = true;
        bool result = dfs(board, word.substr(1), i - 1, j, visited) || dfs(board, word.substr(1), i + 1, j, visited) ||
                      dfs(board, word.substr(1), i, j + 1, visited) || dfs(board, word.substr(1), i, j - 1, visited);
        visited[i][j] = false;
        return result;
    }
};

417. 太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动,且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”,又能流动到“大西洋”的陆地单元的坐标。

 

提示:

输出坐标的顺序不重要
m 和 n 都小于150
 

示例:

 

给定下面的 5x5 矩阵:

  太平洋 ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * 大西洋

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
public class Fourhundred_seventeen {
    /**
     *  反向思维---DFS
     *  依题意,最左边和最上面可以流向太平洋,最右边和最下面可以流向大西洋
     *  那么,可以从最左边和最上面开始dfs所有可以到达的山脉,即为可以流向太平洋的山脉
     *  从最右边和最下面开始dfs所有可以到达的山脉,即为可以流向大西洋的山脉
     *  注意:此时dfs的方向为从高度低的山脉向高度高的山脉走
     *  参考:https://leetcode-cn.com/problems/pacific-atlantic-water-flow/comments/36773
     */
    public List<List<Integer>> pacificAtlantic2(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return ans;
        m = matrix.length;
        n = matrix[0].length;
        boolean[][] reachPacific = new boolean[m][n];
        boolean[][] reachAtlantic = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(matrix, i, 0, reachPacific);//从最左出发判断是否可到达Pacific
            dfs(matrix, i, n - 1, reachAtlantic);//从最右出发判断是否可达到Atlantic
        }
        for (int j = 0; j < n; j++) {
            dfs(matrix, 0, j, reachPacific);//从最上出发判断是否可到到Pacific
            dfs(matrix, m - 1, j, reachAtlantic);//从最下出发判断是否可到达Atlantic
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (reachPacific[i][j] && reachAtlantic[i][j]) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    ans.add(temp);
                }
            }
        }
        return ans;
    }

    private void dfs(int[][] matrix, int startX, int startY, boolean[][] reach) {
        if (startX < 0 || startX > m || startY < 0 || startY > n || reach[startX][startY])
            return;
        reach[startX][startY] = true;
        for (int i = 0; i < 4; i++) {
            int newstartX = startX + direction[i][0];
            int newstartY = startY + direction[i][1];
            if (isValid(newstartX, newstartY) && matrix[newstartX][newstartY] >= matrix[startX][startY])
                dfs(matrix, newstartX, newstartY, reach);
        }
    }

}
class Solution {
private:
    const vector<pair<int, int>> directions{{0,  1},
                                            {0,  -1},
                                            {1,  0},
                                            {-1, 0}};
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>> &matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0)
            return vector<vector<int>>{};
        vector<vector<bool>> reach_pacific(matrix.size(), vector<bool>(matrix[0].size(), false));
        vector<vector<bool>> reach_atlantic(matrix.size(), vector<bool>(matrix[0].size(), false));
        for (int i = 0; i < matrix.size(); i++) {
            dfs(matrix, i, 0, reach_pacific);
            dfs(matrix, i, matrix[0].size() - 1, reach_atlantic);
        }
        for (int j = 0; j < matrix[0].size(); j++) {
            dfs(matrix, 0, j, reach_pacific);
            dfs(matrix, matrix.size() - 1, j, reach_atlantic);
        }
        vector<vector<int>> ans;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (reach_atlantic[i][j] && reach_pacific[i][j]) {
                    ans.push_back({i, j});
                }
            }
        }
        return ans;
    }

    void dfs(vector<vector<int>> &matrix, int x, int y, vector<vector<bool>> &reach) {
        if (x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size() || reach[x][y])
            return;
        reach[x][y] = true;
        for (auto direction:directions) {
            int new_x = x + direction.first;
            int new_y = y + direction.second;
            if (new_x >= 0 && new_x < matrix.size() && new_y >= 0 && new_y < matrix[0].size()) {
                if (matrix[new_x][new_y] >= matrix[x][y])
                    dfs(matrix, new_x, new_y, reach);
            }
        }
    }
};

133. 克隆图

给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 val(Int) 和其邻居的列表(list[Node])。

示例:



输入:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释:
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。
 

提示:

节点数介于 1 到 100 之间。
无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
必须将给定节点的拷贝作为对克隆图的引用返回。
package main.gongel_first;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
    }

    public Node(int _val, List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Onehundred_thirtyThree {
    /**
     * 深拷贝就是对于所有的指针成员,不能仅仅是赋值,还有重新分配空间
     */
    private Map<Node, Node> map;

    public Node cloneGraph(Node node) {
        map = new HashMap<>();
        return dfs(node);
    }

    public Node dfs(Node node) {
        if (!map.containsKey(node)) {//防止成环
            Node copy = new Node(node.val, new ArrayList<Node>());
            map.put(node, copy);
            for (Node neibor : node.neighbors) {
                copy.neighbors.add(dfs(neibor));
            }
        }
        return map.get(node);
    }
}
class Node {
public:
    int val;
    vector<Node *> neighbors;

    Node() {
        val = 0;
        neighbors = vector<Node *>();
    }

    Node(int _val) {
        val = _val;
        neighbors = vector<Node *>();
    }

    Node(int _val, vector<Node *> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

class Solution {
//和138. 复制带随机指针的链表 相似
private:
    unordered_map<Node *, Node *> map;//存着节点和他自己的拷贝
public:
    Node *cloneGraph(Node *node) {
        if (node == nullptr)
            return nullptr;
        return dfs(node);
    }

    Node *dfs(Node *node) {
        if (map.count(node) == 0) {
            Node *copy = new Node(node->val, vector<Node *>());
            map[node] = copy;
            for (Node *neighbor:node->neighbors) {
                copy->neighbors.push_back(dfs(neighbor));
            }
        }
        return map[node];
    }
};

473. 火柴拼正方形

还记得童话《卖火柴的小女孩》吗?现在,你知道小女孩有多少根火柴,请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴,可以把火柴连接起来,并且每根火柴都要用到。

输入为小女孩拥有火柴的数目,每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形,每边两根火柴。
示例 2:

输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。
注意:

给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。
package gongel_first;

public class Fourhundred_seventyThree {
    /**
     * DFS自己去寻找最优解
     * 和494题相同
     */
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length == 0)
            return false;
        int sum = 0;
        for (int num : nums)
            sum += num;
        if (sum / 4 * 4 != sum)
            return false;
        //每个边的长度初始化为0
        return dfs(0, nums, 0, 0, 0, 0, sum / 4);
    }

    private boolean dfs(int i, int[] nums, int up, int down, int left, int right, int len) {
        if (i == nums.length)
            return up == len && down == len && left == len && right == len;
        if (up > len || down > len || left > len || right > len)
            return false;
        //对每个边进行加和,一旦满足则返回
        return dfs(i + 1, nums, up + nums[i], down, left, right, len) || dfs(i + 1, nums, up, down + nums[i], left, right, len) || dfs(i + 1, nums, up, down, left + nums[i], right, len) || dfs(i + 1, nums, up, down, left, right + nums[i], len);
    }
}
class Solution {
public:
    bool makesquare(vector<int> &nums) {
        if (nums.empty())
            return false;
        //剪枝: 大的先放,减少比较次数
        sort(nums.rbegin(), nums.rend());
        int sum = 0;
        for (auto num:nums)
            sum += num;
        if (sum % 4 != 0)
            return false;
        int len = sum / 4;
        return helper(nums, 0, 0, 0, 0, 0, len);

    }

    bool helper(vector<int> &nums, int index, int left, int right, int up, int down, int len) {
        if (index > nums.size() || left > len || right > len || up > len || down > len)
            return false;
        if (index == nums.size()) {
            if (left == len && right == len && up == len && down == len)
                return true;
            else
                return false;
        }
        //剪枝: 提前判断长度
        return (left + nums[index] <= len && helper(nums, index + 1, left + nums[index], right, up, down, len)) ||
               (right + nums[index] <= len && helper(nums, index + 1, left, right + nums[index], up, down, len)) ||
               (up + nums[index] <= len && helper(nums, index + 1, left, right, up + nums[index], down, len)) ||
               (down + nums[index] <= len && helper(nums, index + 1, left, right, up, down + nums[index], len));
    }
};

 

494. 目标和

给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。
注意:

数组的长度不会超过20,并且数组中的值全为正数。
初始的数组的和不会超过1000。
保证返回的最终结果为32位整数。
package gongel_first;

public class Fourhundred_ninetyFour {
    public int findTargetSumWays(int[] nums, int S) {
        /**
         * 法一:dp
         sum(P) 前面符号为加号的集合;sum(N) 前面符号为减号的集合
         * 所以题目可以转化为
         * sum(P) - sum(N) = target
         * => sum(nums) + sum(P) - sum(N) = target + sum(nums)
         * => 2 * sum(P) = target + sum(nums)
         * => sum(P) = (target + sum(nums)) / 2
         * 因此题目转化为01背包,也就是能组合成容量为sum(P)的方式有多少种*/
        if (nums == null || nums.length == 0)
            return 0;
        int sum = 0;
        for (int num : nums)
            sum += num;
        if (sum < S || (((S) + sum) & 1) == 1)//target + sum(nums)必须为偶数
            return 0;
        int w = (S + sum) / 2;
        int[] dp = new int[w + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = w; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[w];
    }

    /**
     * 法二:DFS,和473题相同
     */
    public int findTargetSumWays2(int[] nums, int S) {
        if (nums == null || nums.length == 0)
            return 0;
        return dfs(nums, 0, 0, S);
    }

    private int dfs(int[] nums, int index, int sum, int target) {
        if (index == nums.length)
            return target == sum ? 1 : 0;//找到则最终结果加1
        return dfs(nums, index + 1, sum + nums[index], target) + dfs(nums, index + 1, sum - nums[index], target);
    }
}
class Solution {
public:
    int findTargetSumWays(vector<int> &nums, int S) {
        if (nums.empty())
            return 0;
        return dfs(nums, 0, 0, S);
    }

    int dfs(vector<int> &nums, int index, int sum, int target) {
        if (index == nums.size())
            return sum == target ? 1 : 0;
        return dfs(nums, index + 1, sum + nums[index], target) + dfs(nums, index + 1, sum - nums[index], target);
    }
};
0