后端书面考试标题-编程题解

前言

近日无事，写题有感，遂作此文
本文所触及的的标题来自于青训营后端书面考试操练(编程)题，标题的题解基于我的个人实践，很多东西基于我个人的理解，所以有望我们多多指教。
为了照料更多读者，我运用了Python和Golang两种言语分别编写了标题的题解。假如你发现了本文的错误之处，欢迎你在谈论区留言，我会及时的进行修正。假如你有其他的主意，也欢迎在谈论区留言，我会在看到谈论的第一时间回复。
Tips为了更好地整合文章，我现已将本文章录入至专栏“青训营题解”，专栏内有其他方向的内容，感爱好的小伙伴能够关注一下专栏。

标题：36进制加法

完成一个 36 进制的加法 0-9 a-z。
示例
输入：[“abbbb”,”1″]，输出：”abbbc”

题解

写题思路

本题的难点在于如何完成进制转化，完成进制转化的方法有很多，比如：逐位取数、取对数、位权法、查表法等，我运用的是位权法。
位权法的核心思维是将待转化的数的每一位与对应的位权相乘，再将一切的积相加得到转化成果。
以我的Python解法为例，我在代码的第二行和第三行，运用列表推导式遍历 n1 或 n2 的每个字符，并运用列表 cov_table 中的索引查找对应的数字。每个字符对应的数字乘以 36 的幂次方再累加到成果中，行将待转化的数的每一位与对应的位权相乘，再将一切的积相加得到转化成果。

位权法的数学原理： $x=∑i=0n−1aibix=\sum_{i=0}^{n-1}a_ib^i$

位权法能够用来完成恣意进制之间的转化，只需求修正进制数 $b$ 即可。其间， $x$ 是待转化的数， $a_i$ 是该数的第 $i$ 位的值， $b$ 是转化的进制数， $n$ 是该数的位数。

例如，将数字 ABC（十六进制）转化为十进制的进程能够用如下公式表明： $\times 16^2 + B \times 16^1 + C \times 16^0$
其间， $A$ 、 $B$ 、 $C$ 分别表明数字 ABC 的第三位、第二位、第一位的值。

代码完成

python解法

def add_36(n1, n2):
    cov_table = [str(i) for i in range(10)] + [chr(i) for i in range(ord('a'),ord('z')+1)]
    num1 = sum(cov_table.index(c) * 36 **i for i, c in enumerate(n1[::-1]))
    num2 = sum(cov_table.index(c) * 36 **i for i, c in enumerate(n2[::-1]))
    num = num1 + num2
    result = ''
    while num > 0:
        result = chr(num % 36 + ord('a') - 10) + result
        num //= 36
    return result

golang解法

package main
import (
	"fmt"
	"strconv"
)
func add36(num1, num2 string) string {
	// 创立转化表
	convertTable := "0123456789abcdefghijklmnopqrstuvwxyz"
	// 将字符串转化为数字
	num1Int, _ := strconv.ParseInt(num1, 36, 64)
	num2Int, _ := strconv.ParseInt(num2, 36, 64)
	// 将两个数字相加
	resultInt := num1Int + num2Int
	// 将成果转化为字符串
	resultStr := strconv.FormatInt(resultInt, 36)
	return resultStr
}

成果展现

标题：电影院座位引荐

抖音电影票事务支撑电影院选座，需求在用户买票时自动引荐座位，假如一个用户买了多张票，则需求引荐相邻(上下相邻、左右相邻都可)的座位。现在运用一个二维数组来表明电影院的座位，数组中 0 表明未被选座，1 表明已被选座或许为障碍物，请完成一个方法求出给定影院中最大可引荐的相邻座位个数。

示例输入：
[1,0,0,1,0,0,0]
[1,0,0,0,0,1,1]
[0,0,0,1,0,0,0]
[1,1,0,1,1,0,0]

输出：18

题解

写题思路

