LeetCode学习日记1

数组学习一：

题目在看题解时候看动图描述会理解得更好！！！

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

思考：

对于这道题运用二分法查找目标值，首先需要知道二分法的概念，按照我自身理解的方式，我是将二分法理解为：将一段内容不断按照1/2进行切割，以此对目标不断接近。放在这题目中是：由题可以知道数组是按照升序排列的，因此按照1/2分割后看目标值与中间值哪个大，再判断是在中间值的左边还是右边，一直按照这个规律不断查找，最后找到目标值。按照这道题需要进行不断找中间值，因此使用双指针法，左指针指数组开端，右指针指数组结尾，根据数组不断变短的过程，对左右指针位置进行不一样的变化。

class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            //没有搞懂题解里面防止溢出的计算方法是什么意思
            int mid=(left+right)/2;
            if(target<nums[mid]){
                right=mid-1;
            }else if(target>nums[mid]){
                left=mid+1;
            }else{
                return mid;
            }
        }
            return -1;
    }
}

2.题目（27.移除元素）：

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

*注意：关于数组需要注意一点：数值里面的值无法删除，只能进行覆盖。

思考：

按照本题意是需要将给出的数进行覆盖，用双指针法，分为快慢指针，快指针负责遍历数组内全部内容，而慢指针是到最后的数组末尾位置，也就是慢指针返回的位置就是数组的新长度。

未解决疑问：

慢指针是是从索引0开始的，那么最后返回的索引下标应该是比数组长度少1的，那么为什么不用加上1呢？

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

3.题目（977.有序数组的平方）：

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
 

思考：按照题目和示例，数组内的数字是按照升序排列的，并且包含有负数，将所有数平方后得到新的经过排序的数组，首先想到的办法就是将所有数进行平方，然后将数利用某种排序方法进行排序得到新的数组，但是会有更加有效率的方法，首先一个按顺序且包含负数的数组，在经过平方后左右两头的数肯定是最大的，也即是两头向中间递减，按照这个规律我们需要使用双指针法，左右两端各一指针，然后一直进行平方后的比较，将较大的平方数放入新数组的末尾，所以我们也需要创建一个同原数组长度的新数组，由于最后得到的数组也要按照升序排列，所以将指针比较到的较大数依次从新数组末尾开始逐个放入。

class Solution {
    public int[] sortedSquares(int[] nums) {
        //新建一个和原数组长度一样的数组来存放排序后的数组
        int [] result=new int [nums.length];
        int left=0;
        int right=nums.length-1;
        int index=result.length-1;
        while(left<=right){
        if((nums[left]*nums[left])>(nums[right]*nums[right])){
            result[index]=nums[left]*nums[left];
            left++;
            index--;
        }else{
            result[index]=nums[right]*nums[right];
            right--;
            index--;
        }
        }
        return result;
    }
}

今日总结：在看到题目后，不一定能想出解决办法，想出来的也是使用暴力解法，所以还是要再多熟悉以下相关问题，还有熟悉记住“双指针”的使用，注意数组具有怎么样的排列或者是数字规律，进而想方法解决问题。