个人空间 - AcWing

w_CHAOS

访客：157

发消息

离线：14小时前

活动打卡代码 AcWing 826. 单链表

w_CHAOS
2天前

                package main

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

const N = 100010

var ne, e [N]int
var head = -1
var idx = -0


// 插入到头head节点
func addToHead(x int) {

    e[idx] = x
    ne[idx] = head
    head = idx
    idx++
}

//将x插入到下标是k的数的后面（在第k个输入的数后面插入一个数x（此操作中k均大于0）
func add(k, x int) {
    e[idx] = x
    ne[idx] = ne[k]
    ne[k] = idx
    idx++

}

// 删除k后面的一个节点（第k个输入的数后面的数（当k为0时，表示删除头结点）
func remove(k int) {
    //ne[k]=-1
    ne[k] = ne[ne[k]]
}

//遍历链表

func readLine(input *bufio.Reader) []string {
    str, _ := input.ReadString('\n')
    strSlice := strings.Fields(str)
    return strSlice
}

func main() {
    var M int
    fmt.Scanf("%d", &M)
    r := bufio.NewReader(os.Stdin)
    //  start()
    for i := M; i > 0; i-- {
        //var s string
        //var x int
        //fmt.Scanf("%s",&s)
        cin := readLine(r)
        s := cin[0]
        switch s {
        case "H":
            //var x int
            //fmt.Scanf("%d", &x)
            x,_ := strconv.Atoi(cin[1])
            addToHead(x)
        case "I":
            //var k, x int
            //fmt.Scanf("%d%d", &k, &x)
            k,_:=strconv.Atoi(cin[1])
            x,_ := strconv.Atoi(cin[2])
            add(k-1, x)
        case "D":
            //var k int
            //fmt.Scanf("%d", &k)
            k,_:=strconv.Atoi(cin[1])
            if k == 0 {
                head = ne[head]
            } else {
                remove(k - 1)
            }

        }
    }

    for i := head; i != -1; i = ne[i] {
        fmt.Printf("%d ", e[i])
    }
}


            

活动打卡代码 AcWing 803. 区间合并

w_CHAOS
2天前

                package main

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


type pair struct {
    l int
    r int
}


func readLine(inputReader *bufio.Reader) (res []int) {
    inputString, _ := inputReader.ReadString('\n')
    stringSlice := strings.Fields(inputString)
    for _, v := range stringSlice {
        i, _ := strconv.Atoi(v)
        res = append(res, i)
    }
    return res
}
func merge(segs *[]pair) []pair {
    var st int = -2e9
    var ed int = -2e9
    res := make([]pair, 0) // 存放结果
    for i := 0; i < len(*segs); i++ {
        seg := (*segs)[i] //1，2
        if ed < seg.l {
            if (st != -2e9) {
                res = append(res, pair{st, ed})
                st = seg.l
                ed = seg.r
            } else {
                st = seg.l
                ed = seg.r
            }

        } else {
            ed = max(ed, seg.r)
        }

    }
    if (st != -2e9) {
        //res.push_back({st, ed})
        res =append(res,pair{st, ed})
    }
    return res
}
func max(a, b int) int {
    if a >= b {
        return a
    } else {
        return b
    }
}
func main() {
    var n int
    fmt.Scanf("%d", &n)
    var segs []pair
    inputReader := bufio.NewReader(os.Stdin)
    for i := 0; i < n; i++ {
        input := readLine(inputReader)
        l := input[0]
        r := input[1]
        segs = append(segs, pair{l, r})
    }
    //fmt.Println(segs)
    sort.SliceStable(segs, func(i, j int) bool {
        return segs[i].l < segs[j].l
    })
    res := merge(&segs)
    fmt.Println(len(res))
}


            

活动打卡代码 AcWing 802. 区间和

w_CHAOS
3天前

                不要用scanf输入大量的数！！！
package main

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



// alls数组里存放的是所有原数组的位置信息，包括x，l，r
const N  =300010
var a,s [N]int // a[]存放离散化后的元素，s[]存放前缀和
type Pair struct {
    first int
    second int
}
func readLine(input *bufio.Reader)[]int{
    str,_:=input.ReadString('\n')
    strslice:=strings.Fields(str)
    a:=make([]int,len(strslice))
    for k,v:=range strslice{
        sti,_:=strconv.Atoi(v)
        a[k]=sti
    }
    return a
}
func unique(a *[]int)  {
    j:=0
    for i:=0;i<len(*a);i++{
        if i==0 || (*a)[i]!=(*a)[i-1]{
            (*a)[j]=(*a)[i]
            j++
        }
    }
    *a = (*a)[:j]
}

