陕西网站建设维护_app开发哪个公司专业_网站搜索优化_windows清理优化大师

一：子数组系列

1.1 最大子数组和

题目链接：最大子数组和

class Solution {public int maxSubArray(int[] nums) {// 采用动态规划的思想解决问题int n = nums.length;// 因为 dp 表要通过 dp[n] 获取以 n 为结尾的最大数组和，所以我们创建 dp 表时要多加一个空间int[] dp = new int[n + 1];// 初始化dp[0] = 0;// 开始填表，一边填表一边记录 dp 表中的最大值int ret = Integer.MIN_VALUE;for(int i = 1; i <= n; i++){// 注意映射关系，当我们遍历 dp 表去找 nums 中的元素时， i -> i - 1dp[i] = Math.max(nums[i - 1], dp[i - 1] + nums[i - 1]);ret = Math.max(ret, dp[i]);}return ret;}
}

1.2 环形子数组的最大和

题目链接：环形子数组的最大和

class Solution {public int maxSubarraySumCircular(int[] nums) {// 采用动态规划的思想解决问题int n = nums.length;int[] f = new int[n + 1];int[] g = new int[n + 1];// 用 sum 记录整个数组的和，fmax 记录 f 表中的最大值，gmin 记录 g 表中的最小值int sum = 0, fmax = Integer.MIN_VALUE, gmin = Integer.MAX_VALUE;// 接下来开始填表，一边填表一边记录一下 f 表的最大值，g 表的最小值，以及数组的总和 sumfor(int i = 1; i <= n; i++){f[i] = Math.max(nums[i - 1], nums[i - 1] + f[i - 1]);g[i] = Math.min(nums[i - 1], nums[i - 1] + g[i - 1]);fmax = Math.max(fmax, f[i]); gmin = Math.min(gmin, g[i]);sum += nums[i - 1];}return sum == gmin ? fmax : Math.max(fmax, sum - gmin);}
}

1.3 乘积最大子数组

题目链接：乘积最大子数组

class Solution {public int maxProduct(int[] nums) {// 采用动态规划的思想解决问题，首先创建两个表// f[i] 表示以第 i 个元素结尾的子数组的最大乘积// g[i] 表示以第 i 个元素结尾的子数组的最小乘积int n = nums.length;int[] f = new int[n + 1];int[] g = new int[n + 1];// 初始化f[0] = g[0] = 1;// 接着从左往右开始填表，一边填表一边记录 f 表中的最大值int ret = Integer.MIN_VALUE;;for(int i = 1; i <= n; i++){f[i] = Math.max(Math.max(nums[i - 1], f[i - 1] * nums[i - 1]), g[i - 1] * nums[i - 1]);g[i] = Math.min(nums[i - 1], Math.min(f[i - 1] * nums[i - 1], g[i - 1] * nums[i - 1]));ret = Math.max(ret, f[i]);}return ret;}
}

1.4 乘积为正数的最长子数组长度

题目链接：乘积为正数的最长子数组长度

class Solution {public int getMaxLen(int[] nums) {// 先创建两个 dp 表//  ret 用于记录全局的最长正数乘积子数组长度// f[i] 表示以第 i 个元素结尾的正数乘积子数组的最大长度// g[i] 表示以第 i 个元素结尾的负数乘积子数组的最大长度int n = nums.length, ret = Integer.MIN_VALUE;int[] f = new int[n + 1];int[] g = new int[n + 1];// 先初始化两个表f[0] = 0; g[0] = 0;// 开始从左往右填写两个表，边填表边记录 f 表中的最大值for (int i = 1; i <= n; i++) {if (nums[i - 1] > 0) { f[i] = f[i - 1] + 1;g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;} else if (nums[i - 1] < 0) { f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;g[i] = f[i - 1] + 1;} ret = Math.max(ret, f[i]);}return ret;}
}

1.5 等差数列划分

题目链接：等差数列划分

class Solution {public int numberOfArithmeticSlices(int[] nums) {// 采用动态规划的思想解决该问题,n 用于记录数组长度，sum 记录 dp 表中所有元素的和int n = nums.length, sum = 0;int[] dp = new int[n];// 接着开始填表for(int i = 2; i < n; i++){dp[i] = (nums[i] - nums[i - 1]) == (nums[i - 1] - nums[i - 2]) ? dp[i - 1] + 1 : 0;sum += dp[i];}return sum;}
}

1.6 最长湍流子数组

题目链接：最长湍流子数组

class Solution {public int maxTurbulenceSize(int[] arr) {// 采用动态规划的思想解决问题，首先先创建两个 dp 表再处理一下特殊情况,ret 记录两个表中的最大值int n = arr.length, ret = 0;if(n == 1) return 1;int[] f = new int[n];int[] g = new int[n];// 接着把两个表中的值全部初始化为 1for(int i = 0; i < n; i++) f[i] = g[i] = 1;// 从左往右同时填写两个表，在填写的同时统计两个表中的最大值for(int i = 1; i < n; i++){if(arr[i - 1] < arr[i]) f[i] = g[i - 1] + 1;else if(arr[i - 1] > arr[i]) g[i] = f[i - 1] + 1;ret = Math.max(ret, Math.max(f[i], g[i]));}return ret;}
}

1.7 单词拆分

题目链接：单词拆分

class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 优化：将字典中的单词存入哈希表，便于快速查找Set<String> hash = new HashSet<>(wordDict);// 接着创建一个 dp 表，dp[i] 表示前 i 个字符是否可以被分割成字典中的单词int n = s.length();boolean[] dp = new boolean[n + 1];// 初始化dp[0] = true;// 为了处理下标映射问题，给字符串 s 前面加一个空格s = " " + s;// 遍历字符串，从第 1 个字符到第 n 个字符for (int i = 1; i <= n; i++) {// 遍历最后一个单词的起始位置，从 i 向前检查for (int j = i; j >= 1; j--) {if (dp[j - 1] && hash.contains(s.substring(j, i + 1))) {dp[i] = true;  break;        // 优化：找到一个可行解即可退出内层循环}}}return dp[n];}
}

1.8 环绕字符串中唯一的子字符串

题目链接：环绕字符串中唯一的子字符串

class Solution {public int findSubstringInWraproundString(String ss) {// 先创建一个 dp 表，dp[i] 表示以第 i 个字符为结尾的最长连续子串的长度，接着将字符串转换为字符数组，便于逐个字符处理int n = ss.length();int[] dp = new int[n];char[] s = ss.toCharArray();// 把 dp 表中的每一个元素都初始化为 1for (int i = 0; i < n; i++) dp[i] = 1;// 开始填表for (int i = 1; i < n; i++) if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))  dp[i] += dp[i - 1];// 去重操作// 用一个数组模拟哈希表来记录每个字母能组成的最长连续子串的长度int[] hash = new int[26];for (int i = 0; i < n; i++)  hash[s[i] - 'a'] = Math.max(hash[s[i] - 'a'], dp[i]);// 将哈希表中所有字母对应的最长子串长度累加，得到最终结果int sum = 0;for (int x : hash) sum += x;return sum;}
}

二：子序列问题

2.1 最长递增子序列

题目链接：最长递增子序列

class Solution {public int lengthOfLIS(int[] nums) {// 采用动态规划的思想解决问题，首先创建一个 dp 表int n = nums.length;int[] dp = new int[n];// 初始化，把所有元素初始化为最差的状态for(int i = 0; i < n; i++) dp[i] = 1;// 接着开始用 i 从 1 开始到结尾固定所有的结束位置// 用 j 从 0 到 i - 1 固定以当前 i 位置为结尾 i 前面一个位置可能的所有情况// 一边填写 dp 表一边统计 dp 表中所有元素的最大值int ret = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);}// 外层 for 循环才是固定所有的结束位置。当然 ret 的更新也可以放在内层 for 循环中，但是会执行很多次没有必要的更新ret = Math.max(ret, dp[i]);}return ret;}
}

2.2 摆动序列

题目链接：摆动序列

class Solution {public int wiggleMaxLength(int[] nums) {// 这题采用动态规划的思想解决问题，首先创建两个 dp 表// f[i] 表示以第 i 个元素为结尾，最后一个差值为正的最长摆动子序列长度// g[i] 表示以第 i 个元素为结尾，最后一个差值为负的最长摆动子序列长度int n = nums.length;int[] f = new int[n];int[] g = new int[n];// 把两个表中的数据全都初始化为 1for(int i = 0; i < n; i++) f[i] = g[i] = 1;// 接着用 i 从 1 开始到 n - 1 结束固定每一个位置为结尾的情况// 用 j 从 0 开始到 i - 1 固定所有以 i 位置为结尾，i 前面元素的所有可能情况// 遍历的同时用 ret 记录两个表中的最大值int ret = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]) f[i] = Math.max(f[i], g[j] + 1);else if(nums[j] > nums[i]) g[i] = Math.max(g[i], f[j] + 1);}ret = Math.max(ret, Math.max(f[i], g[i]));}return ret;}
}

2.3 最长递增子序列的个数

题目链接：最长递增子序列的个数

class Solution {public int findNumberOfLIS(int[] nums) {// 先定义两个 dp 表// len[i] 表示以 nums[i] 结尾的最长递增子序列的长度// count[i] 表示以 nums[i] 结尾的最长递增子序列的个数int n = nums.length;int[] len = new int[n];int[] count = new int[n];// 两个表中的元素都初始化为 1for (int i = 0; i < n; i++) len[i] = count[i] = 1;// retlen 记录全局最长递增子序列的长度，retcount 记录全局最长递增子序列的个数int retlen = 1, retcount = 1; // 开始填表for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {if (len[j] + 1 == len[i]) count[i] += count[j];else if (len[j] + 1 > len[i]) {len[i] = len[j] + 1;count[i] = count[j];}}}if (retlen == len[i]) retcount += count[i];else if (retlen < len[i]) {retlen = len[i];retcount = count[i];}}return retcount;}
}

2.4 最长数对链

题目链接：最长数对链

class Solution {public int findLongestChain(int[][] pairs) {// 预处理数组，对数组进行升序排列Arrays.sort(pairs, (a, b) -> a[0] - b[0]);// 接着创建一个 dp 表int n = pairs.length;int[] dp = new int[n]; // 把 dp 表中的元素都初始化为 1for (int i = 0; i < n; i++) dp[i] = 1;// 填表int ret = 1; // 保存最长链的长度，初始值为 1，因为至少有一个区间for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) if (pairs[j][1] < pairs[i][0]) dp[i] = Math.max(dp[j] + 1, dp[i]);// 更新 retret = Math.max(ret, dp[i]);}return ret;}
}

2.5 最长定差子序列

题目链接：最长定差子序列

class Solution {public int longestSubsequence(int[] arr, int difference) {// 创建一个哈希表，用于记录以某个数结尾的最长子序列长度，键为数组中的数字，值为以该数字为结尾的子序列的最长长度Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); int ret = 1; // 用于记录最终结果，初始值为 1for (int a : arr) {hash.put(a, hash.getOrDefault(a - difference, 0) + 1);ret = Math.max(ret, hash.get(a));}return ret;}
}

2.6 最长斐波那契子序列的长度

题目链接：最长斐波那契子序列的长度

class Solution {public int lenLongestFibSubseq(int[] arr) {// 创建一个哈希表，用于快速查找数组中的值对应的下标，键为数组中的值，值为该值在数组中的下标，接着将数组中的元素和对应的下标绑定存入哈希表Map<Integer, Integer> hash = new HashMap<Integer, Integer>();int n = arr.length;for (int i = 0; i < n; i++)  hash.put(arr[i], i);// 定义 dp 数组，dp[i][j] 表示以 arr[i] 和 arr[j] 为最后两个数字的斐波那契子序列的最大长度int[][] dp = new int[n][n];// 初始化 dp 数组，所有初始值为 2，因为最短的斐波那契子序列长度为 2for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dp[i][j] = 2;int ret = 2; // 用于记录全局最长的斐波那契子序列长度for (int j = 2; j < n; j++) {for (int i = 1; i < j; i++) {int a = arr[j] - arr[i];if (a < arr[i] && hash.containsKey(a))  dp[i][j] = dp[hash.get(a)][i] + 1;ret = Math.max(ret, dp[i][j]);}}return ret < 3 ? 0 : ret;}
}