宿松网站建设推荐秒搜科技,域名申请好了 怎么做网站,众划算网站开发,装饰公司网站模板11.盛水最多的容器 思路#xff1a;最大水量 底边 * 高度。较短的一边控制最大水量#xff0c;因此#xff0c;采用双指针的方式#xff0c;左、右指针指向开始和末尾#xff0c;逐个向中间移动#xff0c;判断左右指针所指向的高度哪个更低#xff0c;它就向中间移动一…11.盛水最多的容器 思路最大水量 底边 * 高度。较短的一边控制最大水量因此采用双指针的方式左、右指针指向开始和末尾逐个向中间移动判断左右指针所指向的高度哪个更低它就向中间移动一个坐标另外的指针不动记录最大值循环结束条件是两个指针指向一处。
代码
public int maxArea(int[] height) {//特殊情况if (height.length 2){return 0;}//双指针int l 0;int r height.length-1;//最终结果(最大容量)int max 0;while (lr){//当前容量int capacity Math.min(height[l],height[r])*(r-l);max Math.max(capacity,max);if (height[l]height[r]){l;}else {r--;}}return max;
} 12.整数转罗马数字 思路我们可以把特殊的数值对应的罗马数字依次列举出来如下图 而我们转换的时候一定是先找到与要转换的数值能表示的最大的罗马数字例如
140与上表对照一定是140 100 40而不是505040
这里可以采用贪心算法依次找剩余面值的最大表示。
代码
public String intToRoman(int num) {int[] values{1000,900,500,400,100,90,50,40,10,9,5,4,1};String[] rom{M,CM,D,CD,C,XC,L,XL,X,IX,V,IV,I};StringBuilder sbnew StringBuilder();//贪心算法只要numvalues[i],就在最终的字符串中加入对应的罗马数字for(int i0;ivalues.length;i){while(numvalues[i]){sb.append(rom[i]);num-values[i];}if (num 0){break;}}return sb.toString();}
13.罗马数字转整数 思路
通常情况下罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况那么可以将每个字符视作一个单独的值累加每个字符对应的数值即可。
例如XVII XVII 1051117
若存在小的数字在大的数字的左边的情况根据规则需要减去小的数字。对于这种情况我们也可以将每个字符视作一个单独的值若一个数字右侧的数字比它大则将该数字的符号取反。
XIVX-IV10-1514
代码
public int romanToInt(String s) {//存放最终结果int sum 0;int preNum getValue(s.charAt(0));for (int i 1; i s.length(); i) {int num getValue(s.charAt(i));if (preNum num)sum - preNum;else sum preNum;preNum num;}//添加最后一个sum preNum;return sum;}//将罗马数字转化为对应的阿拉伯数组public int getValue(char ch){switch (ch){case I: return 1;case V: return 5;case X: return 10;case L: return 50;case C: return 100;case D: return 500;case M: return 1000;default: return 0;}}
14.最长公共前缀 思路我们可以先将字符串数组的第一个字符串的第一个字符与后续的字符串数组的每一个字符串的第一个字符相互比较如果相等就依次比较第二个以此类推。循环结束条件如果存在第 j 个字符不相等就截取已经比较过的字符为最终结果如果第一个字符串遍历完毕都相等则最终结果就是第一个字符串。 代码
public String longestCommonPrefix(String[] strs) {if (strs.length0)return ;//获取第一个字符串的长度int length strs[0].length();//获取整个字符数组的长度也就是字符串的个数int count strs.length;//逐个比较for (int i 0; i length; i) {char c strs[0].charAt(i);for (int j 1; j count; j) {if (istrs[j].length() || c!strs[j].charAt(i))return strs[0].substring(0,i);//左闭右开}}return strs[0];}
15.三数之和 思路题目要求输出的是一个数组的数组我们可以用ListListInteger存储并且不能重复。我们可以先对数组进行排序然后用双指针的方法依次找出题目要求的三元组。
因为排好序了为从小到大的顺序因此随着第一个元素的递增第二个元素是递减的用双指针依次检查三个数的和0比较如果大于0则右指针递减如果小于0则左指针递增如果等于0则将三个数添加在存储结果中。
代码
public ListListInteger threeSum(int[] nums) {//最终返回的List集合ListListInteger lists new ArrayList();//如果数组的长度小于3则返回空结果int n nums.length;if (n 3){return lists;}//对数组进行排序Arrays.sort(nums);for (int i 0; i n - 2; i) {//如果大于0则之后的都大于0不可能三数之和 0if (nums[i] 0)return lists;//跳过重复值if (i 0 nums[i] nums[i-1] )continue;//双指针int left i1;int right n - 1;int target -nums[i];while (left right){if (target nums[left]nums[right]){ListInteger temp new ArrayList();temp.add(nums[i]);temp.add(nums[left]);temp.add(nums[right]);lists.add(temp);//去重while (left right nums[left] nums[left1])left;while (left right nums[right] nums[right-1])right--;//双指针收缩left;right--;}else if(target nums[left] nums[right]){right--;}elseleft;}}return lists;}
