免费建设网站怎么样,沣东新城开发建设集团有限公司网站,php个人网站怎么做,上海网站建设公司推荐5. 最长回文子串 给你一个字符串 s#xff0c;找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同#xff0c;则该字符串称为回文字符串。 示例 1#xff1a; 输入#xff1a;s babad
输出#xff1a;bab
解释#xff1a;aba找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同则该字符串称为回文字符串。 示例 1 输入s babad
输出bab
解释aba 同样是符合题意的答案。我们可以根据前面的子串结果在头尾拼接上一个字符并判断其是否相同。DP
class Solution {public String longestPalindrome(String s) {int lens.length();int maxStart 0; int maxEnd 0; int maxLen 1; boolean[][] isReversenew boolean[len][len];for(int j1;jlen;j){for(int i0;ilen;i){//if(j-i1maxLen)continue;if((s.charAt(i)s.charAt(j))((j-i2)||(isReverse[i1][j-1]))){isReverse[i][j]true;if(j-i1maxLen){maxLenj-i1;maxEndj;maxStarti;}}else isReverse[i][j]false;}}return s.substring(maxStart,maxEnd1);}
}注意第一层循环是右指针第二层循环是左指针。这样才能用到前面的结果。
7. 整数反转 给你一个 32 位的有符号整数 x 返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] 就返回 0。 假设环境不允许存储 64 位整数有符号或无符号。 示例 1 输入x 123
输出321翻转好做但是有个要求翻转后的数字大小超出了 int 范围则返回0.
我们用 long 存储翻转后的数字如果 (int)res!res 就返回0.
11. 盛最多水的容器 给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 **说明**你不能倾斜容器。 如图给定一个 height[] 数组让我找到盛水最高的两条边。
思路直接遍历超时。首先我们让左右指针到最左最右。算出当前面积。
然后我们左右指针往里挪底边变短那么我们必须想办法让 height 最小值增加才能有面积的提升因此我们让最矮的 height 那边指针先动比如上图就是右边红色指针先动。这样效率高。
15. 三数之和
找到三数求和0的所有组合。不能重复。肯定是不能直接遍历太慢了。
排序数组。从左到右遍历 i从第二次遍历开始判断当前位数值和上一次循环是否相同相同直接 continue.从 i1 到右遍历 j和 i 一样如果和上次循环值一样则 continue。从 nums.length-1 往左遍历 k。逻辑是我们固定了 i j逐渐减小 k直至找到求和0的组合。如果求和结果 0说明 i j 太小了继续尝试下一个 j。如果求和结果 0 则一直向左移动 k 指针直到求和结果0或者 jk 相遇或者求和结果 0. jk 相遇说明这个 i j 组合过大了接下来 j 再继续增大求和结果也只会更大没有继续尝试的必要了因此直接跳出当前 j 循环即可。求和结果 0 则尝试下一个 j。
class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);List resListnew ArrayListList();int i0,lennums.length;for(;ilen-2;i){if(i0nums[i]nums[i-1])continue;int target-nums[i];for(int ji1;jlen-1;j){if(ji1nums[j]nums[j-1])continue;int klen-1;while(jknums[j]nums[k]target)k--;if(jk)break;else if(nums[j]nums[k]target){List subListnew ArrayListInteger();subList.add(nums[i]);subList.add(nums[j]);subList.add(nums[k]);resList.add(subList);}}}return resList;}
}33. 下一个排列 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如arr [1,2,3] 以下这些都可以视作 arr 的排列[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地如果数组的所有排列根据其字典顺序从小到大排列在一个容器中那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列那么这个数组必须重排为字典序最小的排列即其元素按升序排列。 例如arr [1,2,3] 的下一个排列是 [1,3,2] 。类似地arr [2,3,1] 的下一个排列是 [3,1,2] 。而 arr [3,2,1] 的下一个排列是 [1,2,3] 因为 [3,2,1] 不存在一个字典序更大的排列。 给你一个整数数组 nums 找出 nums 的下一个排列。 必须** 原地 **修改只允许使用额外常数空间。 主要就是算法。
第一遍遍历数组检查是否为倒序找到第一个不为倒序的位置。第一个不为倒序的位置和它后面的数作比较找到一个刚好大于他的最小的数换到他的位置然后排序其后面的位置。如果全部满足为倒序排序那么数组反转。
class Solution {public void swap(int[] nums, int i, int j){nums[i]nums[i]^nums[j];nums[j]nums[i]^nums[j];nums[i]nums[i]^nums[j];}public void reverse(int[] nums){for(int i0;inums.length/2-1;i){swap(nums, i, nums.length-1-i);}}public void nextPermutation(int[] nums) {int lennums.length;int ilen-1;while(i!0!(nums[i-1]nums[i])){i--;}if(i0)reverse(nums);else {i--;int min101;for(int jlen-1;ji;j--){if(nums[j]minnums[j]nums[i]){swap(nums, i, j);Arrays.sort(nums,i1,len);return;}}}}
}
34. 在排序数组中查找元素的第一个和和最后一个位置 给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1 输入nums [5,7,7,8,8,10], target 8
输出[3,4]是二分法但是不完全是因为我们要找到起始区间。
我们可以通过两次二分第一次找起始位置或小于目标值的最大的数的位置第二次找结束位置或大于目标值的最小数的位置。
class Solution {public int[] searchRange(int[] nums, int target) {int lennums.length;int[] resnew int[2];res[0]-1;res[1]-1;int left0,rightlen-1;while(leftright){int mid(leftright)/2;if(nums[mid]target){rightmid-1;res[0]mid;}else leftmid1;}left0;rightlen-1;while(leftright){int mid(leftright)/2;if(nums[mid]target){rightmid-1;res[1]mid;}else leftmid1;}res[1]right;if(!(res[0]res[1])||res[0]-1||res[1]-1){res[0]-1;res[1]-1;}return res;}
}如果数组中一定存在给定数那么只靠两个 while 循环是可以找到起始和结束位置的。但是如果不存在这两个循环查询可能会出现一些错误比如一个是找到的位置一个是-1或者 rightleft。这种情况要单独判别后再决定返回值。
