个体户可以注册网站建设服务,馆陶网站,沈阳网络营销推广的公司,市场调研分析报告1. 二分查找题目链接 704. 二分查找 - 力扣#xff08;LeetCode#xff09;给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中的 target#xff0c;如果目标值存在返回下标#xff0c;否则返回 -…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]之间。思路进行二分查找的前置条件数组有序并且数组中无重复元素写二分查找题的代码需要考虑清楚边界条件比如应该是 while(left right) 还是 where(left right)应该是 right mid - 1 还是 right mid主要在写代码时要考虑清楚区间的范围必须要在二分查找的过程中根据范围保持不变量也就是在 while 中每一次边界的处理根据区间进行操作写二分查找区间的定义一般有两种左闭右闭 [left , right]左闭右开 [left , right)写法一左闭右闭首先明确我们定义的 target 是在区间 [left , right] 中其次根据范围确定两点while (left right) 这里要使用 因为是左闭右闭的区间 left right 有意义if (nums[mid] target) right mid - 1因为 nums[mid] target所以当前这个 nums[mid] 一定不是 target并且是左闭右闭区间所以缩小范围right mid - 1class Solution {public int search(int[] nums, int target) {int left 0, right nums.length - 1;if (target nums[left] || target nums[right]) {return -1;}while (left right) {int mid left (right - left)/2;if (nums[mid] target) {right mid - 1;} else if (nums[mid] target) {left mid 1;} else {return mid;}}return -1;}
}写法二左闭右开首先明确我们定义的 target 是在区间 [left , right) 中其次根据范围确定两点while (left right) 这里要使用 left right 没有意义因为是左闭右开的区间if (nums[mid] target) right mid 因为 nums[mid] target所以当前这个 nums[mid] 一定不是 target那么就要去左区间寻找因为区间范围是左闭右开的所以 right mid下一次查询区间不会去比较 nums[mid]class Solution {public int search(int[] nums, int target) {int left 0, right nums.length;while (left right) {int mid left (right - left)/2;if (nums[mid] target) {right mid;} else if (nums[mid] target) {left mid 1;} else {return mid;}}return -1;}
}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] 104nums 为 无重复元素 的 升序 排列数组-104 target 104思路在数组中插入目标值 target只有这四种情况target 在数组所有元素之前target 数组中某一个元素target 插入数组中位置target 在数组所有元素之后写法一暴力解法这道题最为直接的暴力解法遍历数组中每个元素只要发现遍历到某个元素 target 时直接返回下标如果遍历完 target 是最大的那就返回 nums.length 直接插入到最后class Solution {public int searchInsert(int[] nums, int target) {for(int i 0; i nums.length; i) {if(target nums[i]) {return i;}}return nums.length;}
}时间复杂度 O(n)空间复杂度 O(1)写法二二分法使用二分法前提数组有序并且无重复元素确定边界 [left , right]class Solution {public int searchInsert(int[] nums, int target) {int left 0, right nums.length - 1;while(left right) {int mid left (right - left)/2;if(nums[mid] target) {return mid;} else if(nums[mid] target) {left mid 1;} else {right mid - 1;}}// 分析四种上面四种插入的情况// target 在数组所有元素之前 0// target 数组某个元素 mid// target 插入到数组中某个位置 right 1 // target 在数组所有元素之后 right 1return right 1;}
}时间复杂度 O(log n)空间复杂度 O(1)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] 109nums 是一个非递减数组-109 target 109思路寻找 target 在数组中的左右边界有这三种情况target 在数组范围的右边或左边比如数组 {3,4,5}target 2 或 target 6此时应该返回 {-1-1}target 在数组范围中且数组中不存在 target比如数组 {3,4,7}target 6此时应该返回 {-1-1}target 在数组范围中且数组中存在 target比如数组 {3,4,5}target 4此时应该返回 {1, 1}下面就是找左右边界了采用二分法寻找左右边界写法一二分法二分查找寻找 target 的右边界不包括 target如果 rightBorder 为没有被赋值即 target 在数组范围的左边比如 数组 {3,3}target 2为了处理这种情况class Solution {public int[] searchRange(int[] nums, int target) {int leftBorder getLeftBorder(nums, target);int rightBorder getRightBorder(nums, target);// 情况一if (leftBorder -2 || rightBorder -2) {return new int[]{-1, -1};} // 情况三if (rightBorder - leftBorder 1) {return new int[]{leftBorder1, rightBorder-1};}// 情况二return new int[]{-1, -1};}private int getLeftBorder(int[] nums, int target) {int left 0, right nums.length - 1;int leftBorder -2;while (left right) {int mid left (right - left)/2;if (target nums[mid]) {// 找左边界nums[mid]target 时更新 rightright mid - 1;leftBorder right;} else {left mid 1;}}return leftBorder;}private int getRightBorder(int[] nums, int target) {int left 0, right nums.length - 1;int rightBorder -2;while (left right) {int mid left (right - left)/2;if (target nums[mid]) {//找右边界nums[mid]target 时更新 leftleft mid 1;rightBorder left;} else {right mid - 1;}}return rightBorder;}
}写法二二分法双指针推荐在 nums 数组中二分查找 target如果二分查找失败则 binarySearch 返回 -1表名 nums 中没有 target此时直接返回 {-1-1}如果二分查找成功则 binarySearch 返回 nums 中值为 target 的一个下标通过左右滑动指针来找到符合题意的区间class Solution {public int[] searchRange(int[] nums, int target) {int index binarySearch(nums, target);if(index -1) {return new int[]{-1,-1};} int left index, right index;while(left - 1 0 nums[left - 1] target) {left--;}while(right 1 nums.length - 1 nums[right 1] target) {right;}return new int[]{left,right};}private int binarySearch(int[] nums, int target) {int left 0, right nums.length - 1;while(left right) {int mid left (right - left)/2;if(target nums[mid]) {return mid;} else if(target nums[mid]) {right mid - 1;} else {left mid 1;}}return -1;}
}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 - 1class Solution {public int mySqrt(int x) {long left 0,right x,ans -1;while(left right) {long mid left (right - left)/2;if((long)(mid*mid) x) {ans mid;left mid 1;} else {right mid - 1;}}return (int)ans;}
}5. 有效的完全平方数题目链接367. 有效的完全平方数 - 力扣LeetCode给你一个正整数 num 。如果 num 是一个完全平方数则返回 true 否则返回 false 。完全平方数 是一个可以写成某个整数的平方的整数。换句话说它可以写成某个整数和自身的乘积。不能使用任何内置的库函数如 sqrt 。示例 1输入num 16输出true解释返回 true 因为 4 * 4 16 且 4 是一个整数。示例 2输入num 14输出false解释返回 false 因为 3.742 * 3.742 14 但 3.742 不是一个整数。提示1 num 231 - 1class Solution {public boolean isPerfectSquare(int num) {int left 0, right num;while(left right) {int mid left (right - left)/2;long square (long)mid*mid;if(square num) {right mid - 1;} else if(square num) {left mid 1;} else {return true;}}return false;}
}
