wordpress制作网站步骤,电商网站建设公司排名,jquery网站模板下载,怎么注册一个空壳公司提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、704. 二分查找二、35. 搜索插入位置三、34. 在排序数组中查找元素的第一个和最后一个位置四、69. x 的平方根五、367. 有效的完全平方数六、27. 移除元素七… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、704. 二分查找二、35. 搜索插入位置三、34. 在排序数组中查找元素的第一个和最后一个位置四、69. x 的平方根五、367. 有效的完全平方数六、27. 移除元素七、26. 删除有序数组中的重复项八、283. 移动零九、844. 比较含退格的字符串十、977. 有序数组的平方 前言
使用左闭右闭区间的二分查找时 最后low一定是被查找元素的插入位置若查找的数带小数low-1 便是最终结果
一、704. 二分查找
1、左闭右闭
class Solution {public int search(int[] nums, int target) {int low 0, high nums.length-1, mid 0;while(low high){mid (low high)/2;if(nums[mid] target){return mid;}else if(nums[mid] target){low mid 1;}else{high mid - 1;}}return -1;}
}2、左闭右开
class Solution {public int search(int[] nums, int target) {int low 0, high nums.length, mid 0;while(low high){mid (low high)/2;if(nums[mid] target){return mid;}else if(nums[mid] target){low mid 1;}else{high mid;}}return -1;}
}二、35. 搜索插入位置
class Solution {public int searchInsert(int[] nums, int target) {int low 0, high nums.length, mid;while(low high){mid (low high)/2;if(nums[mid] target){return mid;}else if(nums[mid] target){low mid 1;}else{high mid;}}return low;}
}三、34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {public int[] searchRange(int[] nums, int target) {int low 0, high nums.length, mid; int[] res {-1, -1};while(low high){mid (low high)/2;if(nums[mid] target){res[0] res[1] mid;while(res[0]-1 0 nums[res[0] - 1] target){res[0] - 1;}while(res[1] 1 nums.length nums[res[1] 1] target){res[1] 1;}return res;}else if(nums[mid] target){low mid 1;}else{high mid;}}return res;}
}四、69. x 的平方根
class Solution {public int mySqrt(int x) {int low 0, high x, mid;if(x 0 || x 1){return x;}while(low high){mid (low high)/2;if(x / mid mid){return mid;}else if(x / mid mid){low mid 1;}else{high mid -1;}}return low - 1;}
}五、367. 有效的完全平方数
lass Solution {public boolean isPerfectSquare(int num) {int x 1;while(num 0){num - x;x 2;}return num 0;}
}六、27. 移除元素
class Solution {public int removeElement(int[] nums, int val) {int i 0, j 0;for(;i nums.length; ){if(nums[i] ! val){nums[j] nums[i];i ; j ;}else{i ;}}return j;}
}七、26. 删除有序数组中的重复项
class Solution {public int removeDuplicates(int[] nums) {if(nums.length 1){return 1;}int i 1, j 0;for(; i nums.length; ){if(nums[i] ! nums[j]){nums[j] nums[i];}else{i ;}}return j 1;}
}八、283. 移动零
class Solution {public void moveZeroes(int[] nums) {int i 0, j 0, len nums.length;if(len 1)return;while(i len){if(nums[i] ! 0){nums[j] nums[i];if(i j){i ;}else{nums[i] 0;}j ;}else{i ;}}}
}九、844. 比较含退格的字符串
class Solution {public boolean backspaceCompare(String s, String t) {DequeCharacter deq1 new ArrayDeque();DequeCharacter deq2 new ArrayDeque();char[] ch1 s.toCharArray();char[] ch2 t.toCharArray();for(int i 0; i ch1.length; i ){if(ch1[i] ! #){deq1.offerFirst(ch1[i]);}else if(!deq1.isEmpty()){deq1.pollFirst();}}for(int j 0; j ch2.length; j ){if(ch2[j] ! #){deq2.offerFirst(ch2[j]);}else if(!deq2.isEmpty()){deq2.pollFirst();}}while(!deq1.isEmpty() !deq2.isEmpty()){char c1 deq1.pollFirst();char c2 deq2.pollFirst();if(c1 ! c2){return false;}}return deq1.isEmpty() deq2.isEmpty();}
}十、977. 有序数组的平方
class Solution {public int[] sortedSquares(int[] nums) {DequeInteger deq1 new LinkedList();DequeInteger deq2 new LinkedList();for(int i 0; i nums.length; i ){if(nums[i] 0){deq1.offerLast(nums[i] * nums[i]);}else{deq2.offerLast(nums[i] * nums[i]);}}int k 0;while(!deq1.isEmpty() !deq2.isEmpty()){if(deq1.peekLast() deq2.peekFirst()){nums[k ] deq1.pollLast();}else{nums[k ] deq2.pollFirst();}}while(!deq1.isEmpty()){nums[k ] deq1.pollLast();}while(!deq2.isEmpty()){nums[k ] deq2.pollFirst();}return nums;}
}
