vampire`blogs

leetcode-300. 最长上升子序列 1234567891011121314151617181920212223242526272829class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; if (n == 0) { return 0; } // 定义dp数组 int[] dp = new int[n]; // 初始化dp for (int i = 0; i < n; i++) { dp[i] = 1; } for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nu ...

leetcode-714. 买卖股票的最佳时机含手续费 原始思路 1234567891011121314151617181920class Solution { public int maxProfit(int[] prices, int fee) { int n = prices.length; if (n < 2) { return 0; } // 定义dp数组 int[][] dp = new int[n][2]; dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < n; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee); dp[i][1] = Math.max(dp[i - 1] ...

leetcode-面试题 08.01. 三步问题 123456789101112131415161718192021222324class Solution { public int waysToStep(int n) { if (n < 3) { return n; } if (n == 3) { return 4; } //定义三个状态 long[] dp = new long[n + 1]; //初始化dp dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i = 4; i <= n; i++) { dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3])%(1000000007); } ...

leetcode-309. 最佳买卖股票时机含冷冻期 原始思路 1234567891011121314151617181920212223242526class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n < 2) { return 0; } //定义dp数组 int[][][] dp = new int[n][2][2]; //未处于冷冻期 dp[0][0][0] = 0; dp[0][0][1] = -prices[0]; //处于冷冻期 dp[0][1][0] = 0; dp[0][1][1] = -prices[0]; for (int i = 1; i < n; i++) { dp[i][1 ...

leetcode-1314. 矩阵区域和 12345678910111213141516171819202122232425262728293031class Solution { public int[][] matrixBlockSum(int[][] mat, int K) { // 确定矩阵的大小 int n = mat.length; int c = mat[0].length; int[][] result = new int[n][c]; for (int i = 0; i < n; i++) { for (int j = 0; j < c; j++) { //计算原始数组中需要计算的角标 int xmin = i - K < 0 ? 0 : i - K; int xmax = i + K > n - 1 ? n - 1 ...

leetcode-1583. 统计不开心的朋友 原始思路 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566class Solution { int count = 0; public int unhappyFriends(int n, int[][] preferences, int[][] pairs) { for (int i = 0; i < n/2; i++) { //一对对进行判断是否亲密 isUnHappy(n, preferences, pairs, i, 0); isUnHappy(n, preferences, pairs, i, 1); } return count; } public ...

leetcode-1582. 二进制矩阵中的特殊位置 原始思路 123456789101112131415161718192021222324252627282930313233343536373839404142434445class Solution { int count = 0; public int numSpecial(int[][] mat) { int row = mat.length; int cols = mat[0].length; for (int i = 0; i < row; i++) { for (int j = 0; j < cols; j++) { if (mat[i][j] == 1) { dfs(mat, i, j, row, cols); } } } ...

leetcode-188. 买卖股票的最佳时机 IV 题解思路 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; if (n <= 0 || k <= 0) { return 0; } if (2*k > n) { int res = 0; for (int i = 1; i < n; i++) { res += Math.max(0, prices[i] - prices[i - 1]); } retur ...

leetcode-123. 买卖股票的最佳时机 III 1234567891011121314151617181920212223242526272829303132333435class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n < 2) { return 0; } //定义一个数组,n表示第几天,3表示交易了几次,2表示持有或者不持有股票 int[][][] dp = new int[n][3][2]; //一共有5中状态 // 表示一直未买进股票 dp[0][0][0] = 0; //表示第一次买进股票,未进行卖出的交易,卖出只能有两次 dp[0][0][1] = -prices[0]; //第一次卖出,此状态还未发生,设置为不可能的值 ...

leetcode-122. 买卖股票的最佳时机 II 原始思路 1234567891011121314151617181920class Solution { public int maxProfit(int[] prices) { int n = prices.length; if (n < 2) { return 0; } //定义数组存放 int[] dp = new int[2]; dp[0] = 0; dp[1] = -prices[0]; for (int i = 0; i < n; i++) { dp[0] = Math.max(dp[0], dp[1] + prices[i]); dp[1] = Math.max(dp[1], dp[0] - prices[i]); } return dp ...