提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
使用左闭右闭区间的二分查找时， 最后low一定是被查找元素的插入位置，若查找的数带小数，low-1， 便是最终结果
一、704. 二分查找
1、左闭右闭文章来源：https://www.toymoban.com/news/detail-657723.html
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、左闭右开文章来源地址https://www.toymoban.com/news/detail-657723.html
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) {
Deque<Character> deq1 = new ArrayDeque<>();
Deque<Character> 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) {
Deque<Integer> deq1 = new LinkedList<>();
Deque<Integer> 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;
}
}
到了这里，关于代码随想录二刷day01的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
