2020秋招小米软件开发笔试题

题型结构

10道单选
10道多选
2道编程

单选和多选题，难度不高偏基础。

编程题

1.判断密码是否符合要求：
给一行密码：每个密码用空格分隔
（1）同时具有大写、小写、符号、数字，则输出0；
（2）长度不在8-120之间，则输出1；
（3）类型不符合输出，即不符合（1）条件，则输出2；

2.leetcode 79 原题：单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

思路

第一题是正则，不过类型要分开写，标4个状态即可。
第二题DFS+回溯，关键点在于统一大小写。

代码

1.只过了83%，问题是符号忘了怎么表示。符号直接else就好了。。
贴的别人100%代码。

#include <bits/stdc++.h>

using namespace std;

int Process(string &code) {
	int n = code.length();
	if (n < 8 || n>120) return 1;
	bool num = false, symbol = false, D = false, X = false;
	for (int i = 0; i < n; ++i) {
		if (num == true && symbol == true && D == true && X == true) return 0;
		if (code[i] >= '0' && code[i] <= '9') num = true;
		if (code[i] >= 'a' && code[i] <= 'z') X = true;
		if (code[i] >= 'A' && code[i] <= 'Z') D = true;
		else symbol = true;
	}
	return 2;
}

int main()
{
	vector<string> str;
	string s = "";
	while (cin >> s) {
		str.emplace_back(s);
	}
	vector<int> ret;
	for (auto &s : str) {
		ret.emplace_back(Process(s));
	}
	for (auto &v : ret)
		cout << v << "\n";
}

2.应该是100%AC，不过小米这出题出的有点问题，最后半小时不到给的公告，也没注意到。。有点尬。
用python写的。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        row = len(board)
        col = len(board[0])

        def helper(i, j, k, visited):
            #print(i,j, k,visited)
            if k == len(word):
                return True
            for x, y in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                tmp_i = x + i
                tmp_j = y + j
                if 0 <= tmp_i < row and 0 <= tmp_j < col and (tmp_i, tmp_j) not in visited \
                and board[tmp_i][tmp_j] == word[k]:
                    visited.add((tmp_i, tmp_j))
                    if helper(tmp_i, tmp_j, k+1, visited):
                        return True
                    visited.remove((tmp_i, tmp_j)) # 回溯
            return False
        
        for i in range(row):
            for j in range(col):
                if board[i][j] == word[0] and helper(i, j, 1,{(i, j)}) :
                        return True
        return False