[TOC]
20年安卓暑期考核算法题
一：缺失数字
题目描述
给定一个包含
0, 1, 2, ..., n中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
解题思路
将给定数列排序，然后使用for循环依次进行比对，比对结果不匹配的数字即为所求。
Java代码
class Solution {
public int missingNumber(int[] nums) {
Arrays.sort(nums); //排序操作
for(int i=0; i < nums.length; i++){
if(nums[i] != i) //if判断
return i;
}
return nums.length;
}
}python代码
class Solution:
def missingNumber(self, nums: List[int]) -> int:
# 排序
nums.sort()
# 使用for循环进行对比
for i in range(len(nums)):
if nums[i] != i:
return i
return i+1二：字母异位词分组
题目描述
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明：所有输入均为小写字母。
不考虑答案输出的顺序。
解决思路
将给定的字符串转换为数组，在将数组排序后重新转换为字符串然后进行比对，如果存在就放在一起，不存在就另起一行，使用HashMap建立映射关系，最终返回一个ArrayList。
Java代码
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 返回值为List类型，List里面嵌套List，数据为String类型，因此定义HashMap值为List
Map<String, List> map = new HashMap<String, List>();
for (String i : strs){
// 将字符串转换为数组
char[] arr = i.toCharArray();
Arrays.sort(arr);
// 重新转换回来
String str = String.valueOf(arr);
if (!map.containsKey(str)) {
// 若不存在建立映射关系，排序后的字符串成为新的List集合
map.put(str, new ArrayList());
}
// 建立映射关系后添加
map.get(str).add(i);
}
//返回值是List集合 通过构造器 构造一个包含指定 collection 的元素的列表
return new ArrayList(map.values());
}
}python代码
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
from collections import defaultdict
look = defaultdict(list)
for s in strs:
look["".join(sorted(s))].append(s)
return list(look.values())三：金字塔转换矩阵
题目描述
现在，我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。
使用三元组表示金字塔的堆砌规则如下：
对于三元组(A, B, C) ，“C”为顶层方块，方块“A”、“B”分别作为方块“C”下一层的的左、右子块。当且仅当(A, B, C)是被允许的三元组，我们才可以将其堆砌上。
初始时，给定金字塔的基层 bottom，用一个字符串表示。一个允许的三元组列表 allowed，每个三元组用一个长度为 3 的字符串表示。
如果可以由基层一直堆到塔尖就返回 true ，否则返回 false 。
示例 1：
输入：bottom = “BCD”, allowed = [“BCG”, “CDE”, “GEA”, “FFF”]
输出：true
解析：
可以堆砌成这样的金字塔:
A
/
G E
/ \ /
B C D因为符合(‘B’, ‘C’, ‘G’), (‘C’, ‘D’, ‘E’) 和 (‘G’, ‘E’, ‘A’) 三种规则。
示例 2：输入：bottom = “AABA”, allowed = [“AAA”, “AAB”, “ABA”, “ABB”, “BAC”]
输出：false
解析：
无法一直堆到塔尖。
注意, 允许存在像 (A, B, C) 和 (A, B, D) 这样的三元组，其中 C != D。提示：
bottom 的长度范围在 [2, 8]。
allowed 的长度范围在[0, 200]。
方块的标记字母范围为{‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}。
python代码
class Solution:
def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
table = {}
for a, b, c in allowed:
table.setdefault(a, {}).setdefault(b, set()).add(c)
def get_next_bottoms(bottom, start=0):
if start >= len(bottom) - 1:
yield ''
return
a, b = bottom[start], bottom[start+1]
if a in table and b in table[a]:
for c in table[a][b]:
for res in get_next_bottoms(bottom, start+1):
yield c + res
def check(bottom):
return len(bottom) == 1 or any(check(next_bottom) for next_bottom in get_next_bottoms(bottom))
return check(bottom)四：被围绕的区域
题目描述
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：X X X X
X X X X
X X X X
X O X X
解释:被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
解题思路
典型的bfs问题，找到所有与边界‘O’相连的‘O’，标记为1，将其余标记为0的‘O’变换为‘X’
Java代码
class Solution {
int m, n;
boolean[][] visited;
private int d[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public void solve(char[][] board) {
if(board.length == 0){
return;
}
m = board.length;
n = board[0].length;
visited = new boolean[m][n];
//首先找到所有跟外界相连的O
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
if (isEdge && board[i][j] == 'O') {
dfs(board, i, j);
}
}
}
//根据数组visited的情况进行替换
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
public void dfs(char[][] board, int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int newx = x + d[i][0];
int newy = y + d[i][1];
if (inArea(newx, newy) && !visited[newx][newy] && board[newx][newy] == 'O') {
dfs(board, newx, newy);
}
}
}
private boolean inArea(int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n;
}
}五：最小路径和
题目描述
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
解题思路
这个是典型的数据结构中的最小路径问题，解题方法可用dfs+动态规划。
Java代码
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length < 1 || grid[0] == null || grid[0].length < 1) {
return 0;
}
int row = grid.length;
int col = grid[row - 1].length;
int dp[][] = new int[row][col];
dp[0][0] = grid[0][0];
for (int i = 1;i < row;i++)
dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int i = 1;i < col;i++)
dp[0][i] = dp[0][i - 1] + grid[0][i];
for (int i = 1;i < row;i++) {
for (int j = 1;j < col;j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[row - 1][col - 1];
}
}python代码
# 网上看到的大神代码，在原数组上进行最小计算，最终得到的结果
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
h, w=len(grid), len(grid[0])
for j in range(1,w):
grid[0][j]+=grid[0][j-1]
for i in range(1,h):
for j in range(w):
if j==0:
grid[i][j]+=grid[i-1][j]
else:
grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
return grid[-1][-1]
