OD高频面试题：手撕代码（一）
题目描述
给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换 操作的步骤如下：选出某个字符串中的两个
下标（不必不同），并交换这两个下标所对应的字符。
如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等，返回 true ；否则，返
回 false 。
示例 1：
输入：s1 = "bank", s2 = "kanb"
输出：true
解释：例如，交换 s2 中的第一个和最后一个字符可以得到 "bank"
示例 2：
输入：s1 = "attack", s2 = "defend"
输出：false
解释：一次字符串交换无法使两个字符串相等
示例 3：
输入：s1 = "kelb", s2 = "kelb"
输出：true
解释：两个字符串已经相等，所以不需要进行字符串交换
示例 4：
输入：s1 = "abcd", s2 = "dcba"
输出：false
提示：
1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 和 s2 仅由小写英文字母组成
/\*
题目理解：在某一个字符串中去交换两个字符后，是否可以和另外一个字符串相同
思路：遍历s1和s2，用find记录同位置字符不同出现的次数
找到第一处不同也就是find = 1时，记录不同的两个字符s1char和s2char
找到第二处不同也就是find = 2时，比较s1当前字符与s2char，s1char与s2当前字符是否相等
不相等则证明无法通过交换s1当前字符与s1char来满足s1 = s2，返回false
找到第三处不同也就是find = 3时，无法通过一次交换满足s1 = s2，返回false
遍历结束后，如果find = 1，则依然无法通过一次交换满足s1 = s2，返回false
\*/
public static boolean areAlmostEqual(String s1, String s2) {
int find = 0;//记录同位置字符不同出现的次数
char ch1 = ' ';
char ch2 = ' ';
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
find++;//同位置字符不同出现的次数+1
if (find == 3) {//已经有3处不同，就说明不可能通过交换一次实现连个字
符串相等
173.2. LCR 037. 行星碰撞
PS：面试官对原题做了修改，请注意对比不同。
题目描述
代码实现：
return false;
} else if (find == 2) {//两处不同的话，还要看保存的字符能否通过交换
后得到相同的字符串
if (s1.charAt(i) != ch2 || s2.charAt(i) != ch1) {//无法通
过交换满足s1 = s2
return false;
}
} else {//第一次发现不同
ch1 = s1.charAt(i);
ch2 = s2.charAt(i);
}
}
}
return find != 1;//只有一对不同时无法通过交换满足s1 = s2
}
public static void main(String\[] args) {
String s1 = "bank";
String s2 = "kanb";
System.out.println(areAlmostEqual(s1,s2));
}
行星碰撞
PS：面试官对原题做了修改，请注意对比不同
题目描述
给定一个整数数组planets,表示在同一行的行星。
对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向左移动，负表
示向右移动）。每一颗行星以相同的速度移动。
找出碰撞后身下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相
同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
示例1：
输入：planets = [-5,-10,5]
输出：[-5,-10]
解释：-10和5进行碰撞后只剩下-10，-5和-10永远不会发生碰撞
示例2：
输入：planets = [-8,8]
输出：[]
解释：-8和8进行碰撞后，全部行星都爆炸了。剩下为空。
public static void main(String[] args) {
int[] plants = {-8,8};
int[] res = getRes(plants);
for (int item : res) {
System.out.println(item);
}
}
//思路：用栈的思想去实现：
//负数直接入栈，用正数去和栈顶元素抵消(相同才能抵消，不同的时候留下值大的）
//抵消后还是整数的话，继续和栈顶元素进行抵消，直到不能抵消为止。
//最后栈中剩余的元素就是想要的结果
//举例：-5, -10, 5
// -5 先入栈 -10来了后也直接入栈 5来了以后和-10比较，留下-10，所以最后结果是
[-5,-10]
//1、栈中没有元素的时候，小于0的直接将值入栈
//2、遇到正数且栈中有元素的时候，当前正数与栈顶元素进行比较，如果正数大于负数的相反值
则碰撞未完全抵消
//那么继续循环去抵消 若完全抵消 则循环终止 每抵消一个 出栈一个元素 若flag扔为true
代表当前是负数
// 则当前遍历入栈
public static int[] getRes(int[] planets) {
Stack<Integer> stack = new Stack<>();
for (int planet : planets) {
boolean flag = true;//是否要添加到栈中
while (flag && planet > 0 && !stack.isEmpty() && stack.peek() <
0) {//元素为正数且栈不为空，且栈顶为负数
flag = stack.peek() > -planet; //栈顶与遍历值的相反数是否可以碰撞
if (stack.peek() >= -planet) { // 栈顶小行星爆炸，也就是要弹栈
stack.pop();
}
}
if (flag) {
stack.push(planet);
}
}
int size = stack.size();
int[] ans = new int[size];
for (int i = size - 1; i >= 0; i--) {
ans[i] = stack.pop();
}
return ans;
}
盛最多水的容器
题目描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i,
height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色
部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
//思路：使用双指针算法，初始时左指针指向0位置，右指针指向最后的位置
//不断移动左右指针向中间移动获取左右指针上的最小的高度，以便获得该窗口的面积
//当左指针小于右指针的时候进入循环：
//1、right-left ：就是x轴的长度 左右指针上选择一个较小的作为高度
// 计算出面积后 更新最大值maxArea
//2、左指针上的值小于右指针的值，左指针后移（也就是left++）
//3、左指针上的值大于等于右指针的值，右指针前移（也就是right--）
public static int getMaxCapacity(int[] height) {
int maxArea = 0;
int left = 0;
int right = height.length - 1;
while (left < right) {
int area = (right - left) *
Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
public static void main(String[] args) {
int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
System.out.println(getMaxCapacity(height));
}
下一个更大元素||
题目描述
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums
中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应
该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]
提示:
1 <= nums.length <= 104
-109 <= nums[i] <= 109
//1、暴力解法（候选人年限低的时候可以用这个版本）
public static int[] findNextEle(int[] nums) {//格式化你的代码
int length = nums.length; //获取原数组长度
int[] res = new int[length]; //存储结果数据
for (int i = 0; i < length; i++) { //遍历字符串
boolean flag = false; //设计一个标志位 用来判断是否能找到下一个更大值
for (int j = i + 1; j < i + length; j++) { //从当前数字开始遍历后面
的length - 1个元素
int num = nums[j % length]; //若j越界 则获取j%length位置元素 相
当于从0继续遍历 保证不越界
if (num > nums[i]) { //若内层循环遍历元素大于外层循环遍历元素 则说
明找到了
res[i] = num; //将当前值记录到res数组对应位置
flag = true; //更改标记变量为true
break; //因为只找第一个大于的 所以这里结束循环
}
}
if (!flag) { //若flag标记为仍然为false 则说明没找到下一个更大的
res[i] = -1; //则将当前下标对应元素存为-1
}
}
return res; //返回结果数组
}
public static void main(String[] args) {
int []nums = {4,1,3,5};
int []res = findNextEle(nums);
for (int i = 0; i < res.length; ++i){
System.out.print(res[i] + " ");
}
}
//单调栈
public static int[] findNextEle(int[] nums) {
int[] res = new int[nums.length];
Arrays.fill(res, -1);//默认所有数组为-1
Stack<Integer> st = new Stack<>();//使用单调栈来解决，注意单调栈中存放的是
下标
for (int i = 0; i < nums.length * 2; i++) {//因为是循环数组，所以这里循环
2次
//i % nums.length :取余的目的是为了循环数组2次
//当元素大于栈顶元素时，持续出栈并更新最大值
while (!st.empty() && nums[i % nums.length] > nums[st.peek()]) {
res[st.pop()] = nums[i % nums.length];
}
st.push(i % nums.length);//每次将当前元素入栈
}
return res;
}
public static void main(String[] args) {
int[] nums = {4, 1, 3, 5};
int[] res = findNextEle(nums);
for (int i = 0; i < res.length; ++i) {
System.out.print(res[i] + " ");
}
}
一亿以内的素数
public static void main(String[] args) {
int n = 100000000;
System.out.println(getCount(n));
}
//思路很简单：就是把数字的倍数全部都判断一下是否为false
//就不用再判断倍数是不是素数了，能提升效率
public static int getCount(int n) {
boolean[] flag = new boolean[n + 1];
int count = 0;
for (int i = 2; i <= n; i++) {
if (!flag[i]) {
count++;
} else {
continue;
}
for (int j = 2; i * j <= n; j++) {
flag[i * j] = true;
}
}
return count;
}
小岛问题(翻转矩阵)
题目描述：
给定一个N行M列的二维矩阵，矩阵中每个位置的数字取值为0或1，矩阵示例如：
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
现需要将矩阵中所有的1进行翻转为0，规则如下：
1）当点击一个1时，该1被翻转为0，同时相邻的上、下、左、右，以及左上、左下、右上、右下8个方
向的1（如果存在1）均会自动反转为0；
2）进一步地，一个位置上的1被反转为0时，与其相邻的8个方向的1（如果存在1）均会自动反转为0；
按照上述规则示例中的矩阵只最少需要点击2次后，所有均值0。请问，给定一个矩阵，最少需要点击几
次后，所有数字均为0
输出
输出一个整数，表示最少需要点击的次数
示例1
输入
3 3
1 0 1
0 1 0
1 0 1
输出
1
说明：上述4个角的1均在中间位置1的相邻8个方向上，因此点击一次即可。
public static void main(String[] args) {
// int[][] nums = {{1,1,0,0},{0,0,0,1},{0,0,1,1},{1,1,1,1}};
// int[][] nums = {{1,0,1},{0,1,0},{1,0,1}};
int[][] nums = {{1,0,1},{0,1,0},{1,0,1}};
int cnt = 0;
for (int i = 0; i < nums.length; ++i){
for (int j = 0; j < nums[0].length; j++) {
if(nums[i][j] == 1){ //遍历矩阵 如果遇到1 就将1相邻的八个方向都改为
0 那么进入该if几次
dfs(nums, i, j); //就相当于有几个小岛
cnt++;
}
}
}
System.out.print(cnt);
}
private static void dfs(int[][] nums, int i, int j) {
if(i < 0 || j < 0 || i >= nums.length || j >= nums[0].length){
return ; //递归可以走八个方向 那么i j下标有可能越界 越界了 就结束当前递归
}
if(nums[i][j] == 0){
return ; //若当前位置值为0 则结束递归 不继续翻转
}
nums[i][j] = 0; //若能走到这里 代表当前值为1 那么将其翻转为0 防止重复走回头路
int [][]run = {{0, 1},{0, -1},{1, 0},{-1, 0},{1, 1},{-1, -1},{-1,
1},{1, -1}};
//用数组存储八个相邻方向的差值 比如 0 1 就是向右 0 -1 就是向左 1, 0 就是向
下 1 1 就是右下方
for (int m = 0; m < run.length; ++m){
for (int n = 0; n < 2; n++) { //循环遍历数组的每一个方向 继续递归调用
传播翻转
dfs(nums, i + run[m][0], j +run[m][1]);
}
}
}
OJ红绿砖
题目描述
在美丽的尧山，有一个大广场，50周年校庆的时候Solo就在大广场上见证了史上最壮观的焰火。
在广场上有一排方砖是有颜色的，被涂上红色或者绿色，从左到右排列。
现在校方要求重新喷涂颜色，但不一定要每一块方砖都重新喷涂，
因为校方的目的是：每一块红色的方砖都至少在绿色方砖的左边（也就是每一个红的左边不能有绿的），
并且尽量喷涂最少的次数。
解答要求
时间限制：1000ms, 内存限制：64MB
输入
输入只有一行，包含一个字符串S，且只包含’R’(代表红色)或者’G’(代表绿色)。
我们保证字符串S的长度L的范围是(0 < L < 50 )。
输出
输出需要重新喷涂的方砖的最少数量。
样例
输入样例 RGRGR
输出 2
/*根据题目描述，我们需要计算重新喷涂的方砖的最少数量。为了满足校方的要求，即每一块红色的方
砖都至少在绿色方砖的左边，我们可以采用贪心算法的思路来解决。具体的解题思路如下：
初始化一个变量 count 用于记录重新喷涂的方砖的次数，初始值为0。
遍历字符串 S 中的每一个字符。
如果当前字符是红色方砖（'R'），则判断该红色方砖是否满足要求，即其左边没有绿色方砖（'G'）。
如果满足要求，则继续遍历下一个字符；如果不满足要求，则将该红色方砖重新喷涂为绿色方砖，并将
count 值加1。
如果当前字符是绿色方砖（'G'），则无需操作，继续遍历下一个字符。
完成遍历后，输出 count 的值，即重新喷涂的方砖的最少数量。
以下是相应的 Java 代码实现：*/
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String S = scanner.nextLine();
int count = 0;
for (int i = 0; i < S.length(); i++) {
if (S.charAt(i) == 'R') {
if (i == 0 || S.charAt(i - 1) != 'G') {
count++;
}
}
}
System.out.println(count);
}
}
这段代码根据输入的字符串 S 进行遍历，根据当前字符和前一个字符的关系来判断是否需要重新喷涂方
砖，并计算重新喷涂的次数。最后输出结果即为重新喷涂的方砖的最少数量。
void LRedRGreen()
{
string colors;
cin >> colors;
int size = colors.size();
int* sprayNum = new int[size + 1]();
int left = 0;
int right = size - 1;
while (left <= right) {
if (colors[left] == 'R') {
for (int i = 0; i <= left; i++) {
sprayNum[i]++;
}
} else {
for (int i = left + 1; i <= size; i++) {
sprayNum[i]++;
}
}
if (left != right) {
if (colors[right] == 'R') {
for (int i = 0; i <= right; i++) {
sprayNum[i]++;}
} else {
for (int i = right + 1; i <= size; i++) {
sprayNum[i]++;
}
}
}
left++;
right--;
}
int min = sprayNum[0];
for (int i = 0; i < size + 1; i++) {
min = min < sprayNum[i] ? min : sprayNum[i];
}
cout << min;
delete[] sprayNum;
}
用户分组
题目描述
有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的唯一ID 。
给定一个整数数组 groupSizes ，其中 groupSizes[i] 是第 i 个人所在的组的大小。例如，如
果 groupSizes[1] = 3 ，则第 1 个人必须位于大小为 3 的组中。
返回一个组列表，使每个人 i 都在一个大小为 groupSizes[i] 的组中。
每个人应该 恰好只 出现在 一个组 中，并且每个人必须在一个组中。如果有多个答案，返回其中 任何
一个。可以 保证 给定输入 至少有一个 有效的解。
示例 1：
输入：groupSizes = [3,3,3,3,3,1,3]
输出：[[5],[0,1,2],[3,4,6]]
解释：
第一组是 [5]，大小为 1，groupSizes[5] = 1。
第二组是 [0,1,2]，大小为 3，groupSizes[0] = groupSizes[1] = groupSizes[2] = 3。
第三组是 [3,4,6]，大小为 3，groupSizes[3] = groupSizes[4] = groupSizes[6] = 3。
其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
示例 2：
输入：groupSizes = [2,1,3,3,3,2]
输出：[[1],[0,5],[2,3,4]]
提示：
groupSizes.length == n
1 <= n <= 500
1 <= groupSizes[i] <= n
//这个题的意思就是：把数组中的每个元素都按照元素的值分到不同的组中
//然后把下表放入数组中返回
//例如： 3,3,3,3,3,1,3
// 第一个3：map 存 3 1
// 第二个3：map 存 3 2
// 第三个3：map 存 3 3 因为到这里分组满了 所以分组有一个[0,1,2]
// 第四个3：map 存 3 1
// 第五个3：map 存 3 2
// 第六个1：map 再存一个 1 1
// 第七个3：map 中的3 2 变成了 3 3 分组满了，所以有一个分组[3,4,6]
//最后将 1 1这个map也放入是一个分组 [5]
//所以最终结果是 [0,1,2] [3,4,6] [5]
public static List<List<Integer>> group(int[] groupSizes) {
//创建一个hash表，键为 组的人数groupSizes[i]，值为 这一组的人的编号i的集合。
Map<Integer, List<Integer>> hash = new HashMap<>();
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < groupSizes.length; i++) {
int x = groupSizes[i];
//看看这个索引的数组存在不
if (hash.get(x) == null) {
hash.put(x, new ArrayList<>());
}
//将这个人的编号 i 放在 groupSizes[i] 这个索引的数组上
hash.get(x).add(i);
//链子满了，上传结果，清空这个数组
if (hash.get(x).size() == x) {
//满一组，就放进返回值容器
res.add(hash.get(x));
//将 groupSizes[i] 这个索引的数组清空，方便来存下一组
hash.put(x, null);
}
}
return res;
}
public static void main(String[] args) {
int []groupSizes = {2,1,3,3,3,2};
List<List<Integer>> groups = group(groupSizes);
System.out.println(groups);
}
产生由1，2，3这3个数字符号所构成、长度为n的字符串
编写程序，产生由1，2，3这3个数字符号所构成、长度为n的字符串，并且在字符串中对于任何一个子
串而言，都不会有相邻的、完全相同的子串；
解答要求
时间限制：1000ms, 内存限制：64MB
输入
字符串长度n(1=<n<=10)；
输出
无相邻重复子串的所有字符串，每个字符串换行输出。(由小到大输出)
样例
输入样例 1
5
输出样例 1
12131
12132
12312
12313
12321
13121
13123
13212
13213
13231
21231
21232
21312
21321
21323
23121
23123
23132
23212
23213
31213
31231
31232
31321
31323
32123
32131
32132
32312
32313
//结果不是很对，需要确认代码是否正确
public static List<Character> ans;
public static void main(String[] args) {
int n = 5;
ans = new ArrayList<>();
dfs(n, 0);
}
//n:几位数字 curCount：当前已经存入的元素个数
private static void dfs(int n, int curCount) {
if (n == curCount) {
StringBuilder sb = new StringBuilder();
for (Character an : ans) {
sb.append(an);
}
if (sb.indexOf("1") != -1 && sb.indexOf("2") != -1 &&
sb.indexOf("3") != -1) {
System.out.println(sb);
}
return;
}
for (int i = 0; i < 3; i++) {
char ch = (char) ('0' + i + 1);
if (ans.size() != 0 && ans.get(ans.size() - 1) == ch) {
continue;
}
ans.add(ch);
dfs(n, curCount + 1);
ans.remove(ans.size() - 1);
}
}
删除有序数组中的重复项||
题目描述
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次
，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
public static int removeDuplicates(int[] nums) {
int count = 1;
int cur = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[cur] == nums[i]) {
if (count < 2) {
nums[++cur] = nums[i];
count++;
}
}else {
nums[++cur] = nums[i];
count = 1;
}
}
return cur + 1;
}
public static void main(String[] args) {
int[] nums = {0, 0, 1, 1, 1, 1, 2, 3, 3};
System.out.println(removeDuplicates(nums));
}
查看3道真题和解析
字节跳动三面100人在聊