// 二分查找
func find(x int,alls *[]int)int {
    l :=0
    r := len(*alls)-1

    for l<r{
        mid := (l+r)>>1
        if (*alls)[mid] >=x{
            r = mid
        }else {
            l = mid+1
        }
    }
    return r+1 // 从1开始

}
func main() {

    // scanner是自己定义的一个新的扫描器缓存区，不可以在扫描后再定义
    //缓存区。
    scanner := bufio.NewScanner(os.Stdin)
    bs :=make([]byte,20000*1024) // 缓存区的大小约20M
    scanner.Buffer(bs,len(bs))

    var n,m int
    //fmt.Scan(&n,&m)
    fmt.Scanf("%d%d", &n, &m)
    alls:=make([]int,0) // 存放可供散列化的位置元素
    adds :=make([]Pair,n) // 存放每次的插入信息
    querys :=make([]Pair,m) // 存放每次询问的信息
    //var x,c int
    inputReader:= bufio.NewReader(os.Stdin)
    for i:=0;i<n;i++{
        //fmt.Scanf("%d%d",&x,&c)
        input := readLine(inputReader)
        adds[i] =Pair{input[0],input[1]}
        alls = append(alls,input[0])
    }
    //var l,r int
    for i:=0;i<m;i++{
        //fmt.Scanf("%d%d",&l,&r)
        input:=readLine(inputReader)
        l:=input[0]
        r:=input[1]
        alls = append(alls, l)
        alls = append(alls, r)
        querys[i] = Pair{l,r}
    }

    // 排序去重
    sort.Ints(alls)
    unique(&alls)
//  fmt.Println("去重后的alls：",alls)

    //将alls中的坐标信息二分查找映射到数组a[]
    //for i:=0;i<len(adds);i++{
    //  x :=adds[i].first
    //  res:=find(x,&alls)
    //  a[i]=res
    //}
    // 处理插入
    for _,item:=range adds{
        x:=find(item.first,&alls)
//      fmt.Println(x)
//      fmt.Println("item.first:",item.first)
        a[x] += item.second
//      fmt.Println(a[:10])
        //fmt.Println("alls:",alls)
    }

    // 预处理前缀和
    for i:=1;i<=len(alls);i++{
        s[i] = s[i-1]+a[i]
    }
    // 处理查询
    for _,item :=range querys{
        l:=find(item.first,&alls)
        r:=find(item.second,&alls)
        fmt.Println(s[r]-s[l-1])
    }
//fmt.Println(a[:10])
    return
}


            

活动打卡代码 AcWing 801. 二进制中1的个数

w_CHAOS
4天前

//查看一个数x的二进制表示的第k位是几 x>>k&1
// low-bit操作作用是返回二进制标志的x的最后一位1

package main

import "fmt"
func lowBit(x int)int  {
    return x & -x
}
func getCount(x int)int  {
    res :=0
    for x>0{
        x -=lowBit(x)
        res++
    }
    return res
}
func main() {
    var n int
    fmt.Scanf("%d",&n)
    q :=make([]int,n)
    for i:=0;i<n;i++{
        fmt.Scanf("%d",&q[i])
    }
    for _,v :=range q{
        res:=getCount(v)
        fmt.Printf("%d ",res)
    }
    //res :=getCount(3)
    //fmt.Println(res)
}

活动打卡代码 AcWing 800. 数组元素的目标和

w_CHAOS
4天前

                package main

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

const N  =100010
var A,B [N]int
func main() {
    var n,m,x int
    fmt.Scan(&n,&m,&x)
    stringreader:=bufio.NewReader(os.Stdin)
    inputString,_:=stringreader.ReadString('\n')
    stringSlice := strings.Fields(inputString)
    for i :=0;i<n;i++{
        A[i],_=strconv.Atoi(stringSlice[i])
    }
    inputString,_=stringreader.ReadString('\n')
    stringSlice = strings.Fields(inputString)
    for i :=0;i<m;i++{
        B[i],_=strconv.Atoi(stringSlice[i])
    }
    j:=m-1
    for i:=0;i<n;i++{
        for j>=0 && A[i]+B[j]>x{. // 此部分是核心，将时间复杂度从O(nm)降为O(n+m)
            j--
            }
        if j>=0 && A[i]+B[j]==x{
            fmt.Println(i,j)
            //break
        }
    }
}


            

