|
目录
1.二分查找
2.搜索插入位置
3.在排序数组中查找元素的第一个和最后一个位置
4.x的平方根
5.有效的完全平方数
1.二分查找
地址：704. 二分查找 - 力扣（LeetCode）
题目：
给定一个 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(right>=left){
? ? ? ? ? ?int mid=(left+right)/2;
? ? ? ? ? ?if(target==nums[mid]){
? ? ? ? ? ? ? ?return mid;
? ? ? ? ? }else if(target>nums[mid]){
? ? ? ? ? ? ? ?left=mid+1;
? ? ? ? ? }else if(target<nums[mid]){
? ? ? ? ? ? ? ?right=mid-1;
? ? ? ? ? }else{
? ? ? ? ? ? ? ?return -1;
? ? ? ? ? }
? ? ? }
? ? ? ?return -1;
? }
}
解题思路：代码随想录 (programmercarl.com)
2.搜索插入位置
地址：35. 搜索插入位置 - 力扣（LeetCode）
题目：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
提示:
1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums 为 无重复元素 的 升序 排列数组 -104 <= target <= 104
答案：
class Solution {
? ?public int searchInsert(int[] nums, int target) {
? ? ? ?int left=0;
? ? ? ?int right=nums.length-1;
? ? ? ?while(right>=left){
? ? ? ? ? ?int mid=(left+right)/2;
? ? ? ? ? ?if(target==nums[mid]){// 1. 目标值等于数组中某一个元素 return mid;
? ? ? ? ? ?return mid;
? ? ? ? ? }else if(target<nums[mid]){
? ? ? ? ? ? ? ?right=mid-1;
? ? ? ? ? }else if(target>nums[mid]){
? ? ? ? ? ? ? ?left=mid+1;
? ? ? ? ? }
? ? ? }
? ? ? ?//当right=left-1时跳出while循环
? ? ? ?// 2.目标值在数组所有元素之前 3.目标值插入数组中 4.目标值在数组所有元素之后 return left 或者 right + 1;
? ? ? ?return left;
? }
}
3.在排序数组中查找元素的第一个和最后一个位置
地址：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
题目：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]
示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
提示：
0 <= nums.length <= 105 -109 <= nums[i] <= 109 nums 是一个非递减数组 -109 <= target <= 109
答案：
class Solution {
? ?public int[] searchRange(int[] nums, int target) {
? ? ? ?//rightBorder是不包含target的右边界，leftBorder是不包含target的左边界
? ? ? ?int rightBorder=getRightBorder(nums,target);
? ? ? ?int leftBorder=getLeftBorder(nums,target);
? ? ? ?int res[]=new int[2];
? ? ? ?if(nums.length==0){
? ? ? ? ? ?res[0]=-1;
? ? ? ? ? ?res[1]=-1;
? ? ? ? ? ?return res;
? ? ? }
? ? ? ?if(target<nums[0] || target>nums[nums.length-1]){
? ? ? ? ? ?res[0]=-1;
? ? ? ? ? ?res[1]=-1;
? ? ? ? ? ?return res;
? ? ? }else if(rightBorder-leftBorder>1){
? ? ? ? ? ?res[0]=leftBorder+1;
? ? ? ? ? ?res[1]=rightBorder-1;
? ? ? ? ? ?return res;
? ? ? }else{
? ? ? ? ? ?res[0]=-1;
? ? ? ? ? ?res[1]=-1;
? ? ? ? ? ?return res;
? ? ? }
? }
?
? ?/**
? ? *求右边界
? ? */
? ?private int getRightBorder(int[] nums,int target){
? ? ? ?int left=0;
? ? ? ?int right=nums.length-1;
? ? ? ?int rightBorder=-1;
? ? ? ?while(left<=right){
? ? ? ? ? ?int mid=(left+right)/2;
? ? ? ? ? ?if(nums[mid]>target){//当target在左半边的时候
? ? ? ? ? ? ? ?right=mid-1;
? ? ? ? ? }else{
? ? ? ? ? ? ? ?left=mid+1;
? ? ? ? ? ? ? ?rightBorder=left;
? ? ? ? ? }
? ? ? }
? ? ? ?return rightBorder;
? }
?
? ?/**
? ? *求左边界
? ? */
? ?private int getLeftBorder(int[] nums,int target){
? ? ? ?int left=0;
? ? ? ?int right=nums.length-1;
? ? ? ?int leftBorder=-1;
? ? ? ?while(left<=right){
? ? ? ? ? ?int mid=(left+right)/2;
? ? ? ? ? ?if(nums[mid]<target){//当target在右半边的时候
? ? ? ? ? ? ? ?left=mid+1;
? ? ? ? ? }else{
? ? ? ? ? ? ? ?right=mid-1;
? ? ? ? ? ? ? ?leftBorder=right;
? ? ? ? ? }
? ? ? }
? ? ? ?return leftBorder;
? }
}
解题思路：代码随想录 (programmercarl.com)
4.x的平方根
地址：69. x 的平方根 - 力扣（LeetCode）
题目：
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
答案：
class Solution {
? ?public int mySqrt(int x) {
? ? ? ?//x的算数平方根的整数部分就是满足k*k<=x的最大k值
? ? ? ?//采用二分查找
? ? ? ?int left=0;
? ? ? ?int right=x;
? ? ? ?//最终答案在两个相邻的整数之前产生，取更小的那个
? ? ? ?//比如8的算术平方根是2.82842...，由于返回类型是整数，小数部分被舍去后为结果2
? ? ? ?//while循环运行到最后会在2和3之间选择，更小的那个是left的值，即最终答案
? ? ? ?//对于一个非负数其取整数的平方根一定在其0到他的一半之间（除了0，1）
? ? ? ?if(x==0)
? ? ? ?return 0;
? ? ? ?if(x==1)
? ? ? ?return 1;
? ? ? ?//此为界定条件，一个巧妙的1使得最后经过若干次循环后，左值右值差不多相等
? ? ? ?while(right>left+1){//因为都是整型，所以差极小时即为差了1。所以当到了差1的条件时就可以跳出循环了。
? ? ? ? ? ?int mid=(left+right)/2;
? ? ? ? ? ?if(mid>x/mid){//一开始mid*mid肯定比x大，如果写mid*mid>x会越界，超出时间限制
? ? ? ? ? ? ? ?right=mid;
? ? ? ? ? }else{
? ? ? ? ? ? ? ?left=mid;
? ? ? ? ? }
? ? ? }
? ? ? ?return left;
? }
}
解题思路：(4条消息) 力扣求平方根三种方法小白理解向光.的博客-CSDN博客力扣 平方根
5.有效的完全平方数
地址：367. 有效的完全平方数 - 力扣（LeetCode）
题目：
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16 输出：true
示例 2：
输入：num = 14 输出：false
提示：
1 <= num <= 2^31 - 1
答案：
class Solution {
? ?public boolean isPerfectSquare(int num) {
? ? ? ?int left=0;
? ? ? ?int right=num;
? ? ? ?while(right>=left){
? ? ? ? ? ?int mid=(left+right)/2;
? ? ? ? ? ?//使用mid*mid==num会越界，超出时间限制；使用num/mid==mid会报by zero错误
? ? ? ? ? ?//by zero错误：当我们定义的被除数为整型时候(short int long)会抛出此异常,被除数为整型时不可以为零。
? ? ? ? ? ?long temp_mid=(long)mid*mid;//转成long型才不会报错
? ? ? ? ? ?if(temp_mid==num){
? ? ? ? ? ? ? ?return true;
? ? ? ? ? }else if(temp_mid<num){
? ? ? ? ? ? ? ?left=mid+1;
? ? ? ? ? }else{
? ? ? ? ? ? ? ?right=mid-1;
? ? ? ? ? }
? ? ? }
? ? ? ?return false;
? }
}
解题思路：(4条消息) 力扣题：367有效的完全平方数_追梦偏执狂的博客-CSDN博客
|