5.24 奇安信笔试-Golang

24届第一次参加笔试，两题都没做出来

一、拓扑图求路径数

输入一个二维数组表示图，输出从起始点到终点可能的路径数

package main

import "fmt"

var res int

func main() {
	var nodes [][]int
	nodes = append(nodes, []int{1, 2, 3})
	nodes = append(nodes, []int{3})
	nodes = append(nodes, []int{3})
	nodes = append(nodes, []int{4})
	nodes = append(nodes, []int{})
	dfs(0, nodes)
	fmt.Println(res)
}

func dfs(start int, nodes [][]int) {
	if start == len(nodes)-1 {
		res++
		return
	}
	for _, v := range nodes[start] {
		dfs(v, nodes)
	}
}

二、九键手机

输入是只包含1-9的字符串，输出是对应按键可能的组合

例：

输入：2

输出：['d', 'e', 'f']

输入：22

输出：['dd', 'de', 'df', 'ed', 'ee', 'ef', 'fd', 'fe', 'ff']

package main

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

var s string
var res []string
var m map[int]string

func backTrack(nums []int, index int) {
	if index == len(nums) {
		res = append(res, s)
		return
	}
	letters := m[nums[index]]
	for i := 0; i < len(letters); i++ {
		s += string(letters[i])
		backTrack(nums, index+1)
		s = s[:len(s)-1]
	}
}

func main() {
	m = make(map[int]string, 0)
	m[1] = "abc"
	m[2] = "def"
	m[3] = "ghi"
	m[4] = "jkl"
	m[5] = "mno"
	m[6] = "pqr"
	m[7] = "stu"
	m[8] = "vwx"
	m[9] = "yz"

	scanner := bufio.NewScanner(os.Stdin)
	for scanner.Scan() {
		nums := make([]int, 0)
		res = make([]string, 0)
		s = ""
		data := strings.Split(scanner.Text(), "")
		for i := 0; i < len(data); i++ {
			if num, err := strconv.Atoi(data[i]); err == nil {
				nums = append(nums, num)
			}
		}
		backTrack(nums, 0)
		fmt.Printf("%v\n", res)

	}
}