宿迁网站制作公司,高级seo优化招聘,商贸信息网站,企业做的网站计入什么科目目录 二、双指针
25. 验证回文数 ①
26. 判断子序列 ①
27. 两数之和II - 输入有序数组 ②
28. 盛最多水的容器 ②
29. 三数之和 ② 二、双指针
25. 验证回文数 ① 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后#xff0c;短语正着读和反着读都一…目录 二、双指针
25. 验证回文数 ①
26. 判断子序列 ①
27. 两数之和II - 输入有序数组 ②
28. 盛最多水的容器 ②
29. 三数之和 ② 二、双指针
25. 验证回文数 ① 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s如果它是 回文串 返回 true 否则返回 false 。 示例 1
输入: s A man, a plan, a canal: Panama
输出true
解释amanaplanacanalpanama 是回文串。示例 2
输入s race a car
输出false
解释raceacar 不是回文串。示例 3
输入s
输出true
解释在移除非字母数字字符之后s 是一个空字符串 。
由于空字符串正着反着读都一样所以是回文串。提示
1 s.length 2 * 105s 仅由可打印的 ASCII 字符组成 方法1 public static boolean isPalindrome(String s) {StringBuilder stringBuilder new StringBuilder();for (int i 0; i s.length(); i) {char c s.charAt(i);if (Character.isUpperCase(c)){c Character.toLowerCase(c);}if (Character.isLowerCase(c) || Character.isDigit(c)){stringBuilder.append(c);}}
// 比较的时候要把stringBuilder放左边
// 因为stringBuilder.reverse()会改变stringBuilder的值if (stringBuilder.toString().equals() || stringBuilder.toString().equals(stringBuilder.reverse().toString())){return true;}else {return false;}}
方法2 public boolean isPalindrome(String s) {int first 0;int last s.length() - 1;char[] chars s.toCharArray();while (first last) {if(chars[first] 48 || (chars[first] 57 chars[first] 65) || (chars[first] 90 chars[first] 97) || chars[first] 122) {first;continue;}if(chars[last] 48 || (chars[last] 57 chars[last] 65) || (chars[last] 90 chars[last] 97) || chars[last] 122) {last--;continue;}if(chars[first] 97) chars[first] 32;if(chars[last] 97) chars[last] 32;if(chars[first] ! chars[last]) return false;first;last--;}return true;} 26. 判断子序列 ① 给定字符串 s 和 t 判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。
进阶
如果有大量输入的 S称作 S1, S2, ... , Sk 其中 k 10亿你需要依次检查它们是否为 T 的子序列。在这种情况下你会怎样改变代码
致谢
特别感谢 pbrother 添加此问题并且创建所有测试用例。 示例 1
输入s abc, t ahbgdc
输出true示例 2
输入s axc, t ahbgdc
输出false提示
0 s.length 1000 t.length 10^4两个字符串都只由小写字符组成。 方法12ms public boolean isSubsequence(String s, String t) {int small 0;for (int i 0; i t.length(); i) {if (small s.length() t.charAt(i) s.charAt(small)){small;}}if (small s.length()){return true;}else {return false;}} public boolean isSubsequence(String s, String t) {int i 0, j 0;while (i s.length() j t.length()) {if (s.charAt(i) t.charAt(j)){i;}j;}return i s.length();}
方法20ms public boolean isSubsequence(String s, String t) {//运用数组和String APIint index-1;for(char ch:s.toCharArray()){indext.indexOf(ch,index1);if(index-1){return false;}}return true;} 27. 两数之和II - 输入有序数组 ② 给你一个下标从 1 开始的整数数组 numbers 该数组已按 非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。 示例 1
输入numbers [2,7,11,15], target 9
输出[1,2]
解释2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。返回 [1, 2] 。
示例 2
输入numbers [2,3,4], target 6
输出[1,3]
解释2 与 4 之和等于目标数 6 。因此 index1 1, index2 3 。返回 [1, 3] 。
示例 3
输入numbers [-1,0], target -1
输出[1,2]
解释-1 与 0 之和等于目标数 -1 。因此 index1 1, index2 2 。返回 [1, 2] 。提示
2 numbers.length 3 * 104-1000 numbers[i] 1000numbers 按 非递减顺序 排列-1000 target 1000仅存在一个有效答案 方法1447ms public int[] twoSum(int[] numbers, int target) {int[] result new int[2];for (int i 0; i numbers.length; i) {for (int j numbers.length - 1; j i; j--) {if (numbers[j] target - numbers[i]){result[0] i 1;result[1] j 1;return result;}}}return result;}
1ms public int[] twoSum(int[] numbers, int target) {int[] result new int[2];int left 0;int right numbers.length - 1;while (true){if (numbers[left] numbers[right] target){right--;}else if (numbers[left] numbers[right] target){left;}else {result[0] left 1;result[1] right 1;return result;}}} 28. 盛最多水的容器 ② 给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。 示例 1 输入[1,8,6,2,5,4,8,3,7]
输出49
解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。
示例 2
输入height [1,1]
输出1提示
n height.length2 n 1050 height[i] 104 方法13ms public static int maxArea(int[] height) {int left 0;int right height.length - 1;int area 0;while (left right){int min Math.min(height[left], height[right]);if (min * (right - left) area){area min * (right - left);}if (min height[left]){left;}else {right--;}}return area;}
方法21ms public int maxArea(int[] height) {int l 0;int r height.length-1;int max 0;int minH;while(lr){minH Math.min(height[l],height[r]);max Math.max(max,minH*(r-l));while(lrheight[l]minH) l;while(lrheight[r]minH) --r;}return max;} 29. 三数之和 ② 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。 示例 1
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。示例 2
输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。示例 3
输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。提示
3 nums.length 3000-105 nums[i] 105 方法1通过311/312 public static ListListInteger threeSum(int[] nums) {ArrayListListInteger result new ArrayList();Arrays.sort(nums);for (int i 0; i nums.length; i) {int left i;int right nums.length - 1;int mid left 1;while (mid right){if (nums[mid] nums[right] nums[left] 0){mid;}else if (nums[mid] nums[right] nums[left] 0){right--;}else {ArrayListInteger list new ArrayList();list.add(nums[left]);list.add(nums[mid]);list.add(nums[right]);mid;right--;if (!result.contains(list)){result.add(list);}}}}return result;}
对以上代码的修改使得通过所有用例38ms public static ListListInteger threeSum(int[] nums) {ArrayListListInteger result new ArrayList();Arrays.sort(nums);for (int i 0; i nums.length; i) {int left i;if (i 0 nums[i] nums[i - 1]){continue;}int right nums.length - 1;int mid left 1;while (mid right){if (nums[mid] nums[right] nums[left] 0){mid;}else if (nums[mid] nums[right] nums[left] 0){right--;}else {result.add(Arrays.asList(nums[left], nums[mid], nums[right]));while (mid right nums[mid 1] nums[mid]){mid;}while (mid right nums[right] nums[right - 1]){right--;}mid;right--;}}}return result;} 方法2 public ListListInteger threeSum(int[] nums) {//定义一个结果集ListListInteger res new ArrayList();//数组的长度int len nums.length;//当前数组的长度为空或者长度小于3时直接退出if(nums null || len 3){return res;}//将数组进行排序Arrays.sort(nums);//遍历数组中的每一个元素for(int i 0; ilen;i){//如果遍历的起始元素大于0就直接退出//原因此时数组为有序的数组最小的数都大于0了三数之和肯定大于0if(nums[i]0){break;}//去重当起始的值等于前一个元素那么得到的结果将会和前一次相同if(i 0 nums[i] nums[i-1]) continue;int l i 1;int r len-1;//当 l 不等于 r时就继续遍历while(lr){//将三数进行相加int sum nums[i] nums[l] nums[r];//如果等于0将结果对应的索引位置的值加入结果集中if(sum0){// 将三数的结果集加入到结果集中res.add(Arrays.asList(nums[i], nums[l], nums[r]));//在将左指针和右指针移动的时候先对左右指针的值进行判断//如果重复直接跳过。//去重因为 i 不变当此时 l取的数的值与前一个数相同所以不用在计算直接跳while(l r nums[l] nums[l1]) {l;}//去重因为 i不变当此时 r 取的数的值与前一个相同所以不用在计算while(l r nums[r] nums[r-1]){r--;} //将 左指针右移将右指针左移。l;r--;//如果结果小于0将左指针右移}else if(sum 0){l;//如果结果大于0将右指针左移}else if(sum 0){r--;}}}return res;}
方法39ms public ListListInteger threeSum(int[] nums) {ListListInteger res new ArrayListListInteger();if (nums null || nums.length 3) return res;Arrays.sort(nums);for (int i 0; i nums.length - 2; i) {if (i ! 0 nums[i] nums[i - 1]) continue;int low i 1;int high nums.length - 1;while (low high) {int sum nums[low] nums[high] nums[i];if (sum 0) {ListInteger item new ArrayListInteger();item.add(nums[i]);item.add(nums[low]);item.add(nums[high]);res.add(item);low;high--;while (low high nums[low] nums[low - 1]) low;while (low high nums[high] nums[high 1]) high--;} else if (sum 0) {high--;} else {low;}}}return res;}
