golang算法题记录

文件头

package test

import (
	"fmt"
	"strings"
	"testing"
	"unicode"
)

6 问题描述
请编写⼀个⽅法，将字符串中的空格全部替换为“%20”。 假定该字符串有⾜够的空间存放新增的字符，并且知道字符串的真实⻓度(⼩于等1000)，同时保证字符串由【⼤⼩写的英⽂字⺟组成】。 给定⼀个string为原始的串，返回替换后的string。
解题思路
两个问题，第⼀个是只能是英⽂字⺟，第⼆个是替换空格。

func Test_que6(t *testing.T) {
	var s string
	s = "asd zxc  到处撒"
	var result string
	if len([]rune(s)) > 1000 {
		goto FALSE
	}
	for _, v := range s {
		if string(v) != " " && unicode.IsLetter(v) == false {
			goto FALSE
		}
	}
	result = strings.Replace(s, " ", "%20", -1)
	goto TRUE
FALSE:
	fmt.Println(s, false)
	return
TRUE:
	fmt.Println(result, true)
}

7 问题描述
有⼀个机器⼈，给⼀串指令，L左转 R右转，F前进⼀步，B后退⼀步，最后机器⼈的坐标，最开始，机器⼈位于 0 0，⽅向为正Y。 可以输⼊重复令n ： ⽐如 R2(LF) 这个等于指令 RLFLF。 问最后机器⼈的坐标是多少？
解题思路
这⾥的⼀个难点是解析重复指令。主要指令解析成功，计算坐标就简单了

func Test_que7(t *testing.T) {
	println(move("R2(LF)", 0, 0, 1))
}
func move (cmd string, x0 int, y0 int, z0 int) (x, y, z int) {
	const (
		Left = iota
		Top
		Right
		Bottom
	)
	x, y, z = x0, y0, z0
	repeat := 0
	repeatCmd := ""
	for _, s := range cmd {
		switch {
		case unicode.IsNumber(s):
			repeat = repeat * 10 + (int(s) - '0')
		case s == ')':
			for i := 0 ; i < repeat; i++ {
				x, y, z = move(repeatCmd, x, y, z)
			}
			repeat = 0
			repeatCmd = ""
		case repeat > 0 && s != '(' && s != ')':
			repeatCmd = repeatCmd + string(s)
		case s == 'L':
			z = (z + 1) % 4
		case s == 'R':
			z = (z - 1 + 4) % 4
		case s == 'F':
			switch {
			case z == Left || z == Right:
				x = x + z - 1
			case z == Top || z == Bottom:
				y = y - z + 2
			}
		case s == 'B':
			switch {
			case z == Left || z == Right:
				x = x - z + 1
			case z == Top || z == Bottom:
				y = y + z - 2
			}
		}
	}
	return
}

8
把一个整数数组的第一个元素和最后一个元素连接起来，就能形成一个环。任意截取环中长度为N的连续的一段元素，对这一段元素求和得到一个值
求截取的长度为N时，可以截取到的最大的求和值。
输入:cycle=[1，6，9，-1，2，20]，N=3输出:27

func Test_que8(t *testing.T) {
	var cycle = []int{1, 6, 9, -1, 2, 20}
	var N = 3
	l := len(cycle)
	var sum int = 0
	for i := 0; i < l; i++ {
		num := cycle[i]
		for j := 1; j < N ; j++ {
			num = num + cycle[(j+i)%l]
		}
		if num > sum {
			sum = num
		}
	}
	fmt.Println("max: ", sum)
}

9设计一个数据结构HashMap，并实现其get操作。

func Test_que9(t *testing.T) {
	const BucketCount = 128
	type KV struct {
		Key string
		Value interface{}
	}
	type LinkNode struct {
		Data KV
		NextNode *LinkNode
	}
	type HashMap struct {
		Buckets [BucketCount]*LinkNode
	}
	var HashCode = func(key string) int {
		var sum = 0
		for i := 0; i < len(key); i++ {
			sum += int(key[i])
		}
		return sum % BucketCount
	}
	var Get = func(m *HashMap ,key string) (interface {}, bool) {
		h := HashCode(key)
		l := m.Buckets[h]
		for l != nil {
			if l.Data.Key == key {
				return l.Data.Value, true
			}
			l = l.NextNode
		}
		return nil, false
	}
	var hm = HashMap{}
	fmt.Println(Get(&hm, "123"))
}

10 已知一个无序数组array，元素均为正整数。给定一个目标值target输出数组中是否存在若干元素的组合，相加为目标值。
输入:array=[2，1，2，5，10，10，20，50] target=71输出:true
输入:array=[2，1，2，5，1010，20，50] target=101输出:false

func Test_que10(t *testing.T)  {
	var target = 71
	var array = []int{2, 1, 2, 5, 10, 10, 20, 50, 80}
	sort.Slice(array, func(i, j int) bool {
		return array[i] > array[j]
	})
	fmt.Println(array, target)
	r := test_que10(array, target)
	fmt.Println(r)
}
func test_que10(array []int, target int) bool {
	fmt.Println(array, target)
	for i, v := range array {
		fmt.Println(i,v,target)
		if target < v {
			continue
		}
		var t = target
		t -= v
		if t == 0{
			return true
		} else if t < 0 {
			return false
		} else {
			if test_que10(array[i+1:], t) {
				return true
			}
		}
	}
	return false
}