头像

BobToGoooo




离线:3个月前



BobToGoooo
3个月前

/
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
/
```
package main

import “fmt”

// 时间复杂度O(n),滑动窗口+双指针
func lengthOfLongestSubstring(s string) int {
kmap :=make(map[byte]int)
i,j :=0,0
res :=0
for ;i[HTML_REMOVED]1{
kmap[s[j]] -=1
j++
}
res =max(res,i-j+1)
}
return res
}

//此方法的利用是map的元素查找 时间复杂度O(n)?
func lengthOfLongestSubstring2(s string) int {
kmap :=make(map[string]int)
k,res :=-1,0
for i,v :=range s{
_,ok :=kmap[string(v)]
if ok && kmap[string(v)]>k{ // 如果元素在map并且上一次出现的位置在大于当前长度的起始下标
k = kmap[string(v)]
kmap[string(v)]=i
}else {
kmap[string(v)]=i
res = max(res,i-k)
}
}
return res
}
func max(a,b int)int {
if a>=b{
return a
}
return b
}
func main() {
//s :=”pwwkew” //3
//s :=”aab” //2
s :=”abcabcbb” //3
//s :=”dvdf” //3
//s :=”ckilbkd” //5
res :=lengthOfLongestSubstring(s)
fmt.Println(res)
}
```



活动打卡代码 LeetCode 2. 两数相加

BobToGoooo
3个月前

/*
两数相加
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
```
package main

type ListNode struct {
Val int
Next ListNode
}
// 时间复杂度 O(n),n为连个链表之中的最大长度
func addTwoNumbers(l1
ListNode, l2 ListNode) ListNode {
var head, t *ListNode
carry :=0 // 进位
sum :=0
for l1 !=nil ||l2!=nil{
n1,n2 :=0,0
if l1 !=nil{
n1 =l1.Val
l1 = l1.Next
}
if l2 !=nil{
n2 = l2.Val
l2 =l2.Next
}
sum = n1+n2+carry
sum,carry = sum%10,sum/10
if head == nil{
head = &ListNode{Val:sum}
t = head
}else {
t.Next = &ListNode{Val:sum}
t = t.Next
}
}
if carry >0{
t.Next = &ListNode{Val:carry}
}
return head
}

func addTwoNumbers1(l1, l2 ListNode)(head ListNode) {
var t *ListNode
sum :=0
for l1 != nil || l2 !=nil{
n1,n2 :=0,0
if l1 !=nil{
n1 = l1.Val
sum +=n1
l1 = l1.Next
}
if l2 !=nil{
n2 = l2.Val
sum +=n2
l2 = l2.Next
}
//sum = n1+n2+sum
if head ==nil{
head=&ListNode{Val:sum%10}
t = head
}else {
t.Next = &ListNode{Val:sum%10}
t = t.Next
}
sum /=10 // 进位

}
if sum !=0{
    t.Next = &ListNode{Val:1}
}
return

}
func main() {

}
```



活动打卡代码 AcWing 1. 两数之和

BobToGoooo
3个月前

/*
两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案
示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

*/

package main
import "fmt"
// 方法1 双指针:时间复杂度O(n^2)
func towSum(nums []int,target int)[]int{
    for i,v :=range nums{
        for k:=i+1;k<len(nums);k++{
            if target-v == nums[k]{
                return []int{i,k}
            }
        }
    }
    return []int{}
}
// 方法2:map 时间复杂度为O(1)+O(1)=O(n)
func towSum2(nums []int,target int)[]int  {
    kmap:=make(map[int]int)
    for i,v :=range nums{
        if r,ok:=kmap[target-v];ok{
            return []int{r,i}
        }
        kmap[v]=i
    }
    return []int{}

}
func main(){
    nums := []int{2,7,11,15}
    target := 9
    res:=towSum2(nums,target)
    res2:=towSum(nums,target)
    // fmt.Println(towSum(nums,target))
    fmt.Println(res)
    fmt.Println(res2)
}


活动打卡代码 AcWing 125. 耍杂技的牛

BobToGoooo
3个月前
package main

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

type Pair struct {
    first, second int
}
type PairArray []Pair

// const N = 50010

var n int
var cows []Pair

