BobToGoooo

1494

BobToGoooo
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)
}


BobToGoooo
3个月前

/*

*/

package main

type ListNode struct {
Val int
Next ListNode
}
// 时间复杂度 O(n),n为连个链表之中的最大长度
ListNode, l2 ListNode) 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
}else {
t.Next = &ListNode{Val:sum}
t = t.Next
}
}
if carry >0{
t.Next = &ListNode{Val:carry}
}
}

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
}else {
t.Next = &ListNode{Val:sum%10}
t = t.Next
}
sum /=10 // 进位

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


}
func main() {

}


BobToGoooo
3个月前

/*

*/

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)
}


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]
}
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)
for i := 0; i < n; i++ {
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
}



BobToGoooo
3个月前
package main

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

var n int
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)
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)
}


BobToGoooo
3个月前
package main

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

var n int
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)
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
}
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(){
fmt.Scanf("%d\n",&n)
//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)
}


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
}
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(){
fmt.Scanf("%d\n",&n)
//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)
}


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
)
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() {
//st,ed = in[0],in[1]
fmt.Scan(&st,&ed)
fmt.Scan(&n)
for i:=0;i<n;i++{
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)

}



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
}
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)
for i := 0; i < n; i++ {
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())

}