剑指offer几道值得一看的题

---

剑指 Offer 57 - II. 和为s的连续正数序列

滑动窗口

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

class Solution {
    public int[][] findContinuousSequence(int target) {
        // (a+b)/2 *(b-a+1)
        int[] nums = new int[target];
        for(int i=0;i<target;i++) {
            nums[i] = i;
        }
        List<int[]> list = new ArrayList<>();
        int j=1;
        for(int i=1;i<=target/2+1;i++) {
            for(;j<=target/2+1;j++) {
                int curSum = (i+j)*(j-i+1)/2;
                if(curSum>target) {
                    break;
                } else if(curSum==target) {
                    list.add(Arrays.copyOfRange(nums,i,j+1));
                    break;
                }
            } 
        }
        return list.toArray(new int[list.size()][]);
    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

class Solution {
    public int search(int[] nums, int target) {
        return biLargeSearch(nums,target,0,nums.length-1)-
                biLargeSearch(nums,target-1,0,nums.length-1);
    }

    private int biLargeSearch(int[] nums,int target,int left,int right) {
        int mid;
        while(left<=right) {
            mid = (left+right)/2;
            if(nums[mid]>target) right = mid-1;
            else  left = mid+1;
        }
        return left;
    }
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

还是右边界问题。

class Solution {
    public int missingNumber(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        int mid;
        while(start<=end) {
            mid = (start+end)/2;
            if(nums[mid]==mid) start=mid+1;
            else end=mid-1;
        }
        return start;
    }
}

剑指 Offer 65. 不用加减乘除做加法

class Solution {
    public int add(int a, int b) {
        while(b!=0) {
            int step = (a&b)<<1;
            a = a^b;
            b = step;
        }
        return a;
    }
}

剑指 Offer 49. 丑数

class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n+1];
        ugly[1] = 1;
        //比较三个指针
        int p2 = 1;
        int p3 = 1;
        int p5 = 1;
        for(int i=2;i<=n;i++) {
            int a = ugly[p2]*2;
            int b = ugly[p3]*3;
            int c = ugly[p5]*5;
            if(a<=b&&a<=c) {
                ugly[i]=a;
                p2++;
            }
             if(b<=a&&b<=c) {
                ugly[i]=b;
                p3++;
            }
             if(c<=a&&c<=b) {
                ugly[i]=c;
                p5++;
            }
        }
        //System.out.println(Arrays.toString(ugly));
        return ugly[n];
    }
}

剑指 Offer 59 - I. 滑动窗口的最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] result = new int[nums.length-k+1];
        int resultIndex = 0;
        for(int i=0;i<k;i++) {
            while(!deque.isEmpty()&&nums[i]>deque.getLast()) deque.pollLast();
            deque.addLast(nums[i]);
        }
        result[resultIndex++] = deque.getFirst();
        for(int i=k;i<nums.length;i++) {
            //如果滑动窗口移除的元素和队列头相同，说明该元素已经不在窗口内，此时队列头出队
            if(deque.getFirst()==nums[i-k]) deque.pollFirst();
            while(!deque.isEmpty()&&nums[i]>deque.getLast()) deque.pollLast();
            deque.addLast(nums[i]);
            result[resultIndex++]=deque.getFirst();
        }
        return result;
    }
}