华为OD高频面试题-手撕代码（完）
最短超串
总体思路：
用一个map集合记录small中所有元素
在窗口内的出现次数，用count记录窗口内的种类数，
如果种类数和small的长度相等
（因为small没有重复元素，种类数就是它的长度），
那么就更新结果，并且left右移。
1、创建一个空的哈希表 sMap 用于存储 small 数组中的元素及其出现的次数。
初始化计数器 count 为 0，用于记录当前窗口中包含了多少个 small 数组中的元素。
初始化滑动窗口的左边界 left 和右边界 right，初始值都为 0。
2、遍历 big 数组： 从左到右依次遍历 big 数组中的元素。
对于每个元素，如果它在 sMap 中存在，则更新计数器 count 和对应元素的计数值。
3、滑动窗口操作：当 count 等于 small 数组的长度时，表示当前窗口包含了 small 数组中的所
有元素，此时开始收缩窗口。
在收缩窗口的过程中，不断更新最小区间的长度 res 以及对应的左右索引值 l 和 r。
收缩窗口的条件是：当 left 指向的元素在 sMap 中存在，并且当前元素在窗口中的计数值等于 1
时，
将 count 减 1，表示当前窗口已不包含该元素。
4、返回结果：如果 res 的值大于 big 数组的长度，则说明不存在符合条件的最小区间，返回空数
组。
否则返回最小区间的左右索引值 l 和 r。
这种算法利用了滑动窗口的思想，在遍历 big 数组的过程中不断调整窗口的大小，最终找到了符合条件
的最小区间。
import java.util.*;
public class Main {
public static int[] func(int[] big, int[] small) {
if (big.length == 0 || small.length == 0) {
return new int[0];
}
Map<Integer, Integer> sMap = new HashMap<>();
for (int i = 0; i < small.length; i++) {
sMap.put(small[i], 0);
}
int count = 0;
int left = 0;
int right = 0;
int res = big.length + 100; //记录最小区间长度
int l = 0; //记录最小区间的左索引值
int r = 0; //记录最小区间的右索引值
while (right < big.length) {
int tmp = big[right];
right++;
if (sMap.containsKey(tmp)) {
if (sMap.get(tmp) == 0) {
count++;
}
sMap.put(tmp, sMap.get(tmp) + 1);
}
while (count == small.length && left < right) {
if (res > right - left) {
res = right - left;
l = left;
r = right - 1;
}
if (sMap.containsKey(big[left])) {
if (sMap.get(big[left]) == 1) {
count--;
}
sMap.put(big[left], sMap.get(big[left]) - 1);
}
left++;
}
}
return res > big.length ? new int[0] : new int[]{l, r};
}
public static void main(String[] args) {
int[] big = {7, 5, 9, 0, 2, 1, 3, 5, 7, 9, 1, 1, 5, 8, 8, 9, 7};
int[] small = {1, 5, 9};
int[] res = func(big, small);
for (int item : res) {
System.out.print(item + " ");
}
}
}
快乐数
/*通过获取数字的每一个数位 求得下一个数字的值
根据题意来说 要么变成1 要么死循环
感觉这是一个环形问题 不然完全不知道会循环多少次
那么环形问题就可以用快慢指针的方式来判断是否成环
如果成环就说明陷入死循环了 那么fast一次走两步
slow一次走一步 那么两个指针一定会相遇 那么循环就会结束
以次来判断是否成环*/
class Solution {
public static boolean isHappy(int n) {
int fast = n;
int slow = n;
do{
slow = bitSquareSum(slow);
fast = bitSquareSum(fast);
fast = bitSquareSum(fast);
}while(fast != slow);
return fast == 1;
}
public static int bitSquareSum(int n){
int sum = 0;
while(n > 0){
int bit = n % 10;
sum += bit * bit;
n = n / 10;
}
return sum;
}
public static void main(String[] args) {
System.out.println(isHappyNum(19));
System.out.println(isHappyNum(2));
}
}
//使用集合的方式实现
public class Main {
public static boolean isHappyNum(int n) {
Set<Integer> set = new HashSet<>();
do {
int tmp = calc(n);
if (set.contains(tmp)) {
return false;
}
set.add(tmp);
n = tmp;
} while (n != 1);
return true;
}
public static int calc(int n) {
int sum = 0;
while (n > 0) {
int bit = n % 10;
sum += bit * bit;
n = n / 10;
}
return sum;
}
public static void main(String[] args) {
System.out.println(isHappyNum(19));
System.out.println(isHappyNum(2));
}
}
对包含字母数字的字符串按规则排序
import java.util.*;
/*思路：
1、先把数字，大写字母，小写字母分别取出来，放到三个集合中
2、分别对三个结合进行升序排序
3、遍历原字符数组，
遇到数字就从数字数组中获取第一个字符，更新到原字符数组中
遇到字母优先放入小写字母，然后把小写字母删除掉
等小写字母放完后，再放大写字母
4、最后将字符数组转成字符串返回即可
题目意思：
1、数字的相对位置不能变化，对所有数字进行升序排序
2、大小写字母位置也不能发生变化，小写字母升序排序后再排序大写字母
所以把数字，大写字母，和小写字母分别存储起来
然后排序，再拼接会字符串中就可以了*/
public class Main {
public static void main(String[] args) {
String str = "a2CB1c";
System.out.println(sort(str));
String str1 = "ab12C4Ac3B";
System.out.println(sort(str1));
}
private static String sort(String str) {
char[] chs = str.toCharArray();
List<Character> upper = new ArrayList<>();
List<Character> digit = new ArrayList<>();
List<Character> lower = new ArrayList<>();
for (int i = 0; i < chs.length; i++) {
if (chs[i] >= '0' && chs[i] <= '9') {
digit.add(chs[i]);
} else if(chs[i] >= 'a' && chs[i] <= 'z') {
lower.add(chs[i]);
}else{
upper.add(chs[i]);
}
}
Collections.sort(upper);
Collections.sort(digit);
Collections.sort(lower);
for (int i = 0; i < chs.length; i++) {
if (chs[i] >= '0' && chs[i] <= '9') {
chs[i] = digit.get(0);
digit.remove(0);
} else{
if(!lower.isEmpty()){
chs[i] = lower.get(0);
lower.remove(0);
}else{
chs[i] = upper.get(0);
upper.remove(0);
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i <chs.length ; i++) {
sb.append(chs[i]);
}
return sb.toString();
}
}
找到最大周长的多边形
题目：
给你一个长度为 n 的 正 整数数组 nums 。
多边形 指的是一个至少有 3 条边的封闭二维图形。多边形的 最长边 一定 小于 所有其他边长度之
和。
如果你有 k （k >= 3）个 正 数 a1，a2，a3, …，ak 满足 a1 <= a2 <= a3 <= … <= ak 且
a1 + a2 + a3 + … + ak-1 > ak ，那么 一定 存在一个 k 条边的多边形，每条边的长度分别为
a1 ，a2 ，a3 ， …，ak 。
一个多边形的 周长 指的是它所有边之和。
请你返回从 nums 中可以构造的 多边形 的 最大周长 。如果不能构造出任何多边形，请你返回 -1
。
示例 1：
输入：nums = [5,5,5]
输出：15
解释：nums 中唯一可以构造的多边形为三角形，每条边的长度分别为 5 ，5 和 5 ，周长为 5 + 5
+ 5 = 15 。
示例 2：
输入：nums = [1,12,1,2,5,50,3]
输出：12
解释：最大周长多边形为五边形，每条边的长度分别为 1 ，1 ，2 ，3 和 5 ，周长为 1 + 1 + 2
+ 3 + 5 = 12 。
我们无法构造一个包含变长为 12 或者 50 的多边形，因为其他边之和没法大于两者中的任何一个。
所以最大周长为 12 。
示例 3：
输入：nums = [5,5,50]
输出：-1
解释：无法构造任何多边形，因为多边形至少要有 3 条边且 50 > 5 + 5 。
提示：
3 <= n <= 10^5
1 <= nums[i] <= 10^9
import java.util.*;
public class Main {
//O(n)
public static int getRes(int[] nums) {
Arrays.sort(nums);
int sum = Arrays.stream(nums).sum();
for (int i = nums.length - 1; i > 1; i--) {
if (sum > nums[i] * 2) {
return sum;
}
sum -= nums[i];
}
return -1;
}
public static void main(String[] args) {
int[] nums = {5, 5, 5};
System.out.println(getRes(nums));
int[] nums1 = {1, 12, 1, 2, 5, 50, 3};
System.out.println(getRes(nums1));
int[] nums2 = {5, 5, 50};
System.out.println(getRes(nums2));
}
}
6个数找最大时间
思路：
1、首先要处理下小时的两位数
小时的第一位不能超过2，23
小时的第二位不能超过4
所以先去数组中查找小于3的最大值，确定小时的第一位
再去数组中查找小于4的最大值，确定小时的第二位
两个数字要在数组中删除掉
2、然后再去判断分钟
分钟的第一位不能超过6
分钟的地位为不能超过10
同1原理
3、再去确定秒
秒和分钟的判断差不多
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] data = {0, 2, 3, 0, 5, 6};
System.out.println(getRes(data));
int[] data1 = {1, 5, 6, 3, 4, 5};
System.out.println(getRes(data1));
}
/**
* 解题思路: 时间格式第一位不能大于2,第二位不能大于3等
* 所以从头开始,一位一位找,先找满足第一位的集合中的数字,然后找出最大的一个,
* 碰到任何不满足条件的直接返回 invalid,满足则从数组从移除,以此类推
*/
private static String getRes(int[] data) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < data.length; i++) {
list.add(data[i]);
}
String s = "invalid";
String c = ":";
StringBuilder res = new StringBuilder();
//第一位不能大于3,获取数组中小于3的数字中最大的一个
int d1 = getPos(list, 3);
if (d1 != -1) {
list.remove(Integer.valueOf(d1));
res.append(d1);
} else {
return s;
}
//如果第一位是2,那么第二位则不能超过4
if (res.charAt(0) == '2') {
//第二位
Integer d2 = getPos(list, 4);
if (d2 != -1) {
// 按照元素删除
list.remove(Integer.valueOf(d2));
res.append(d2);
res.append(c);
} else {
return s;
}
// 否则,第一位可能是0或者1,这样第二位可以是0-9,即小于10
} else {
//第二位
Integer d3 = getPos(list, 10);
if (d3 != -1) {
list.remove(d3);
res.append(d3);
res.append(c);
} else {
return s;
}
}
//第三位,分钟最大是59,即小于6
int d4 = getPos(list, 6);
if (d4 != -1) {
list.remove(Integer.valueOf(d4));
res.append(d4);
} else {
return s;
}
//第四位,0-9
int d5 = getPos(list, 10);
if (d5 != -1) {
list.remove(Integer.valueOf(d5));
res.append(d5);
res.append(c);
} else {
return s;
}
//第五位
int d6 = getPos(list, 6);
if (d6 != -1) {
list.remove(Integer.valueOf(d6));
res.append(d6);
} else {
return s;
}
//最后一位
if (getPos(list, 10) != -1) {
res.append(getPos(list, 10));
} else {
return s;
}
return res.toString();
}
/**
* 获取数组中比 val 小的数字中最大的一个数,没有返回-1
*/
private static int getPos(List<Integer> list, int val) {
return list.stream().filter(x -> x < val).mapToInt(x ->
x).max().orElse(-1);
}
}
逆波兰表达式求值
/*
具体思路如下：
总体思路就是利用栈来模拟计算过程，
遇到操作符时从栈中取出操作数进行相应的计算，
然后将计算结果再次入栈，直到整个表达式遍历完为止，
最终栈中只会有一个元素，即为计算结果。
1、创建一个整型类型的栈 st，用于存储数字。
2、遍历输入的 tokens 数组，依次处理每个元素。
如果当前元素是操作符（"+"、"-"、"*"、"/"），
则从栈中弹出两个操作数进行相应的运算，并将结果重新压入栈中。
如果当前元素是数字（非运算符），则将其转换为整型并压入栈中。
3、最终栈中只会剩下一个元素，即为计算结果，将其弹出并返回。*/
public class od_online {
public static int getRes(String[] tokens) {
Stack<Integer> st = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
if ("+".equals(tokens[i])) {
int t1 = st.pop();
int t2 = st.pop();
st.push(t1 + t2);
} else if ("-".equals(tokens[i])) {
int t1 = st.pop();
int t2 = st.pop();
st.push(t2 - t1);
} else if ("*".equals(tokens[i])) {
int t1 = st.pop();
int t2 = st.pop();
st.push(t1*t2);
} else if ("/".equals(tokens[i])) {
int t1 = st.pop();
int t2 = st.pop();
st.push(t2 / t1);
} else {
st.push(Integer.valueOf(tokens[i]));
}
}
return st.pop();
}
public static void main(String[] args) {
String tokens[] = {"2", "1", "/"};
System.out.println(getRes(tokens));
}
}
跳跃游戏3
public class od_online {
/*
使用深度优先搜索算法实现。
1、首先判断当前位置是否越界或者已经被访问过
（如果访问过用-1表示——，如果是则返回false。
2、然后判断当前位置的值是否为0，如果是则返回true。
3、接下来记录当前位置的值，并将该位置标记为已访问（改成-1）。
4、使用递归方式，分别从当前位置向前和向后进行跳跃，
判断是否能到达目标位置。如果任意一个方向可以到达，则返回true。
如果都无法到达，并返回false。
这个题意就是：
从给定的位置开始向前或者向后找，能不能
遇到0，如果可以返回真，否则返回假
所有就从当前的位置开始递归向前向后找
只有向前向后任意一个遇到0就可以返回了
*/
public static boolean dfs(int[] arr, int i) {
if (i < 0 || i >= arr.length || arr[i] == -1) {
return false;
}
if (arr[i] == 0) {
return true;
}
int backup = arr[i];
arr[i] = -1;
boolean res = dfs(arr, backup + i) || dfs(arr, i - backup);
return res;
}
public static void main(String[] args) {
int arr[] = {4, 2, 3, 0, 3, 1, 2};
int start = 5;
System.out.println(dfs(arr, start));
}
}
早餐组合
/*思路：
1、首先，对 staple 和 drinks 数组进行排序。
这是因为在求解满足条件的组合数时，
排序可以帮助我们更有效地使用二分查找。
2、遍历staple数组中的所有元素，然后再 drinks数组中查找
drinks[mid] <= x - item 最大索引位置
3、使用二分查找在drinks数组中查找符合drinks[mid] <= val的值
的最大索引位置，它的返回值是 left，即第一个大于 val 的位置
4、最后将下标位置返回，并累加就是组合的结果
5、最后，返回 res % 1000000007，确保结果在取模后不会溢出，
并符合题目要求。
*/
public class od_online {
public static int bSearch(int[] arr, int val) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= val) {
left = mid + 1;
} else if (arr[mid] > val) {
right = mid;
}
}
return left;
}
public static int breakfastNumber(int[] staple, int[] drinks, int x) {
Arrays.sort(staple);
Arrays.sort(drinks);
long res = 0;
for (int item : staple) {
if (item > x) {
break;//如果i直接大于x了就可以直接退出循环了
} else {
res += bSearch(drinks, x - item);
}
}
return (int) (res % 1000000007);
}
public static void main(String[] args) {
int[] staple = {10, 20, 5};
int[] drinks = {5, 5, 2};
int x = 15;
System.out.println(breakfastNumber(staple,drinks,x));
}
}
工作级
乘积计算
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int MaxProduct(const char *numStr) {
int max = 0;
for (size_t pos = 0; pos < strlen(numStr) - 1; pos++) {
char s1[10] = {0};
char s2[10] = {0};
strncpy(s1, numStr, pos + 1);
strncpy(s2, numStr + 1 + pos, strlen(numStr) - 1 - pos);
int product = atoi(s1) * atoi(s2);
if(max < product){
max = product;
}
}
return max;
}
int main() {
char numStr[] = "33333";
printf("%d\n", MaxProduct(numStr));
return 0;
}
区间中位和
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(const int *a, const int *b) {
return *a - *b;
}
static int GetMedianSum(const int *numbers, size_t numbersSize) {
int ret = 0;
for (int size = 1; size <= numbersSize; ++size) {
for (int idx = 0; idx + size <= numbersSize; ++idx) {
int array[size];
memcpy(array, numbers + idx, sizeof(int) * size);
qsort(array, size, sizeof(size), cmp);
if (size % 2 == 0) {
ret += array[size / 2 - 1];
} else {
ret += array[size / 2];
}
}
}
return ret;
}
int main() {
int nums[] = {1, 5, 7, 4};
int size = sizeof(nums) / sizeof(int);
printf("%d", GetMedianSum(nums, size));
}
定时器系统
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
typedef struct {
int time;
int timerId;
} ResultInfo;
typedef struct {
int now;
int *time;
int *begin;
int *status;
size_t size;
} TimerSystem;
static TimerSystem *TimerSystemCreate(const int *timers, size_t timersSize)
{
TimerSystem *sys = (TimerSystem *) malloc(sizeof(TimerSystem));
size_t tmp = sizeof(int) * timersSize;
sys->now = 0;
sys->begin = (int *) malloc(tmp);
memset(sys->begin, 0, tmp);
sys->status = (int *) malloc(tmp);
memset(sys->status, 0, tmp);
sys->time = (int *) malloc(tmp);
memcpy(sys->time, timers, tmp);
sys->size = timersSize;
return sys;
}
static bool TimerSystemTimerStart(TimerSystem *sys, int timerId) {
if (timerId < 0 || timerId >= sys->size) {
return false;
}
sys->begin[timerId] = sys->now;
sys->status[timerId] = 1;
return true;
}
static bool TimerSystemTimerStop(TimerSystem *sys, int timerId) {
if (timerId < 0 || timerId >= sys->size) {
return false;
}
sys->begin[timerId] = sys->now;
sys->status[timerId] = 2;
return true;
}
static int Compare(const ResultInfo *a1, const ResultInfo *a2) {
if (a1->time == a2->time) {
return a1->timerId - a2->timerId;
}
return a1->time - a2->time;
}
static ResultInfo *TimerSystemRunTimerSystem(TimerSystem *sys, int nowTime,
size_t *returnValSize) {
int len = 0;
*returnValSize = 0;
for (int i = 0; i < sys->size; ++i) {
if (sys->status[i] == 1) {
len += (nowTime - sys->begin[i]) / sys->time[i];
}
}
if (len == 0) {
sys->now = nowTime;
return NULL;
}
ResultInfo *res = (ResultInfo *) malloc(sizeof(ResultInfo) * len);
int resSize = 0;
for (int i = 0; i < sys->size; ++i) {
if (sys->status[i] == 1) {
int val = (nowTime - sys->begin[i]) / sys->time[i];
for (int j = 1; j <= val; ++j) {
res[resSize].timerId = i;
res[resSize].time = sys->begin[i] + sys->time[i] * j;
resSize++;
}
sys->begin[i] += sys->time[i] * val;
}
}
sys->now = nowTime;
qsort(res, resSize, sizeof(ResultInfo), Compare);
*returnValSize = resSize;
return res;
}
static void TimerSystemFree(TimerSystem *sys) {
if (sys->status != NULL) {
free(sys->status);
}
if (sys->time != NULL) {
free(sys->time);
}
if (sys != NULL) {
free(sys);
}
}
void test01() {
int arr[] = {3, 5};
int size = 2;
TimerSystem *sys = TimerSystemCreate(arr, size);
printf("%d\n", TimerSystemTimerStart(sys, 0));
printf("%d\n", TimerSystemTimerStart(sys, 1));
size_t returnSize = 0;
ResultInfo *res = TimerSystemRunTimerSystem(sys, 15, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d %d\n", res[i].time, res[i].timerId);
}
printf("%d\n", TimerSystemTimerStop(sys, 1));
returnSize = 0;
res = TimerSystemRunTimerSystem(sys, 20, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d %d\n", res[i].time, res[i].timerId);
}
printf("%d\n", TimerSystemTimerStop(sys, 1));
printf("%d\n", TimerSystemTimerStop(sys, 2));
}
void test02() {
int arr[] = {8, 4, 11};
int size = 3;
TimerSystem *sys = TimerSystemCreate(arr, size);
size_t returnSize = 0;
ResultInfo *res = TimerSystemRunTimerSystem(sys, 2, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d %d\n", res[i].time, res[i].timerId);
}
printf("%d\n", TimerSystemTimerStart(sys, 1));
printf("%d\n", TimerSystemTimerStart(sys, 4));
res = TimerSystemRunTimerSystem(sys, 8, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d %d\n", res[i].time, res[i].timerId);
}
printf("%d\n", TimerSystemTimerStart(sys, 0));
printf("%d\n", TimerSystemTimerStart(sys, 2));
printf("%d\n", TimerSystemTimerStart(sys, 1));
res = TimerSystemRunTimerSystem(sys, 20, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d %d\n", res[i].time, res[i].timerId);
}
printf("%d\n", TimerSystemTimerStop(sys, 1));
returnSize = 0;
res = TimerSystemRunTimerSystem(sys, 30, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d %d\n", res[i].time, res[i].timerId);
}
}
int main() {
setbuf(stdout, NULL);
test01();
// test02();
return 0;
}
查看10道真题和解析
华为主管面250人在聊
投递华为等公司10个岗位