重生做皇帝小说网站,个人门户网站,wordpress sql 导入,个人网站设计作业4.图 4.1.被围绕的区域
思路#xff1a;图中只有与边界上联通的O才不算是被X包围。因此本题就是从边界上的O开始递归#xff0c;找与边界O联通的O#xff0c;并标记为##xff08;代表已遍历#xff09;#xff0c;最后图中剩下的O就是#xff1a;被X包围的O。图中所有… 4.图 4.1.被围绕的区域
思路图中只有与边界上联通的O才不算是被X包围。因此本题就是从边界上的O开始递归找与边界O联通的O并标记为#代表已遍历最后图中剩下的O就是被X包围的O。图中所有 # 则是与边界O联通的情况 class Solution {public void solve(char[][] board) {for (int i 0; i board.length; i) {for (int j 0; j board[0].length; j) {if (i 0 || j 0 || i board.length - 1 || j board[0].length - 1) {//如果当前点在边界if (board[i][j] O) {//当前点在边界且当前点为Odfs(board, i, j);}}}}for (int i 0; i board.length; i) {for (int j 0; j board[0].length; j) {if (board[i][j] O) {//说明当前点是不与边界O联通的O说明当前O被X包围board[i][j] X;//赋值为X}if (board[i][j] #) {//说明当前位置是O但是是与边界O联通的Oboard[i][j] O;//说明当前点不被X包围重置为O}}}}//该方法用于找到所有与边界O联通的Opublic void dfs(char[][] board, int i, int j) {if (i 0 || i board.length - 1 || j 0 || j board[0].length - 1//如果当前点越界||board[i][j] X || board[i][j] # //或者当前点不为O ) return;//直接返回board[i][j] #;//能到这一步说明当前点是与边界O联通的O标记为已遍历防止死循环//找与当前位置相邻的、与边界O联通的Odfs(board, i 1, j);dfs(board, i - 1, j);dfs(board, i, j 1);dfs(board, i, j - 1);}
} 5.贪心 5.1项目利润问题
贪心的题目思路不太好写最主要就是贪心的一种感觉。如果要严格的数学证明太麻烦了
本题思路本题就是一个局部最优解到全局最优解的题。每次都在已经解锁 (当前手上有的钱大于某个项目的花费该项目就算是被解锁)了的项目中选一个利润最大的项目。这样最后得到的就是最大的最终资本。要注意的是每次做完一次项目手头上的钱就变为之前的钱本次项目的利润。因此每次做项目之前都要更新一下被解锁的项目 代码实现
class Solution {public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {int[][] arr new int[profits.length][2];//数组第一个元素为当前项目的最小资金第二个元素为利润for (int i 0; i profits.length; i) {arr[i][0] capital[i];arr[i][1] profits[i];}//用于存放每个项目花费的小根堆PriorityQueueint[] capitalQ new PriorityQueue(new Comparatorint[]() {Overridepublic int compare(int[] arr1, int[] arr2) {return arr1[0] - arr2[0];}});//存放已经解锁的每个项目的利润的大根堆每次都要已经解锁了切利润最大的项目PriorityQueueint[] profitsQ new PriorityQueue(new Comparatorint[]() {Overridepublic int compare(int[] arr1, int[] arr2) {return arr2[1] - arr1[1];}});//全部项目都进入被锁的队列中for (int i 0; i arr.length; i) {capitalQ.add(arr[i]);}for (int i 0; i k; i) {//进行k轮//如果资金w大于当前项目的花费且花费队列不为空该项目被解锁//这个while循环执行完以后就会把当前所有能解锁的项目(当前手上的钱w 项目花费 视为解锁)全部放入利润大根堆。while (!capitalQ.isEmpty() capitalQ.peek()[0] w) {profitsQ.add(capitalQ.poll());//该项目被解锁放入利润大根堆}if (profitsQ.isEmpty()) {//当我手上的钱不足以做接下来任何一个项目时就会出现利润大根堆提前为空的情况return w;//提前返回现在所有的钱}//每次都从利润大根堆找出利润最高的项目w profitsQ.poll()[1];}return w;}
} 6.递归回溯 6.1N皇后问题 class Solution {public int totalNQueens(int n) {if (n 1) return 0;//代表第i行的皇后放在了第record[i]列int[] record new int[n];return process(0, record, n);}/*** param i 目前来到了第i行* param record 之前已经摆好皇后的位置(潜台词前面的皇后位置都不冲突)* param n 整体一共有多少行*/public int process(int i, int[] record, int n) {if (i n) {//递归结束,前n个皇后都已经摆放好了位置return 1;//前n个皇后都已经摆好了位置代表找到了一种摆法}int res 0;for (int j 0; j n; j) {//当前在第i行遍历第i行的所有列判断是否合法摆放。j代表列// 判断当前位置是否可以摆放皇后if (isValid(record, i, j)) {record[i] j;//当前位置可以摆放皇后//递归摆放接下来皇后的位置//当前行尝试的所有位置做累加就是当前情况(在record已经摆好的情况下接下来所有合法情况的总数)res process(i 1, record, n);}}return res;}/*** 判断第i行的第i列是否可以摆放皇后(是否和之前的皇后位置冲突)** param record 之前已经摆放好皇后的位置* param i 第i行* param j 第i列* return true可以摆放到当前位置不冲突。false位置冲突*/private boolean isValid(int[] record, int i, int j) {for (int k 0; k i; k) {//只有前k行皇后位置被摆放好需要比较。遍历之前每个皇后的位置if (j record[k]//如果和之前某个皇后同一列|| //或者Math.abs(record[k] - j) Math.abs(i - k)//当前位置和之前某一个皇后位置在同一列(横坐标之差绝对值纵坐标之差绝对值)) {return false;}}return true;}
} 6.2经典汉诺塔问题 这类问题只要把握住局部情况每次的局部情况符合要求整体情况就不会出错。
比如说当前A中有i个盘
1.先把上面i-1个盘从A经过C移动到B。把第i个盘空出来因为大盘不能叠在小盘上。
2.现在第i个盘空出来了可以直接从A移动到C。
3.最后把上面i-1个盘从B经过A移动到C。
这样当A中有i个盘的情况就完成了。 如果我每次移动都遵守这个规律每次要移动大盘的时候就把上面的小盘全部移都把大盘空出来这次移动就保证了大盘一定不会叠着小盘且大盘在小盘下。整体情况就一定也会满足这个要求。 这类递归题目不好理解。对于尝试的时候我们没必要想着全局情况是怎么样变化的。而是应该定义一个统一的标准每次局部都满足这个情况。整体一定也满足 总的来说我们不应该想着全局如何变化。应该想在当前局部情况我们应该怎么样拆解问题只要局部拆解问题对了决策对了。整体也就对了。 还有一点要注意的就是我们拆解问题拆到最后一定有一个拆不了的情况。比如说本题就是当A中只有一个盘的情况就可以直接移动了。这就是递归的终止条件 public void hanota(ListInteger A, ListInteger B, ListInteger C) {func(A.size(), A, B, C);}/*** 当前A中有1~i个圆盘把最下面一个圆盘从A经过B移动到C** param i 圆盘数量* param A 移动起始位置* param B 经过位置* param C 目标位置*/public void func(int i, ListInteger A, ListInteger B, ListInteger C) {if (i 1) {//当A中只有一个元素了一定是最小的直接从A移动到CC.add(A.remove(1));}//先把A上面i - 1个圆盘从A经过C移动到B。func(A.size() - 1, A, C, B);//再把第i个圆盘从A移动到C,因为此时i-1个圆盘全部在B可以直接移动C.add(A.remove(i));//再把i - 1个圆盘从B移动回Afunc(A.size() - 1, B, C, A);} 6.3.岛屿数量
本题借鉴了leetcode大佬的思路讲的非常清晰
. - 力扣LeetCode class Solution {public int numIslands(char[][] grid) {int res 0;for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length; j) {if (grid[i][j] 1) {//如果当前位置是一个岛屿dfs(grid, i, j);res;}}}return res;}public void dfs(char[][] grid, int r, int c) {//当前元素在第r行第c列if (!inArea(grid, r, c)) return;//如果当前位置越界了直接返回if (grid[r][c] ! 1) return;//如果当前位置不是岛屿直接返回//能走到这说明当前位置没遍历过且是岛屿grid[r][c] 2;//当前位置标记为已遍历// 访问上、下、左、右四个相邻结点dfs(grid, r - 1, c);dfs(grid, r 1, c);dfs(grid, r, c - 1);dfs(grid, r, c 1);}public boolean inArea(char[][] grid, int r, int c) {//判断当前位置是否越界,true 代表没越界return r 0 r grid.length c 0 c grid[0].length;}
}
6.4.岛屿最大面积
本题大致思路和上一题差不多。 class Solution {public int maxAreaOfIsland(int[][] grid) {int max 0;for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length; j) {max Math.max(max, dfs(grid, i, j));}}return max;}public int dfs(int[][] grid, int r, int c) {if (!inArea(grid, r, c)) return 0;if (grid[r][c] ! 1) return 0;grid[r][c] 2; // 标记为已遍历return 1 dfs(grid, r, c - 1) //当前岛屿的面积等于当前位置就是一个岛屿面积为1 上下左右方岛屿面积之和dfs(grid, r, c 1) dfs(grid, r - 1, c) dfs(grid, r 1, c);}public boolean inArea(int[][] grid, int r, int c) {return r 0 r grid.length c 0 c grid[0].length;}
}
6.5.岛屿周长
本题思路与上面类似就是注意base case的判断 class Solution {public int islandPerimeter(int[][] grid) {int max 0;for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length; j) {if (grid[i][j] 1) return dfs(grid, i, j);}}return 0;}public int dfs(int[][] grid, int r, int c) {// 函数因为「坐标 (r, c) 超出网格范围」返回对应一条越界的边if (!inArea(grid, r, c)) {return 1;}// 函数因为「当前格子是海洋格子」返回对应一条与海洋相邻的边if (grid[r][c] 0) {return 1;}// 函数因为「当前格子是已遍历的陆地格子」返回和周长没关系if (grid[r][c] ! 1) {return 0;}grid[r][c] 2;return dfs(grid, r, c - 1) //当前岛屿的周长等于上下左右方岛屿面积之和dfs(grid, r, c 1) dfs(grid, r - 1, c) dfs(grid, r 1, c);}public boolean inArea(int[][] grid, int r, int c) {return r 0 r grid.length c 0 c grid[0].length;}
} 6.6.预测赢家(博弈) public boolean predictTheWinner(int[] nums) {// 返回我先手能获取的最大值和后手获取的最大值return a(nums, 0, nums.length - 1) b(nums, 0, nums.length - 1);}//来到当前位置还剩第l个元素到第r个元素没有选我先选public int a(int[] arr, int l, int r) {if (l r) {//如果只剩一个元素了还是我先选return arr[l];}return Math.max(arr[l] b(arr, l 1, r),//选了第l个元素那么接下来我就是后手了arr[r] b(arr, l, r - 1)//选了第r个元素接下来我也是后手 且选择元素范围也改变了);}//来到当前位置还剩第l个元素到第r个元素没有选我后手//注意当前不是我拿是对方先手在l到r范围上拿public int b(int[] arr, int l, int r) {if (l r) {//当前最后只有最后一个元素我还是后手肯定就被对手选了return 0;//返回0没有元素选了}//注意这里可能不好理解为什么是min//这两种情况是对手做完我是后手情况被迫接受的!所以就是最差情况min//因为这是二人博弈对手先手选的是最大的值轮到后手的我选的只会是最小的值。//对手选的分多我的分就少了。下回合轮到我先手也是同理对手分就少了return Math.min(//注意当前是我在等待对方先手在l到r范围上拿我没得拿a(arr, l 1, r),a(arr, l, r - 1));} 7.动态规划 7.1.买卖股票的最佳时期1
思路动态规划问题最重要的就是找到问题的状态。把问题状态不重不漏的划分出来。对于本题每日的股票持有最大价值可以分为两种情况。
1.第i天我手上有股票的最大价值两种情况1.和我昨天有股票的情况一样。2.昨天没有股票买当天的股票。
2.第i天我手上没有股票的最大价值两种情况1.和我昨天没有股票的情况一样。2.昨天有股票当天卖了股票。 要注意的是这里只能买一次股票。注意和下一题比较区分。
class Solution {public int maxProfit(int[] prices) {//dp[i][0]:代表第i天有股票之前就有股票/当天买入的最大利润//dp[i][1]:代表第i天没有股票之前没有/当天卖了的最大利润int[][] dp new int[prices.length][2];dp[0][0] -prices[0];dp[0][1] 0;for(int i 1; i prices.length; i){//dp[i][0]:代表第i天有股票之前就有股票/当天买入的最大利润 前一天的股票价值/前天没有当天买入的最大值dp[i][0] Math.max(dp[i-1][0],-prices[i]);dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]prices[i]);}return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);}
}
7.2.买卖股票的最佳时期2
大致思路和上一题差不多但要区分这里可以进行多次股票买卖。 注意这里的dp[i-1][1]-prices[i] 就包含了多次买卖股票的情况。
class Solution {public int maxProfit(int[] prices) {//dp[i][0]:代表第i天有股票之前就有股票/当天买入的最大利润//dp[i][1]:代表第i天没有股票之前没有/当天卖了的最大利润int[][] dp new int[prices.length][2];dp[0][0] -prices[0];dp[0][1] 0;for(int i 1; i prices.length; i){//dp[i][0]:代表第i天有股票之前就有股票/当天买入的最大利润 前一天的股票价值/前天没有当天买入的最大值dp[i][0] Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]prices[i]);}return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);}
}
7.3.买卖股票的最佳时期3 class Solution {public int maxProfit(int[] prices) {// dp[i][0]: 第一次有股票 Math.max(前天就有买今天的) 注意买第i天股票就是 -prices[i]// dp[i][1]: 第一次卖完股票不持有股票 Math.max(前天没有今天还有当天卖) // dp[i][2]: 第二次有股票 Math.max(前天就有在第一次买卖完没有股票的基础上买入今天股票)// dp[i][3]: 第二次卖完股票不持有 Math.max(前天就没有今天是第二次有股票当天卖)int[][] dp new int[prices.length][4];dp[0][0] -prices[0];dp[0][1] 0;dp[0][2] -prices[0];dp[0][3] 0;for (int i 1; i prices.length; i) {dp[i][0] Math.max(dp[i - 1][0], -prices[i]);dp[i][1] Math.max(dp[i - 1][1], dp[i][0] prices[i]);dp[i][2] Math.max(dp[i - 1][2], dp[i][1] - prices[i]);dp[i][3] Math.max(dp[i - 1][3], dp[i][2] prices[i]);}return dp[prices.length - 1][3];}
}
7.4.买卖股票的最佳时期4
7.5.买卖股票的最佳时期(含手续费)
7.6.买卖股票的最佳时期(含冷冻期) 7.7.打家劫舍 class Solution {public int rob(int[] nums) {if(nums.length 1) return nums[0];if(nums.length 3) return Math.max(nums[0],nums[1]);int[][] dp new int[nums.length 1][2];dp[1][0] nums[0];dp[1][1] 0;dp[2][0] nums[1];dp[2][1] nums[0];for(int i 3; i nums.length; i){//抢第i家能获取的最大金额dp[i][0] Math.max(dp[i - 2][0],dp[i -1][1]) nums[i -1];//不抢第i家dp[i][1] Math.max(dp[i - 1][0],dp[i - 1][1]);}return Math.max(dp[nums.length][0],dp[nums.length][1]);}
} 7.7.打家劫舍III (树形dp) /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int rob(TreeNode root) {int[] process process(root);return Math.max(process[0],process[1]);}//返回数组有两个元素第一个元素代表偷当前节点的最大值第二个元素为不偷当前节点的最大值public int[] process(TreeNode root) {if (root null) return new int[]{0, 0};if (root.left null root.right null) return new int[]{root.val, 0};int[] left process(root.left);int[] right process(root.right);//偷当前节点最大值 当前节点的值 不偷左右孩子int max1 root.val left[1] right[1];//不偷当前节点 偷/不偷左孩子价值更大的一个 偷/不偷右孩子价值更大的一个 int max2 Math.max(left[1], left[0]) Math.max(right[0], right[1]);return new int[]{max1, max2};}
} 7.8.单词拆分 class Solution {public boolean wordBreak(String s, ListString wordDict) {//把wordDict中的元素放到set集合中方便后续判断有没有某个单词SetString set new HashSetString(wordDict);//dp数组dp[i] 代表字符串0到i在不在set中能不能被字典中的单词表示boolean[] dp new boolean[s.length() 1];dp[0] true;for(int i 1; i s.length(); i){//遍历字符串sfor(int j 0; j i; j){//判断从字符串0到i的长度能不能被字典中的单词表示if(dp[j] set.contains(s.substring(j, i))){//如果0到j能被表示且j到i能被表示 (在字典中)dp[i] true;//则0到i也能被表示break;}}}return dp[s.length()];}
}
7.9.零钱兑换(完全背包问题) class Solution {public int coinChange(int[] coins, int amount) {// dp[i] 就代表凑齐 i 元所需要的硬币数量int[] dp new int[amount 1];Arrays.fill(dp, amount 1);dp[0] 0;for (int i 1; i amount; i) {for (int j 0; j coins.length; j) {if (i coins[j]) {//当前遍历到第j个硬币一共凑齐了i元//凑齐这i元最小硬币数dp[i] 没有用当前硬币//用了当前硬币才凑齐的i元所用的硬币数dp[i - coins[j]] 1(当前硬币的数量)dp[i] Math.min(dp[i], dp[i - coins[j]] 1);}}}return dp[amount] amount 1 ? -1 : dp[amount];}
} 7.10.骑士在棋盘上的概率(三维dp)
左神第p18大概一小时左右讲了类似题目 class Solution {//用来代表每一对骑士的走法int[][] dirs new int[][]{{-1,-2},{-1,2},{1,-2},{1,2},{-2,1},{-2,-1},{2,1},{2,-1}};public double knightProbability(int n, int k, int row, int column) {//一个三维dp数组z方向代表剩余步数//xy方向用来决定当前骑士的位置//如果dp[][][] 1 代表骑士在棋盘里的概率double[][][] dp new double[n][n][k 1];for(int i 0; i n; i){for(int j 0; j n; j){dp[i][j][0] 1;//剩余步数为0棋盘中的每一个点都代表在棋盘里}}//每一层(z轴)都依赖于下一层的走法for(int h 1; h k; h){//遍历当前层的每一个点for(int i 0; i n; i){for(int j 0; j n; j){for(int[] d : dirs){//走完以后的位置int nx i d[0], ny j d[1];//如果越界了就不进入概率计算if (nx 0 || nx n || ny 0 || ny n) continue;//如果当前位置在棋盘里dp[i][j][h] dp[nx][ny][h - 1] / 8;}}}}// 本题求从最下面一层的起始 x row y column 到达最上面一层合法区域的概率// 和求从最上面的 x row y column 出发达到最下面一层的合法区域的概率 是相同的// 因此返回值为从最下面合法区域的任何一个点开始到达最顶上 x row y column 的概率return dp[row][column][k];}
} 8.滑动窗口和单调栈 1.滑动窗口最大值 注意每次从队尾添加一个数进队列一定要跟在比它大的元素后面。如果队尾元素不满足比当前添加元素大就一直弹出。直到满足队尾元素比它大或者队列弹空了。
原理窗口中维持的信息是有可能成为最大值的下标。每次添加一个值已经在队列中且比当前元素小的元素就再也不可能成为最大值了。因为那些数比当前元素小且当前元素比它们更晚被淘汰 (更晚出队列因为从左往右遍历的如果窗口左边界也移动当前元素一定比那些元素更晚淘汰) class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if (nums.length k) {int max Integer.MIN_VALUE;for (int num : nums) {max Math.max(num, max);}return new int[]{max};}int l -1;//窗口左边界int r -1;//窗口右边界int index 0;//存放答案的数组int[] res new int[nums.length - k 1];//双端队列规则队头元素始终是最大元素队头到队尾由小到大LinkedListInteger maxQ new LinkedList();while (r nums.length) {//当窗口还没遍历结束//如果队尾还有元素且队尾元素比当前元素小while (!maxQ.isEmpty() nums[maxQ.peekLast()] nums[r]) {maxQ.pollLast();}//到了这里说明队列为空或者队尾元素比当前元素大//当前元素入队尾maxQ.addLast(r);if (maxQ.peekFirst() l) {//如果当前队头元素过期出队maxQ.pollFirst();}if (r - l k) {l;res[index] nums[maxQ.peekFirst()];}}return res;}
} 2.每日温度
思路维护一个由小到大的单调栈栈顶元素最小。每次从栈顶加入一个数都要进行一次判断
如果加入的元素 栈顶元素 满足单调性直接入栈。 加入的元素 栈顶元素 栈顶元素弹出一直弹到栈为空或者加入元素小于等于栈顶元素。
每次从栈顶弹出一次元素对该元素进行计算。当前加入的元素就是比栈顶弹出的元素大且离它最近的元素。 class Solution {public int[] dailyTemperatures(int[] temperatures) {//单调栈LinkedListInteger stack new LinkedList();//用于保存结果res[i] 就代表比temperatures[i] 大的右边最近一个元素距离i的位置int[] res new int[temperatures.length];for (int i 0; i temperatures.length; i) {//当栈为空或者栈顶元素比当前元素大while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) {Integer pop stack.pop();res[pop] i - pop;}//能到这一步说明栈为空/栈顶元素大于等于当前元素stack.push(i);}return res;}
} 3.接雨水
思路与上题略有不同的就是本题还要找遍历当前值左侧最近且比当前值大的元素。就是栈中每个值下面一个元素。 class Solution {public int trap(int[] height) {int res 0;LinkedListInteger stack new LinkedList();for (int i 0; i height.length; i) {while (!stack.isEmpty() height[i] height[stack.peek()]) {int pop stack.pop();Integer peek stack.peek();if (peek ! null) {//peek null 说明当前出栈的栈顶元素左边没有比它大的数// 出栈元素pop对应雨水面积的高为 左右两个中较小的那个 - pop元素的高 int h Math.min(height[i], height[peek]) - height[pop];res h * (i - peek - 1);}}stack.push(i);}return res;}
} 4.长度最小子序列(滑动窗口) class Solution {public int minSubArrayLen(int target, int[] nums) {int res Integer.MAX_VALUE;int l 0;//代表滑动窗口左边界int r 0;//代表滑动窗口右边界int cnt 0;//用于计算窗口中元素的和while (r nums.length) {while (r nums.length) {//不断右移r往窗口中加元素cnt nums[r];if (cnt target) break;r;}while (l r) {//不断缩小窗口if (cnt - nums[l] target) {cnt - nums[l];l;} else {break;}}//到了这一步要不就是窗口中元素大于等于target要不就是r遍历完res Math.min(res, r - l 1);r;}return cnt target ? res : 0;}
}