func (p PairArray) Less(i, j int) bool {
    return p[i].first < p[j].first
}
func (p PairArray) Len() int {
    return len(p)
}
func (p PairArray) Swap(i, j int) {
    p[i], p[j] = p[j], p[i]
}
func ReadLine(r *bufio.Reader)[]int  {
    s,_:=r.ReadString('\n')
    ss:=strings.Fields(s)
    res :=make([]int,len(ss))
    for i,v :=range ss{
        res[i],_=strconv.Atoi(v)
    }
    return res
}

func main() {
    fmt.Scanf("%d\n", &n)
    r := bufio.NewReader(os.Stdin)
    for i := 0; i < n; i++ {
        in := ReadLine(r)
        w, s := in[0], in[1]
        //cows[i].first,cows[i].second=w+s,w
        cows = append(cows, Pair{s + w, w})
    }
    //fmt.Println(cows)

    sort.Sort(PairArray(cows))
//  fmt.Println(cows)
    res, sum := math.MinInt32, 0
    for i := 0; i < n; i++ {
        s := cows[i].first - cows[i].second
        w := cows[i].second
        res = max(res, sum-s)
        sum += w
    }
    fmt.Println(res)
}
func max(a, b int) int {
    if a <= b {
        return b
    }
    return a
}



活动打卡代码 AcWing 104. 货仓选址

BobToGoooo
3个月前
package main

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

var n int
func readLine(r *bufio.Reader)[]int  {
    s,_:=r.ReadString('\n')
    ss:=strings.Fields(s)
    res :=make([]int,len(ss))
    for i,v :=range ss{
        res[i],_=strconv.Atoi(v)
    }
    return res
}

func main() {
    fmt.Scanf("%d\n",&n)
    r:=bufio.NewReader(os.Stdin)
    nums :=readLine(r)
    sort.Ints(nums)

    res := 0
    for i := 0; i < n; i++ {
        num := (nums[i] - nums[n/2])
        if num < 0 {// 绝对值
            num = -1 * num
        }
        res += num
    }

    fmt.Printf("%d\n", res)
}


活动打卡代码 AcWing 913. 排队打水

BobToGoooo
3个月前
package main

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

var n int
func readLine(r *bufio.Reader)[]int  {
    s,_:=r.ReadString('\n')
    ss:=strings.Fields(s)
    res :=make([]int,len(ss))
    for i,v :=range ss{
        res[i],_=strconv.Atoi(v)
    }
    return res
}

func main() {
    fmt.Scanf("%d\n",&n)
    r:=bufio.NewReader(os.Stdin)
    nums :=readLine(r)
    sort.Ints(nums)
    //sort.Reverse(nums)
    old :=make([]int,n)
    for i,v :=range nums{
        old[n-1-i] = v
    }
    res :=0
    for i:=0;i<n;i++{
        res +=old[i]*i
    }
    fmt.Println(res)
}



BobToGoooo
3个月前

go实现

package main
import (
    "bufio"
    "container/heap"
    "fmt"
    "os"
    "strconv"
    "strings"
)
type intHeap []int
var n 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{}){
    *h = append(*h,x.(int))
}
func (h *intHeap)Pop()interface{}{
    old := *h
    n:=len(old)
    x :=old[n-1]
    *h=old[:n-1]
    return x
}
func readLine(r *bufio.Reader) *intHeap {
    s, _ := r.ReadString('\n')
    ss := strings.Fields(s)
    res :=&intHeap{}
    heap.Init(res)
    for _, v := range ss {
        vv, _ := strconv.Atoi(v)
        heap.Push(res,vv)
    }
    return res
}
func main(){
    r:=bufio.NewReader(os.Stdin)
    fmt.Scanf("%d\n",&n)
    nums :=readLine(r)
    //fmt.Println(nums)
    res:=0
    // 将堆中的最小数取出
    for len(*nums)>1{
        a :=heap.Pop(nums)
        b :=heap.Pop(nums)
        c:=a.(int)+b.(int)
        res +=c
        heap.Push(nums,c)
    }
    fmt.Println(res)
}


活动打卡代码 AcWing 148. 合并果子

