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