验证回文串
直接双指针对比就行。
public boolean isPalindrome(String s) {
char[] arr = s.toLowerCase().toCharArray();
int l=0,r=arr.length-1;
while(l<r){
while (l<r&&!ischar(arr[l])){
l++;
}
while (l<r&&!ischar(arr[r])){
r--;
}
if (arr[l++]!=arr[r--]){
return false;
}
}
return true;
}
public boolean ischar(char c){
return (c>='0'&&c<='9')||(c>='a'&&c<='z');
}
判断子序列
同样使用双指针。
public boolean isSubsequence(String s, String t) {
int slow=0;
int fast=0;
while(fast<t.length()&&slow<s.length()){
if(s.charAt(slow)==t.charAt(fast)){
slow++;
}
fast++;
}
if(slow==s.length()){
return true;
}
return false;
}
两数之和||
167. 两数之和 II - 输入有序数组 - 力扣(LeetCode)
使用双指针,一个从头,一个从尾,如果当前值比target小,头指针++,如果当前值比target大,尾指针--
public int[] twoSum(int[] numbers, int target) {
int l=0,r=numbers.length-1;
while(l<r){
int res = numbers[l]+numbers[r];
if(res == target){
return new int[]{l+1,r+1};
}else if(res > target){
r--;
}else{
l++;
}
}
return null;
}
盛水最多的容器
双指针,一个从头,一个从尾,每次比较两个指针当前的所指的值,头指针小,则头指针++,尾指针小,则尾指针--,同时计算当前的面积并更新最大值。
public int maxArea(int[] height) {
int n = height.length;
int left=0;
int right=n-1;
int max=(right-left)*Math.min(height[left],height[right]);
while(left<right){
if(height[left]<height[right]){
left++;
}else{
right--;
}
int index = (right-left)*Math.min(height[left],height[right]);
if(max<index){
max=index;
}
}
return max;
}
三数之和
与二数之和原理一致,多加了去重处理。
if (nums.length<3){
return null;
}
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
int i=0;
int j,k;
while (i<nums.length-2){
j=i+1;
k=nums.length-1;
while(j<k){
if(nums[j]+nums[k]+nums[i]==0){
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
res.add(list);
while(j<k&&nums[j+1]==nums[j]) {
j++;
};
while(j<k&&nums[k-1]==nums[k]) {
k--;
};
j++;
k--;
}else if(nums[j]+nums[k]+nums[i]>0){
k--;
}else {
j++;
}
}
while (i<nums.length-2&&nums[i]==nums[i+1]){
i++;
}
i++;
}
return res;
}