算法题
2021-04-12 本文已影响0人
voidFan
行列都是有序的二维数组，查找k是否存在【查找法】
package main
import "fmt"
func Find(target int, arr [][]int) bool {
if arr == nil || len(arr) <= 0 {
return false
}
row := len(arr)
cols := len(arr[0])
i := row - 1 // 从左下角的元素开始查找, 也可以从右上角开始找
j := 0
for i >= 0 && j < cols {
if arr[i][j] == target {
return true
} else if arr[i][j] > target {
i-- // 只能往上查找
} else {
j++ // 只能往右查找
}
}
return false
}
func main() {
var arr = [][]int{[]int{1,2,3,4,5}, []int{6,7,8,9,10}, []int{11,12,13,15,16}, []int{17,19,20,21,22}}
fmt.Println(Find(18, arr))
}
二维数组中的查找（行列分别有序数组的二分查找）【递归法】
package main
import "fmt"
var arr [][]int = [][]int{[]int{1,2,8,9}, []int{2,4,9,12}, []int{4,7,10,13}, []int{6,8,11,15}}
const N = 4
func main() {
if(BinarySearchMat(arr,0,0,4,4,9)) {
fmt.Println(true)
} else {
fmt.Println(false)
}
return
}
func BinarySearchMat(mat [][]int, beginR int, beginC int, sumR int, sumC int, val int) bool {
if (sumC <= 0 || sumR <=0) {
return false
}
halfR := sumR / 2
halfC := sumC / 2
midR := beginR + halfR
midC := beginC + halfC
if (val == mat[midR][midC]) {
return true
}
if(val < mat[midR][midC]) {
if(BinarySearchMat(mat,beginR,beginC,halfR,sumC,val)){
return true
}
if (BinarySearchMat(mat,midR,beginC,sumR - halfR ,halfC ,val)) {
return true
}
} else {// val > mat[midR][midC]
if(BinarySearchMat(mat,midR + 1,beginC,sumR - halfR - 1,sumC,val)) {
return true
}
if (BinarySearchMat(mat,beginR,midC + 1,halfR + 1,sumC - halfC - 1,val)) {
return true
}
}
return false
}
快速排序递归实现
package main
//快速排序递归实现
func QuickSort(arr []int) {
_quicksort(arr, 0, len(arr) - 1)
}
func _quicksort(arr []int, left, right int) {
if left < right {
p := partition(arr, left, right)
_quicksort(arr, left, p - 1)
_quicksort(arr, p + 1, right)
}
}
func partition(arr []int, left, right int) int {
pivot := left
//TODO:从第二个数据开始处理:"待处理的元素"
index := pivot + 1
//TODO:i为遍历记数，index记录待遍历的第一个元素。遍历待遍历的数 与 参考值比较
for i := index; i <= right; i++ {
if arr[i] < arr[pivot] {
arr[i], arr[index] = arr[index], arr[i] //TODO:将小于pivot的数，放在index的位置，后面依次放
index++
}
}
arr[pivot], arr[index - 1] = arr[index -1], arr[pivot] // TODO:最后将pivot上的元素移动到合适的位置
return index - 1
}
快速排序非递归实现
//快速排序非递归实现
package main
func _quicksortOpt(arr []int, left, right int) {
//递归退出条件
if left >= right { return }
pivot := arr[right] //从右边开始遍历
i := left
j := right - 1
for i < j {
for i < j && arr[i] < pivot {i++} //从左边找一个小于 p 的数
for i < j && arr[j] > pivot {j--} //从右边找一个大于 p 的数
arr[i], arr[j] = arr[j], arr[i]
}
if arr[i] >= pivot {
arr[i], arr[right] = arr[right],arr[i]
} else {
i++
}
_quicksort(arr, left, i-1)
_quicksort(arr, i+1, right)
}
func QuickSortOpt(arr []int) {
_quicksortOpt(arr, 0, len(arr) - 1)
}
归并排序递归实现
package main
func MergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
//拆分数组，再合并。拆分到数组只有一个元素。
mid := len(arr) / 2
left := MergeSort(arr[:mid])
right := MergeSort(arr[mid:])
return Merge(left, right)
}
func Merge(left, right []int) []int {
result := make([]int, 0)
i, j := 0, 0 // left和right的index位置
lLen, rLen := len(left), len(right)
//左右两边数组，只要有长度大于0的就需要处理
for i < lLen && j < rLen {
if left[i] > right[j] {
result = append(result, right[j])
j++
continue
}
result = append(result, left[i])
i++
}
result = append(result, right[j:]...)
result = append(result, left[i:]...)
return result
}
链表排序leetcode归并解决
func sortList(head *ListNode) *ListNode {
// 如果 head为空或者head就一位,直接返回
if head == nil || head.Next == nil {
return head
}
// 定义快慢俩指针,当快指针到末尾的时候,慢指针肯定在链表中间位置
slow,fast := head,head
for fast != nil && fast.Next != nil && fast.Next.Next != nil {
slow,fast = slow.Next,fast.Next.Next
}
// 把链表拆分成两段,所以设置中间位置即慢指针的next为nil
n := slow.Next
slow.Next = nil
// 递归排序
return merge(sortList(head),sortList(n))
}
func merge(node1 *ListNode,node2 *ListNode)*ListNode {
// 设置一个空链表,
node := &ListNode{Val:0}
current := node
// 挨个比较俩链表的值,把小的值放到新定义的链表里,排好序
for node1 != nil && node2 != nil {
if node1.Val <= node2.Val {
current.Next,node1 = node1,node1.Next
} else {
current.Next,node2 = node2,node2.Next
}
current = current.Next
}
// 两链表可能有一个没走完,所以要把没走完的放到链表的后面
// 注意,此处跟 数组不一样的是, 数组为什么要循环,因为数组可能一个数组全部走了(比如 12345与6789比较, 前面的全部走完,后面一个没走),另一个可能有多个没走..
// 链表虽然也有这种可能,但是 node1和node2已经是有序的了,如果另外一个没有走完,直接把next指向node1或者node2就行,因为这是链表
if node1 != nil {
current.Next,node1 = node1,node1.Next
}
if node2 != nil {
current.Next,node2 = node2,node2.Next
}
return node.Next
}
反转字符串中的单词 III
func reverseWords(s string) string {
sr := []rune(s)
length := len(sr)
first := 0
last := 0
for first < length {
if sr[first] == []rune(" ")[0] {
reverse(sr, last, first - 1)
first++
last = first
} else {
first++
}
}
reverse(sr, last, first - 1)
return string(sr)
}
func reverse(s []rune, start int, end int) {
for start < end {
s[start], s[end] = s[end], s[start]
start++
end--
}
}
大小端的判断
- 大端模式：数据的高字节保存在内存的低地址中
- 小端模式：数据的高字节保存在内存的高地址中
//若将0x00000001放入计算机中就有两种方法：
// 此时数据的高地址是：0x00
//—————————————————————> 小端
//低地址 01 00 00 00 高地址
//—————————————————————> 大端
//高地址 00 00 00 01 低地址
//————————————————
package main
import (
"fmt"
"unsafe"
)
func main() {
s := int16(0x1234) //数据高地址： 0x12
b := int8(s)
fmt.Println("int16 size:", unsafe.Sizeof(s))
//
if b == 0x34 {
fmt.Println("little endian")
} else {
fmt.Println("big endian")
}
}
