本系列文章记录labuladong的算法小抄中剑指offer题目
剑指 Offer II 018. 有效的回⽂
题目链接：https://leetcode.cn/problems/XltzEq/
class Solution {
public boolean isPalindrome(String s) {
// 先把所有字符转化成小写，并过滤掉空格和标点这类字符
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isLetterOrDigit(c)) {
sb.append(Character.toLowerCase(c));
}
}
// 然后对剩下的这些目标字符执行双指针算法，判断回文串
s = sb.toString();
int left = 0;
int right = s.length()-1;
while(right>left){
if(s.charAt(left)!=s.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}
剑指 Offer 58 - I. 翻转单词顺序
题目链接：https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/
//先反转整个字符串，再逐个单词反转
class Solution {
public String reverseWords(String s) {
StringBuilder sb = trimSpaces(s);
//整个字符串反转
sb = sb.reverse();
//逐个单词反转
return reverseWord(sb);
}
//去除多余空格
public StringBuilder trimSpaces(String s) {
int left = 0, right = s.length() - 1;
// 去掉字符串开头的空白字符
while (left <= right && s.charAt(left) == ' ') {
left++;
}
// 去掉字符串末尾的空白字符
while (left <= right && s.charAt(right) == ' ') {
right--;
}
// 将字符串间多余的空白字符去除
StringBuilder sb = new StringBuilder();
while(left<=right){
char c=s.charAt(left);
if(c!=' '){
sb.append(c);
}else if (sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
left++;
}
return sb;
}
//逐单词反转
public String reverseWord(StringBuilder sb){
int left=0,right=0;
while(right<sb.length()){
while(right<sb.length() && sb.charAt(right)!=' '){right++;}
//反转[left,right)的字符
reverse(sb,left,right);
right++;
left=right;
}
return sb.toString();
}
//原地反转
public void reverse(StringBuilder sb, int left, int right){
while(right>left){
char temp=sb.charAt(--right);
sb.setCharAt(right,sb.charAt(left));
sb.setCharAt(left,temp);
left++;
}
}
}
剑指 Offer 21. 调整数组顺序使奇数位于偶数前⾯
题目链接：https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
//维护 nums前半部分 都是奇数
class Solution {
public int[] exchange(int[] nums) {
int left=0,right=0;
while(right<nums.length){
if(nums[right]%2==1){
int temp=nums[right];
nums[right]=nums[left];
nums[left]=temp;
left++;
}
right++;
}
return nums;
}
}
//将后半部分奇数换到前半部分
class Solution {
public int[] exchange(int[] nums) {
int left=0,right=nums.length-1;
while(left<right){
while(left<right && nums[left]%2==1){
left++;
}
int temp = nums[left];
while(left<right && nums[right]%2==0){
right--;
}
nums[left]=nums[right];
nums[right]=temp;
}
return nums;
}
}
剑指 Offer 57. 和为s的两个数字
题目链接：https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
class Solution {
public int[] twoSum(int[] nums, int target) {
int left=0,right=nums.length-1;
int[] res = new int[2];
while(left<=right){
if(nums[left]+nums[right]>target){
right--;
}else if(nums[left]+nums[right]<target){
left++;
}else{
res[0]=nums[left];
res[1]=nums[right];
return res;
}
}
return res;
}
}
剑指 Offer II 007. 数组中和为 0 的三个数
题目链接：https://leetcode.cn/problems/1fGaJU/
文章来源：https://www.toymoban.com/news/detail-500240.html
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for(int i=0;i<nums.length-2;i++){
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int j=i+1;
int k=nums.length-1;
while(j<k){
if(nums[i]+nums[j]+nums[k]<0){
j++;
}else if(nums[i]+nums[j]+nums[k]>0){
k--;
}else{
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[k]);
res.add(temp);
while(j<k && nums[j]==nums[j+1]){j++;}
while(j<k && nums[j]==nums[k-1]){k--;}
j++;
k--;
}
}
}
return res;
}
}
总结
使用的内置函数：文章来源地址https://www.toymoban.com/news/detail-500240.html
//判断字符是否是字母和数字
Character.isLetterOrDigit(c)
//字符转化成小写
Character.toLowerCase(c)
//反转字符串
stringbuilder.reverse()
到了这里，关于【剑指offer刷题记录 java版】数组双指针 之 其它题目的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
