快速排序
AcWing 785. 快速排序
基础型:给一个数组快排
算法流程:
- 输入要排序的数组的左右两端l, r(如果数组不是全局的,也要输入)
- 终止条件为 $l <= r$
- 选取主元,这里用中值x := nums[l + (r - l) >> 1]
。还有另外一种选取主元的方法:随机选取数组中其中一个值,这方法可用在数据更加不等概览的情况
- 准备要从数组范围外入场的左右指针 i, j := l - 1, r + 1
- 在i, j相遇之前,在数组相向移动。其中当i指着的nums[i] >= x,马上停下;j指着的nums[j] <= x, 马上停下
- 在满足i < j下,交换nums[i], nums[j]
- 递归(l, j)
- 递归(j + 1, r)
func quickSort(nums []int, l, r int) { // 核心:快排
if l >= r { return } // 终止条件
x := nums[l + (r - l) >> 1] // 选取“中”值
i, j := l - 1, r + 1 // 左右指针入场准备
for i < j {
for {
i++
if nums[i] >= x { break } // 左指针 i 一直往右扫,直到第一次遇到 >= x ,停下
}
for {
j--
if nums[j] <= x { break } // 右指针 j 一直往左扫,直到第一次遇到 <= x ,停下
}
if i < j { nums[i], nums[j] = nums[j], nums[i] } // 当 i < j 仍满足,互换
}
quickSort(nums, l, j) // 递归处理左半段
quickSort(nums, j + 1, r) // 递归处理右半段
}
以上的是把数组按从小到大排序
如果想要从大到小排序
只需要把其中的这样改:
for i < j {
for {
i++
if nums[i] <= x {break} // 修改位置1
}
for {
j++
if nums[j] >= x {break} // 修改位置2
}
}
就能实现,效果
AcWing 786. 第k个数
是快速排序的一种应用,叫快速选择
也许不用把整个数组排序完就能选出第k大的数
关键是如何写k在左半数组递归或者在右半数组递归
func quickSort(l, r, K int) int { // 核心:快速选择
if l >= r { return nums[l] } // 当停止递归时,K就是左边界
x := nums[l + (r - l) >> 1]
i, j := l - 1, r + 1
for i < j {
for { i++; if nums[i] >= x { break } }
for { j--; if nums[j] <= x { break } }
if i < j { nums[i], nums[j] = nums[j], nums[i] }
}
if j - l + 1 >= K {
return quickSort(l, j, K) // 第K小的数在左边,下次递归左边
} else {
return quickSort(j + 1, r, K - (j - l + 1)) // 第K小的数在右边,下次递归右边
}
}
归并排序
AcWing 787. 归并排序
基础型:给一个数组归并排序
另外一种只用分治的排序算法
与快速排序的不同:
- 归并要使用额外的临时数组,快排不用
- 归并先分治再处理本层逻辑,而快排相反
- 归并用数组下标的中值划分数组,而快排可以使用数组下标的中值的值甚至是数组任一个值来划分数组
算法流程:
- 输入要排序的数组的左右两端l, r(如果数组不是全局的,也要输入)
- 终止条件为 $l <= r$
- 计算数组下标中值mid := l + (r - l) >> 1
- 用mid为标,先递归处理数组的左半(l, mid)以及右半(mid + 1, r)
- 准备3个指针k, i, j := 0, l, mid + 1
,其中k是临时数组tmp的指针,i是待排序数组的左半指针,j是待排序数组的右半指针
- i向mid移动, j向r移动。其中,如果arr[i] <= arr[j],arr[i]进tmp数组,k递增;反之就是arr[j]进tmp数组
- i没还没到mid,继续移动,arr[i]进tmp数组,k递增
- j没还没到r,继续移动,arr[j]进tmp数组,k递增
- 最后把tmp数组复制进arr数组
func mergeSort(l, r int) { // 核心:归并排序
if l >= r { return }
mid := l + (r - l) >> 1
mergeSort(l, mid)
mergeSort(mid + 1, r)
k, i, j := 0, l, mid + 1
for i <= mid && j <= r {
if nums[i] <= nums[j] {
tmp[k] = nums[i]
k += 1; i += 1
} else {
tmp[k] = nums[j]
k += 1; j += 1
}
}
for i <= mid { // 如果左边还有剩,继续放
tmp[k] = nums[i]
k += 1; i += 1
}
for j <= r { // 如果右边还有剩,继续放
tmp[k] = nums[j]
k += 1; j += 1
}
for i, j := l, 0; i <= r; i, j = i + 1, j + 1 { nums[i] = tmp[j] } // 把临时数组里的数据复制回数组
}
AcWing 788. 逆序对的数量
这是归并排序的一种应用
在完成对数组排序的同时,顺手统计出逆序对,就是当nums[i] > nums[j] res = mid + 1 - i
func mergeSort(l, r int) (res int64) {
if l >= r { return 0 }
mid := l + (r - l) >> 1
res = mergeSort(l, mid) + mergeSort(mid + 1, r)
k, i, j := 0, l, mid + 1
for i <= mid && j <= r {
if nums[i] <= nums[j] {
tmp[k] = nums[i]
k += 1; i += 1
} else {
res += int64(mid - i + 1)
tmp[k] = nums[j]
k += 1; j += 1
}
}
for i <= mid {
tmp[k] = nums[i]
k += 1; i += 1
}
for j <= r {
tmp[k] = nums[j]
k += 1; j += 1
}
for a, b := l, 0; a <= r; a, b = a + 1, b + 1 { nums[a] = tmp[b] }
return
}
二分
AcWing 789. 数的范围
二分查找的模板题
题目的意思:
- 开始:找到第一个>=target的数的下标
- 结尾:找到最后一个<=target的数的下标
就是找两次
在找开始时,注意其查找范围和条件
left, right := 0, n // 正常范围[0 ... n - 1] + 找不到的[n] => 查找范围[0 ... n]
for left < right {
mid := left + (right - left) >> 1
if arr[mid] >= target { // 条件
right = mid // 大于target,自然是【右边】
} else {
left = mid + 1
}
}
return right // right是答案
同样的,找结束时,也要注意其查找范围和条件
left, right := -1, n - 1 // 找不到的[-1] + 正常范围[0 ... n - 1] => 查找范围[-1 ... n - 1]
for left < right {
mid := left + (right - left) + 1 >> 1 // 要加1
if arr[mid] <= target { // 条件
left = mid // 小于target,自然是在左边
} else {
right = mid - 1
}
}
return right // right是答案
代码模板
func mySearch(x int) []int {
ans := []int{}
l, r := 0, n // [0...n - 1] + [n] 找开始
for l < r {
mid := l + (r - l) >> 1
if nums[mid] >= x {
r = mid
} else { l = mid + 1 }
}
ans = append(ans, r)
l, r = -1, n - 1 // [-1] + [0...n - 1] 找结尾
for l < r {
mid := l + (r - l) + 1 >> 1
if nums[mid] <= x {
l = mid
} else { r = mid - 1 }
}
ans = append(ans, r)
if ans[0] > ans[1] { return []int{-1, -1} }
return ans
}
AcWing 790. 数的三次方根
浮点数的二分
这题直接是二分查找
只是因为题目要求使用浮点数,用go写的话需注意一下细节:
- 不能使用 >> 1
,只能 / 2
- 记得转化类型float64
- 题目要求保留小数点后6位,那么计算过程中的精度要在$10^{-8}$【经验之谈】,用代码表示就是1e-8
package main
import "fmt"
func main() {
var n, l, r, mid float64
fmt.Scan(&n)
l, r = -100, 100
for r - l > 1e-8 { // 为保证结果能有.6精度,计算过程中得有.8精度
mid = l + (r - l) / 2
if mid * mid * mid >= n {
r = mid
} else {
l = mid
}
}
fmt.Printf("%.6f", l)
}
高精度
func highAdd(numA, numB []int) []int {
ans := []int{}
if len(numA) < len(numB) { return highAdd(numB, numA) }
t := 0 // 当前位数值
for i := 0; i < len(numA); i++ {
t += numA[i]
if i < len(numB) { t += numB[i] }
ans = append(ans, t % 10) // 当前位数值
t /= 10 // 进位
}
if t > 0 { ans = append(ans, t) }
return ans
}
func cmp(numA, numB []int) bool { // 判断两数谁大
if len(numA) != len(numB) { return len(numA) > len(numB) } // 比谁的数位大
for i := len(numA) - 1; i >= 0; i-- { // 从高位开始比
if numA[i] != numB[i] { return numA[i] > numB[i] } // 从高位过来的每一位谁大
}
return true
}
func highMinus(numA, numB []int) []int { // 核心:高精度减法 出正数的
ans := []int{}
t := 0
for i := 0; i < len(numA); i++ {
t = numA[i] - t
if i < len(numB) { t -= numB[i] }
ans = append(ans, (t + 10) % 10)
if t < 0 { // 不够减了
t = 1 // 向前借位
} else { t = 0 } // 不用借
}
for len(ans) > 1 && ans[len(ans) - 1] == 0 { ans = ans[:len(ans) - 1]} // 去掉前导0
return ans
}
func highMul(numA []int, B int) []int { // 核心:高精度乘法
ans := []int{}
t := 0
for i := 0; i < len(numA) || t != 0; i++ {
if i < len(numA) { t += numA[i] * B }
ans = append(ans, t % 10)
t /= 10
}
for len(ans) > 1 && ans[len(ans) - 1] == 0 { ans = ans[:len(ans) - 1] }
return ans
}
func highDiv(numA []int, B int) ([]int, int) { // 核心:高精度除法
ans, t := []int{}, 0
for i := len(numA) - 1; i >= 0; i-- {
t = t * 10 + numA[i]
ans = append(ans, t / B)
t %= B
}
for i, j := 0, len(ans) - 1; i < j; i, j = i + 1, j - 1 { ans[i], ans[j] = ans[j], ans[i] } // 整个数组反转
for len(ans) > 1 && ans[len(ans) - 1] == 0 { ans = ans[:len(ans) - 1] }
return ans, t
}
前缀和与差分
AcWing 795. 前缀和
一维前缀和
num, s = make([]int, n + 1), make([]int, n + 1)
for i := 1; i <= n; i++ { fmt.Fscan(in, &num[i]) }
s[1] = num[1]
for i := 2; i <= n; i++ { s[i] = s[i - 1] + num[i] }
for i := 1; i <= m; i++ {
fmt.Fscan(in, &l, &r)
fmt.Fprint(out, s[r] - s[l - 1], "\n")
}
AcWing 796. 子矩阵的和
二维前缀和
nums = make([][]int, n + 1)
for i := 0; i <= n; i++ { nums[i] = make([]int, m + 1) }
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
fmt.Fscan(in, &nums[i][j])
nums[i][j] += nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1]
}
}
// for i := 1; i <= n; i++ {
// for j := 1; j <= m; j++ {
// nums[i][j] += nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1]
// }
// }
for ; q > 0; q-- {
fmt.Fscan(in, &x1, &y1, &x2, &y2)
fmt.Fprint(out, nums[x2][y2] - nums[x2][y1 - 1] - nums[x1 - 1][y2] + nums[x1 - 1][y1 - 1], "\n")
}
AcWing 797. 差分
一维差分
nums, B = make([]int, n + 1), make([]int, n + 2)
for i := 1; i <= n; i++ {
fmt.Fscan(in, &nums[i])
B[i] = nums[i] - nums[i - 1]
}
for ; m > 0; m-- {
fmt.Fscan(in, &l, &r, &c)
B[l] += c; B[r + 1] -= c
}
for i := 1; i <= n; i++ {
nums[i] = nums[i - 1] + B[i]
fmt.Fprint(out, nums[i], " ")
}
为了方便与二维差分一起记忆,也准备了以下函数
func diff(x, y, c int) { // 核心操作函数:初始化 + 计算
b[x] += c
b[y + 1] -= c
}
AcWing 798. 差分矩阵
二维差分
以下是二维差分的核心操作,剩下的就要看题目的要求
用二维前缀和能还原至初始矩阵
【牢记】二维差分矩阵是要+2,而且坐标都是从1开始的
func diff(x1, y1, x2, y2, c int) { // 核心:初始化、计算
b[x1][y1] += c
b[x2 + 1][y1] -= c
b[x1][y2 + 1] -= c
b[x2 + 1][y2 + 1] += c
}
双指针算法
核心思路:
先写出暴力写法,找出其中的单调性,用双指针将其优化
基本模板
// 按照输入的内容(字符串)按照空格分割,分行输出,双指针做法
package main
import (
"fmt"
"bufio"
"os"
)
var in = bufio.NewScanner(os.Stdin)
func main() {
in.Scan()
s := in.Text()
for i := 0; i < len(s); i++{
j := i
for j < len(s) && s[j] != ' ' {j++}
for k := i; k < j; k++ {fmt.Printf("%s", string(s[k]))}
fmt.Println()
i = j
}
}
for i, j := 0, 0; i < n; i++ {
s[nums[i]]++
for j < i && s[nums[i]] > 1 { s[nums[j]]--; j++ }
res = max(res, i - j + 1)
}
for i, j := 0, m - 1; i < n; i++ {
for j >= 0 && numA[i] + numB[j] > x { j-- }
if j >= 0 && numA[i] + numB[j] == x { fmt.Println(i, j) }
}
i, j := 0, 0
for i < n && j < m {
if numA[i] == numB[j] { i++ }
j++
}
if i == n {
fmt.Println(ans[0])
} else {
fmt.Println(ans[1])
}
位运算
func cal(a int) (res int) {
for a > 0 {
res++
a -= a & -a
}
return
}
离散化
package main
import (
"bufio"
"fmt"
"os"
"sort"
"strconv"
"strings"
)
type pair struct {
first int
second int
}
var (
n, m int
scanner = bufio.NewScanner(os.Stdin) // 整行读取器
bs = make([]byte, 20000 * 1024)
readLine = func() (res []int) {
scanner.Scan()
l := strings.Split(scanner.Text(), " ")
res = make([]int, len(l))
for i, s := range l {
x, _ := strconv.Atoi(s)
res[i] = x
}
return
}
out = bufio.NewWriter(os.Stdout)
find = func(alls []int, x int) int { // 在离散化数组上查找位置(下标),二分查找
l, r := 0, len(alls) - 1
for l < r {
mid := l + (r - l) >> 1
if alls[mid] >= x {
r = mid
} else {
l = mid + 1
}
}
return r + 1
}
unique = func(a []int) (b []int) { // 给已经排过序的数组去重
j := 0
for i := 0; i < len(a); i = j {
for j < len(a) && a[j] == a[i] { j++ }
b = append(b, a[i])
}
return
}
add = make([]pair, 0) // 数组:pair{x, c}, 把n次的“在位置x存值c的操作”一并处理(存起来)
query = make([]pair, 0) // 数组:pair{l, r}, 把m次的“查[l, r]的区间和的操作”一并处理(存起来)
alls = make([]int, 0) // 离散化数组,存的值是已经排序+去重的[x, l, r]
)
func main() {
scanner.Buffer(bs, len(bs))
cur := readLine()
n, m = cur[0], cur[1]
for i := 0; i < n; i++ {
cur := readLine()
add = append(add, pair{cur[0], cur[1]})
alls = append(alls, cur[0])
}
for i := 0; i < m; i++ {
cur := readLine()
alls = append(alls, cur[0])
alls = append(alls, cur[1])
query = append(query, pair{cur[0], cur[1]})
}
sort.Ints(alls)
alls = unique(alls)
a := make([]int, len(alls) + 1) // 建比离散数组长1的存c的数组
for _, item := range add { // 读取add里的操作指令
x := find(alls, item.first) // 在离散数组上寻址 x
a[x] += item.second // 执行在“x插入c”操作
}
s := make([]int, len(a))
for i := 1; i <= len(alls); i++ { s[i] = s[i - 1] + a[i] } // 生成数组a的前缀和数组
for _, item := range query { // 读取queue里的操作指令
l, r := find(alls, item.first), find(alls, item.second) // 在离散数组上寻址 l, r
fmt.Fprint(out, s[r] - s[l - 1], "\n") // 计算[l, r]的区间和
}
out.Flush()
}
区间合并
func merge(a []pair) int {
max := func(a, b int) int { if a > b { return a }; return b }
sort.Slice(a, func(i, j int) bool {
if a[i].left == a[j].left { return a[i].right < a[j].right }
return a[i].left < a[j].left
})
res := []pair{}
start, end := -1 << 31, -1 << 31
for _, cur := range a {
if end < cur.left {
if start != -1 << 31 { res = append(res, pair{start, end}) }
start = cur.left; end = cur.right
} else { end = max(end, cur.right) } // 延展区间的右边
}
if start != -1 << 31 { res = append(res, pair{start, end}) } // 新开一段
return len(res)
}
func merge(a []enevts) int {
sort.Slice(a, func(i, j int) bool { // 按位置(开始 > 结束)排序
if a[i].ene == a[j].ene { return a[i].effect > a[j].effect }
return a[i].ene < a[j].ene
})
res := []enevts{}
count, left := 0, 0 // count标志当前事件的状态,1:在前面已经开始新的区间, 0:没有开始区间
for _, cur := range a {
if count == 0 { left = cur.ene }
count += cur.effect
if count == 0 { res = append(res, enevts{left, cur.ene}) } // 这里count经历了从0,1,0之后,已经合并好一个区间,把该区间存进res
}
return len(res)
}