常用小算法集锦

前提:所有的输入无论是数字还是字符等等都是通过字符串的形式被程序读入,如果是数字则先转化成数字数组

          然后在接下来的算法中,直接对标准输入进行处理

func getInput() string{
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Scan()
    if err := scanner.Err(); err != nil {
        fmt.Fprintln(os.Stderr, "error:", err)
    }
    return scanner.Text()
}

如果是数字:
inputString := getInput();
//strArray := strings.Split(inputString," ")
strArray :=strings.Fields(inputString)    //这个比split好,因为会将不止一个空格的处理,空格专用
count := len(strArray)
var numArray []int =make([]int, count)
var j =0
for i := range strArray{ num,err := strconv.Atoi(strArray[i]) if err!=nil{ continue} numArray[j]=num j++ }

 

例一:

N个1到1000之间的随机整数(N≤1000),对于其中重复的数字,只保留一个,把其余相同的数去掉。然后再把这些数从小到大排序

例如:输入11 10 20 40 32 67 40 20 89 300 400 15,输出10 15 20 32 40 67 89 300 400。

方式一:
func test1(){count=len(numArray) for i:=0;i<count-1;i++ { for j := i+1;j<count;{if numArray[i] > numArray[j]{ temp := numArray[i] numArray[i]=numArray[j] numArray[j]=temp j++ } else if numArray[i] == numArray[j]{ //如果遇到重复的,就让最后一个数过来补齐,同时总长度减少一位 numArray[j]=numArray[count-1] count-- }else{ j++ } } } }

方式二:
func test1(){ sort.Ints(numArray) //首先利用库函数进行排序
  //去重.....省略....... }

 

例二:

给定一个字符串,找他的子串是回文字符串的,要是有多个就要最长的那个,比如:gaabcdcbahahah,则最大回文字符串是abcdcba

说明:所谓回文就是 从左向右和从右向左是一样的,例如abccba  或者 abcxcba

 

func testHuiwen(input string){
    fmt.Println(input)
    count := len(input)
    var max =0
    var index=0
    if input[0]==input[1]{
        index=0
        max=2
    }
    for i := 1; i<count-1; i++{
        if input[i]==input[i+1]{   //如果是连续两个相同,则为axxa型回文
            step:=1
            for i-step>=0&&(i+step+1<count){
                if(input[i-step]!=input[i+1+step]){
                    break
                }
                step++
            }
            if max<step*2{
                max=step*2
                index=i
            }
        } else if input[i-1]==input[i+1]{   //如果是abxba型的回文
            step:=2
            for i-step>=0&&(i+step<count){
                if(input[i-step]!=input[i+step]){
                    break
                }
                step++
            }

            if max<(step-1)*2 + 1{
                max=(step-1)*2 + 1
                index=i
            }
        }
    }
//9kssk9js;     "gaabcdcbahahah"
    fmt.Printf("the result:max:%d,max/2:%d, index:%d,output:%v",max,max/2,index,input[(index -(max-1)/2):index+max/2+1])
}


注意一个很巧妙的配置
pbaxxab类型,index为3,总长度max是6,即input[1:7]
pbaxab类型,index为3,总长度是5,即input[1:6]
注意go语言的切片类型是是左包含右不包含,于是
左边=index -(max-1)/2 3-(6-1)/2=1, 3-(5-1)/2=1
右边=index + max/2 + 1 3+ 6/2 + 1= 7, 3 + 5/2 + 1=6

 

例三:递归用例1

简要描述: 给定一个M行N列的矩阵(M*N个格子),每个格子中放着一定数量的平安果。 你从左上角的各自开始,只能向下或者向右走,目的地是右下角的格子。 每走过一个格子,就把格子上的平安果都收集起来。求你最多能收集到多少平安果。

输入描述: 输入包含两部分: 

第一行M, N 

接下来M行,包含N个平安果数量 

 

输出描述: 一个整数 ,最多拿走的平安果的数量 


示例:

输入
2, 4
1 2 3 40
6 7 8 90

输出
136

思路,一看就是递归,从左上角开始,有两个方向:向右走,找到最优的路;  向下走找到最优的路,然后对比两条路哪条最优

           至于选定了方向后,需要继续选定接下来的方向然后走,直到走到最右下的角落里

          注:为了准确判断目的地,我们可以反着来,即从右下开始,到坐上结束,方向只能是向左或向上,这样到了[0][0]坐标就是到头了

func findMax(m,n int, git [5][5]int) int{
    if(m==0 && n==0){
        return git[0][0]
    }

    if m==0 {
        return git[0][n] + findMax(0,n-1,git)
    }
    if n==0 {
        return git[m][0] + findMax(m-1,0,git)
    }
    var sum1, sum2  int
    sum1 = git[m][n] + findMax(m-1,n,git)
    sum2 = git[m][n] + findMax(m,n-1,git)

    if sum1 > sum2{
        return sum1
    }else {
      return sum2
    }
}


func testDigui(){
    var m, n int
    var line string
    var input [5][5]int
    fmt.Scanf("%d,%d", &m, &n)
    fmt.Println("m and n:",m,n)

    reader := bufio.NewReader(os.Stdin)

    for i:= 0; i<m; i++{
        fmt.Printf("Enter line:%d: \n",i)
        line, _ = reader.ReadString('\n')
        fmt.Print("this line is:",line)
        strArray :=strings.Fields(line)
        for j:=0;j<len(strArray) && j<n;j++{
            num,_ :=strconv.Atoi(strArray[j])
            input[i][j]=num
        }
    }

    fmt.Printf(">>>input:%v",input)
    sum := findMax(m,n,input)

    fmt.Println(">>>>.the reslt:",sum)

}

 

例4:对小写字母进行转换,转换规则是a->b,b->c,....y->z,z->a;如果输入的字符串中出现两个相同的字母,则后一个字母需要连续转换2次,例如aa转换为bc,zz转换成ab;当连续字母出现超过2次的时候,第三个字母按照第一次出现算。比如:abbbcd   ---->   bcdcde

思路:首先我的第一反应是想到了二进制:01,第一次+1 +0,第二次+1+1,第三次 +1 +0,,于是按照这个思路程序如下:

func traslate(data string, count int){
    var flag byte =0
    var output [20]byte
    j := 0
    tmp := data[0]
    for i := range data{
        if i==0 {
            output[j]=data[i]+1
        } else{
            if tmp==data[i] {
                flag +=1
            }else{
                tmp=data[i]
            }
            step := flag & 0x01
            output[j]=data[i]+1 + step
        }

        if output[j]>=123 {
            output[j]=97+output[j]-123
        }
        j++
    }
    output[j-1]=0
    fmt.Printf("the result:%s",output)
}

 

 

例5:识别有效的IP地址和掩码并进行分类
题目描述
请解析IP地址和对应的掩码,进行分类识别。要求按照A/B/C/D/E类地址归类,不合法的地址和掩码单独归类。

所有的IP地址划分为 A,B,C,D,E五类

A类地址1.0.0.0~126.255.255.255;

B类地址128.0.0.0~191.255.255.255;

C类地址192.0.0.0~223.255.255.255;

D类地址224.0.0.0~239.255.255.255;

E类地址240.0.0.0~255.255.255.255

私网IP范围是:

10.0.0.0~10.255.255.255

172.16.0.0~172.31.255.255

192.168.0.0~192.168.255.255

子网掩码为前面是连续的1,然后全是0。(例如:255.255.255.32就是一个非法的掩码)

本题暂时默认以0开头的IP地址是合法的,比如0.1.1.2,是合法地址

输入描述:
多行字符串。每行一个IP地址和掩码,用~隔开。

输出描述:
统计A、B、C、D、E、错误IP地址或错误掩码、私有IP的个数,之间以空格隔开。

//检查是不是IP地址类型的格式,即xxx.sss.sss.sss
func checkIPFormat(ip string) bool{
    //regx:= `^(1\d{2}|2[0-4]\d|25[0-5]|[1-9]\d|[1-9])\.(1\d{2}|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.(1\d{2}|2[0-4]\d|25[0-5]|[1-9]\d|\d)\.(1\d{2}|2[0-4]\d|25[0-5]|[1-9]\d|\d)$`
    regx:="^(\\d+)\\.(\\d+)\\.(\\d+)\\.(\\d+)$"   //比较宽松的正则

    r,_:=regexp.Compile(regx)
    b:=r.MatchString(ip)
    fmt.Println(b)  //结果为true
    return b

}


func checkMash(m string) bool{
    strArray := strings.Split(m,".")
    last :=false
    for _, v:=range strArray{
        num,_ := strconv.Atoi(v)
        if (last && num != 0) || num > 255 {return false}
        if !last && num < 255{
            num1:=uint8(num)
            for j:=0;j<8;j++{
                if (num1 & (1<<7)) == 0 {   //如果发现了有一个零的位,那么接下来必须是全0才对
                    if num1==0 {last=true;break}else{return false}
                }
                num1 <<= 1
            }
        }
    }
    return true
}

func testValidIPandMask(){
    var line,ip,mask string
    var input [50]int

    var typeA,typeB,typeC,typeD,typeIpErr,typeMaskErr, typePrivate int

    reader := bufio.NewReader(os.Stdin)

outer:
    for true{
        fmt.Print("please 输入待处理数据:\n",line)
        line, _ = reader.ReadString('\n')
        fmt.Printf("this %d length line is:",len(line),line)

        ipAndmask := strings.Split(line,"~")
        ip = ipAndmask[0]
        mask = ipAndmask[1]

        if !checkIPFormat(ip){
            typeIpErr++
            fmt.Println("ip not ok",ip)
            continue
        }
        if !checkIPFormat(mask){
            typeMaskErr++
            fmt.Println("mask not ok",mask)
            continue
        }

        if !checkMash("255.255.249.0"){
            typeMaskErr++
            fmt.Println("mask not ok",mask)
            continue
        }
        //开始正式判定ip地址是哪一类的
        strArray := strings.Split(ip,".")
        for _, v:=range strArray{
            num, err := strconv.(v)
            if err{
                typeIpErr++
                continue outer
            }
            if num
        }

    }


}

 

上一篇:【逆向&编程实战】Metasploit中的安卓载荷凭什么吊打SpyNote成为安卓端最强远控


下一篇:Mysql索引优化和锁机制