LeetCode中级算法-排序和搜索（1）
LeetCode中级算法-排序和搜索（1）
颜色分类
[题目]
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
[输入1]
nums = [2,0,1]
[返回1]
[0,1,2]
[输入2]
nums = [2,0,2,1,1,0]
[返回2]
[0,0,1,1,2,2]
[解法1]
使用一个指针，遍历两遍数组，第一遍遍历将数组中所有的0交换到数组的开头，记录一个targetIndex为当前替换到了哪个位置，第二遍遍历的时候，从上一次的targetIndex开始，将数组中所有的1从这个位置开始交换
[代码实现1]
func computeResult(input []int) []int {
// 首先将所有的0交换到最前面
targetIndex, input := _compute(input, 0, 0)
// 然后将1接着targetIndex放置
_, input = _compute(input, 1, targetIndex)
return input
}
func _compute(input []int, target int, targetIndex int) (int, []int) {
for i := 0; i len(input); i++ {
if input[i] == target {
input[i], input[targetIndex] = input[targetIndex], input[i]
targetIndex++
}
}
return targetIndex, input
}[解法2]
使用两个指针，分别遍历0和2的元素，将0交换到数组的开头位置，将2交换到数组结尾的位置
[代码实现2]
func computeResult2(input []int) []int {
targetStartIndex := 0
targetEndIndex := len(input) - 1
for i := 0; i len(input); i++ {
if input[i] == 0 {
input[i], input[targetStartIndex] = input[targetStartIndex], input[i]
targetStartIndex++
} else if input[i] == 2 {
input[i], input[targetEndIndex] = input[targetEndIndex], input[i]
targetEndIndex--
}
}
return input
}[代码测试]
package main
import fmt
func main() {
//input := []int {2,0,2,1,1,0}
input := []int {2, 0, 1}
result := computeResult(input)
fmt.Println(result:, result)
result2 := computeResult2(input)
fmt.Println(result2:, result2)
}前 K 个高频元素
[题目]
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
[输入1]
nums = [1,1,1,2,2,3], k = 2
[返回1]
[1,2]
[输入2]
nums = [1], k = 1
[返回2]
[1]
[解法]
首先遍历一遍数组，按照key-value存储每个元素出现的次数，key为元素，value是该元素出现的次数，遍历完成之后，建立一个小顶堆，golang中小顶堆的建立可以使用heap.Init，遍历元素出现次数的map，将[key, value]的数组加入到小顶堆中，当小顶堆中元素超过k的时候，就弹出堆顶的元素，直到将整个map遍历完毕
[代码实现]
package main
import (
container/heap
fmt
)
func main() {
input := []int {1,1,1,2,2,3}
result := computeResult(input, 2)
fmt.Println(result:, result)
}
func computeResult(input []int, k int) []int {
filter := map[int]int {}
for i := 0; i len(input); i++ {
if _, exists := filter[input[i]]; exists {
filter[input[i]] += 1
} else {
filter[input[i]] = 1
}
}
h := IHeap{}
heap.Init(h)
for key, value := range filter {
heap.Push(h, [2]int{key, value})
if h.Len() k {
heap.Pop(h)
}
}
result := make([]int, k)
// 小顶堆是最小的在最上面，最先被Pop出来
for i := 0; i k; i++ {
result[k - i - 1] = heap.Pop(h).([2]int)[0]
}
return result
}
type IHeap struct {
items [][2]int
}
func (h *IHeap) Push(x interface{}) {
h.items = append(h.items, x.([2]int))
}
func (h *IHeap) Len() int {
return len(h.items)
}
// 构建小顶堆
func (h *IHeap) Less(i, j int) bool {
return h.items[i][1] h.items[j][1]
}
func (h *IHeap) Swap(i, j int) {
h.items[i], h.items[j] = h.items[j], h.items[i]
}
func (h *IHeap) Pop() interface{} {
n := h.Len()
item := h.items[n - 1]
h.items = h.items[0: n - 1]
return item
}寻找峰值
[题目]
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
[输入1]
nums = [1,2,3,1]
[返回1]
2
[输入2]
nums = [1,2,1,3,5,6,4]
[返回2]
1 或 5
[解法]
因为题目中只需要返回一个，那么我们可以使用类似二叉树遍历，需要注意下面都是mid + 1，这是因为整数除以2，会向下取整，e.g. (2 + 3) / 2 = 2。算法的复杂度为O(logn)
[代码实现]
package main
import fmt
func main() {
input := []int {1,2,1,3,5,6,4}
result := computeResult(input)
fmt.Println(result:, result)
}
func computeResult(input []int) int {
left := 0
right := len(input) - 1
for left right {
mid := (left + right) / 2
if input[mid] input[mid + 1] {
right = mid
} else {
left = mid + 1
}
}
return left
}在排序数组中查找元素的第一个和最后一个位置
[题目]
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
[输入1]
nums = [5,7,7,8,8,10], target = 8
[返回1]
[3,4]
[输入2]
nums = [5,7,7,8,8,10], target = 6
[返回2]
[-1,-1]
[解法]
排序好的数组，使用二分查找，向前计算开头元素的下标。注意计算尾部下标的时候，可以计算target + 1元素的首个下标，这个下标减去1，就是target尾部下标
[代码实现]
package main
import fmt
func main() {
input := []int {5,7,7,8,8,10}
target := 8
result := computeResult(target, input)
fmt.Println(result:, result)
}
func computeResult(target int, input []int) []int {
before := beforeIndex(target, input)
after := beforeIndex(target + 1, input)
if after == -1 {
after = before
}
return []int { before, after }
}
func beforeIndex(target int, input []int) int {
left := 0
right := len(input) - 1
for left right {
mid := (left + right) / 2
if target == input[mid] {
return mid
} else if target input[mid] {
left = mid + 1
} else {
right = mid + 1
}
}
return -1
}
LeetCode中级算法-排序和搜索（1） 相关文章
- LeetCode中级算法-动态规划
跳跃游戏 [题目] 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。 [输入1] [2,3,1,1,4] [返回1] true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位
- LeetCode中级算法-数学（1）
快乐数 [题目] 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐
- Angel图神经网络算法在推荐场景下的实践
分享嘉宾：孙瑞鸿?腾讯大数据 编辑整理：赵文娇 出品平台：DataFunTalk、AI启蒙者 导读： 随着数据多样性的发展，图计算已经成为业界的一个重要的研究方向，其中图神经网络广泛应用于图的表征学习，与传统的图学习相比，既能学习图网络的拓扑结构，也能聚合
- 贪心算法：我要监控二叉树！
一路跟着「代码随想录」刷题的录友们，二叉树是不是都快忘了，哈哈，反正我讲过的内容我就默认大家都会了，来来来，本题是二叉树上的贪心。需要重温二叉树的录友，传送门： leetcode刷题最强指南（版本1.0） 通知： 一些录友表示经常看不到每天的文章，现在
- LeetCode中级算法-数学（2）
Pow(x, n) [题目] 实现 pow(x, n) ，即计算 x 的 n 次幂函数。 [输入1] 2.00000, 10 [返回1] 1024.00000 [输入2] 2.10000, 3 [返回2] 9.26100 [输入3] 2.00000, -2 [返回3] 0.25000 [解法] 无 [代码实现] package mainimport fmtfunc main() { input := floa
- Angel推荐算法在游戏推荐中的应用
文章作者：王培军?腾讯 高级工程师 整理编辑：李沛欣 出品平台：DataFunTalk、AI启蒙者 导读： Angel是腾讯自研的分布式高性能的机器学习平台，支持机器学习、深度学习、图计算以及联邦学习等场景。Angel的深度学习平台已应用在腾讯的很多个场景中。本次分享
- 计算机算法的五个特性是什么
计算机算法的五个特性是：1、有穷性，算法必须能在执行有限个步骤之后终止；2、确切性，算法的每一步骤必须有确切的定义；3、输入项，一个算法有0个或多个输入；4、输出项，一个算法有一个或多个输出；5、可行性，每个计算步骤都可以在有限时间内完成。 算法
- 一个算法示例：PHP实现开心消消乐
本文主要介绍了关于PHP如何实现我们大家都知道的开心消消乐的算法。 推荐：《PHP视频教程》 一、需求描述： 1、在一个8*8的矩阵方格中随机出现5种颜色的色块。 2、当有三个或以上色块在横向或纵向上相连，则消除这些色块。 3、色块消除后，上方色块往下平移，
- LRU算法的实现
缘由：看到redis的缓存淘汰机制，便自己实现了一下 代码实现（双向链表+HashMap） package com.jarjune.jdalao.framework.algorithm;import java.util.*;/** * LRU * @author jarjune * @version 1.0.1 * @date 2020/11/19 */public class LRUCacheK, V { //
- 拉斯维加斯算法之n后问题
1、拉斯维加斯(Las Vegas)算法 舍伍德算法优点在于计算时间复杂度对所有实例相对均匀，但与其相应的确定性算法相比，其平均时间复杂度没有改进。拉斯维加斯算法则不然，它能显著改进算法的有效性，甚至对某些迄今为止找不到有效算法的问题，也能得到满意的算