华为OD高频面试题-手撕代码（二）

全排列

乘积小于 K 的子数组

子数组按位或操作

我们有一个非负整数数组 arr 。

对于每个（连续的）子数组 sub = [arr[i], arr[i + 1], ..., arr[j]] （ i <= j），我们

对 sub 中的每个元素进行按位或操作，获得结果 arr[i] | arr[i + 1] | ... | arr[j] 。

返回可能结果的数量。 多次出现的结果在最终答案中仅计算一次。

示例 1：

输入：arr = [0]

输出：1

解释：

只有一个可能的结果 0 。

示例 2：

输入：arr = [1,1,2]

输出：3

解释：

可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。

产生的结果为 1，1，2，1，3，3 。

有三个唯一值，所以答案是 3 。

示例 3：

输入：arr = [1,2,4]

输出：6

解释：

可能的结果是 1，2，3，4，6，以及 7 。

代码实现

public class Main {
//题目理解：在A数组中获取连续的子数组B，对子数组进行或运算之后，保存或运算之后的结果
//程序执行流程：以 [1,1,2]为例
//1、先将1放入cur中（cur保存的是上一次异或的结果），因为第1次子数组只有一个1，所以直
接放入cur中。
//2、再循环第二个1的时候，cur中已经有一个1了，cur中的所有值和1进行或运算，并将中间结
果保存到tmp中
//3、将每次或运算的结果存入res中（因为结果不能重复所以res使用的是hashset存储的）
//4、再将当前的x存入到cur中，避免只有一个元素的子数组的情况发生
//5、最终返回res的大小即可。
//cur中保存的是以前的结果，每次会向cur中添加一个值的，就相当于子数组了
public static int subarrayBitwiseORs(int[] nums) {
HashSet<Integer> res = new HashSet<>();//因为结果不能重复，所以使用set来
保存结果
HashSet<Integer> cur = new HashSet<>();//存储上一次或运算的结果
cur.add(0);
for (int x : nums) {
HashSet<Integer> tmp = new HashSet<>();// 存储当前值的结果
for (int y : cur) {//枚举x及之前的元素的所有异或值
tmp.add(x | y);
}
tmp.add(x);
cur = tmp;
res.addAll(cur);
}
return res.size();
}
public static void main(String[] args) {
int[] nums = {1, 1, 2};
System.out.println(subarrayBitwiseORs(nums));
}
}

划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"

输出：[9,7,8]

解释：

划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。

每个字母最多出现在一个片段中。

像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = "eccbbbbdec"

输出：[10]

提示：

1 <= s.length <= 500

s 仅由小写英文字母组成

public class Main {
//题目含义：将一个字符串划分成多个子字符串，每个子字符串不能和其他字符串存在相同的字
符，而且分割后的多个子字符串可以合成原始的字符串
//思路：
// 1、统计出每个字符在字符串中出现的最后位置到hash数组中（相当于找打了每个字符最后出
现的位置）
// 2、使用双指针算法，循环原始字符串中的每一个字符，如果i还未到达hash中的位置，则更新
右指针
//3、直到i和hash中的位置相等时，记录一次子串的长度，左指针移动到右指针的下一位，继续
循环
//例如： ababcbacadefegdehijhklij
//1、先统计出每个字符出现的次数，a 最后出现的下标是 8
// b 最后出现的下标是 5
// c 最后出现的下标是 7 后边依次类推
//2、定义左右指针默认位置都在0位置 进入循环后，在hash中取得当前字符的最后一次出现的
位置和右指针比较
//a 在hash中的位置是8，所以移动右指针end 到 8
//b 在hash中的位置是5，所以右指针不动
//c 在hash中的位置是7，所以右指针也不动
//3、直到发现当前循环变量i 和右指针相等了，说明已经找到了一组子字符串和其他的字符串不
存在相同的字符了，将长度添加到结果中
//4、更新左指针到右指针的下一个位置，继续循环，直到将所有子字符串长度获取到为止
public static List<Integer> partitionLabels(String s) {
List<Integer> res = new ArrayList<>();
// 1.统计字母最后一次出现的位置
int[] hash = new int[26];
for (int i = 0; i < s.length(); i++) {
hash[s.charAt(i) - 'a'] = i;
}
// 2.划分区间 ababcbaca defegde hijhklij
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
int pos = hash[s.charAt(i) - 'a'];
if (end < pos) {
end = pos;
}
if (i == end) {
res.add(end - start + 1);
start = end + 1;
}
}
return res;
}
public static void main(String[] args) {
String s = "ababcbacadefegdehijhklij";
System.out.println(partitionLabels(s));
}
}

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

