做网站公司简介模版,有关网站建设国内外现状的文献,深圳网站推广,如何编辑网站后台双指针
125.验证回文串
题目
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后#xff0c;短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s#xff0c;如果它是 回文串 #xff0c;返回…双指针
125.验证回文串
题目
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s如果它是 回文串 返回 true 否则返回 false 。
提示
1 s.length 2e5 s 仅由可打印的 ASCII 字符组成
示例 1
输入: s A man, a plan, a canal: Panama
输出true
解释amanaplanacanalpanama 是回文串。示例 2
输入s race a car
输出false
解释raceacar 不是回文串。
示例 3
输入s
输出true
解释在移除非字母数字字符之后s 是一个空字符串 。由于空字符串正着反着读都一样所以是回文串。解析:
该题是个水题只需要移除所有非字母数字字符之后利用双指针从新的字符串的头部和尾部不断地向对方推进进行比较。 当两个不相同的字符时就结束说明此串不是回文串。
代码:
class Solution {public boolean isPalindrome(String s) {String ps.toLowerCase();System.out.print(p);char[] anew char[p.length()];int len0;for (int i0;ip.length();i){if (p.charAt(i)ap.charAt(i)z||p.charAt(i)0p.charAt(i)9){a[len]p.charAt(i);}}boolean flagtrue;for (int i0,jlen-1;ij;i,j--){if (a[i]!a[j]){flagfalse;break;}}return flag;}
}392.判断子序列
题目
给定字符串 s 和 t 判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。
提示
0 s.length 100 0 t.length 1e4 两个字符串都只由小写字符组成。
示例 1
输入s abc, t ahbgdc
输出true示例 2
输入s axc, t ahbgdc
输出false解析
遍历字符串 t用一个指针 l 指向字符串 s 的最后一个与 s 匹配的字符的位置。 当 t[i]s[l] 时l。直到遍历结束比较 l 与字符串 s 的长度即可。
代码
class Solution {public boolean isSubsequence(String s, String t) {int n t.length(), m s.length();if (m 0)return true;int l 0;for (int i 0; i n; i) {if (t.charAt(i) s.charAt(l)) {l;}if (l m) {break;}}if (l m)return true;return false;}
}167.两数之和 II - 输入有序数组
题目
给你一个下标从 1 开始的整数数组 numbers 该数组已按非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。 如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length 。 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。 你可以假设每个输入 只对应唯一的答案 而且你 不可以 重复使用相同的元素。 你所设计的解决方案必须只使用常量级的额外空间。
提示
2 numbers.length 3 * 1e4 -1000 numbers[i] 1000 , numbers 按 非递减顺序 排列 -1000 target 1000 仅存在一个有效答案
示例 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] 。解析
该数组已经按照非递减顺序排列设置两个指针分别指向数组头部和尾部。 如果指向的两个数的和大于目标数就需要将小的那个数变大即头部指针向后移动反之尾部指针向前移动。 直到两个数的和等于目标数。(仅存一个有效答案哦)
代码
class Solution {public int[] twoSum(int[] numbers, int target) {int nnumbers.length;int l0,rn-1;int[] ansnew int[2];while (lr){if (numbers[l]numbers[r]target){ans[0]l1;ans[1]r1;break;}else if (numbers[l]numbers[r]target){l;}else{r--;}}return ans;}
}11.盛最多水的容器
题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明你不能倾斜容器。
提示
n height.length 2 n 1e5 0 height[i] 1e4
示例 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解析
首先知道怎么计算水量水量等于两个端点的距离 * 两条线较短的一条的长度。 设置两个指针指向数组的头部和尾部一个最开始的水量就是尾部减头部的距离 * 较小的长度。 什么情况才可能比这个状态的水量大呢就是取决于两点的距离和较短的一条线长度。 将短的那条线的指针向里面推进只有当较短的变长了才有可能水量变大。 这样不断推进两边端点不断增加线的长度。每次找到后取水量的最大值即可。
代码
class Solution {public int maxArea(int[] height) {int ans 0;int l 0, r height.length - 1;while (l r) {if (height[l] height[r]) {ans Math.max(ans, height[l] * (r - l));int t height[l];while (l r height[l] t)l;} else {ans Math.max(ans, height[r] * (r - l));int t height[r];while (l r height[r] t)r--;}}return ans;}
}
15.三数之和
题目
给你一个整数数组 nums 判断是否存在三元组[nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。 请你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。
提示
3 nums.length 3000 -1e5 nums[i] 1e5
示例 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 。解析
首先数据最大是3000所以双for循环不会超时所以用双for循环遍历nums[i]和nums[j]那么关于剩下的数就是判断0-nums[i]-nums[j]是否在数组中了我是用的map将数组中的数和它的坐标存在map对象中判断该数是否存在且不是第i个数也不是第j个数。 然后就是去重问题我将符合条件的三个数存放进一个数组中进行sort。然后将数组的三个数放进List中将List放进一个Set中进行去重。(有更简便的算法我这个是更加合理地使用集合的那些容器)
代码
class Solution {public ListListInteger threeSum(int[] nums) {SetListInteger res new HashSet();MapInteger, Integer m new HashMap();for (int i 0; i nums.length; i) {m.put(nums[i], i);}for (int i 0; i nums.length; i)for (int j i 1; j nums.length; j) {int k 0 - nums[i] - nums[j];if (m.containsKey(k) m.get(k) ! i m.get(k) ! j) {ListInteger s new ArrayList();int[] a new int[3];a[0] nums[i];a[1] nums[j];a[2] k;Arrays.sort(a);s.add(a[0]);s.add(a[1]);s.add(a[2]);res.add(s);}}return new ArrayListListInteger(res);}
}