做过”01背包“这道标题的小伙伴在看到这道题的第一瞬间应该能够反应过来：这不就是一道动态规划标题嘛，还是很简单的。假如你有爱好，能够测验用动态规划的思维来测验处理这道题，我会把我写的动规的解法放在文末”码上“里供我们参阅。在这里，我介绍一下本题运用DFS和BFS的解法。
BFS（广度优先查找）和 DFS（深度优先查找）都是图论中常用的查找算法，它们能够用来遍历图中的一切节点，寻觅满足某些条件的途径。
关于本题，假如运用 BFS 或 DFS 进行查找，能够从每一个能够占用的座位动身，向相邻的座位进行拓宽，直到无法拓宽为止。在拓宽的进程中，能够运用一个变量记载现已拓宽的座位数，并更新最大值。
可是，BFS 和 DFS 的时间复杂度较高，在处理大规模数据时或许会超时。

运用 DFS 处理本题的思路如下：

界说四个方向数组，表明向左、向右、向上、向下移动一格。
界说一个二维数组，表明当时方位是否现已被访问过。
界说一个递归函数，用来从当时方位开端 DFS。
在递归函数中，判别当时方位是否现已被访问过或许是障碍物。假如是，则不进行 DFS，直接回来 0。不然，将当时方位符号为已访问，并初始化可引荐座位个数为 1。
遍历当时方位的每个相邻方位，假如相邻方位未被访问过且不是障碍物，则持续 DFS。
最终，回来可引荐座位个数。

运用 BFS 处理本题的思路如下：

界说四个方向数组，表明向左、向右、向上、向下移动一格。
界说一个二维数组，表明当时方位是否现已被访问过。
初始化一个行列，将一切能够占用的座位参加行列。
初始化最大可引荐座位个数为 0。
重复履行以下操作，直到行列为空：
- 取出行列的头元素。
- 将当时方位符号为已访问。
- 遍历当时方位的每个相邻方位，假如相邻方位未被访问过且不是障碍物，则将相邻方位参加行列。
- 更新最大可引荐座位个数。
回来最大可引荐座位个数。

代码完成

python解法

import random
from collections import deque
# DFS解法
def maxRecommend_dfs(cinema):
    # 四个方向数组，表明向左、向右、向上、向下移动一格
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    # 二维数组，表明当时方位是否现已被访问过
    visited = [[0] * len(cinema[0]) for _ in range(len(cinema))]
    def dfs(x, y):
        # 假如当时方位现已被访问过或许是障碍物，则不进行 DFS
        if visited[x][y] or cinema[x][y] == 1:
            return 0
        # 符号当时方位现已被访问过
        visited[x][y] = 1
        # 初始化可引荐座位个数
        count = 1
        # 遍历当时方位的每个相邻方位
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            # 假如相邻方位未被访问过且不是障碍物，则持续 DFS
            if 0 <= nx < len(cinema) and 0 <= ny < len(cinema[0]) and not visited[nx][ny] and cinema[nx][ny] == 0:
                count += dfs(nx, ny)
        return count
    # 初始化最大可引荐座位个数
    result = 0
    # 遍历每个未被访问过的座位
    for i in range(len(cinema)):
        for j in range(len(cinema[0])):
            if not visited[i][j] and cinema[i][j] == 0:
                # 从当时方位开端 DFS，并更新最大可引荐座位个数
                result = max(result, dfs(i, j))
    return result
