360 服务端开发工程师-Golang 笔试记录附算法题解题

投递时间3.20

3.23笔试

题型 40选择题 2道代码题

选择题 ：c++代码阅读 填空选择 数据库基础知识选择 计算机网络知识选择 操作系统知识选择

C++代码完全看不懂基本上靠蒙

代码题 1

描述的很 复杂 简化来说给 定一个 长度为n的整型数组 中元素无序 且 有重复数字

对元素可以进行的操作为 可以将任意两个元素x与y相加 再放入数组中代替 x或y

最后返回 将数组中所有元素 都无重复情况的 元素操作次数

基本思路 ：将元素排序后 遍历 将第一个重复的数字与最大值相加后再放入数组中 再排序 再遍历

代码通过70% 不知道那种情况没处理好

package main

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

func main() {
	var n int
	fmt.Scanf("%d\n", &n)
	arr := ReadLineNum()

	if chongfu(arr) {
		fmt.Println(0)
		return
	}

	count := 0
	sort.Ints(arr)

	for !chongfu(arr) {
		arr, count = zhonghe(arr, count)
	}
	fmt.Println(count)

}

// 判断一个arr有无重复元素
func chongfu(arr []int) bool {
	for i := 0; i < len(arr)-1; i++ {
		if arr[i] != arr[i+1] {
			continue
		} else {
			return false
		}
	}
	return true
}

// 将一个美食中和
func zhonghe(arr []int, count int) ([]int, int) {
	maxnum := arr[len(arr)-1]
	for i := 0; i < len(arr); i++ {
		j := i + 1
		if arr[i] == arr[j] {
			arr[i] = maxnum + arr[i]
			maxnum = arr[i]
			sort.Ints(arr)
			count++
			break
		}
	}
	return arr, count
}

// 读取一行带空格的数据
func ReadLineNum() []int {
	read := bufio.NewReader(os.Stdin)
	s, _ := read.ReadString('\n')
	sarr := strings.Fields(s)
	arr := make([]int, 0)
	for _, s2 := range sarr {
		v, _ := strconv.Atoi(s2)
		arr = append(arr, v)
	}
	return arr

}

代码题 2

给定一组人的坐标 与 限定距离 人与人之间的 距离小于限定距离就会传染成高风险患者 被传染的人会 再次传染个身边小于限定距离的人 求从任意一个人开始最多的传染人数

解题思路 ：想到了要递归处理 但是时间不够了没写完 后面又花了大半个小时写好了 供大家参考

package main

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

type man struct {
	x    int
	y    int
	flag bool  //true为已传染  
}

// 两人间的距离
func length(man1 man, man2 man) int {
	lengt := int(math.Abs(float64(man1.x-man2.x))) + int(math.Abs(float64(man1.y-man2.y)))
	return lengt
}

// 传染过程  n为第n个人感染
func chuanran(n int, mans []man, k int) {
	mans[n].flag = true
	for i := 0; i < len(mans); i++ {
		if i == n {
			continue
		}
		if length(mans[i], mans[n]) < k && mans[i].flag == false {
			mans[i].flag = true
			chuanran(i, mans, k)  //递归传染
		}
	}
	return
}

func main() {
	var n, k int
	fmt.Scanf("%d %d\n", &n, &k)
	xi := ReadLineNum()
	yi := ReadLineNum()
	peoples := make([]man, 0)
	for i := 0; i < n; i++ {
		people := man{
			x:    xi[i],
			y:    yi[i],
			flag: false,
		}
		peoples = append(peoples, people)
	}

	maxcount := 0
  //
	for i := 0; i < len(peoples); i++ {
		arr := make([]man, len(peoples))
		copy(arr, peoples)
		chuanran(i, arr, k)
		for _, a := range arr {
			fmt.Println(a)
		}
		count := 0
		for _, m := range arr {
			if m.flag == true {
				count++
			}

		}
		if count > maxcount {
			maxcount = count
		}
		fmt.Println(count)
	}
	fmt.Println(maxcount)
	/*for _, people := range peoples {
		fmt.Println(people)
	}*/
}

func ReadLineNum() []int {
	read := bufio.NewReader(os.Stdin)
	s, _ := read.ReadString('\n')
	sarr := strings.Fields(s)
	arr := make([]int, 0)
	for _, s2 := range sarr {
		v, _ := strconv.Atoi(s2)
		arr = append(arr, v)
	}
	return arr

}