标签：String offer int 复杂度 nums result day13 指针

调整数组顺序使奇数位于偶数前面

题目描述

思路

双指针

代码实现

双指针

class Solution {
    public static void main(String[] args) {
        int [] nums={1,2,3,4};
        exchange(nums);
    }
    public static int[] exchange(int[] nums) {
        int i=0,j=nums.length-1;
        while(i<j){
            while(i<j&&(nums[i]&1)==1)i++;
            while(i<j&&(nums[j]&1)==0)j--;
            int tmp=nums[i];
            nums[i]=nums[j];
            nums[j]=tmp;
        }
        return nums;
    }
}

复杂度分析

时间复杂度

O(N)

空间复杂度

O(1)

反思不足

思路

思路很模糊，结构化、可视化以及debug建议都用用

和为s的两个数字

题目描述

思路

双指针+二分查找

自己的思路，虽然不咋地但毕竟是自己想的

双指针+对撞指针

需要看到一个规律：

不等于目标值，要么小于要么大于，小于的情况下，要增大，于是可以移动左指针，反之同理

代码实现

双指针+二分查找

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //确定边界
        int l=0,r=nums.length-1,mid=l+(r-l)/2;;
        //一个遍历，一个二分查找
        while(l<=r){
            if(nums[mid]>target)r=mid-1;
            else l=mid+1;
            mid=l+(r-l)/2;
        }
        int len=r;
        int i=0;
        for(i=0;i<len;i++){
            l=i;
            mid=l+(r-l)/2;
            while(l<=r){
                if(nums[mid]+nums[i]==target)break;
                else if(nums[mid]+nums[i]<target)l=mid+1;
                else r=mid-1;
                mid=l+(r-l)/2;
            }
            if(l<=r)break;
        }
        int [] result={nums[i],nums[mid]};
        return result;
    }
}

双指针+对撞指针

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l=0,r=nums.length-1;
        while(l<r){
            int s=nums[l]+nums[r];
            if(s<target)l++;
            else if(s>target)r--;
            else return new int[] {nums[l],nums[r]};
        }
        return new int[]{};
    }
}

复杂度分析

时间复杂度

二分查找那个O(NlogN)，对撞指针O(N)

空间复杂度

O(1)

反思不足

思路

看到有序数组能想到二分查找，是好的，比暴力好

不足之处在于没能看出数量关系，对对撞指针也没什么概念

java se

return new int[]{};

题目描述

思路

库函数法

分割，然后倒着拼接

双指针

用两个指针维护单词的边界，挨个去找

代码实现

库函数法

class Solution {
    public String reverseWords(String s) {
        String [] strs = s.split("[ ]+");
        StringBuilder result=new StringBuilder();
        for(int i=strs.length-1;i>=0;i--){
            result.append(strs[i]+" ");
        }
        return result.toString().trim();
    }
}

双指针法

class Solution {
    public String reverseWords(String s) {
        
        String s_=s.trim();
        int i=s_.length()-1,j=i;
        StringBuilder result=new StringBuilder();
        while(i>=0){
            while(i>=0&&s_.charAt(i)!=' ')i--;
            result.append(s_.substring(i+1,j+1)+" ");
            while(i>=0&&s_.charAt(i)==' ')i--;
            j=i;
        }
        return result.toString().trim();
    }
}

复杂度分析

时间复杂度

库函数法为O(N)，所调用的api均不超过这个数量级

双指针亦为O(N)

空间复杂度

因为有个StingBuilder，所以均为O(N)

反思不足

思路

标签：String,offer,int,复杂度,nums,result,day13,指针
From： https://www.cnblogs.com/zhouj-learn/p/16802825.html