算法基础课相关代码模板

活动链接 —— 算法基础课

快速排序算法模板——模板题AcWing 785. 快速排序

func quickSort(q []int, l, r int) {
    if l >= r {
        return 
    }
    
    i, j := l - 1, r + 1
    x := q[l + (r - l) >> 1]
    for i < j {
        for {
            i ++ 
            if q[i] >= x {
                break
            }
        }
        for {
            j -- 
            if q[j] <= x {
                break
            }
        }
        if i < j {
            q[i], q[j] = q[j], q[i]
        }
    }
    
    quickSort(q, l, j)
    quickSort(q, j + 1, r)
}

归并排序算法模板——模板题AcWing 787. 归并排序

func mergeSort(q []int, l, r int) {
    if l >= r {
        return 
    }

    mid := (l + r) >> 1
    tmp := make([]int, r - l + 1)
    mergeSort(q, l, mid)
    mergeSort(q, mid + 1, r)

    k, i, j := 0, l, mid + 1
    for i <= mid && j <= r {
        if q[i] <= q[j] {
            tmp[k] = q[i]
            k ++
            i ++
        } else {
            tmp[k] = q[j] 
            k ++
            j ++
        }
    }

    for i <= mid {
        tmp[k] = q[i] 
        i ++
        k ++
    }
    for j <= r {
        tmp[k] = q[j]
        j ++
        k ++
    }

    i, j = l, 0
    for i <= r {
        q[i] = tmp[j]
        i ++
        j ++
    }
    // fmt.Println(q)
}

整数二分算法模板 —— 模板题 AcWing 789. 数的范围

func check(x int) bool {  // 检查x是否满足某种性质
    // ...
}

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
func bsearch_l(l, r int) {   // 找出最左边满足性质的元素, eg: q[mid] >= k
    for l < r {
        mid := (l + r) >> 1
        if (check(mid)) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}  
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
func bsearch_r(l, r int) {
    for l < r {
        mid := (l + r + 1) >> 1
        if (check(mid)) {
            l = mid 
        } else {
            r = mid - 1
        }
    }
    return l 
}

浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根

func check(x float64) {
    // ... 
}
func bsearch_f(l, r float64) {
    const eps float64 = 1e-6  //eps表示精度，取决于题目对精度的要求
    for r - l > eps {
        mid := (l + r) / 2
        if (check(mid)) {
            r = mid
        } else {
            l = mid
        }
    }
    return l
}

高精度加法 —— 模板题 AcWing 791. 高精度加法

// C = A + B, A >= 0, B >= 0
func add(A, B []int) []int {
    if len(A) < len(B) {
        return add(B, A)
    }
    t := 0
    res := make([]int, 0)
    for i := 0; i < len(A); i ++ {
        t += A[i]
        if i < len(B) {
            t += B[i]
        }
        res = append(res, t%10)
        t /= 10
    }
    if t > 0 {
        res = append(res, t)
    }
    return res
}

高精度减法 —— 模板题 AcWing 792. 高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
func cmp(A, B []int) bool {
    if len(A) != len(B) {
        return len(A) > len(B)
    }
    for i := len(A) - 1; i >= 0; i -- {
        if A[i] != B[i] {
            return A[i] > B[i]
        }
    }
    return true
} 

func sub(A, B []int) []int {
    t := 0
    res := make([]int, 0)
    for i := 0; i < len(A); i ++ {
        t = A[i] - t 
        if i < len(B) {
            t -= B[i]
        }
        res = append(res, (t + 10)%10)   // 这一步
        if t < 0 {
            t = 1
        } else {
            t = 0
        }
    }
    
    i := len(res) - 1     // 防止高位出现 0 ， 把高位的0全都去掉。 
    for ; i > 0 && res[i] == 0; i -- {
        
    }
    return res[:i + 1]  // 如果全是0 ，会保留个位上的0
   	
}

高精度乘低精度 —— 模板题 AcWing 793. 高精度乘法

// C = A * b, A >= 0, b >= 0
func mul(A []int, b int) []int {
    t := 0
    res := make([]int, 0)
    for i := 0; i < len(A) || t > 0; i ++ {
        if i < len(A) {
            t += A[i] * b
        }
        res = append(res, t % 10)
        t /= 10
    }
    i := len(res) - 1
    for ; i > 0 && res[i] == 0; i -- {
        
    }
    return res[:i + 1]
}