# BFS解法
def maxRecommend_bfs(cinema):
    # 四个方向数组，表明向左、向右、向上、向下移动一格
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    # 二维数组，表明当时方位是否现已被访问过
    visited = [[0] * len(cinema[0]) for _ in range(len(cinema))]
    # 界说一个行列，用来存储 BFS 查找时遍历到的方位
    queue = deque()
    # 初始化最大可引荐座位个数
    result = 0
    # 遍历每个未被访问过的座位
    for i in range(len(cinema)):
        for j in range(len(cinema[0])):
            if not visited[i][j] and cinema[i][j] == 0:
                # 将当时方位参加行列
                queue.append((i, j))
                # 符号当时方位现已被访问过
                visited[i][j] = 1
                # 初始化当时引荐座位个数
                count = 1
                # 循环遍历行列中的每个方位
                while queue:
                    # 从行列中取出一个方位
                    x, y = queue.popleft()
                    # 遍历当时方位的每个相邻方位
                    for i in range(4):
                        nx, ny = x + dx[i], y + dy[i]
                        # 假如相邻方位未被访问过且不是障碍物，则参加行列
                        if 0 <= nx < len(cinema) and 0 <= ny < len(cinema[0]) and not visited[nx][ny] and cinema[nx][ny] == 0:
                            queue.append((nx, ny))
                            #符号相邻方位现已被访问过
                            visited[nx][ny] = 1
                            # 更新当时引荐座位个数
                            count += 1
                            # 更新最大可引荐座位个数
                            result = max(result, count)
    return result
# 数据生成器
def generate_random_seats(rows, cols):
    seats = [[random.randint(0, 1) for _ in range(cols)] for _ in range(rows)]
    return seats

golang解法

// DFS 完成
func maxSeatsDFS(seats [][]int) int {
	// 初始化答案
	maxSeats := 0
	// 创立 visited 数组记载每个方位是否访问过
	visited := make([][]bool, len(seats))
	for i := range visited {
		visited[i] = make([]bool, len(seats[0]))
	}
	// DFS 查找函数
	var search func(seats [][]int, visited [][]bool, i, j int) int
	search = func(seats [][]int, visited [][]bool, i, j int) int {
		// 假如越界或许当时方位为障碍物或许现已访问过，回来 0
		if i < 0 || i >= len(seats) || j < 0 || j >= len(seats[0]) || seats[i][j] == 1 || visited[i][j] {
			return 0
		}
		// 符号当时方位为已访问
		visited[i][j] = true
		// 递归查找上下左右四个方向
		return 1 + search(seats, visited, i-1, j) + search(seats, visited, i+1, j) + search(seats, visited, i, j-1) + search(seats, visited, i, j+1)
	}
	// 遍历一切方位，核算最大的相邻座位个数
	for i := 0; i < len(seats); i++ {
		for j := 0; j < len(seats[0]); j++ {
			if seats[i][j] == 0 {
				maxSeats = max(maxSeats, search(seats, visited, i, j))
			}
		}
	}
	return maxSeats
}
// BFS完成
func maxSeatsBFS(cinema [][]int) int {
	// 四个方向数组，表明向左、向右、向上、向下移动一格
	dx := []int{-1, 1, 0, 0}
	dy := []int{0, 0, -1, 1}
	// 二维数组，表明当时方位是否现已被访问过
	visited := make([][]int, len(cinema))
	for i := range visited {
		visited[i] = make([]int, len(cinema[0]))
	}
	// 界说一个行列，用来存储 BFS 查找时遍历到的方位
	queue := []int{}
	// 初始化最大可引荐座位个数
	result := 0
	// 遍历每个未被访问过的座位
	for i := 0; i < len(cinema); i++ {
		for j := 0; j < len(cinema[0]); j++ {
			if visited[i][j] == 0 && cinema[i][j] == 0 {
				// 将当时方位参加行列
				queue = append(queue, i*len(cinema[0])+j)
				// 符号当时方位现已被访问过
				visited[i][j] = 1
				// 初始化当时引荐座位个数
				count := 1
				// 循环遍历行列中的每个方位
				for len(queue) > 0 {
					// 从行列中取出一个方位
					x, y := queue[0]/len(cinema[0]), queue[0]%len(cinema[0])
					queue = queue[1:]
					// 遍历当时方位的每个相邻方位
					for i := 0; i < 4; i++ {
						nx, ny := x+dx[i], y+dy[i]
						// 假如相邻方位未被访问过且不是障碍物，则参加行列
						if nx >= 0 && nx < len(cinema) && ny >= 0 && ny < len(cinema[0]) && visited[nx][ny] == 0 && cinema[nx][ny] == 0 {
							queue = append(queue, nx*len(cinema[0])+ny)
							//符号相邻方位现已被访问过
							visited[nx][ny] = 1
							// 更新当时引荐座位个数
							count++
							// 更新最大可引荐座位个数
							result = max(result, count)
						}
					}
				}
			}
		}
	}
	return result
}
// 界说 max 函数
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

