首页 > 编程语言 >代码随想录算法训练营第一天| LeetCode704 二分查找,LeetCode35,LeetCode34,leetcode27.移除元素

代码随想录算法训练营第一天| LeetCode704 二分查找,LeetCode35,LeetCode34,leetcode27.移除元素

时间:2024-01-17 19:34:10浏览次数:45  
标签:right target LeetCode704 int nums 随想录 middle 移除 left

LeetCode704题目链接:704. 二分查找 - 力扣(LeetCode)

第一时间的想法:

  简单来说,二分法给我的印象就是想一条绳子上打很多的结,每次对折正好是一个结点,我们需要找到想要的结点比如(a)代码思路就是不断对折一直到绳子两端重合中间没有结点,最后剩下的就是要找的结点a了。

        所以要使用是while循环来判断两端结点  数组左右闭区间(left<=right),左闭右开或者左开右闭就没有等于,每次中间值就等于两端之和的一半,当中间值在目标左边时,说明中间值比目标小,必须更改区间来往目标值靠近,所以要将左区间改为middle值的下一位。以此类推,在右边也是一样,当middle值和目标值一样时,直接输出即可。当left=right时,循环结束,还没找到说明目标值不存在,输出-1,

左闭右闭区间代码:

class Solution {
    public int search(int[] nums, int target) {
        
        int left=0;
        int right = nums.length-1;
        while(left<=right){
            int middle=left+(right-left)/2;
            if(nums[middle]<target){
                left = middle+1;
            }
            else if(nums[middle]>target){
                right = middle-1;
            }
            else
            return middle;
        }
        return -1;
    }
       
    
}

 左开右闭区间代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right)
        while (left < right) { // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间,在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间,在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

LeetCode35题目链接:35. 搜索插入位置 - 力扣(LeetCode)

思路:简单,不说了。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int index=0;
        for(int i =0;i<nums.length;i++){
            if(nums[i]<target){
                index++;
            }
            
        }
        return index;
        
    
}
}

LeetCode27题目链接:27. 移除元素 - 力扣(LeetCode)

思路:用循环判断与val相同,相同跳过,不同后边取代前边实现移除;

一,暴力破解(双层for循环)

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};

二,双指针操作:

思路,慢指针充当index,快指针判断是否与val一致,不一致就是新数组要的。

class Solution {
    public int removeElement(int[] nums, int val) {
      int slow=0;
      for(int fast=0;fast<nums.length;fast++){
          if(nums[fast]!=val){
              nums[slow]=nums[fast];
              slow++;
          }
      }
      return slow;
}
}

 

标签:right,target,LeetCode704,int,nums,随想录,middle,移除,left
From: https://www.cnblogs.com/lengbo/p/17958909

相关文章

  • [代码随想录] 第七天
    344.翻转字符串[https://leetcode.cn/problems/reverse-string/submissions/496111203/]思路:类似于原地翻转数组,左指针右指针向中间靠拢,交换对应元素。classSolution{publicvoidreverseString(char[]s){intleft=0;intright=s.length-1;......
  • 代码随想录 day21 二叉搜索树的最小绝对差 二叉搜索树中的众数 二叉树的最近公共祖先
    二叉搜索树的最小绝对差二叉搜索树就是有序数组那么转换一下就很简单了也可以直接在遍历二叉搜索树的时候进行比较需要一个指针记录前一个节点二叉搜索树中的众数既可以把这题的二叉搜索树当成一般树来做这样就是层序遍历树然后用map记录频率再取频率最高的值这里用......
  • [代码随想录] 第六天
    383.赎金信https://leetcode.cn/problems/ransom-note/description/思路:本题与242.有效的字母异位词几乎相同。将字母-'a',变成0-26的数字存放于数组中,再遍历数组对比次数。classSolution{publicbooleancanConstruct(StringransomNote,Stringmagazine){in......
  • [FAQ] Docker查询出所有的停止容器并移除
     $ dockerrm`dockercontainerls-a--filter"status=exited"|awk'{print$1}'|sed'1,1d'|xargs` Ref:phvia/dkcRef:[Shell]字符截取命令:cut,printf,awk,sedRef:使用nodejs的puppeteer库使用完关闭后,linux上面有很多chrome进程Link:https......
  • 代码随想录 day20 最大二叉树 合并二叉树 二叉搜索树中的搜索 验证二叉搜索树
    最大二叉树前序遍历递归效率不高因为每次都要新开数组给左右子树可以在同一个数组上做这个事情合并二叉树一开始不知道怎么同时遍历两棵树其实只要同时传入两棵树的节点就可以了这里判断两棵树谁空就另外一个作为构造树全为空那就会构造空节点二叉搜索树中的搜索......
  • [代码随想录] 第五天
    242.有效的字母异位词https://leetcode.cn/problems/valid-anagram/description/思路:做一个基础版哈希表,哈希函数为key-'a',这样两个字符串的每个字母都会映射在26长的数组中,使用数组自增记录字母出现次数。classSolution{publicbooleanisAnagram(Strings,Stringt){......
  • #yyds干货盘点# LeetCode程序员面试金典:移除盒子
    题目给出一些不同颜色的盒子boxes,盒子的颜色由不同的正数表示。你将经过若干轮操作去去掉盒子,直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续k个盒子(k>=1),这样一轮之后你将得到k*k个积分。返回你能获得的最大积分和。 示例1:输入:boxes=[1,3,2,......
  • 吴师兄学算法day06 双指针 27. 移除元素
    题目:27. 移除元素易错点:差点猛住了,可以用pass顺着逻辑来识别代码示例:classSolution:defremoveElement(self,nums:List[int],val:int)->int:slow=0forfastinrange(len(nums)):ifnums[fast]==val:#删除......
  • [刷题班] LeetCode27. 移除元素
    题目描述思路:快慢指针slow指针:其前面都是数值不等于val的元素。fast指针:用于遍历。方法一:classSolution{publicintremoveElement(int[]nums,intval){intslow=0,fast=0;for(;fast<nums.length;fast++){if(nums[fas......
  • 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
    找树左下角的值最简单就是想到层序遍历之后取第一个位置元素就是了递归的话需要先判断哪里最深的节点至于最左保持中左右的遍历顺序第一次得到最大深度处就是最左的路径总和有点像查找子树路径所以递归回溯是比较好的选择在求路径的适合,targetSum-node->val是否为......