算法 - Githubissues

BitMap 算法 所谓 BitMap 就是用一个 bit 位来标记某个元素对应的 value，而 key 即是这个元素。由于采用bit为单位来存储数据，因此在可以大大的节省存储空间。 https://www.cnblogs.com/chanshuyi/p/5287825.html 海量数据处理-BitMap算法

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储一个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。

方法一

//呵呵
func ten(n int) (sum int) {
    sum = 1
    for i := 0; i < n; i++ {
        sum = sum * 10
    }
    return
}

func desten(n, sum int) (b, sub int) {
    for i := 0; i < 10; i++ {
        sub = sum - ten(n)*i
        if sub < ten(n) {
            return i, sub
        }
    }
    return
}

func plusOne(digits []int) []int {
    l := len(digits)
    var sum int
    for i, j := l-1, 0; i >= 0; i-- {
        sum = sum + ten(i)*digits[j]
        j++
    }
    sum++
    if sum/ten(l) == 1 {
        l = l + 1
    }
    ok:=make([]int,l)
    for x,y := l-1,0; x >= 0; x-- {
        b, sub := desten(x, sum)
        sum = sub
        ok[y]=b
        y++
    }
    return ok
}

方法二

func plusOne(digits []int) []int {
    l := len(digits)
    if digits[l-1]+1 == 10 {
        digits[l-1] = 10
        for i := l - 1; i >= 1; i-- {
            if digits[i] == 10 {
                digits[i] = 0
                digits[i-1] = digits[i-1] + 1
            }

        }
        if digits[0] == 10 {
            digits[0] = 0
            digits = append([]int{1}, digits...)
        }
    } else {
        digits[l-1] = digits[l-1] + 1
    }
    return digits
}

给定两个二进制字符串，返回他们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = "11", b = "1" 输出: "100" 示例 2: 输入: a = "1010", b = "1011" 输出: "10101"

func pow(x, n int) int {
    ret := 1
    for n != 0 {
        if n%2 != 0 {
            ret = ret * x
        }
        n /= 2
        x = x * x
    }
    return ret
}

func stringTounit(a string) uint {
    var aa uint
    l := len(a)
    for x, y := l-1, 0; x >= 0; x-- {
        if a[y] == uint8(49) {
            aa = aa + uint(pow(2, x))
        }
        y++
    }
    return aa
}

func conv(n uint) string {
    s := make([]byte, 0)
    if n == 0 {
        return "0"
    }
    for n != 0 {
        temp := n % 2
        if temp == 1 {
            s = append(s, 49)
        } else {
            s = append(s, 48)
        }
        n = n / 2
    }
    out := make([]byte, len(s))
    for i, j := 0, len(s)-1; i < len(s); i++ {
        out[i] = s[j]
        j--
    }
    return string(out)
}

func addBinary(a string, b string) string {
    ok := stringTounit(a) + stringTounit(b)
    return conv(ok)
}

func addBinary(a string, b string) string {
    lslice := []byte(a)
    sslice := []byte(b)
    llen := len(a)
    slen := len(b)
    if llen < slen {
        llen, slen = slen, llen
        lslice, sslice = sslice, lslice
    }
    out := make([]byte, llen)
    for x, y := slen-1, llen-1; x >= 0; x-- {
        out[y] = lslice[y] + sslice[x] - 48*2
        y--
    }
    for i := 0; i != (llen - slen); i++ {
        out[i] = lslice[i] - 48
    }
    for i := llen - 1; i > 0; i-- {
        if out[i]/2 > 0 {
            out[i-1] = out[i-1] + 1
        }
        temp := out[i] % 2
        if temp == 1 {
            out[i] = 49
        } else {
            out[i] = 48
        }
    }
    if out[0]/2 > 0 {
        out = append([]byte{49}, out...)
        temp := out[1] % 2
        if temp == 1 {
            out[1] = 49
        } else {
            out[1] = 48
        }
    }
    temp := out[0] % 2
    if temp == 1 {
        out[0] = 49
    } else {
        out[0] = 48
    }
    return string(out)
}

妙

func addBinary(a string, b string) string {
    i, j := len(a)-1, len(b)-1
    res := ""
    c := uint8(0)
    for i >= 0 || j >= 0 || c == 1 {
        if i >= 0 {
            c += a[i] - '0'
            i--
        }
        if j >= 0 {
            c += b[j] - '0'
            j--
        }
        res = string(c%2 + '0') + res
        c /= 2
    }

    return res
}

实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。 示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2 示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1 说明:当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

func strStr(haystack string, needle string) int {
    if needle == "" {
        return 0
    }
    h := len(haystack)
    n := len(needle)
    for i := 0; i < h; i++ {
        if haystack[i] == needle[0] && h-n >= i && haystack[i:i+n] == needle {
            return i
        }
    }
    return -1
}

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。说明: 返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

