NC105 二分查找-I

请实现无重复数字的升序数组的二分查找

给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1

数据范围：0≤len(nums)≤2×1050 \le len(nums) \le 2\times10^50≤len(nums)≤2×105 ， 数组中任意值满足 ∣val∣≤109|val| \le 10^9∣val∣≤109
进阶：时间复杂度 O(log⁡n)O(\log n)O(logn) ，空间复杂度 O(1)O(1)O(1)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        int left=0;
        int right=nums.length;
        int mid;
        while(left<right)
        {
            mid=left+((right-left)>>1);
            if(nums[mid]>target)
            {
                right=mid;
            }
            else if(nums[mid]<target)
            {
                
                left=mid+1;
            }
            else{
                return mid;
            }
        }
        return -1;
    }
}

NC105 二分查找-II

请实现有重复数字的升序数组的二分查找
给定一个 元素有序的（升序）长度为n的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1

数据范围：0≤n≤100000 0 \le n \le 100000\ 0≤n≤100000
进阶：时间复杂度O(logn) O(logn)\ O(logn) ，空间复杂度O(n) O(n)\ O(n)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        int left=0;
        int right=nums.length;
        int mid=-1;
        while(left<right)
        {
            mid=(left+right)>>1;
            if(nums[mid]>target)
            {
                right=mid;
             
            }
            else if(nums[mid]<target)
            {
                 left=mid+1;
            }
            else
            {
                while(mid>0&&nums[mid-1]==nums[mid])
                {
                   mid--;
                }
                
                return mid;
            }
        }
        
        return -1;
        
    }
}

移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

class Solution {
    public int removeElement(int[] nums, int val) {
       int slow;
       int fast=0;
       for(slow=0;fast<nums.length;fast++){
           if(nums[fast]!=val){
               nums[slow]=nums[fast];
               slow++;
           }
       }
       return slow;
    }
}

有序数据的平方

class Solution {
    public int[] sortedSquares(int[] nums) {
       for(int i=0;i<nums.length;i++)
       {
           nums[i]=nums[i]*nums[i];
       }
       Arrays.sort(nums);
       return nums;
    }

}

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
       int left=0;
       int right=0;
       int sum=0;
       int result=Integer.MAX_VALUE;
       for(right=0;right<nums.length;right++)
       {
           sum=sum+nums[right];
            while(sum>=target)
            {
                result=Math.min(result,right-left+1);
                sum=sum-nums[left++];
            }
       }
       return result==Integer.MAX_VALUE?0:result;
    }
}

螺旋矩阵II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result=new int[n][n];
        int sum=1;
        int j=0;
        while(sum<=n*n)
        {
            for(int i=j;i<n-j;i++)
            {
                result[j][i]=sum++;
            }
            for(int i=j+1;i<n-j;i++)
            {
                result[i][n-j-1]=sum++;
            }
            for(int i=n-j-2;i>=j;i--)
            {
                result[n-j-1][i]=sum++;
            }
            for(int i=n-j-2;i>j;i--)
            {
                result[i][j]=sum++;
            }
            j++;
        }
        return result;
    }
}