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;
}
}
class Solution {
public:
int findCircleNum(vector<vector<int>> &M) {
int num_circle = 0;
vector<bool> visited(M.size(), false);
for (int i = 0; i < M.size(); i++) {
if (!visited[i]) {//对角线必为1，也就是说自己和自己一定是一个朋友圈，免去了二重循环
num_circle++;
dfs(M, i, visited);
}
}
return num_circle;
}
void dfs(vector<vector<int>> &M, int i, vector<bool> &visited) {
visited[i] = true;
for (int j = 0; j < M.size(); j++) {
if (M[i][j] == 1 && visited[j] == false) {
dfs(M, j, visited);
}
}
}
};
332. 重新安排行程
给定一个机票的字符串二维数组 [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