头像

一只鱼




在线 



一只鱼
16小时前

摘花生-golang

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var t int

var scan *bufio.Scanner
var r, c int

func main() {
    fmt.Scanf("%d", &t)
    scan = bufio.NewScanner(os.Stdin)

    for t > 0 {
        t--
        r, c := readLine2()
        w := make([][]int, r+1)
        for j := 0; j <= r; j++ {
            w[j] = make([]int, c+1)
            if j == 0 {
                continue
            }
            w[j] = readLine(c)
        }
        fmt.Println(maxNum(w, r, c))
    }

}

func maxNum(w [][]int, r, c int) int {
    f := make([][]int, r+1)
    for i := 0; i <= r; i++ {
        f[i] = make([]int, c+1)
    }

    for i := 1; i <= r; i++ {
        for j := 1; j <= c; j++ {
            f[i][j] = max(f[i-1][j], f[i][j-1]) + w[i][j]
        }
    }
    return f[r][c]
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func readLine2()(int, int){
    for {
        scan.Scan()
        data := strings.Split(scan.Text(), " ")
        if len(data) != 2 {
            continue
        }

        r, _ := strconv.Atoi(data[0])
        c, _ := strconv.Atoi(data[1])
        return r, c
    }
}

func readLine(c int) []int {
    for {
        scan.Scan()
        data := strings.Split(scan.Text(), " ")
        if len(data) != c {
            continue
        }

        sli := make([]int, c+1)
        for k, v := range data {
            tmp, _ := strconv.Atoi(v)
            sli[k+1] = tmp
        }
        return sli
    }
}




活动打卡代码 AcWing 1015. 摘花生

一只鱼
16小时前

[//]: # AcWing 1015. 摘花生-golang

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var t int

var scan *bufio.Scanner
var r, c int

func main() {
    fmt.Scanf("%d", &t)
    scan = bufio.NewScanner(os.Stdin)

    for t > 0 {
        t--
        r, c := readLine2()
        w := make([][]int, r+1)
        for j := 0; j <= r; j++ {
            w[j] = make([]int, c+1)
            if j == 0 {
                continue
            }
            w[j] = readLine(c)
        }
        fmt.Println(maxNum(w, r, c))
    }

}

func maxNum(w [][]int, r, c int) int {
    f := make([][]int, r+1)
    for i := 0; i <= r; i++ {
        f[i] = make([]int, c+1)
    }

    for i := 1; i <= r; i++ {
        for j := 1; j <= c; j++ {
            f[i][j] = max(f[i-1][j], f[i][j-1]) + w[i][j]
        }
    }
    return f[r][c]
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func readLine2()(int, int){
    for {
        scan.Scan()
        data := strings.Split(scan.Text(), " ")
        if len(data) != 2 {
            continue
        }

        r, _ := strconv.Atoi(data[0])
        c, _ := strconv.Atoi(data[1])
        return r, c
    }
}

func readLine(c int) []int {
    for {
        scan.Scan()
        data := strings.Split(scan.Text(), " ")
        if len(data) != c {
            continue
        }

        sli := make([]int, c+1)
        for k, v := range data {
            tmp, _ := strconv.Atoi(v)
            sli[k+1] = tmp
        }
        return sli
    }
}





区间分组-golang

package main

import (
    "bufio"
    "container/heap"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

var n int

var scan *bufio.Scanner

type elem struct {
    l, r int
}

func main() {
    fmt.Scanf("%d", &n)
    data := make([]elem, 0, n)

    scan = bufio.NewScanner(os.Stdin)

    for i := 0; i < n; i++ {
        tmp := elem{}
        tmp.l, tmp.r = readLine()
        data = append(data, tmp)
    }

    sort.Slice(data, func(i, j int) bool {
        return data[i].l < data[j].l
    })

    minHeap := &IntHeap{}
    heap.Init(minHeap)
    for k, v := range data {
        if k == 0 {
            heap.Push(minHeap, v.r)
            continue
        }

        top := heap.Pop(minHeap)

        topNum := top.(int)
        if minHeap.Len() == 0 || topNum >= v.l {
            heap.Push(minHeap, topNum)
            heap.Push(minHeap, v.r)
            continue
        }
        heap.Push(minHeap, v.r)
    }

    fmt.Println(minHeap.Len())
}

func readLine() (int, int) {
    for {
        scan.Scan()
        sli := strings.Split(scan.Text(), " ")
        if len(sli) == 2 {
            l, _ := strconv.Atoi(sli[0])
            r, _ := strconv.Atoi(sli[1])
            return l, r
        }
    }
}

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func (h *IntHeap) Top() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    return x
}



活动打卡代码 AcWing 906. 区间分组

[//]: #AcWing 906. 区间分组-golang

package main

import (
    "bufio"
    "container/heap"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

var n int

var scan *bufio.Scanner

type elem struct {
    l, r int
}

func main() {
    fmt.Scanf("%d", &n)
    data := make([]elem, 0, n)

    scan = bufio.NewScanner(os.Stdin)

    for i := 0; i < n; i++ {
        tmp := elem{}
        tmp.l, tmp.r = readLine()
        data = append(data, tmp)
    }

    sort.Slice(data, func(i, j int) bool {
        return data[i].l < data[j].l
    })

    minHeap := &IntHeap{}
    heap.Init(minHeap)
    for k, v := range data {
        if k == 0 {
            heap.Push(minHeap, v.r)
            continue
        }

        top := heap.Pop(minHeap)

        topNum := top.(int)
        if minHeap.Len() == 0 || topNum >= v.l {
            heap.Push(minHeap, topNum)
            heap.Push(minHeap, v.r)
            continue
        }
        heap.Push(minHeap, v.r)
    }

    fmt.Println(minHeap.Len())
}

func readLine() (int, int) {
    for {
        scan.Scan()
        sli := strings.Split(scan.Text(), " ")
        if len(sli) == 2 {
            l, _ := strconv.Atoi(sli[0])
            r, _ := strconv.Atoi(sli[1])
            return l, r
        }
    }
}

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func (h *IntHeap) Top() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    return x
}




一只鱼
10天前
package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

var n int

type node struct {
    l int
    r int
}

var count int

var scan *bufio.Scanner

func main() {
    scan = bufio.NewScanner(os.Stdin)
    fmt.Scanf("%d", &n)
    arr := make([]node, n)

    for i := 0; i < n; i++ {
        arr[i].l, arr[i].r = scanLine()
    }

    sort.SliceStable(arr, func(i, j int) bool {
        return arr[i].r < arr[j].r
    })

    edge := int(-2e9)
    for i := 0; i < n; i++ {
        if arr[i].l > edge {
            count++
            edge = arr[i].r
        }
    }
    fmt.Println(count)
}

func scanLine() (int, int) {
    scan.Scan()
    var num int
    for {
        str := strings.Split(scan.Text(), " ")
        if len(str) != 2 {
            num++
            fmt.Println(num)
            continue
        }
        left, _ := strconv.Atoi(str[0])
        right, _ := strconv.Atoi(str[1])
        return left, right
    }
}



一只鱼
10天前

最大不相交区间数量-golang

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

var n int

type node struct {
    l int
    r int
}

var count int

var scan *bufio.Scanner

func main() {
    scan = bufio.NewScanner(os.Stdin)
    fmt.Scanf("%d", &n)
    arr := make([]node, n)

    for i := 0; i < n; i++ {
        arr[i].l, arr[i].r = scanLine()
    }

    sort.SliceStable(arr, func(i, j int) bool {
        return arr[i].r < arr[j].r
    })

    edge := int(-2e9)
    for i := 0; i < n; i++ {
        if arr[i].l > edge {
            count++
            edge = arr[i].r
        }
    }
    fmt.Println(count)
}

func scanLine() (int, int) {
    scan.Scan()
    var num int
    for {
        str := strings.Split(scan.Text(), " ")
        if len(str) != 2 {
            num++
            fmt.Println(num)
            continue
        }
        left, _ := strconv.Atoi(str[0])
        right, _ := strconv.Atoi(str[1])
        return left, right
    }
}




一只鱼
10天前

二维数组中的查找-golang

func searchArray(array [][]int, target int) bool {
    if len(array) == 0 || len(array[0]) == 0{
        return false
    }
    i, j := 0, len(array[0])-1

    for i < len(array) && j >= 0{
        if array[i][j] == target{
            return true
        }
        if array[i][j] > target{
            j--
            continue
        }
        if array[i][j] < target{
            i++
        }
    }
    return false
}



一只鱼
10天前
func searchArray(array [][]int, target int) bool {
    if len(array) == 0 || len(array[0]) == 0{
        return false
    }
    i, j := 0, len(array[0])-1

    for i < len(array) && j >= 0{
        if array[i][j] == target{
            return true
        }
        if array[i][j] > target{
            j--
            continue
        }
        if array[i][j] < target{
            i++
        }
    }
    return false
}



一只鱼
14天前
func duplicateInArray(nums []int) int {
   l, r := 1, len(nums)-1

   for l < r{
       mid := (l+r)>>1
       var count int
       for _, v := range nums{
           if v >= l && v <= mid{
               count++
           }
       }
       if count > mid-l+1{
           r = mid
           continue
       }
       l = mid+1
   }
   return r
}




一只鱼
14天前

不修改数组找出重复的数字-golang

func duplicateInArray(nums []int) int {
   l, r := 1, len(nums)-1

   for l < r{
       mid := (l+r)>>1
       var count int
       for _, v := range nums{
           if v >= l && v <= mid{
               count++
           }
       }
       if count > mid-l+1{
           r = mid
           continue
       }
       l = mid+1
   }
   return r
}