March 7.2022.

2024-04-28 05:08

文章标签 march 7.2022

本文主要是介绍March 7.2022.，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

704. 二分查找

力扣题目链接(opens new window)

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -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

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

代码实现

class Solution {public int search(int[] nums, int target) {if(target < nums[0] || target > nums[nums.length-1]){return -1;   }int left = 0;int right = nums.length-1;while(left<=right){int mid = left + ((right-left)>>1);// 即 (left+right)/2；if(nums[mid] == target)return mid;else if(nums[mid]>target)right = mid-1;//最优化中的二分法，右边大则迭代右边的选点，左边同理else if(nums[mid]<target)left = mid+1;}return -1;}
}

27. 移除元素

力扣题目链接(opens new window)

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

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

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

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

解题思路：

本题可以考虑双指针的解法！！！！！！！！！

双指针法

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

慢指针先从nums[0]处开始，快指针先从慢指针处循环，如果目标值不等于快指针处的值，就让快慢指针指向同一个值的位置上，慢指针向前移动。
如果快指针指向的位置等于目标值，慢指针的位置不动，快指针向前继续移动，直到又不等于目标值，此时再把该处的值赋给慢指针位置

暴力法在此处不做赘述

双指针法代码实现

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

977.有序数组的平方

力扣题目链接(opens new window)

给你一个按非递减顺序排序的整数数组 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]

解题思路

暴力排序
双指针法

选择双指针法的原因：

同移除元素题27 相似，有序数组的平方最大值之可能出现在数组的左右两端，故可考虑在数组的左右两端各设置一个指针，通过比较两个指针处值的大小来决定把哪一个值 sort 到新数组（即新创建的结果数组）的右端

代码实现

class Solution {public int[] sortedSquares(int[] nums) {int left = 0;int right = nums.length-1;//设置好储存结果的数组int[] result = new int[nums.length];//排序指针，从大往小int index = nums.length-1;while(left <= right){if(nums[left]*nums[left] > nums[right]*nums[right]){//左边的值大，在index处存放左边的值 左边的指针向前移动，继续比较，++left先加后用result[index--] = nums[left]*nums[left];++left;}else  {//右边的值大，存放右边的值，右边的指针向前移动，下标变小--rightresult[index--] =nums[right]*nums[right];--right;}}return result;}
}