判断一个二叉树是否对称
分为三个情况
1、左右节点有的值相同时，分别判断左右子树是否相等
2、左右节点均为空，返回true时，返回为真
3、左右节点值不相同的时候，返回为false
public boolean isSymmetric(TreeNode root) {
if (root == null) return true; // 如果根节点为空，返回true，因为空树被认为是对
称的
return check(root.left, root.right); // 调用check函数检查左右子树是否对称
}
public boolean check(TreeNode left, TreeNode right) {
// 结构上不成立，一个节点为空，另一个不为空，返回false
if (left == null && right != null || left != null && right == null) {
return false;
}
// 左右节点均为空，返回true
if (left == right && left == null) {
return true;
} else if (left.val == right.val) { // 值相同，继续递归判断
return (check(left.left, right.right) && check(left.right,
right.left));
}
// 值不同，返回false
else return false;
}

单字符重复子串的最大长度

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。

给你一个字符串 text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子

串。返回其中最长的子串的长度。

示例 1：

输入：text = "ababa"

输出：3

示例 2：

输入：text = "aaabaaa"

输出：6

提示：

1 <= text.length <= 20000

text 仅由小写英文字母组成。

class Solution {
public int maxRepOpt1(String text) {
Map<Character, Integer> count = new HashMap<Character, Integer>();
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
count.put(c, count.getOrDefault(c, 0) + 1);
}
int res = 0;
for (int i = 0; i < text.length(); ) {
// step1: 找出当前连续的一段 [i, j)
int j = i;
while (j < text.length() && text.charAt(j) == text.charAt(i)) {
j++;
}
int curCnt = j - i;
// step2: 如果这一段长度小于该字符出现的总数，并且前面或后面有空位，则使用
curCnt + 1 更新答案
if (curCnt < count.getOrDefault(text.charAt(i), 0) && (j <
text.length() || i > 0)) {
res = Math.max(res, curCnt + 1);
}
// step3: 找到这一段后面与之相隔一个不同字符的另一段 [j + 1, k)，如果不存
在则 k = j + 1
int k = j + 1;
while (k < text.length() && text.charAt(k) == text.charAt(i)) {
k++;
}
res = Math.max(res, Math.min(k - i,
count.getOrDefault(text.charAt(i), 0)));
i = j;
}
return res;
}
}

路径总和Ⅱ

思路：要使用深度优先算法来实现
1、从二叉树的根节点开始进行遍历
2、记录每次遍历的节点值，保存到path中，并在targetSum和中减掉当前节点的值
3、如果sum已经是0了，并且左右节点都是空，说明找到了一组，添加到ans
4、递归找左右节点
5、左右节点递归完成后，把第2步保存的值删除掉，称为回溯
举例：比如这个用例 targetSum = 22
1、先将5添加到path中，targetSum = 22 减掉 5后是17
2、再去递归4这个左节点，给targetSum见到13
3、再去递归11这个节点，给targetSum减到2
4、再去递归7这个节点，但是减完之后是-6，不满足条件。这个时候左右节点都是空的，递归结束
5、当递归2节点的时候，targetSum减完之后刚好是0，所以把
所以把5，4，11，2添加到ans结果中
6、直到把所有节点都递归完后，可以得到两个结果
public class Main {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
dfs(root, targetSum);
return ans;
}
void dfs(TreeNode root, int targetSum) {
if (root == null) {
return;
}
path.add(root.val);
targetSum -= root.val;
if (targetSum == 0 && root.left == null && root.right == null) {
ans.add(new LinkedList<>(path));
}
dfs(root.left, targetSum);
dfs(root.right, targetSum);
path.remove(path.size()-1);
}
}

Z字形变换