func twoSum(numbers []int, target int) []int {
    ok:=make([]int,2)
    i:=0
    j:=len(numbers)-1
    for i<j {
        for k:=j;i<k;k--{
            if numbers[i]+numbers[k]==target {
                ok[0]=i+1
                ok[1]=k+1
                return ok
            }
        }
        i++
    }
    return ok
}

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。你的实现应该支持如下操作： MyCircularQueue(k): 构造器，设置队列长度为 k 。 Front: 从队首获取元素。如果队列为空，返回 -1 。 Rear: 获取队尾元素。如果队列为空，返回 -1 。 enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。 deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。 isEmpty(): 检查循环队列是否为空。 isFull(): 检查循环队列是否已满。

type MyCircularQueue struct {
    Queue  []int
    Length int
    front  int
    rear   int
    Count  int
}

func Constructor(k int) MyCircularQueue {
    queue := make([]int, k)
    return MyCircularQueue{Queue: queue, Length: k}
}

func (this *MyCircularQueue) EnQueue(value int) bool {
    if this.IsFull() {
        return false
    }
    if this.Count == 0 {
        this.rear = 0
        this.Queue[this.rear] = value
        this.Count++
        return true

    }
    this.Count++
    if this.rear+1 == this.Length {
        this.rear = 0
    } else {
        this.rear++
    }
    this.Queue[this.rear] = value
    return true
}

func (this *MyCircularQueue) DeQueue() bool {
    if this.IsEmpty() {
        return false
    }
    this.Count--
    if this.Count == 0 {
        this.front = 0
        return true
    }
    if this.front+1 == this.Length {
        this.front = 0
    } else {
        this.front++
    }
    return true
}

func (this *MyCircularQueue) Front() int {
    if this.IsEmpty() {
        return -1
    }
    return this.Queue[this.front]
}

func (this *MyCircularQueue) Rear() int {
    if this.IsEmpty() {
        return -1
    }
    return this.Queue[this.rear]
}

func (this *MyCircularQueue) IsEmpty() bool {
    if this.Count == 0 {
        return true
    }
    return false
}

func (this *MyCircularQueue) IsFull() bool {
    if this.Count == this.Length {
        return true
    }
    return false
}

设计链表

type Node struct {
    Val  int
    Next *Node
}

type MyLinkedList struct {
    HeadNode *Node
    TailNode *Node
    Count    int
}

func Constructor() MyLinkedList {
    return MyLinkedList{HeadNode: &Node{0, nil}, TailNode: &Node{0, nil}, Count: 0}
}

func (this *MyLinkedList) Get(index int) int {
    if index+1 > this.Count {
        return -1
    }
    tmpNode := this.HeadNode
    for i := 0; i < index; i++ {
        tmpNode = tmpNode.Next
    }
    return tmpNode.Val
}

func (this *MyLinkedList) AddAtHead(val int) {
    if this.Count == 0 {
        this.HeadNode = &Node{Val: val}
        this.TailNode = this.HeadNode
    }
    if this.Count > 0 {
        this.HeadNode = &Node{Val: val, Next: this.HeadNode}
    }
    this.Count++
}

func (this *MyLinkedList) AddAtTail(val int) {
    if this.Count == 0 {
        this.HeadNode = &Node{Val: val}
        this.TailNode = this.HeadNode
    }
    if this.Count > 0 {
        newTailNode := &Node{Val: val, Next: nil}
        this.TailNode.Next = newTailNode
        this.TailNode = newTailNode
    }
    this.Count++
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
    if index == this.Count {
        this.AddAtTail(val)
        return
    }
    if index == 0 {
        this.AddAtHead(val)
        return
    }
    if index < this.Count {
        tmpNode := this.HeadNode
        for i := 0; i < index-1; i++ {
            tmpNode = tmpNode.Next
        }
        tmpNode.Next = &Node{Val: val, Next: tmpNode.Next}
        this.Count++
    }
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
    if this.Count == 1 && index == 0 {
        this.HeadNode = nil
        this.TailNode = nil
        this.Count = 0
        return
    }
    if index > this.Count-1 {
        return
    }
    preNode := new(Node)
    curNode := this.HeadNode
    for i := 0; i < index; i++ {
        preNode = curNode
        curNode = preNode.Next
    }
    if curNode.Next == nil {
        preNode.Next = nil
        this.TailNode = preNode
    } else if preNode.Next == nil {
        this.HeadNode = curNode.Next
    } else {
        preNode.Next = curNode.Next
    }
    this.Count--
    log.Println(this.Count)
}

https://leetcode-cn.com/submissions/detail/13769825/

shownb / shownb.github.com

算法 #38