BobToGoooo
3个月前
package main
import (
    "bufio"
    "container/heap"
    "fmt"
    "os"
    "strconv"
    "strings"
)
type intHeap []int
var n 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{}){
    *h = append(*h,x.(int))
}
func (h *intHeap)Pop()interface{}{
    old := *h
    n:=len(old)
    x :=old[n-1]
    *h=old[:n-1]
    return x
}
func readLine(r *bufio.Reader) *intHeap {
    s, _ := r.ReadString('\n')
    ss := strings.Fields(s)
    res :=&intHeap{}
    heap.Init(res)
    for _, v := range ss {
        vv, _ := strconv.Atoi(v)
        heap.Push(res,vv)
    }
    return res
}
func main(){
    r:=bufio.NewReader(os.Stdin)
    fmt.Scanf("%d\n",&n)
    nums :=readLine(r)
    //fmt.Println(nums)
    res:=0
    // 将堆中的最小数取出
    for len(*nums)>1{
        a :=heap.Pop(nums)
        b :=heap.Pop(nums)
        c:=a.(int)+b.(int)
        res +=c
        heap.Push(nums,c)
    }
    fmt.Println(res)
}


活动打卡代码 AcWing 907. 区间覆盖

BobToGoooo
3个月前
// 1、将所有区间按左断点从小到大排序
//2、从前往后依次枚举每个区间,在所有能覆盖start的区间中,选择一个右端点最大的区间
//3、选完之后将start更新成右端点的最大值
package main

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

const N = 100010

type Range struct {
    l,r int
}
var (
    n, st,ed int
    rangs [N]Range
)
func readLine(r *bufio.Reader) []int {
    s, _ := r.ReadString('\n')
    ss := strings.Fields(s)
    res := make([]int, len(ss))
    for i, v := range ss {
        res[i], _ = strconv.Atoi(v)
    }
    return res
}
func max(a,b int)int  {
    if a>=b{
        return a
    }
    return b
}

func main() {
    r :=bufio.NewReader(os.Stdin)
    //in :=readLine(r)
    //st,ed = in[0],in[1]
    fmt.Scan(&st,&ed)
    fmt.Scan(&n)
    for i:=0;i<n;i++{
        in := readLine(r)
        rangs[i].l, rangs[i].r = in[0],in[1]
    }
    // 以左端点排序
    sort.Slice(rangs[:n], func(i, j int) bool {
        return rangs[i].l<rangs[j].l
    })
    //
    res :=0
    success :=false
    //for i:=0;i<n;i++{
    for i:=0;i<n;{
        j:=i
        r :=int(-2e9)
        for j<n && rangs[j].l<=st{
            // 选出最大的右端点更新
            r =max(r, rangs[j].r)
            j++
        }
        if r<st{
            res = -1
            //fmt.Println(-1)
            break
        }
        res ++
        if r>=ed{
            success=true
            break
        }
        st = r
        //i = j-1 //? 为了避免重复遍历区间,j循环过的将不用再遍历了,所以i就直接条过去,之所以j-1是因为for循环最后要i++
        i=j
    }
    if !success{
        res =-1
    }
    fmt.Println(res)

}



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

BobToGoooo
3个月前
package main

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

const N  =100010
var n int
var rangs [N]Range
type Range struct {
    l,r int
}
//定义一个堆结构体
type IntHeap []int
//实现heap.Interface接口
func (h IntHeap) Len()int  {
    return len(h)
}
// 实现heap.Interface中的sort.Interface接口
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]
}
// 实现heap.Interface接口
func (h *IntHeap)Push(x interface{})  {
    *h = append(*h,x.(int))
}
func (h *IntHeap)Pop()interface{}  {
    old :=*h
    n:=len(old)
    x:=old[n-1]
    *h = old[:n-1]
    return x
}
func readLine(r *bufio.Reader) []int {
    s, _ := r.ReadString('\n')
    ss := strings.Fields(s)
    res := make([]int, len(ss))
    for i, v := range ss {
        res[i], _ = strconv.Atoi(v)
    }
    return res
}
//var n int
func main() {
    fmt.Scan(&n)
    r := bufio.NewReader(os.Stdin)
    for i := 0; i < n; i++ {
        in := readLine(r)
        rangs[i].l, rangs[i].r = in[0], in[1]
    }
    sort.Slice(rangs[:n], func(i, j int) bool {
        return rangs[i].l < rangs[j].l
    })
    h:=&IntHeap{}
    for i:=0;i<n;i++{
        if h.Len()==0 || rangs[i].l<=(*h)[0]{
            heap.Push(h,rangs[i].r)
        }else {
            heap.Pop(h)
            heap.Push(h,rangs[i].r)
        }
    }
    fmt.Println(h.Len())

}