题目的含义就是让你把给定的字符串
按照给定的几行进行Z型输出
总体思路：
1、建立一个字符串的数组array，去保存每一行的字符
2、当向下走的时候每次给index+1，当向上走的时候给index-1
3、当到最底下的时候给index-1
以上2和3步的时候，每次都把字符放到对应的字符串数组中
4、最后把字符串数组拼接到一起（成一个字符串）就是Z型变化后的结果了
以第一个用例举例说明：
s = "PAYPALISHIRING", numRows = 3
1、循环P，将P添加到array[0]中
2、循环A，将A添加到array[1]中
3、循环Y，将Y添加到array[2]中
4、循环P，index要开始-1，然后将P添加到array[1]中
5、循环A，index要开始-1，然后将A添加到array[0]中
6、循环L, index已经到0位置了，所以开始index+1，将L添加到array[1]中
7、直到循环结束
最终有三个字符串分别是：
PAHN
APLSIIG
YIR
最终结果是：PAHNAPLSIIGYIR
public static String convert(String s, int numRows) {
if (s == null || s.length() < 1 || numRows == 1) {
return s;
}
StringBuilder[] array = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) {
array[i] = new StringBuilder();
}
int dir = 1;
int index = 0;
for (char c : s.toCharArray()) {
array[index].append(c);
index = index + dir;
if (index == numRows - 1 || index == 0) {
dir = -dir;
}
}
StringBuilder res = new StringBuilder();
for (int i = 0; i < numRows; i++) {
res.append(array[i]);
}
return res.toString();
}
public static void main(String[] args) {
String s = "PAYPALISHIRING";
int numRows = 3;
System.out.println(convert(s,numRows));
}

表达式加法和减法

Solo小学一年级的时候做数学题很莫名奇妙，经常把算术表达式加上很多空格(如:7+ 31-2)，让老师很是

头大于是老师决定雇用你编写一个程序来独立计算Solo的答案。Can you help theteacher?

解答要求时间限制:5000ms,内存限制:100MB输入输入只有一行，即一个长度不超过100的字符串S，表

示Solo的算术表达式，且S只包含数字和“+”"-"两种运算符，以及Solo加上的一大堆空格(我们保证输入都

是合法的)。注意:5中不一定包含运算符，且我们保证S中不会出现大于100000的数。

输出:表达式的运算结果

/*题目：
给你一个包含空格的字符串，请你计算出+-运算的结果
思路：记录上次的符号（默认为+），和下一次的数字，进行运算
1、先将每个数求出来，记录到num中，
2、上次是+号，将当前的num加到res结果中
3、上次是-号，将res减去num的结果保存起来
4、记录下次的符号，并重置下num的值
5、直到将s字符串循环完为止，res中就是所求的和
举例：7+31 -2
1、先将7保存到num中
2、遇到+号后，将7加到res中（res=7）
3、遇到3后，将3放入num中
4、遇到1后，将3*10+1放入到num中
5、遇到空格直接跳过
6、遇到-号后，将31加到res中（res=38）
7、遇到2后，将2放入到num中（num=0）
8、因为2是最后一个字符了，所以最后一个字符也可以进入到运算中
9、res-2 放入到res中，res=36
循环结束，结果就是36*/
public class Main {
public static int calc(String s) {
int res = 0;
char op = '+';
int num = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
num = num * 10 + (ch - '0');
}
if (!Character.isDigit(ch) && ch !=' ' || i == s.length() - 1) {
if (op == '+') {
res += num;
} else if (op == '-') {
res -= num;
}
op = ch;
num = 0;
}
}
return res;
}
public static void main(String[] args) {
String s = "10 - 1 + 25";
System.out.println(calc(s));
}
}

下一个更大元素Ⅲ

/*这个题就是小岛问题
思路：
1、就是去循环二维数组中的所有元素，当遇到1的时候进入递归
2、进入递归后，将上下左右四个方向的为1的改成0
3、直到越界或者遇到0为止
总共判断有多少个小岛就可以了*/
import java.util.*;
public class Main {
public static void main(String[] args) {
/*char[][] grid = {{'1','1','1','1','0'},
{'1','1','0','1','0'},
{'1','1','0','0','0'},
{'0','0','0','0','0'}};*/
char[][] grid = {{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}};
System.out.print(numNetworks(grid));
}
public static int numNetworks(char[][] grid) {
int cnt = 0;
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') { //遍历矩阵 如果遇到1 就将1相邻的四个方向
都改为0 那么进入该if几次
dfs(grid, i, j); //就相当于有几个小岛
cnt++;
}
}
}
return cnt;
}
private static void dfs(char[][] nums, int i, int j) {
if (i < 0 || j < 0 || i >= nums.length || j >= nums[0].length) {
return; //递归可以走4个方向 那么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}};
//用数组存储四个个相邻方向的差值 比如 0 1 就是向右 0 -1 就是向左 1, 0 就是
向下 1 1 就是右下方
for (int m = 0; m < run.length; ++m) {//循环遍历数组的每一个方向 继续递归
调用传播翻转
dfs(nums, i + run[m][0], j + run[m][1]);
}
}
}