【大厂真题】阿里巴巴春季实习生招聘3月6日场笔试_阿里笔试需要写输入输出吗

【真题】阿里巴巴3月6日笔试题

这回真挺难的…题量还是不够大

目录

第一题

第二题

第一题 回溯、递推与数学

有1，2，3三张卡片，现在输入一个N，构造一个N*3的矩阵，在矩阵中填入1，2，3

相邻的单元格数字不能重复。

如图所示:

请问有几种填法？

注：$1\le N\le 500$，结果要求对 $1000000007$ 取模

前言

阿里笔试限时1小时做两题，本身还是比较紧张的。

平时力扣刷的比较多，笔试却是acm模式（手动处理输入输出）

用Go刷的题，标准输入却不怎么接触，刚开始调试输入输出花了不少时间，引以为戒。

当然第一道难关是语文，看懂题搞清边界再着手解题，再是编码。

Naive Thoughts

这道题第一想法是回溯剪枝，类似于N皇后的情况。

N皇后的位运算，将每个格子的状态分成了0,1两种状态（放/不放），用二进制比特表示。

而这道题的是将状态变成了三种：1，2，3。需要用三进制（吹特）表示。

位运算剪枝的路子就被堵住了。

只能老老实实回溯。

注意⚠️：以下的解法TLE（超时）

package main

import "fmt"

var res = 0

func main() {
   
	var (
		T int
	)
	fmt.Scanln(&T)
	arr := make([]int, T)
	for t := T-1; t >= 0; t-- {
   
		fmt.Scanln(&arr[t])
	}

	for _,n:=range arr {
   
		solve(n)
		fmt.Println("res: ", res)
		res = 0
	 }
}

func solve(n int) {
   
	board := make([][]int, n)
	for i := 0; i < n; i++ {
   
		board[i] = make([]int, 3)
	}
	dfs(board, n)
}

func dfs(board [][]int, n int,count int) {
   
	if count == n*3 {
   
		fmt.Println(board)
		res++
	}
	// filled out
	for i := 0; i < n; i++ {
   
		for j := 0; j < 3; j++ {
   
			if board[i][j] == 0 {
   
				for k := 1; k <= 3; k++ {
   
					if valid(i, j, board, k) {
   
						board[i][j] = k
						dfs(board, n,count+1) 	
					} 	
				}
			}
		}
		return 
	}
}

func valid(i int, j int, board [][]int, k int) bool {
   
	if i < 0 && i >= len(board) && j < 0 && j >= len(board) {
   
		return false
	}
	up, down, left, right := i-1, i+1, j-1, j+1
	if up >= 0 && board[up][j] == k {
   
		return false
	}
	if left >= 0 && board[i][left] == k {
   
		return false
	}
	if right <= len(board[i])-1 && board[i][right] == k {
   
		return false
	}
	if down <= len(board)-1  && board[down][j] == k {
   
		return false 
	}
	return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

通解法

参考了力扣各路大神的解法

主要思想是要跳出回溯的框架（因为 1