成果展现

标题：有用 IP 地址

有用 IP 地址正好由四个整数（每个整数坐落 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：”0.1.2.201″ 和 “192.168.1.1” 是有用 IP 地址，可是 “0.011.255.245”、”192.168.1.312″ 和 “192.168@1.1” 是无效 IP 地址。

给定一个字符串 s，非数字的字符可替换为恣意不包含在本字符串的数字，相同的字符只能替换为相同的数字，用以表明一个 IP 地址，回来一切或许的有用 IP 地址，这些地址能够经过在 s 中刺进 ‘.’ 来形成。你不能从头排序或删去 s 中的任何数字，你能够按任何次序回来答案。

示例 1
输入：20212118136
输出：
20.212.118.136
202.12.118.136
202.121.18.136
202.121.181.36

示例 2
输入：11a2b22a037
输出：114.252.240.37

题解

解题思路

这道题路首要检测逻辑性，信任很多读者也发现了，leetcode上面有题和这道题相似，但和leetcode上那道题不同的是，本题加了一个条件，即：”非数字的字符可替换为恣意不包含在本字符串的数字，相同的字符只能替换为相同的数字“，这就需求我们处理好替换字母的值不能和字符串本身的数字重复。
我的思路是创立一个列表来记载重复的数字

解题思路如下：

界说一个递归函数，用于在字符串 s 中刺进 ‘.’，并生成或许的有用 IP 地址。
在递归函数中，首要判别当时递归深度是否达到了 4，假如达到了 4，则判别当时字符串是否是有用 IP 地址，假如是，则将其参加答案中。
假如当时递归深度未达到 4，则从当时方位开端，往后枚举或许的 IP 地址数字，并调用递归函数持续刺进 ‘.’。
在枚举进程中，需求留意以下几点：
- 假如当时字符是数字，则直接添加到字符串中。
- 假如当时字符是字母，则枚举一切或许的数字，并将当时字符替换
最终，在主函数中，调用递归函数并回来答案即可。

代码完成

Python解法

import itertools as it
def create_mapping(s, numbers, mappings):
    # 创立字典，用于记载每个非数字字符对应的数字
    # 创立列表，用于记载被删去的数字，避免重复删去
    no = []
    nodigit = []
    for c in s:
        if c in no or c in nodigit:
            continue
        elif c.isdigit():
            no.append(c)
            numbers.remove(c)
        else:
            nodigit.append(c)
    for e in it.permutations(numbers, len(nodigit)):
        mapping = {}
        x = 0
        for c in nodigit:
            mapping[c] = e[x]
            x += 1
        mappings.append(mapping)
    return mappings
def is_valid_part(s, mapping):
    if not s:
        return False
    # if len(s) > 1 and s[0] == '0':
    #     return False
    for c in s:
        if c in mapping:
            s = s.replace(c, mapping[c])
    if len(s) > 1 and s[0] == '0':
        return False
    if not s.isdigit():
        return False
    if int(s) > 255:
        return False
    return True
def dfs(s, path, res, mapping):
    if not s and len(path) == 4:
        res.append('.'.join(path))
        return
    if len(path) == 4:
        return
    for i in range(1, 4):
        if i > len(s):
            break
        part = s[:i]
        if is_valid_part(part, mapping):
            dfs(s[i:], path + [part], res, mapping)
def restoreIpAddresses(s):
    ans = []
    # 创立字典，用于记载每个非数字字符对应的数字
    numbers = [str(i) for i in range(10)]
    mappings = []
    mappings = create_mapping(s, numbers, mappings)
    for mapping in mappings:
        res = []
        dfs(s, [], res, mapping)
        translator = str.maketrans(mapping)
        for i in range(len(res)):
            ans.append(res[i].translate(translator))
    return ans

