2024-05-26-代码随想录-Day1-数组

other

Posted by berlinfog on May 26, 2024

数组

链接

主页:https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
计划:【腾讯文档】代码随想录算法训练营31期
数组part01

Task

数组理论基础,704. 二分查找,27. 移除元素

详细布置

数组理论基础

文章链接:https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

题目建议: 了解一下数组基础,以及数组的内存空间地址,数组也没那么简单。

704. 二分查找

题目建议: 大家能把 704 掌握就可以,35.搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置 ,如果有时间就去看一下,没时间可以先不看,二刷的时候在看。

先把 704写熟练,要熟悉 根据 左闭右开,左闭右闭 两种区间规则 写出来的二分法。

题目链接:https://leetcode.cn/problems/binary-search/
文章讲解:https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
视频讲解:https://www.bilibili.com/video/BV1fA4y1o715

func search(nums []int, target int) int {
    l,r := 0, len(nums)-1
    for l <= r{
        m := (r - l)/2 + l
        if nums[m] == target{
            return m
        }else if nums[m] >target{
            r = m - 1
        }else{
            l = m + 1
        }

    }
    return -1
}

27. 移除元素

题目建议: 暴力的解法,可以锻炼一下我们的代码实现能力,建议先把暴力写法写一遍。 双指针法 是本题的精髓,今日需要掌握,至于拓展题目可以先不看。

题目链接:https://leetcode.cn/problems/remove-element/
文章讲解:https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解:https://www.bilibili.com/video/BV12A4y1Z7LP

暴力

func removeElement(nums []int, val int) int {
    var num int = len(nums)
    for i := 0 ; i < num ; i++{
        if(nums[i] == val){
            for j := i ; j < len(nums)-1; j++{
                nums[j] = nums[j+1]
                nums[j+1] = -1
            }
            i--
            num--
        }
    }
    return num
}

快慢指针

func removeElement(nums []int, val int) int {
    slow := 0
    for fast := 0; fast < len(nums); fast++{
        if val != nums[fast]{
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}