Golang每日一练(leetDay0083) 汇总区间、多数元素II

目录

228. 汇总区间 Summary Ranges  🌟

229. 多数元素 II Majority Element ii  🌟🌟

🌟 每日一练刷题专栏 🌟

Rust每日一练 专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

---

228. 汇总区间 Summary Ranges

给定一个  无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

• "a->b" ，如果 a != b
• "a" ，如果 a == b

示例 1：

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

示例 2：

输入：nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

提示：

• 0 <= nums.length <= 20
• -2^31 <= nums[i] <= 2^31 - 1
• nums 中的所有值都 互不相同
• nums 按升序排列

代码1： 暴力枚举

package mainimport ("fmt""strconv"
)func summaryRanges(nums []int) []string {res := []string{}if len(nums) == 0 {return res}i := 0for i < len(nums) {j := ifor j < len(nums)-1 && nums[j+1]-nums[j] == 1 {j++}if i == j {res = append(res, strconv.Itoa(nums[i]))} else {res = append(res, strconv.Itoa(nums[i])+"->"+strconv.Itoa(nums[j]))}i = j + 1}return res
}func main() {nums := []int{0, 1, 2, 4, 5, 7}fmt.Println(summaryRanges(nums))nums = []int{0, 2, 3, 4, 6, 8, 9}fmt.Println(summaryRanges(nums))
}

代码2： 双指针

package mainimport ("fmt""strconv"
)func summaryRanges(nums []int) []string {res := []string{}if len(nums) == 0 {return res}i, j := 0, 0for j < len(nums) {if j < len(nums)-1 && nums[j+1]-nums[j] == 1 {j++} else {if i == j {res = append(res, strconv.Itoa(nums[i]))} else {res = append(res, strconv.Itoa(nums[i])+"->"+strconv.Itoa(nums[j]))}j++i = j}}return res
}func main() {nums := []int{0, 1, 2, 4, 5, 7}fmt.Println(summaryRanges(nums))nums = []int{0, 2, 3, 4, 6, 8, 9}fmt.Println(summaryRanges(nums))
}

代码3： 字符串拼接

package mainimport ("fmt""strconv"
)func summaryRanges(nums []int) []string {res := []string{}if len(nums) == 0 {return res}i, j := 0, 0for j < len(nums) {if j < len(nums)-1 && nums[j+1]-nums[j] == 1 {j++} else {if i == j {res = append(res, strconv.Itoa(nums[i]))} else {res = append(res, fmt.Sprintf("%d->%d", nums[i], nums[j]))}j++i = j}}return res
}func main() {nums := []int{0, 1, 2, 4, 5, 7}fmt.Println(summaryRanges(nums))nums = []int{0, 2, 3, 4, 6, 8, 9}fmt.Println(summaryRanges(nums))
}

代码4： 迭代器

package mainimport ("fmt""strconv"
)func summaryRanges(nums []int) []string {res := []string{}if len(nums) == 0 {return res}iter, i := nums[1:], nums[0]for len(iter) > 0 {if iter[0]-i == 1 {iter, i = iter[1:], iter[0]} else {if i == nums[0] {res = append(res, strconv.Itoa(i))} else {res = append(res, fmt.Sprintf("%d->%d", nums[0], i))}nums, iter, i = iter, iter[1:], iter[0]}}if i == nums[0] {res = append(res, strconv.Itoa(i))} else {res = append(res, fmt.Sprintf("%d->%d", nums[0], i))}return res
}func main() {nums := []int{0, 1, 2, 4, 5, 7}fmt.Println(summaryRanges(nums))nums = []int{0, 2, 3, 4, 6, 8, 9}fmt.Println(summaryRanges(nums))
}

输出：

[0->2 4->5 7]
[0 2->4 6 8->9]

---

229. 多数元素 II Majority Element ii

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

输入：[3,2,3]
输出：[3]

示例 2：

输入：[1]
输出：[1]

示例 3：

输入：[1,2]
输出：[1,2]

提示：

• 1 <= nums.length <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

进阶：

• 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

相关题目：

169. 多数元素 Majority Element  🌟

代码1： 哈希表

package mainimport "fmt"func majorityElement(nums []int) []int {n := len(nums)if n == 0 {return []int{}}res := []int{}count := make(map[int]int)for _, num := range nums {count[num]++}for key, val := range count {if val > n/3 {res = append(res, key)}}return res
}func main() {nums := []int{3, 2, 3}fmt.Println(majorityElement(nums))nums = []int{1}fmt.Println(majorityElement(nums))nums = []int{1, 2}fmt.Println(majorityElement(nums))
}

代码2： 排序

package mainimport ("fmt""sort"
)func majorityElement(nums []int) []int {n := len(nums)if n == 0 {return []int{}}res := []int{}sort.Ints(nums)var num, count intfor i := 0; i < n; i++ {if nums[i] == num {count++} else {if count > n/3 {res = append(res, num)}num, count = nums[i], 1}}if count > n/3 {res = append(res, num)}return res
}func main() {nums := []int{3, 2, 3}fmt.Println(majorityElement(nums))nums = []int{1}fmt.Println(majorityElement(nums))nums = []int{1, 2}fmt.Println(majorityElement(nums))
}

代码3： 摩尔投票法

package mainimport "fmt"func majorityElement(nums []int) []int {n := len(nums)if n == 0 {return []int{}}res := []int{}var num1, num2, count1, count2 intfor _, num := range nums {if num == num1 {count1++} else if num == num2 {count2++} else if count1 == 0 {num1 = numcount1 = 1} else if count2 == 0 {num2 = numcount2 = 1} else {count1--count2--}}count1, count2 = 0, 0for _, num := range nums {if num == num1 {count1++} else if num == num2 {count2++}}if count1 > n/3 {res = append(res, num1)}if count2 > n/3 {res = append(res, num2)}return res
}func main() {nums := []int{3, 2, 3}fmt.Println(majorityElement(nums))nums = []int{1}fmt.Println(majorityElement(nums))nums = []int{1, 2}fmt.Println(majorityElement(nums))
}

输出：

[3]
[1]
[1 2]

---

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/ 

	Rust每日一练 专栏 （2023.5.16~）更新中...
	Golang每日一练 专栏 （2023.3.11~）更新中...
	Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更
	C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更
	Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更