Leetcode、牛客刷题之旅，不定期更新中
目录
剑指 Offer
1. 二维数组中的查找
原题传送门👉
二维数组中的查找 | 牛客
func find(target int, array [][]int) bool {
if array == nil || len(array) == 0 || len(array[0]) == 0 {
return false
}
rows := len(array)
cols := len(array[0])
// 从右上角开始
curRow := 0
curCol := cols - 1
for curRow <= rows-1 && curCol >= 0 {
switch {
case target == array[curRow][curCol]:
return true
case target < array[curRow][curCol]:
curCol--
case target > array[curRow][curCol]:
curRow++
default:
break
}
}
return false
}
2. 数组中重复的数字
原题传送门👉
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
func duplicate(numbers []int, length int, duplication []int) bool {
if numbers == nil || length <= 0 {
return false
}
for i := 0; i < length; i++ {
for numbers[i] != i {
if numbers[i] == numbers[numbers[i]] {
duplication[0] = numbers[i]
return true
}
numbers[i], numbers[numbers[i]] = numbers[numbers[i]], numbers[i]
}
}
return false
}
3. 构建乘积数组
原题传送门👉
func multiply(A []int) []int {
if A == nil || len(A) == 0 {
return []int{}
}
n := len(A)
B := make([]int, n)
B[0] = 1
for i := 1; i < n; i++ { // 计算下三角连乘
B[i] = B[i-1] * A[i-1]
}
product := 1
for j := n - 2; j >= 0; j-- { // 计算上三角连乘
product *= A[j+1]
B[j] *= product
}
return B
}
4. 替换空格
原题传送门👉
func replaceSpace(str string) string {
return strings.Replace(str, " ", "%20", -1)
}
22. 斐波那契数列
原题传送门👉
func Fibonacci(n int) int {
if n == 0 || n == 1 {
return n
}
fn1, fn2, cur := 0, 1, 0
for i := 2; i <= n; i++ {
cur = fn1 + fn2
fn1, fn2 = fn2, cur
}
return cur
}
26. 二进制中 1 的个数
原题传送门👉
func numberOf1(n int) int {
num := 0
for n != 0 {
num++
n &= n - 1
}
return num
}
28. 调整数组顺序使奇数位于偶数前面
原题传送门👉
func reOrderArray(nums []int) {
oddNum := 0
for _, val := range nums {
if val&0x1 == 1 {
oddNum++
}
}
copyNums := make([]int, len(nums))
copy(copyNums, nums)
i, j := 0, oddNum
for _, val := range copyNums {
if val&0x1 == 1 {
nums[i] = val
i++
} else {
nums[j] = val
j++
}
}
}
Leetcode
179. 最大数
原题传送门👉
179. 最大数 | Leetcode
题目描述
给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。
测试用例
输出结果可能非常大，所以你需要返回一个字符串而不是整数
输入: [10, 2]
输出: 210
输入: [3, 30, 34, 5, 9]
输出: 9534330
Golang 题解
需要注意输入全为
0的特殊情况
func largestNumber(nums []int) string {
length := len(nums)
if length < 1 {
return "0"
}
strs := make([]string, length)
for i := 0; i < length; i++ {
strs[i] = strconv.Itoa(nums[i])
}
sort.Slice(strs, func(i, j int) bool {
return (strs[i] + strs[j]) > (strs[j] + strs[i])
})
numsStr := strings.Join(strs, "")
numsStr = strings.TrimLeft(numsStr, "0")
if numsStr == "" {
return "0"
}
return numsStr
}
本地测试
package main
import (
"fmt"
"sort"
"strconv"
"strings"
)
func main() {
strings1 := []int{3, 30, 34, 5, 9}
strings2 := []int{10, 2}
strings3 := []int{0, 0, 0, 0}
strings4 := make([]int, 10)
fmt.Println(largestNumber(strings1))
fmt.Println(largestNumber(strings2))
fmt.Println(largestNumber(strings3))
fmt.Println(largestNumber(strings4))
}
func largestNumber(nums []int) string {
length := len(nums)
if length < 1 {
return "0"
}
strs := make([]string, length)
for i := 0; i < length; i++ {
strs[i] = strconv.Itoa(nums[i])
}
sort.Slice(strs, func(i, j int) bool {
return (strs[i] + strs[j]) > (strs[j] + strs[i])
})
numsStr := strings.Join(strs, "")
numsStr = strings.TrimLeft(numsStr, "0")
if numsStr == "" {
return "0"
}
return numsStr
}
------
9534330
210
0
0
Process finished with exit code 0
引申一下
上面的解法是在 Leetcode 评论区看到的，比较好奇sort.Slice是用什么算法对切片进行排序。翻了一下sort/slice.go的源码，如下所示：
// Copyright 2017 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// +build !compiler_bootstrap go1.8
package sort
import "reflect"
// Slice sorts the provided slice given the provided less function.
//
// The sort is not guaranteed to be stable. For a stable sort, use
// SliceStable.
//
// The function panics if the provided interface is not a slice.
func Slice(slice interface{}, less func(i, j int) bool) {
rv := reflect.ValueOf(slice)
swap := reflect.Swapper(slice)
length := rv.Len()
quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
}
// SliceStable sorts the provided slice given the provided less
// function while keeping the original order of equal elements.
//
// The function panics if the provided interface is not a slice.
func SliceStable(slice interface{}, less func(i, j int) bool) {
rv := reflect.ValueOf(slice)
swap := reflect.Swapper(slice)
stable_func(lessSwap{less, swap}, rv.Len())
}
// SliceIsSorted tests whether a slice is sorted.
//
// The function panics if the provided interface is not a slice.
func SliceIsSorted(slice interface{}, less func(i, j int) bool) bool {
rv := reflect.ValueOf(slice)
n := rv.Len()
for i := n - 1; i > 0; i-- {
if less(i, i-1) {
return false
}
}
return true
}
可以看到默认的sort.Slice()方法是用快排对切片进行排序的。
我们知道，快排是不稳定的，所以如果希望使用稳定排序算法对切片进行排序，则可以使用SliceStable()方法。
而SliceStable()所使用的stable_func()定义在sort/zfuncversion.go中，而实际上该函数在sort/sort.go中定义：
func stable(data Interface, n int) {
blockSize := 20 // must be > 0
a, b := 0, blockSize
for b <= n {
insertionSort(data, a, b)
a = b
b += blockSize
}
insertionSort(data, a, n)
for blockSize < n {
a, b = 0, 2*blockSize
for b <= n {
symMerge(data, a, a+blockSize, b)
a = b
b += 2 * blockSize
}
if m := a + blockSize; m < n {
symMerge(data, a, m, n)
}
blockSize *= 2
}
}
可以看到SliceStable()中定义了变量blocksize := 20，用来控制插入排序的区间大小。当待排序的切片长度<=20时，相当于直接对该切片进行插入排序：
// Insertion sort
func insertionSort(data Interface, a, b int) {
for i := a + 1; i < b; i++ {
for j := i; j > a && data.Less(j, j-1); j-- {
data.Swap(j, j-1)
}
}
}
而当b <= n即切片长度超过20时，SliceStable()会先调用insertionSort_func()，对切片按照blockSize分段进行插入排序。之后，调用symMerge_func()，对每一段有序的切片元素进行归并排序，逐步翻倍blockSize大小直至归并排序完成：
// SymMerge merges the two sorted subsequences data[a:m] and data[m:b] using
// the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
// Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
// Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
// Computer Science, pages 714-723. Springer, 2004.
//
// Let M = m-a and N = b-n. Wolog M < N.
// The recursion depth is bound by ceil(log(N+M)).
// The algorithm needs O(M*log(N/M + 1)) calls to data.Less.
// The algorithm needs O((M+N)*log(M)) calls to data.Swap.
//
// The paper gives O((M+N)*log(M)) as the number of assignments assuming a
// rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation
// in the paper carries through for Swap operations, especially as the block
// swapping rotate uses only O(M+N) Swaps.
//
// symMerge assumes non-degenerate arguments: a < m && m < b.
// Having the caller check this condition eliminates many leaf recursion calls,
// which improves performance.
func symMerge(data Interface, a, m, b int) {
// Avoid unnecessary recursions of symMerge
// by direct insertion of data[a] into data[m:b]
// if data[a:m] only contains one element.
if m-a == 1 {
// Use binary search to find the lowest index i
// such that data[i] >= data[a] for m <= i < b.
// Exit the search loop with i == b in case no such index exists.
i := m
j := b
for i < j {
h := int(uint(i+j) >> 1)
if data.Less(h, a) {
i = h + 1
} else {
j = h
}
}
// Swap values until data[a] reaches the position before i.
for k := a; k < i-1; k++ {
data.Swap(k, k+1)
}
return
}
// Avoid unnecessary recursions of symMerge
// by direct insertion of data[m] into data[a:m]
// if data[m:b] only contains one element.
if b-m == 1 {
// Use binary search to find the lowest index i
// such that data[i] > data[m] for a <= i < m.
// Exit the search loop with i == m in case no such index exists.
i := a
j := m
for i < j {
h := int(uint(i+j) >> 1)
if !data.Less(m, h) {
i = h + 1
} else {
j = h
}
}
// Swap values until data[m] reaches the position i.
for k := m; k > i; k-- {
data.Swap(k, k-1)
}
return
}
mid := int(uint(a+b) >> 1)
n := mid + m
var start, r int
if m > mid {
start = n - b
r = mid
} else {
start = a
r = m
}
p := n - 1
for start < r {
c := int(uint(start+r) >> 1)
if !data.Less(p-c, c) {
start = c + 1
} else {
r = c
}
}
end := n - start
if start < m && m < end {
rotate(data, start, m, end)
}
if a < start && start < mid {
symMerge(data, a, start, mid)
}
if mid < end && end < b {
symMerge(data, mid, end, b)
}
}
// Rotate two consecutive blocks u = data[a:m] and v = data[m:b] in data:
// Data of the form 'x u v y' is changed to 'x v u y'.
// Rotate performs at most b-a many calls to data.Swap.
// Rotate assumes non-degenerate arguments: a < m && m < b.
func rotate(data Interface, a, m, b int) {
i := m - a
j := b - m
for i != j {
if i > j {
swapRange(data, m-i, m, j)
i -= j
} else {
swapRange(data, m-i, m+j-i, i)
j -= i
}
}
// i == j
swapRange(data, m-i, m, i)
}
/*
Complexity of Stable Sorting
Complexity of block swapping rotation
Each Swap puts one new element into its correct, final position.
Elements which reach their final position are no longer moved.
Thus block swapping rotation needs |u|+|v| calls to Swaps.
This is best possible as each element might need a move.
Pay attention when comparing to other optimal algorithms which
typically count the number of assignments instead of swaps:
E.g. the optimal algorithm of Dudzinski and Dydek for in-place
rotations uses O(u + v + gcd(u,v)) assignments which is
better than our O(3 * (u+v)) as gcd(u,v) <= u.
Stable sorting by SymMerge and BlockSwap rotations
SymMerg complexity for same size input M = N:
Calls to Less: O(M*log(N/M+1)) = O(N*log(2)) = O(N)
Calls to Swap: O((M+N)*log(M)) = O(2*N*log(N)) = O(N*log(N))
(The following argument does not fuzz over a missing -1 or
other stuff which does not impact the final result).
Let n = data.Len(). Assume n = 2^k.
Plain merge sort performs log(n) = k iterations.
On iteration i the algorithm merges 2^(k-i) blocks, each of size 2^i.
Thus iteration i of merge sort performs:
Calls to Less O(2^(k-i) * 2^i) = O(2^k) = O(2^log(n)) = O(n)
Calls to Swap O(2^(k-i) * 2^i * log(2^i)) = O(2^k * i) = O(n*i)
In total k = log(n) iterations are performed; so in total:
Calls to Less O(log(n) * n)
Calls to Swap O(n + 2*n + 3*n + ... + (k-1)*n + k*n)
= O((k/2) * k * n) = O(n * k^2) = O(n * log^2(n))
Above results should generalize to arbitrary n = 2^k + p
and should not be influenced by the initial insertion sort phase:
Insertion sort is O(n^2) on Swap and Less, thus O(bs^2) per block of
size bs at n/bs blocks: O(bs*n) Swaps and Less during insertion sort.
Merge sort iterations start at i = log(bs). With t = log(bs) constant:
Calls to Less O((log(n)-t) * n + bs*n) = O(log(n)*n + (bs-t)*n)
= O(n * log(n))
Calls to Swap O(n * log^2(n) - (t^2+t)/2*n) = O(n * log^2(n))
*/
另外，如果想判断一个切片是否已经有序，则可以使用SliceIsSorted()方法，返回一个bool值。
赛码
分数序列和 - 百度
原题传送门👉
分数序列和（百度2017秋招真题）| 赛码
package main
import (
"fmt"
)
func main() {
n := 0 // total number of test cases
part := 0 // how many elements to calculate
fmt.Scan(&n)
for i := 0; i < n; i++ {
fmt.Scan(&part)
fmt.Printf("%.4f", partSum(part))
}
}
func partSum(n int) float64 {
sum := 0.0
for i := 1; i <= n; i++ {
sum += float64(fibonacci(i+1)) / float64(fibonacci(i))
}
return sum
}
func fibonacci(n int) int {
f1, f2 := 1, 2
var f3 int
switch n {
case 1:
return f1
case 2:
return f2
default:
for i := 3; i <= n; i++ {
f3 = f1 + f2
f1, f2 = f2, f3
}
return f3
}
}
SQL
175. 组合两个表
题目描述
表 1：Person
+-------------+---------+
| 列名 | 类型 |
+-------------+---------+
| PersonId | int |
| FirstName | varchar |
| LastName | varchar |
+-------------+---------+
PersonId 是上表主键
表 2：Address
+-------------+---------+
| 列名 | 类型 |
+-------------+---------+
| AddressId | int |
| PersonId | int |
| City | varchar |
| State | varchar |
+-------------+---------+
AddressId 是上表主键
编写一个 SQL 查询，满足条件：无论Person是否有地址信息，都需要基于上述两表提供Person的以下信息：
FirstName, LastName, City, State
SQL 题解
使用左外连接以及
on过滤条件，参见 SQL中on条件与where条件的区别 | 博客园
SELECT p.FirstName AS FirstName, p.LastName AS LastName, a.City AS City, a.State AS State
FROM Person p LEFT JOIN Address a
ON p.PersonId = a.PersonId;