golang题解

func createMapping(s string, numbers []string, mapping map[byte]string) map[byte]string {
	// 创立字典，用于记载每个非数字字符对应的数字
        // 创立列表，用于记载被删去的数字，避免重复删去
	no := []string{}
        x := 0
	for i := 0; i < len(s); i++ {
		if stringInSlice(string(s[i]), no) {
			continue
		} else if unicode.IsDigit(rune(s[i])) {
			no = append(no, string(s[i]))
			numbers = remove(numbers, string(s[i]))
		} else {
			mapping[s[i]] = numbers[x]
                        x += 1
		}
	}
	return mapping
}
func stringInSlice(a string, list []string) bool {
	for _, b := range list {
		if b == a {
			return true
		}
	}
	return false
}
func remove(slice []string, element string) []string {
	for i, v := range slice {
		if v == element {
			return append(slice[:i], slice[i+1:]...)
		}
	}
	return slice
}
func isValidPart(s string, mapping map[byte]string) bool {
	if s == "" {
		return false
	}
	if len(s) > 1 && s[0] == '0' {
		return false
	}
	for i := 0; i < len(s); i++ {
		if val, ok := mapping[s[i]]; ok {
			s = strings.Replace(s, string(s[i]), val, 1)
		}
	}
	if !isNumber(s) {
		return false
	}
	if strToInt(s) > 255 {
		return false
	}
	return true
}
func isNumber(s string) bool {
	_, err := strconv.ParseInt(s, 10, 64)
	return err == nil
}
func strToInt(s string) int {
	num, _ := strconv.ParseInt(s, 10, 64)
	return int(num)
}
func dfs(s string, path []string, res *[]string, mapping map[byte]string) {
	if s == "" && len(path) == 4 {
		*res = append(*res, strings.Join(path, "."))
		return
	}
	if len(path) == 4 {
		return
	}
	for i := 1; i < 4; i++ {
		if i > len(s) {
			break
		}
		part := s[:i]
		if isValidPart(part, mapping) {
			dfs(s[i:], append(path, part), res, mapping)
		}
	}
}
func restoreIpAddresses(s string) []string {
	ans := []string{}
	// 创立字典，用于记载每个非数字字符对应的数字
	numbers := []string{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}
	mapping := map[byte]string{}
	// 运用字典将输入字符串中的字母替换成没有出现在输入字符串中的单个数字
	mapping = createMapping(s, numbers, mapping)
	res := []string{}
	dfs(s, []string{}, &res, mapping)
	// translator := str.maketrans(mapping)
	// new_res = res[0].translate(translator)
	for i := 0; i < len(res); i++ {
		ip := ""
		for j := 0; j < len(res[i]); j++ {
			if val, ok := mapping[res[i][j]]; ok {
				ip += val
			} else {
				ip += string(res[i][j])
			}
		}
		ans = append(ans, ip)
	}
	return ans
}

成果展现

最终

假如你觉得本文对你有协助，欢迎你留下一个大大的赞，你的支撑是我更新最大的动力，下次更新会更快！（请点击Script检查代码）

【后端部分】青训营题目的思维拓展：解题思路分享

后端书面考试标题-编程题解

前言

标题：36进制加法

题解

写题思路

代码完成

成果展现

标题：电影院座位引荐

题解

写题思路

代码完成

成果展现

标题：有用 IP 地址

题解

解题思路

代码完成

成果展现

最终

作者信息

推广

【后端部分】青训营题目的思维拓展：解题思路分享

后端书面考试标题-编程题解

前言

标题：36进制加法

题解

写题思路

代码完成

成果展现

标题：电影院座位引荐

题解

写题思路

代码完成

成果展现

标题：有用 IP 地址

题解

解题思路

代码完成

成果展现

最终

相关文章

Android 中手指从按钮 A 平移到 B，会发生什么？为什么？

但行好事，莫问前程……

记录我被疫情占据的这半年

SwiftUI魔法：通过DragGesture互动提升用户体验

作者信息

推广