中等难题
这一章包含各种中等难度的综合题目，考察对多种数据结构和算法的综合运用能力。
面试题 16.01. 交换数字
题目描述
编写一个函数，不用临时变量，直接交换两个数的值。
示例：
输入: numbers = [1,2]
输出: [2,1]
解题思路
使用异或运算进行交换。a ^= b; b ^= a; a ^= b; 或者使用加减法。
Java 代码实现
class Solution {
public int[] swapNumbers(int[] numbers) {
numbers[0] ^= numbers[1];
numbers[1] ^= numbers[0];
numbers[0] ^= numbers[1];
return numbers;
}
}
面试题 16.02. 单词频率
题目描述
设计一个方法，找出任意指定单词在一本书中的出现频率。
示例：
WordsFrequency wordsFrequency = new WordsFrequency({"i", "have", "an", "apple", "he", "have", "a", "apple"});
wordsFrequency.get("apple"); // 返回 2
wordsFrequency.get("have"); // 返回 2
wordsFrequency.get("an"); // 返回 1
wordsFrequency.get("orange"); // 返回 0
解题思路
使用哈希表统计每个单词的出现次数。
Java 代码实现
class WordsFrequency {
private Map<String, Integer> map;
public WordsFrequency(String[] book) {
map = new HashMap<>();
for (String word : book) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
}
public int get(String word) {
return map.getOrDefault(word, 0);
}
}
面试题 16.03. 交点
题目描述
给定两条线段（表示为起点 start = {X1, Y1} 和终点 end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。
示例 1：
输入：
start1 = [0,0], end1 = [1,0], start2 = [1,1], end2 = [0,-1]
输出：[0.5,0.0]
解题思路
使用参数方程表示线段，求解两条直线的交点，然后判断交点是否在两条线段上。
Java 代码实现
class Solution {
public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
int x1 = start1[0], y1 = start1[1];
int x2 = end1[0], y2 = end1[1];
int x3 = start2[0], y3 = start2[1];
int x4 = end2[0], y4 = end2[1];
double[] ans = new double[2];
boolean flag = false;
if ((x1 - x2) * (y3 - y4) == (y1 - y2) * (x3 - x4)) {
if (isInside(start1, end1, start2) && isInside(start1, end1, end2)) {
return new double[]{x3, y3};
}
if (isInside(start2, end2, start1) && isInside(start2, end2, end1)) {
return new double[]{x1, y1};
}
return new double[]{};
}
double t1 = (double)(x3 - x1) * (y3 - y4) - (y3 - y1) * (x3 - x4);
double t2 = (double)(x1 - x2) * (y3 - y1) - (y1 - y2) * (x3 - x1);
double t = t1 / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
double u = t2 / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
if (t >= 0 && t <= 1 && u >= 0 && u <= 1) {
ans[0] = x1 + t * (x2 - x1);
ans[1] = y1 + t * (y2 - y1);
flag = true;
}
return flag ? ans : new double[]{};
}
private boolean isInside(int[] start, int[] end, int[] point) {
return Math.min(start[0], end[0]) <= point[0] && point[0] <= Math.max(start[0], end[0]) &&
Math.min(start[1], end[1]) <= point[1] && point[1] <= Math.max(start[1], end[1]);
}
}
面试题 16.04. 井字游戏
题目描述
设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符 " "，"X" 和 "O" 组成，其中 " " 代表一个空位。
示例：
输入： board = ["O X"," X "," X O"]
输出： "X"
解题思路
检查每一行、每一列、两条对角线是否有相同的字符。
Java 代码实现
class Solution {
public String tictactoe(String[] board) {
int n = board.length;
boolean hasEmpty = false;
for (int i = 0; i < n; i++) {
char c = board[i].charAt(0);
if (c == ' ') {
hasEmpty = true;
continue;
}
boolean win = true;
for (int j = 1; j < n; j++) {
if (board[i].charAt(j) != c) {
win = false;
break;
}
}
if (win) return String.valueOf(c);
}
for (int j = 0; j < n; j++) {
char c = board[0].charAt(j);
if (c == ' ') {
hasEmpty = true;
continue;
}
boolean win = true;
for (int i = 1; i < n; i++) {
if (board[i].charAt(j) != c) {
win = false;
break;
}
}
if (win) return String.valueOf(c);
}
char c = board[0].charAt(0);
if (c != ' ') {
boolean win = true;
for (int i = 1; i < n; i++) {
if (board[i].charAt(i) != c) {
win = false;
break;
}
}
if (win) return String.valueOf(c);
}
c = board[0].charAt(n - 1);
if (c != ' ') {
boolean win = true;
for (int i = 1; i < n; i++) {
if (board[i].charAt(n - 1 - i) != c) {
win = false;
break;
}
}
if (win) return String.valueOf(c);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i].charAt(j) == ' ') {
hasEmpty = true;
}
}
}
return hasEmpty ? "Pending" : "Draw";
}
}
面试题 16.05. 阶乘尾数
题目描述
设计一个算法，算出 n 阶乘有多少个尾随零。
示例 1：
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2：
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零。
解题思路
尾随零的数量等于 n! 中因子 5 的个数。因为 2 的个数比 5 多，所以只需要计算 5 的个数。
Java 代码实现
class Solution {
public int trailingZeroes(int n) {
int count = 0;
while (n >= 5) {
count += n / 5;
n /= 5;
}
return count;
}
}
面试题 16.06. 最小差
题目描述
给定两个整数数组 a 和 b，计算具有最小差绝对值的一对数值（每个数组中各取一个值），并返回该对数值的差。
示例：
输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出：3，即数值对(11, 8)
解题思路
先排序两个数组，然后使用双指针找到最小差。
Java 代码实现
class Solution {
public int smallestDifference(int[] a, int[] b) {
Arrays.sort(a);
Arrays.sort(b);
int i = 0, j = 0;
long minDiff = Long.MAX_VALUE;
while (i < a.length && j < b.length) {
minDiff = Math.min(minDiff, Math.abs((long)a[i] - b[j]));
if (a[i] < b[j]) {
i++;
} else {
j++;
}
}
return (int) minDiff;
}
}
面试题 16.07. 最大数值
题目描述
编写一个方法，找出两个数字 a 和 b 中最大的那一个。不得使用 if-else 或其他比较运算符。
示例：
输入： a = 1, b = 2
输出： 2
解题思路
使用数学公式：max(a, b) = (a + b + |a - b|) / 2，或者使用位运算。
Java 代码实现
class Solution {
public int maximum(int a, int b) {
long diff = (long)a - (long)b;
int k = (int)(diff >>> 63);
return a * (1 - k) + b * k;
}
}
面试题 16.08. 整数的英语表示
题目描述
给定一个整数，打印该整数的英文描述。
示例 1：
输入: 123
输出: "One Hundred Twenty Three"
示例 2：
输入: 12345
输出: "Twelve Thousand Three Hundred Forty Five"
解题思路
将数字按三位一组处理，每组使用相同的转换逻辑，然后添加单位（Thousand, Million, Billion）。
Java 代码实现
class Solution {
private String[] ones = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
private String[] teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public String numberToWords(int num) {
if (num == 0) return "Zero";
return helper(num);
}
private String helper(int num) {
StringBuilder sb = new StringBuilder();
if (num >= 1000000000) {
sb.append(helper(num / 1000000000)).append(" Billion");
num %= 1000000000;
if (num > 0) sb.append(" ");
}
if (num >= 1000000) {
sb.append(helper(num / 1000000)).append(" Million");
num %= 1000000;
if (num > 0) sb.append(" ");
}
if (num >= 1000) {
sb.append(helper(num / 1000)).append(" Thousand");
num %= 1000;
if (num > 0) sb.append(" ");
}
if (num >= 100) {
sb.append(ones[num / 100]).append(" Hundred");
num %= 100;
if (num > 0) sb.append(" ");
}
if (num >= 20) {
sb.append(tens[num / 10]);
num %= 10;
if (num > 0) sb.append(" ");
}
if (num >= 10) {
sb.append(teens[num - 10]);
} else if (num > 0) {
sb.append(ones[num]);
}
return sb.toString();
}
}
面试题 16.09. 运算
题目描述
请实现整数数字乘法、减法和除法运算，运算结果均为整数数字，程序中只允许使用加法运算符和逻辑运算符，允许程序中出现正负常数，不允许使用位运算。
解题思路
- 减法：
a - b = a + (-b)，其中-b = ~b + 1（但题目不允许位运算），可以用0 - b实现 - 乘法：使用循环加法
- 除法：使用循环减法
Java 代码实现
class Operations {
public Operations() {
}
public int minus(int a, int b) {
return a + negate(b);
}
public int multiply(int a, int b) {
if (a == 0 || b == 0) return 0;
int result = 0;
int absB = b > 0 ? b : negate(b);
for (int i = 0; i < absB; i++) {
result += a;
}
return b > 0 ? result : negate(result);
}
public int divide(int a, int b) {
if (a == 0) return 0;
if (b == 1) return a;
if (b == -1) return negate(a);
int absA = a > 0 ? a : negate(a);
int absB = b > 0 ? b : negate(b);
int result = 0;
while (absA >= absB) {
absA = minus(absA, absB);
result++;
}
if ((a > 0 && b > 0) || (a < 0 && b < 0)) {
return result;
}
return negate(result);
}
private int negate(int x) {
if (x == 0) return 0;
int neg = 0;
int d = x < 0 ? 1 : -1;
while (x != 0) {
neg += d;
x += d;
}
return neg;
}
}
面试题 16.10. 生存人数
题目描述
给定 N 个人的出生年份和死亡年份，第 i 个人的年份为 birth[i] 和 death[i]，计算存活人数最多的年份。
示例：
输入：
birth = {1900, 1901, 1950}
death = {1948, 1951, 2000}
输出： 1901
解题思路
使用差分数组记录每年的变化，然后计算前缀和找到最大值对应的年份。
Java 代码实现
class Solution {
public int maxAliveYear(int[] birth, int[] death) {
int[] delta = new int[102];
for (int i = 0; i < birth.length; i++) {
delta[birth[i] - 1900]++;
delta[death[i] - 1900 + 1]--;
}
int maxAlive = 0, year = 0, alive = 0;
for (int i = 0; i < 102; i++) {
alive += delta[i];
if (alive > maxAlive) {
maxAlive = alive;
year = i + 1900;
}
}
return year;
}
}
面试题 16.11. 跳水板
题目描述
你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为 shorter，长度较长的木板长度为 longer。你必须正好使用 k 块木板。编写一个方法，生成跳水板所有可能的长度。
示例 1：
输入：
shorter = 1
longer = 2
k = 3
输出： [3,4,5,6]
解题思路
使用 i 块长木板和 k-i 块短木板，计算所有可能的长度。
Java 代码实现
class Solution {
public int[] divingBoard(int shorter, int longer, int k) {
if (k == 0) return new int[0];
if (shorter == longer) return new int[]{shorter * k};
int[] result = new int[k + 1];
for (int i = 0; i <= k; i++) {
result[i] = shorter * (k - i) + longer * i;
}
return result;
}
}
面试题 16.13. 平分正方形
题目描述
给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。正方形通过两个点定义，即左上角和右下角。
示例：
输入：
square1 = {-1, -1, 2}
square2 = {0, -1, 2}
输出： {-1,0,2,0}
解题思路
连接两个正方形的中心点，这条直线将两个正方形平分。
Java 代码实现
class Solution {
public double[] cutSquares(int[] square1, int[] square2) {
double x1 = square1[0] + square1[2] / 2.0;
double y1 = square1[1] + square1[2] / 2.0;
double x2 = square2[0] + square2[2] / 2.0;
double y2 = square2[1] + square2[2] / 2.0;
if (x1 == x2) {
double minY = Math.min(square1[1], square2[1]);
double maxY = Math.max(square1[1] + square1[2], square2[1] + square2[2]);
return new double[]{x1, minY, x2, maxY};
}
double k = (y2 - y1) / (x2 - x1);
double b = y1 - k * x1;
double[] result = new double[4];
if (Math.abs(k) <= 1) {
double minX = Math.min(square1[0], square2[0]);
double maxX = Math.max(square1[0] + square1[2], square2[0] + square2[2]);
result[0] = minX;
result[1] = k * minX + b;
result[2] = maxX;
result[3] = k * maxX + b;
} else {
double minY = Math.min(square1[1], square2[1]);
double maxY = Math.max(square1[1] + square1[2], square2[1] + square2[2]);
result[0] = (minY - b) / k;
result[1] = minY;
result[2] = (maxY - b) / k;
result[3] = maxY;
}
if (result[0] > result[2] || (result[0] == result[2] && result[1] > result[3])) {
double temp = result[0];
result[0] = result[2];
result[2] = temp;
temp = result[1];
result[1] = result[3];
result[3] = temp;
}
return result;
}
}
面试题 16.14. 最佳直线
题目描述
给定一个二维平面及平面上的若干点，求最多有多少个点在同一条直线上。
示例 1：
输入： [[1,1],[2,2],[3,3]]
输出： 3
解题思路
对于每个点，计算它与其他所有点形成的斜率，使用哈希表统计相同斜率的点的数量。
Java 代码实现
class Solution {
public int[] bestLine(int[][] points) {
int maxCount = 0;
int[] result = new int[2];
int n = points.length;
for (int i = 0; i < n; i++) {
Map<String, Integer> slopeCount = new HashMap<>();
Map<String, Integer> firstIndex = new HashMap<>();
int samePoint = 1;
int localMax = 0;
int[] localResult = new int[2];
for (int j = i + 1; j < n; j++) {
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
if (dx == 0 && dy == 0) {
samePoint++;
continue;
}
int g = gcd(dx, dy);
String slope = (dx / g) + "/" + (dy / g);
slopeCount.put(slope, slopeCount.getOrDefault(slope, 0) + 1);
if (!firstIndex.containsKey(slope)) {
firstIndex.put(slope, j);
}
int count = slopeCount.get(slope);
if (count > localMax || (count == localMax && firstIndex.get(slope) < localResult[1])) {
localMax = count;
localResult[0] = i;
localResult[1] = firstIndex.get(slope);
}
}
int total = localMax + samePoint;
if (total > maxCount || (total == maxCount && i < result[0])) {
maxCount = total;
result[0] = i;
result[1] = localResult[1];
}
}
return result;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
面试题 16.15. 珠玑妙算
题目描述
珠玑妙算游戏（the game of master mind）的玩法如下。计算机有 4 个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝色（B）。例如，计算机可能有 RGGB 4 种（槽 1 为红色，槽 2 为绿色，以此类推）。玩家作为猜的一方，需要猜出正确的颜色组合。猜的过程中，玩家需要猜测 4 种颜色是什么，然后计算机给出反馈。反馈以两个数字表示：猜中的次数和伪猜中的次数。猜中是指槽和颜色都正确，伪猜中是指颜色正确但槽不对。
示例：
输入： solution="RGBY",guess="GGRR"
输出： [1,1]
解题思路
先统计猜中的次数，然后统计伪猜中的次数（排除已猜中的位置）。
Java 代码实现
class Solution {
public int[] masterMind(String solution, String guess) {
int hit = 0, pseudoHit = 0;
int[] countS = new int[4];
int[] countG = new int[4];
for (int i = 0; i < 4; i++) {
char s = solution.charAt(i);
char g = guess.charAt(i);
if (s == g) {
hit++;
} else {
countS[getIndex(s)]++;
countG[getIndex(g)]++;
}
}
for (int i = 0; i < 4; i++) {
pseudoHit += Math.min(countS[i], countG[i]);
}
return new int[]{hit, pseudoHit};
}
private int getIndex(char c) {
switch (c) {
case 'R': return 0;
case 'Y': return 1;
case 'G': return 2;
case 'B': return 3;
}
return -1;
}
}
面试题 16.16. 部分排序
题目描述
给定一个整数数组，编写一个函数，找出索引 m 和 n，只要将索引区间 [m,n] 的元素排好序，整个数组就是有序的。注意：n-m 尽量最小，也就是说，找出符合条件的最短序列。
示例：
输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]
解题思路
从左向右找最后一个不满足升序的位置，从右向左找最后一个不满足降序的位置。
Java 代码实现
class Solution {
public int[] subSort(int[] array) {
if (array == null || array.length == 0) return new int[]{-1, -1};
int n = array.length;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int left = -1, right = -1;
for (int i = 0; i < n; i++) {
if (array[i] < max) {
right = i;
} else {
max = array[i];
}
}
for (int i = n - 1; i >= 0; i--) {
if (array[i] > min) {
left = i;
} else {
min = array[i];
}
}
return new int[]{left, right};
}
}
面试题 16.17. 连续数列
题目描述
给定一个整数数组，找出总和最大的连续数列，并返回总和。
示例：
输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
解题思路
使用 Kadane 算法，维护当前子数组的和，如果和为负数则重新开始。
Java 代码实现
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
}
面试题 16.18. 模式匹配
题目描述
你有两个字符串，即 pattern 和 value。pattern 字符串由字母 "a" 和 "b" 组成，描述字符串中的模式。例如，字符串 "catcatgocatgo" 匹配模式 "aabab"（其中 "a" 是 "cat"，"b" 是 "go"）。
示例 1：
输入： pattern = "abba", value = "dogcatcatdog"
输出： true
解题思路
枚举 a 和 b 对应字符串的长度，然后验证是否匹配。
Java 代码实现
class Solution {
public boolean patternMatching(String pattern, String value) {
int countA = 0, countB = 0;
for (char c : pattern.toCharArray()) {
if (c == 'a') countA++;
else countB++;
}
if (countA < countB) {
int temp = countA;
countA = countB;
countB = temp;
char[] chars = pattern.toCharArray();
for (int i = 0; i < chars.length; i++) {
chars[i] = chars[i] == 'a' ? 'b' : 'a';
}
pattern = new String(chars);
}
if (value.length() == 0) {
return countB == 0;
}
for (int lenA = 0; lenA * countA <= value.length(); lenA++) {
int remaining = value.length() - lenA * countA;
if ((countB == 0 && remaining == 0) || (countB != 0 && remaining % countB == 0)) {
int lenB = countB == 0 ? 0 : remaining / countB;
String strA = "", strB = "";
int index = 0;
boolean valid = true;
for (char c : pattern.toCharArray()) {
if (c == 'a') {
String sub = value.substring(index, index + lenA);
if (strA.equals("")) {
strA = sub;
} else if (!strA.equals(sub)) {
valid = false;
break;
}
index += lenA;
} else {
String sub = value.substring(index, index + lenB);
if (strB.equals("")) {
strB = sub;
} else if (!strB.equals(sub)) {
valid = false;
break;
}
index += lenB;
}
}
if (valid && !strA.equals(strB)) {
return true;
}
}
}
return false;
}
}
面试题 16.19. 水域大小
题目描述
你有一个用于表示一片土地的整数矩阵 land，该矩阵中每个点的值代表对应地点的海拔高度。请计算上、下、左、右、左上、左下、右上、右下 8 个方向相连的水域大小。
示例：
输入：
[
[0,2,1,0],
[0,1,0,1],
[1,1,0,1],
[0,1,0,1]
]
输出： [1,2,4]
解题思路
使用 DFS 或 BFS 遍历每个水域，计算其大小。
Java 代码实现
class Solution {
public int[] pondSizes(int[][] land) {
List<Integer> sizes = new ArrayList<>();
int m = land.length, n = land[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (land[i][j] == 0) {
sizes.add(dfs(land, i, j));
}
}
}
int[] result = sizes.stream().mapToInt(Integer::intValue).toArray();
Arrays.sort(result);
return result;
}
private int dfs(int[][] land, int i, int j) {
if (i < 0 || i >= land.length || j < 0 || j >= land[0].length || land[i][j] != 0) {
return 0;
}
land[i][j] = -1;
int size = 1;
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (di != 0 || dj != 0) {
size += dfs(land, i + di, j + dj);
}
}
}
return size;
}
}
面试题 16.20. T9键盘
题目描述
在老式手机上，用户通过数字键盘输入，手机将提供与这些数字相匹配的单词列表。每个数字映射到若干字母。给定一个单词列表和一个数字字符串，返回所有能被该数字字符串匹配的单词。
示例：
输入: num = "8733", words = ["tree", "used"]
输出: ["tree", "used"]
解题思路
将每个单词转换为数字序列，然后与输入的数字字符串比较。
Java 代码实现
class Solution {
public List<String> getValidT9Words(String num, String[] words) {
List<String> result = new ArrayList<>();
int[] map = {2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9};
for (String word : words) {
if (word.length() != num.length()) continue;
boolean valid = true;
for (int i = 0; i < word.length(); i++) {
int digit = map[word.charAt(i) - 'a'];
if (digit != num.charAt(i) - '0') {
valid = false;
break;
}
}
if (valid) {
result.add(word);
}
}
return result;
}
}
面试题 16.21. 交换和
题目描述
给定两个整数数组，请交换一对数值（每个数组取一个数值），使得两个数组所有元素的和相等。
示例：
输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
输出: [1, 3]
解题思路
设两个数组的和分别为 sum1 和 sum2，需要找到 a 和 b 使得 sum1 - a + b = sum2 - b + a，即 a - b = (sum1 - sum2) / 2。
Java 代码实现
class Solution {
public int[] findSwapValues(int[] array1, int[] array2) {
int sum1 = 0, sum2 = 0;
Set<Integer> set1 = new HashSet<>();
for (int num : array1) {
sum1 += num;
set1.add(num);
}
for (int num : array2) {
sum2 += num;
}
int diff = sum1 - sum2;
if (diff % 2 != 0) return new int[]{};
for (int num : array2) {
if (set1.contains(num + diff / 2)) {
return new int[]{num + diff / 2, num};
}
}
return new int[]{};
}
}
面试题 16.22. 兰顿蚂蚁
题目描述
假设蚂蚁位于一个无限网格上，每个格子初始为白色。蚂蚁根据以下规则移动：
- 如果在白色格子上，翻转格子颜色，向右转 90 度，向前移动一步
- 如果在黑色格子上，翻转格子颜色，向左转 90 度，向前移动一步
给定整数 K，返回 K 步后蚂蚁的位置和方向。
解题思路
使用 Set 记录黑色格子的位置，模拟蚂蚁的移动。
Java 代码实现
class Solution {
public List<String> printKMoves(int K) {
Set<String> black = new HashSet<>();
int x = 0, y = 0;
int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
char[] dirChars = {'R', 'D', 'L', 'U'};
int dir = 0;
int minX = 0, maxX = 0, minY = 0, maxY = 0;
for (int i = 0; i < K; i++) {
String pos = x + "," + y;
if (black.contains(pos)) {
black.remove(pos);
dir = (dir + 3) % 4;
} else {
black.add(pos);
dir = (dir + 1) % 4;
}
x += dirs[dir][0];
y += dirs[dir][1];
minX = Math.min(minX, x);
maxX = Math.max(maxX, x);
minY = Math.min(minY, y);
maxY = Math.max(maxY, y);
}
int rows = maxX - minX + 1;
int cols = maxY - minY + 1;
List<String> result = new ArrayList<>();
for (int i = minX; i <= maxX; i++) {
StringBuilder sb = new StringBuilder();
for (int j = minY; j <= maxY; j++) {
if (i == x && j == y) {
sb.append(dirChars[dir]);
} else if (black.contains(i + "," + j)) {
sb.append('X');
} else {
sb.append('_');
}
}
result.add(sb.toString());
}
return result;
}
}
面试题 16.24. 数对和
题目描述
设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
示例：
输入: nums = [5,6,5], target = 11
输出: [[5,6]]
解题思路
使用哈希表统计每个数字的出现次数，然后遍历查找配对。
Java 代码实现
class Solution {
public List<List<Integer>> pairSums(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (int num : nums) {
int complement = target - num;
if (map.getOrDefault(num, 0) > 0 && map.getOrDefault(complement, 0) > 0) {
if (num == complement && map.get(num) < 2) continue;
result.add(Arrays.asList(num, complement));
map.put(num, map.get(num) - 1);
map.put(complement, map.get(complement) - 1);
}
}
return result;
}
}
面试题 16.25. LRU 缓存
题目描述
设计和构建一个"最近最少使用"缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值（允许你插入和检索特定键对应的值），并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
示例：
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1
解题思路
使用哈希表和双向链表实现。哈希表用于 O(1) 访问，双向链表维护访问顺序。
Java 代码实现
class LRUCache {
class Node {
int key, value;
Node prev, next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private int capacity;
private Map<Integer, Node> map;
private Node head, tail;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
remove(node);
addToHead(node);
return node.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
remove(node);
addToHead(node);
} else {
Node node = new Node(key, value);
map.put(key, node);
addToHead(node);
if (map.size() > capacity) {
Node last = tail.prev;
remove(last);
map.remove(last.key);
}
}
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
}
面试题 16.26. 计算器
题目描述
给定一个包含正整数、加(+)、减(-)、乘()、除(/)的算术表达式(括号除外)，计算其结果。表达式仅包含非负整数，+，-，，/ 四种运算符和空格。
示例 1：
输入: "3+2*2"
输出: 7
解题思路
使用栈处理乘除优先级。遍历字符串，遇到数字时解析完整数字，遇到运算符时处理前一个运算符。
Java 代码实现
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int num = 0;
char sign = '+';
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
switch (sign) {
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*':
stack.push(stack.pop() * num);
break;
case '/':
stack.push(stack.pop() / num);
break;
}
sign = c;
num = 0;
}
}
int result = 0;
while (!stack.isEmpty()) {
result += stack.pop();
}
return result;
}
}