活动打卡代码 AcWing 799. 最长连续不重复子序列

w_CHAOS
4天前

方法1 当数组元素不是很大的时候，使用数组s做计数器

package main

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

const N = 10010

var a,s [N]int

func max(a, b int) int {
    if a >= b {
        return a
    } else {
        return b
    }
}
func main() {
    var n int
    fmt.Scan(&n)
    inputReader :=bufio.NewReader(os.Stdin)
    stringss,_ :=inputReader.ReadString('\n')
    stringSlice:=strings.Fields(stringss)
    for i:=0;i<n;i++{
        a[i],_ = strconv.Atoi(stringSlice[i])
    }
    //n := 20
    //a := []int{7, 10, 10, 4, 3, 9, 7, 2, 5, 5, 0, 6, 6, 8, 5, 2, 10, 6, 5, 8}
    j := 0
    res := 0

    // 次方法不能满足 连续不重复的要求，只是相邻不重复
    //for ; i < n; i++ {
    //  if j < i && a[i] == a[i-1] { // 1 2 2
    //      j = i
    //  }
    //  res = max(res, i-j+1)
    //}

    //使用多余的一个数组存放非重复的子序列
    for i := 0; i < n; i++ {
        s[a[i]] +=1 // 1 2 1
        //s[a[i]] ++
        for j < i && s[a[i]] > 1 {
            //s[a[j]]--
            s[a[j]]-=1
            j++

        }
        res = max(res, i-j+1)
    }

    // 使用map 不行
    //m :=make(map[int]int)
    //for i:=0;i<n;i++{
    //  m[a[i]] +=1
    //  for j<i && m[a[i]]>1{
    //      m[a[i]]-=1
    //      j++
    //  }
    //  res = max(res,i-j+1)
    //}
    fmt.Println(res)
    return

}

方法2 使用哈希表做计数器

package main

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

const N = 10010

var a[N]int

func max(a, b int) int {
    if a >= b {
        return a
    } else {
        return b
    }
}
func main() {
    var n int
    fmt.Scanf("%d",&n)
    stringreader:=bufio.NewReader(os.Stdin)
    inputString,_:=stringreader.ReadString('\n')
    stringSlice := strings.Fields(inputString)
    for i :=0;i<n;i++{
        a[i],_=strconv.Atoi(stringSlice[i])
    }

    // 使用map
    m :=make(map[int]int)
    res :=0
    j:=0
    for i:=0;i<n;i++{
        m[a[i]] +=1
        for j<i && m[a[i]]>1{
            m[a[j]] -=1
            j++
        }
        res = max(res, i-j+1)
    }
    fmt.Println(res)
}

活动打卡代码 AcWing 798. 差分矩阵

w_CHAOS
4天前

                该算法会出现超时，但是核心操作的时间复杂度还是O(1),超时的原因是测试数据太多输入时的问题。
package main

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

const N = 1010

var a, b [N][N]int

func insert(x1, y1, x2, y2, c int) {
    b[x1][y1] += c
    b[x2+1][y1] -= c
    b[x1][y2+1] -= c
    b[x2+1][y2+1] +=c
}
func main() {
    var n, m, q int
    inputReader := bufio.NewReader(os.Stdin)
    inputString, _ := inputReader.ReadString('\n')
    stringSlice := strings.Fields(inputString)
    n, _ = strconv.Atoi(stringSlice[0])
    m, _ = strconv.Atoi(stringSlice[1])
    q, _ = strconv.Atoi(stringSlice[2])
    //fmt.Scan(&n, &m, &q)


    for i := 1; i <= n; i++ {
        inputString, _ := inputReader.ReadString('\n')
        stringSlice := strings.Fields(inputString)
        for j := 1; j <= m; j++ {
            a[i][j], _ = strconv.Atoi(stringSlice[j-1])
            insert(i,j,i,j,a[i][j])
        }
    }
    var t [5]int
    var x1,y1,x2,y2,c int
    for i:=0;i<q;i++{
        inputString, _ := inputReader.ReadString('\n')
        stringSlice := strings.Fields(inputString)
        for i:=0;i<5;i++{
            t[i] , _ = strconv.Atoi(stringSlice[i])
        }
        x1,y1,x2,y2,c = t[0],t[1],t[2],t[3],t[4]
        insert(x1,y1,x2,y2,c)
    }

    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
            fmt.Printf("%d ",b[i][j])
            if j==m{
                fmt.Println()
            }
        }
    }
}


            

活动打卡代码 AcWing 797. 差分

