返回总目录 [链接] 26. 删除排序数组中的重复项 题目描述 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 示例 1: 给定数组 nums = [1,1,2], 函数应该返 ..

日刷 leetcode-- 简单版(二)

返回总目录

日刷leetcode–简单版


26. 删除排序数组中的重复项

题目描述

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路

示例代码
func removeDuplicates(nums []int) int {
i := 0
for j :=  1; j < len(nums); j++ {
if nums[i] != nums[j] {
i++
nums[i] = nums[j]
}
}
return i + 1
}
运行结果

执行用时 :100 ms, 在所有 Go 提交中击败了 84.75%的用户
内存消耗 :7.9 MB, 在所有 Go 提交中击败了 66.91%的用户


27. 移除元素

题目描述

给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路

示例代码
func removeElement(nums []int, val int) int {
for i := 0; i < len(nums); i++ {
if nums[i] == val {
nums = append(nums[:i], nums[i+1:]...)
i--
}
}
return len(nums)
}
运行结果

执行用时 :0 ms, 在所有 Go 提交中击败了 100.00%的用户
内存消耗 :2.4 MB, 在所有 Go 提交中击败了 44.67%的用户


28. 实现 strStr()

题目描述

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个 > 位置 (从 0 开始)。如果不存在,则返回 -1。
示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

解题思路

示例代码
func removeElement(nums []int, val int) int {
for i := 0; i < len(nums); i++ {
if nums[i] == val {
nums = append(nums[:i], nums[i+1:]...)
i--
}
}
return len(nums)
}
运行结果

执行用时 :0 ms, 在所有 Go 提交中击败了 100.00%的用户
内存消耗 :2.3 MB, 在所有 Go 提交中击败了 53.10%的用户

35. 搜索插入位置

题目描述

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。
示例 1:

输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1

示例 3:

输入: [1,3,5,6], 7
输出: 4

示例 4:

输入: [1,3,5,6], 0
输出: 0

解题思路

示例代码
func searchInsert(nums []int, target int) int {
l, r := 0, len(nums)
for ; l < r; {
 mid := (l + r) / 2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
l = mid + 1
} else {
r = mid
}
}
return l
}
运行结果

执行用时 :4 ms, 在所有 Go 提交中击败了 97.04%的用户
内存消耗 :3.1 MB, 在所有 Go 提交中击败了 50.79%的用户

38. 报数

题目描述

报数序列是一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:

1.     1
2.     11
3.     21
4.     1211
5.     111221
1 被读作  "one 1"  ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"), 即 21。
21 被读作 "one 2",  "one 1" ("一个二" ,  "一个一") , 即 1211。

给定一个正整数 n(1 ≤ n ≤ 30),输出报数序列的第 n 项。
注意:整数顺序将表示为一个字符串。
示例 1:

输入: 1
输出: "1"

示例 2:

输入: 4
输出: "1211"

解题思路

示例代码
func countStr(n int, str []byte) []byte {
if n == 1 {
return str
}
s := make([]byte, 0, len(str)*2)
this := str[0]
count := 1
for i := 1; i < len(str); i++ {
if this == str[i] {
count++
} else {
s = append(s, byte(count+'0'), this) // count为int型,+'0'相当于+48,得到count对应的ASCII码值
this = str[i]
count = 1
}
}
s = append(s, byte(count+'0'), this)
return countStr(n-1, s)
}
运行结果

执行用时 :0 ms, 在所有 Go 提交中击败了 100.00%的用户
内存消耗 :2.2 MB, 在所有 Go 提交中击败了 50.58%的用户

53. 最大子序列合

题目描述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

解题思路 1

解题思路 2

示例代码
func maxSubArray(nums []int) int {
    return maxSum(nums, 0, len(nums)-1)
}

func maxSum(nums []int, l, r int) int {
    if l == r {
        return nums[l]
    }
    mid := (l + r) / 2
    maxLeft := maxSum(nums, l, mid)
    maxRight := maxSum(nums, mid+1, r)
    lSum, sum := math.MinInt64, 0
    for i := mid; i >= l; i-- {
        sum += nums[i]
        if sum > lSum {
            lSum = sum
        }
    }
    rSum, sum := math.MinInt64, 0
    for i := mid + 1; i <= r; i++ {
        sum += nums[i]
        if sum > rSum {
            rSum = sum
        }
    }
    return max(max(maxLeft, maxRight), lSum+rSum)
}

func max(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

运行结果

执行用时 :8 ms, 在所有 Go 提交中击败了 92.80%的用户

内存消耗 :3.3 MB, 在所有 Go 提交中击败了 73.67%的用户

解题思路 2

假设你是一个选择性遗忘的赌徒,数组表示你这几天来赢钱或者输钱,
你用 sum 来表示这几天来的输赢,
用 ans 来存储你手里赢到的最多的钱,

如果昨天你手上还是输钱(sum < 0),你忘记它,明天继续赌钱;
如果你手上是赢钱(sum > 0), 你记得,你继续赌钱;
你记得你手赢到的最多的钱

示例代码
func maxSubArrays(nums []int) int {
    sum, ans := math.MinInt64, math.MinInt64
    for _,v := range nums {
        if sum > 0 {
            sum += v
        }else{
            sum = v
        }
        if ans < sum {
            ans = sum
        }
    }
    return ans
}
运行结果

执行用时 :4 ms, 在所有 Go 提交中击败了 99.10%的用户
内存消耗 :3.3 MB, 在所有 Go 提交中击败了 80.78%的用户

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    158 引用 • 61 回帖
  • golang

    Go 语言是 Google 推出的一种全新的编程语言,可以在不损失应用程序性能的情况下降低代码的复杂性。谷歌首席软件工程师罗布派克(Rob Pike)说:我们之所以开发 Go,是因为过去 10 多年间软件开发的难度令人沮丧。Go 是谷歌 2009 发布的第二款编程语言。

    319 引用 • 1158 回帖 • 731 关注
回帖   
请输入回帖内容...