临海市城市建设规划局网站,wordpress首页显示一张图片,wordpress风格化页面,新塘网站seo优化本系列为笔者的 Leetcode 刷题记录#xff0c;顺序为 Hot 100 题官方顺序#xff0c;根据标签命名#xff0c;记录笔者总结的做题思路#xff0c;附部分代码解释和疑问解答#xff0c;01~07为C语言#xff0c;08及以后为Java语言。
01 搜索插入位置 class Solution {pub…本系列为笔者的 Leetcode 刷题记录顺序为 Hot 100 题官方顺序根据标签命名记录笔者总结的做题思路附部分代码解释和疑问解答01~07为C语言08及以后为Java语言。
01 搜索插入位置 class Solution {public int searchInsert(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right){int mid (left right) / 2;if(nums[mid] target){return mid;}else if(nums[mid] target){left mid 1;}else{right mid - 1;}}return left;}
}02 搜索二维矩阵 class Solution {public boolean searchMatrix(int[][] matrix, int target) {//思路将二维数组展开为一维数组int row matrix.length;int column matrix[0].length;int left 0;int right row * column - 1;while(left right){int mid (left right) / 2;int x matrix[mid / column][mid % column];if(x target){return true;}else if(x target){left mid 1;}else{right mid - 1;}}return false;}
}03 在排序数组中查找元素的第一个和最后一个位置 class Solution {public int[] searchRange(int[] nums, int target) {int[] positions new int[]{-1, -1};int left1 0, left2 0;int right1 nums.length-1, right2 nums.length-1;//寻找第一个等于target的位置while(left1 right1){int mid1 (left1 right1) / 2;if(nums[mid1] target){positions[0] mid1;right1 mid1 - 1; //重点}else if(nums[mid1] target){left1 mid1 1;}else{right1 mid1 - 1;}}//寻找最后一个等于target的位置while(left2 right2){int mid2 (left2 right2) / 2;if(nums[mid2] target){positions[1] mid2;left2 mid2 1; //重点}else if(nums[mid2] target){left2 mid2 1;}else{right2 mid2 - 1;}}return positions;}
}第一个重点确保了即使找到目标值也会继续向左搜索以确保找到第一个出现的索引。
第二个重点确保了即使找到目标值也会继续向右搜索以确保找到最后一个出现的索引。
04 搜索旋转排序数组 ⭐ class Solution {public int search(int[] nums, int target) {int n nums.length;//特殊情况判断if(n 0){return -1;}if(n 1){return nums[0] target ? 0 : -1;}int left 0;int right n - 1;while(left right){int mid (left right) / 2;if(nums[mid] target){return mid;}else if(nums[0] nums[mid]){ //大山峰、小山峰if(nums[0] target target nums[mid]){right mid - 1;}else{left mid 1;}}else{ //小山峰、大山峰if(nums[mid] target target nums[n - 1]){left mid 1;}else{right mid - 1;}}}return -1;}
}05 寻找旋转排序数组中的最小值 class Solution {public int findMin(int[] nums) {int n nums.length;//特殊情况判断if(n 1){return nums[0];}int left 0;int right n - 1;int flag nums[0];while(left right){int mid (left right) / 2;flag nums[mid] flag ? nums[mid] : flag;if(nums[0] nums[mid]){ //大山峰、小山峰left mid 1;}else{ //小山峰、大山峰right mid - 1;}}return flag;}
}06 寻找两个正序数组的中位数 如果对时间复杂度的要求有log通常都需要用到二分查找。
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int m nums1.length, n nums2.length;int numsLength m n;if(numsLength % 2 1){int mid numsLength / 2 1;double ans myFunction(nums1, nums2, mid); //寻找第k小的数return ans;}else{int mid1 numsLength / 2;int mid2 numsLength / 2 1;double ans (myFunction(nums1, nums2, mid1) myFunction(nums1, nums2, mid2)) / 2.0;return ans;}}public int myFunction(int[] nums1, int[] nums2, int k){int m nums1.length, n nums2.length;int index1 0, index2 0;while(true){//特殊情况判断if(index1 m){return nums2[index2 k - 1];}if(index2 n){return nums1[index1 k - 1];}if(k 1){return Math.min(nums1[index1], nums2[index2]);}int half k / 2;int newIndex1 Math.min(index1 half, m) - 1;int newIndex2 Math.min(index2 half, n) - 1;int pivot1 nums1[newIndex1];int pivot2 nums2[newIndex2];//重点if(pivot1 pivot2){k - (newIndex1 - index1 1);index1 newIndex1 1;}else{k - (newIndex2 - index2 1);index2 newIndex2 1;}}}
}