w_CHAOS
6天前

                package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)
// 差分：给定一个原数组a，构造一个数组b，使得a[i]=b[1]+b[2]+...b[i]
func insert(b *[100010]int,l,r,c int)  {
    (*b)[l]+=c
    (*b)[r+1]-=c

}
func main(){
    const N  =100010
    var a,b [N]int
    var n,m int
    fmt.Scan(&n,&m)
    fmt.Println(n,m)
    inputReader :=bufio.NewReader(os.Stdin)
    inputString,_ := inputReader.ReadString('\n')
    stringSlice:=strings.Fields(inputString)
    for i :=1;i<=n;i++{
        a[i],_= strconv.Atoi(stringSlice[i-1])
        //fmt.Scanf("%d",&a[i])
        fmt.Println(a[:i+1])
        insert(&b,i,i,a[i]) //此步是构造差分数组b
    }
    var l,r,c int
    for i:=0;i<m;i++{
        inputString,_ = inputReader.ReadString('\n')
        stringSlice =strings.Fields(inputString)
        var tmp [3]int
        for i,v :=range stringSlice{
            tmp[i],_ = strconv.Atoi(v)
        }
        //fmt.Scan(&l,&r,&c)
        l,r,c = tmp[0],tmp[1],tmp[2]
        insert(&b,l,r,c)
    }
    for i:=1;i<=n;i++{
        b[i] +=b[i-1]
    }
    for i:=1;i<=n;i++{
        fmt.Printf("%d ",b[i])
    }
}

            

活动打卡代码 AcWing 796. 子矩阵的和

w_CHAOS
6天前

                package main

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

/*
公式：
1、s(i,j)怎么算？
S(i,j) = s(i-1,j)+s(i,j-1)-s(i-1,j-1)+a(i,j)
2、(x1,y1),(x2,y2)之间的矩阵中所以数的和计算
S = S(x2,y2)-S(x1-1,y2)-S(x2,y1-1)+S(x1-1,y1-1)
 */

func main() {
    var n,m,q int
    inputReader := bufio.NewReader(os.Stdin)
    fmt.Scan(&n,&m,&q)

    var a [][]int
    a = append(a,make([]int,m+1))
    for i:=1;i<n+1;i++{
        input,_:= inputReader.ReadString('\n')
        stringslice := strings.Fields(input)
        a = append(a,make([]int,m+1))
        for j:=1;j<m+1;j++{
            x,_:=strconv.Atoi(stringslice[j-1])
            a[i][j]=x
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j]
        }
    }
    var x1,y1,x2,y2 int
    tmp:=make([]int,4)
    for i:=q;i>0;i--{
//      fmt.Scanln(&x1,&y1,&x2,&y2)
        input,_:=inputReader.ReadString('\n')
        stringslice:=strings.Fields(input)
        for k, v := range stringslice {
            tmp[k], _ = strconv.Atoi(v)
        }
        x1, y1, x2, y2 = tmp[0], tmp[1], tmp[2], tmp[3]
        fmt.Println(a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1])
    }
}

            

题解 AcWing 795. 前缀和

w_CHAOS
7天前

题目描述

输入一个长度为n的整数序列。

接下来再输入m个询问，每个询问输入一对l, r。

对于每个询问，输出原序列中从第l个数到第r个数的和。

输入格式
第一行包含两个整数n和m。

第二行包含n个整数，表示整数数列。

接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。

输出格式
共m行，每行输出一个询问的结果。

数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000

样例

输出

3
6
10

go代码

package main

import "fmt"

func main() {
    var n,m int
    fmt.Scan(&n,&m)
    a:=make([]int,n)
    //s:=make([]int,n+1)
    s:=append(a,0)
    for i:=0;i<n;i++{
        fmt.Scanf("%d",&a[i])
    }
    for i:=1;i<=n;i++{
        s[i]=s[i-1]+a[i-1]
    }
    fmt.Println(a)
    fmt.Println(s)
    var l,r int
    for i:=0;i<m;i++{
        fmt.Scan(&l,&r)
        fmt.Println(s[r]-s[l-1])
    }
}

python3 代码

if __name__ == "__main__":
    n, m = map(int, input().split())
    sequence = list(map(int, input().split()))
    if len(sequence) != n:
        print("输入有误，请输入n个整数")
        return
    s = [0]
    t = 0
    for i in sequence:
        t += i
        s.append(t)
    for i in range(0, m):
        l, r = map(int, input().split())
        print(s[r] - s[l - 1])