Leetcode-0412

122. 买卖股票的最佳时机 II

class Solution {public int maxProfit(int[] prices) {if(prices.length == 0)return 0;int dp[] = new int[prices.length];int last = prices[0];for(int i=1;i<prices.length;i++){if(prices[i]>last){dp[i] += (prices[i] - last);}last = prices[i];dp[i] += dp[i-1];}return dp[prices.length-1];}
}

340周赛

6361. 对角线上的质数（简单）

class Solution {public boolean isPrime(int k){if(k<=1)return false;for(int i=2;i*i<=k;i++){if(k%i==0)return false;}return true;}public int diagonalPrime(int[][] nums) {int max = 0;for(int i=0;i<nums.length;i++){for(int j=0;j<nums[i].length;j++){if(i!=j&&j!=nums.length-i-1)continue;if(isPrime(nums[i][j]) && nums[i][j] > max) max = nums[i][j];}}return max;}
}

6353. 网格图中最少访问的格子数（困难）

思路：维护一个node节点信息，记录深度,节点i，j坐标和v值。利用一个二维boolean数组进行标记，保证只搜一遍。将起点节点入队之后，开始bfs。先判断终点是否在移动范围里，如果在直接返回深度，返回时要注意，如果是原点的话，不需要+1。之后是向右搜索和向下搜索。依次将元素入队。如果最终都没有找到，返回-1.

class node {int i, j, v,path;public node(int i, int j,int v,int path) {this.i = i;this.j = j;this.v = v;this.path = path;}}class Solution {public int minimumVisitedCells(int[][] grid) {int mlength = grid.length;int nlength = grid[0].length;boolean flag[][] = new boolean[mlength][nlength];Queue<node> queue = new LinkedList<>();queue.offer(new node(0, 0,grid[0][0],1));flag[0][0] = true;while (!queue.isEmpty()) {node n = queue.poll();//  判断能否到达if((n.i+n.v>=mlength-1&&n.j==nlength-1)||(n.j+n.v>=nlength-1&&n.i==mlength-1)){if(flag[mlength-1][nlength-1])return n.path;return n.path+1;}//  右移for (int j=n.j+1;j<=n.j+n.v&&j<nlength;j++){if(flag[n.i][j])continue;queue.offer(new node(n.i,j,grid[n.i][j],n.path+1));flag[n.i][j] = true;}//  下移动for(int i=n.i+1;i<=n.i+n.v&&i<mlength;i++){if(flag[i][n.j])continue;queue.offer(new node(i,n.j,grid[i][n.j], n.path+1));flag[i][n.j] = true;}}return -1;}}