深圳好蜘蛛网站建设公司,广东品牌女装都有哪些品牌,wordpress 初始化,办公室平面图设计布局剑指 Offer 42. 连续子数组的最大和、剑指 Offer 46. 把数字翻译成字符串、剑指 Offer 47. 礼物的最大价值、剑指 Offer 48. 最长不含重复字符的子字符串
题目描述#xff1a; [42] [46] [47] [48]
考察重点#xff1a;第42题要计算最大子数组和#xff0c;考虑第i位…剑指 Offer 42. 连续子数组的最大和、剑指 Offer 46. 把数字翻译成字符串、剑指 Offer 47. 礼物的最大价值、剑指 Offer 48. 最长不含重复字符的子字符串
题目描述 [42] [46] [47] [48]
考察重点第42题要计算最大子数组和考虑第i位如果前序和为负则一定有nums[i] nums[i] sum所以我们用sum记录当前数组和如果sum0则抛弃前序数组由当前位开始重新计算sum。 第46题要求计算种类数直接可以想到递归求解。 第47题使用dfs会超时考虑使用动态规划列出转移方程即可dp(i, j) max{dp(i - 1, j), dp(i, j - 1)} grid[i][j]。 第48题要求计算最长子序列这里使用快慢指针构成滑动窗口配合HashSet实现。
第42题
class Solution {public int maxSubArray(int[] nums) {int sum Integer.MIN_VALUE;int maxSum nums[0];for(int i 0;i nums.length;i ){if(sum 0){sum nums[i];maxSum Math.max(maxSum, sum);continue;}maxSum Math.max(maxSum, sum);sum nums[i]; }return Math.max(maxSum, sum);}
}第46题
class Solution {int res;public int dfs(String num, int pos){if(pos num.length() - 1){res 1;return 0;}int temp 0;if(pos 2 num.length())temp Integer.parseInt(num.substring(pos, pos 2));dfs(num, pos 1);if(temp 10 temp 25)dfs(num, pos 2);return 0;}public int translateNum(int num) {res 0;dfs(String.valueOf(num), 0);return res;}
}第47题
class Solution {public int maxValue(int[][] grid) {int m grid.length, n grid[0].length; for(int i 1;i m;i ){grid[i][0] grid[i-1][0];}for(int j 1;j n;j ){grid[0][j] grid[0][j-1];}for(int i 1;i m;i )for(int j 1;j n;j ){grid[i][j] Math.max(grid[i-1][j], grid[i][j-1]);}return grid[m-1][n-1];}
}第48题
class Solution {public int lengthOfLongestSubstring(String s) {if(s.length() 0)return 0;SetCharacter set new HashSet();int maxLen 1;int quick 1, slow 0;set.add(s.charAt(slow));while(quick s.length()){char c s.charAt(quick);if(set.contains(c)){maxLen Math.max(maxLen, quick - 1 - slow 1);set.remove(s.charAt(slow));slow ;continue;}set.add(c);quick ;}return Math.max(maxLen, quick - 1 - slow 1);}
}
