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

最长回文子串

/*
1、在函数longest中，
遍历字符串，分别以每个字符为中心，
查找奇数长度和偶数长度的回文子串，
然后比较得到最长的回文子串。
2、在getSubstring函数中，
采用双指针法，从中心向两边展开，
找到回文子串的起始位置和结束位置，最后返回该子串。
举例：
babad
1、先循环b，得到s1是b， s2是””
2、更新回文串长度为1
3、在循环a，s1=bab ，s2=””
4、更新回文串长度为3
持续这样的过程就可以了*/
class Solution {
public String longestPalindrome(String s) {
String n = "";
for(int i = 0; i < s.length(); i++){
String s1 = palindrome(s, i, i);
String s2 = palindrome(s, i, i + 1);
if(s1.length() > n.length())
n = s1;
if(s2.length() > n.length())
n = s2;
}
return n;
}
String palindrome(String s, int l, int r){
//防止左右指针索引越界
while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
// 双指针，向两边展开
l--;
r++;
}
return s.substring(l + 1, r);
}
}

安排工作以达到最大收益

/*可以通过双指针算法，
一个指针指向工作，一个指针指向工人，
指向工人的指针是序号最小的，
能够承受某一工作的工人，这样，
不断增加指向工作的指针，
就能获得每个工人可以干的收益最大的工作。
具体：
1、先把工作难度数组和工作收益数组合并为jobs
2、再对jobs进行升序排序，对工人数组也进行升序排序
3、While循环作用是找到能匹配工作难度的工人
4、如果没有能胜任的工人就直接退出
5、如果有胜任的工人j，为了能使获取到最大的收益所以，先把以前算的每个人的收益减掉后，
再加上当前最大的收益，就是最后的结果*/
import java.util.*;
public class Main {
public static class Work {
public int diffi;//工作难度
public int profit;//工作收益
public Work(int d, int p) {
diffi = d;
profit = p;
}
}
public static int calc(int[] difficulty, int[] profit, int[] worker) {
int n = difficulty.length;//n个工作
int m = worker.length;//m个人
Work[] jobs = new Work[n]; // 构建工作数组
for (int i = 0; i < n; i++) {
jobs[i] = new Work(difficulty[i], profit[i]);
}
// 将工作根据工作难度进行升序
Arrays.sort(jobs, (a, b) -> a.diffi - b.diffi);
// 工人也根据能力进行升序
Arrays.sort(worker);
// top用来保存某一工作难度下得最大收益
int top = 0;
int res = 0;
// i从低到高遍历所有工作，j用于指向可以承受该难度得最低工人序号
for (int i = 0, j = 0; i < n; i++) {
// 剔除掉无法承受该工作强度的工人，j后面的工人能力都是大于工作i的
while (j < m && worker[j] < jobs[i].diffi) {
j++;
}
// 如果j已经指向最后了，那么就没有工人能干剩下得活了，直接退出
if (j == m) {
break;
}
// 我们需要给后面的工人更换价值更高的活，所以，先剔除这部分工人之前工作收益
res -= (m - j) * top;
// 取最大收益
top = Math.max(top, jobs[i].profit);
// 给后面的工人安排新的工作
res += (m - j) * top;
}
return res;
}
public static void main(String[] args) {
int[] difficulty = {2, 4, 6, 8, 10};
int[] profit = {10, 20, 30, 40, 50};
int[] worker = {4, 5, 6, 7};
System.out.println(calc(difficulty, profit, worker));
}
}

MAC地址

void test02(string t){
transform(t.begin(), t.end(), t.begin(),
[](unsigned char c) { return std::tolower(c); });
set<string> set;
regex p("[0-9a-fA-F]{2}(-[0-9a-fA-F]{2}){5}|[0-9a-fA-F]{2}(:[0-9a-fA-F]
{2}){5}");
string::const_iterator it = t.cbegin();
smatch match;
while (regex_search(it, t.cend(), match, p)) {
string s = match[0];
replace(s.begin(),s.end(),':','-');
set.insert(s);
it = match[0].first + 3;
}
cout << set.size() << endl;
}
int main()
{
string test1 = "01:02:03:04:05:06:07:11:12-10:12-00-01-02-03-04-05-06-
07";
test02(test1);
return 0;}

简化路径

/*思路：
使用栈来完成
1、以/分割字符串成多个文件夹
2、遇到..就将栈中的元素弹出（上一层目录弹出）
3、文件夹名上不包含 空格或者.或者包含..的时候将文件夹名入栈
4、如果最后路径为空，就只返回一个/(根目录）
5、如果不为空，返回拼接栈中保存的文件夹，形成的路径就可以了
举例：
/a/./b/../../c/
1、先将字符串按照/分成多个路径
a . b .. .. c
2、让a和b入栈
3、将.跳过
4、遇到..将b弹出
5、再遇到..将a弹出
6、然后将c入栈
最后给c的前边加一个/即可，就是最后的 结果 /c
*/
import java.util.*;
public class Main {
public static String simplifyPath(String path) {
Stack<String> st = new Stack<>();
StringBuilder res = new StringBuilder();
for (String p : path.split("/")) {
if (!st.empty() && p.equals("..")) {
st.pop();
} else if (!" ..".contains(p)) {
st.push(p);
}
}
for (String i : st) {
res.append("/" + i);
}
return res.length() == 0 ? "/" : res.toString();
}
public static void main(String[] args) {
System.out.println(simplifyPath("/home/"));
System.out.println(simplifyPath("/../"));
System.out.println(simplifyPath("/home//foo/"));
System.out.println(simplifyPath("/a/./b/../../c/"));
}
}

字符串相加

/*题目理解：
正常情况下int或者long处理不了太长的数字相加
所以太长的数字相加，可以通过字符串的方式进行相机
思路：
1、用两个指针分别指向两个字符串的最后位置，同时从两个字符串的最后开始遍历，
每次将两个字符串中的两个字符拿出来，转换为int后相加
用carry表示这两个数相加后的进位是几，十进制的个位数相加进位只能是1或者0
2、下一次再拿两个字符出来进行相加并加上进位
3、直到两个字符串遍历完成为止
4、因为计算时从后往前计算的，所以最后需要把结果翻转过来才是最终的结果
4、有一个特殊情况，当两个字符串都遍历完了之后，
如果carry（进位）还是1的话就说明，最后还要结果中添加一个1
例如：
9989
151
1、首先拿出来9和1进行相加，给结果中添加0，进位1
2、在拿出来8和5相加，再加上进位1 ，结果是14，给结果中添加4，进位为1
3、在拿出来9和1，再加上进位1，结果是11，给结果中添加1，进位为1
4、在从第一个字符串中拿一个9，
第二个字符串中没有值了，就给一个默认值0
再加上进位1，相加结果是10，给结果中添加0，进位为1
5、最后，carry进位为1，所以给结果中直接添加一个1
6、最终的结果是：04101，把他翻转过来就是10140
这个就是最终的结果*/
import java.util.*;
public class Main {
public static String addLong(String add, String toAdd) {
StringBuilder ret = new StringBuilder();
int i = add.length() - 1;
int j = toAdd.length() - 1;
int carry = 0;//表示进位
while (i >= 0 || j >= 0) {
int n1 = i >= 0 ? add.charAt(i) - '0' : 0;
int n2 = j >= 0 ? toAdd.charAt(j) - '0' : 0;
int tmp = n1 + n2 + carry;
carry = tmp / 10;//计算本次计算完成后的进位
ret.append(tmp % 10);
i--;
j--;
}
if (carry == 1) {//如果当两个字符串都遍历完了，进位还有1的话，就说明字符串的最
前边还要添加一个1
ret.append(1);
}
return ret.reverse().toString();
}
public static void main(String[] args) {
System.out.println(addLong("9", "1"));
System.out.println(addLong("9999", "1"));}
}

点菜展示表

class Solution {
public List<List<String>> displayTable(List<List<String>> orders) {
TreeSet<String> ts = new TreeSet<>(); // 记录菜的种类
// 映射用户的桌号到菜单的哈希表, 其中 value 保存的是 菜名-数量 表
TreeMap<String, Map<String, Integer>> m = new TreeMap<>
((Comparator.comparingInt(Integer::parseInt)));
// 把订单逐个添加到哈希表, 菜名添加到集合中
for (List<String> order : orders) {
ts.add(order.get(2));
var cnt = m.getOrDefault(order.get(1), new TreeMap<>());
cnt.put(order.get(2), cnt.getOrDefault(order.get(2), 0) + 1);
m.put(order.get(1), cnt);
}
// 返回值
List<List<String>> ans = new ArrayList<>();
// 构造表头
List<String> tableHead = new ArrayList<>();
tableHead.add("Table");
tableHead.addAll(ts);
ans.add(tableHead);
// 逐个添加表的内容
for (Map.Entry<String, Map<String, Integer>> entry : m.entrySet()) {
List<String> list = new ArrayList<>();
// 先添加桌号
list.add(entry.getKey());
for (String item : ts) {
// 如果其中某一个菜没有在订单表中找到, 那么就添加 0
list.add(entry.getValue().getOrDefault(item, 0).toString());
}
ans.add(list);
}
return ans;
}
}

员工设计题

import java.util.*;
class Main {
static class Employee {
private String name;
private int salary;
private String department;public Employee(String name, int salary, String department) {
this.name = name;
this.salary = salary;
this.department = department;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getSalary() {
return salary;
}
public void setSalary(int salary) {
this.salary = salary;
}
public String getDepartment() {
return department;
}
public void setDepartment(String department) {
this.department = department;
}
@Override
public String toString() {
return "Employee{" +
"name='" + name + '\'' +
", salary=" + salary +
", department='" + department + '\'' +
'}';
}
}
static List<String> m1(List<Employee> employees) {
List<String> res = new ArrayList<>();
for (Employee employee : employees) {
res.add(employee.getName());
}
return res;
}
static List<String> m2(List<Employee> employees) {
List<String> names = m1(employees);
Collections.sort(names);
return names;
}
static String m3(List<Employee> employees) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < employees.size(); i++) {
if (i == employees.size() - 1) {
sb.append(employees.get(i).getName());
} else {
sb.append(employees.get(i).getName() + ",");
}
}
return sb.toString();
}
static int m4(List<Employee> employees) {
int sum = 0;
for (int i = 0; i < employees.size(); i++) {
sum += employees.get(i).getSalary();
}
return sum;
}
static Map<String, List<Employee>> m5(List<Employee> employees) {
Map<String, List<Employee>> res = new HashMap<>();
for (Employee employee : employees) {
String key = employee.getDepartment();
if (res.containsKey(key)) {
res.get(key).add(employee);
} else {
List<Employee> tmp = new ArrayList<>();
tmp.add(employee);
res.put(key, tmp);
}
}
return res;
}
static Map<String, Integer> m6(List<Employee> employees) {
Map<String, Integer> res = new HashMap<>();
for (Employee employee : employees) {
String key = employee.getDepartment();
if (res.containsKey(key)) {
res.put(key, res.get(key) + employee.getSalary());
} else {
res.put(key, employee.getSalary());
}
}
return res;
}
static Map<Integer, List<Employee>> m7(List<Employee> employees) {
Map<Integer, List<Employee>> res = new HashMap<>();
for (Employee employee : employees) {
int salary = employee.getSalary();
int level = 0;
if (salary < 1500) {
level = 1;
} else if (salary <= 2000) {
level = 2;
} else {
level = 3;
}
if (res.containsKey(level)) {
res.get(level).add(employee);
} else {
List<Employee> tmp = new ArrayList<>();
tmp.add(employee);
res.put(level, tmp);
}
}
return res;
}
public static void main(String[] args) {
List<Employee> employees = new ArrayList<>();
employees.add(new Employee("zhangsan",3000,"develop"));
employees.add(new Employee("lisi",2000,"develop"));
employees.add(new Employee("wagnwu",2000,"sale"));
System.out.println(m1(employees));
System.out.println(m2(employees));
System.out.println(m3(employees));
System.out.println(m4(employees));
System.out.println(m5(employees));
System.out.println(m6(employees));
System.out.println(m7(employees));
}
}

最长公共前缀

C语言实现
思路：
1、求最长的公共前缀，
所以最长的公共前缀肯定不能超过所有单词的长度
所以先求出最小字符串的长度存到minSize中
2、定义一个char* num（最大情况下它的长度就是minSize+1），存最长的公共前缀
3、然后先将字符串拷贝到num中
4、循环所有的单词，从0位置开始比较，是否和num[i]中的每个字符相等
5、记录最小的位置i到minSize中
6、最后将num[minSize]这个位置置为\0(字符串结束了)
7、返回这个字符串num就可以了
比如：这个例子
"flower", "flow", "flight"
1、先求最小长度minSize = 4
2、定义char *num ,给num赋值为flow
3、在到三个单词中查找
第一次，num=flow到flower中查找，记录i为4，minSize =4
第二次，num=flow到flow中查找，记录i为4，minSize =4
第三次，num=flow 到flight中查找，记录i为2，minSize为2
4、最后将minSize=2的位置置为\0，也就是num字符串的结束置为\0
返回num即可
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *GetTheLongestPrefix(char **strs, int strNum) {
;
}
int minSize = INT_MAX;
for (int i = 0; i < strNum; ++i) {
int cLen = strlen(strs[i]);
minSize = minSize > cLen ? cLen : minSize;
}
char *num = malloc(minSize * (sizeof(char) + 1));
strncpy(num, strs[0], minSize); //将strs[0]中的前minSize个字符拷贝到num中
for (int j = 1; j < strNum; j++) {
int i = 0;
while (i < minSize && strs[j][i] == num[i]) {
i++;
}
minSize = i;
}
num[minSize] = '\0';
return num;
}
int main() {
char *strs[] = {"flower", "flow", "flight"};
int size = sizeof(strs) / sizeof(char *);
printf("%s\n", GetTheLongestPrefix(strs, size));
char *strs1[] = {"dog", "racecar", "car"};
int size1 = sizeof(strs1) / sizeof(char *);
printf("%s\n", GetTheLongestPrefix(strs1, size1));
return 0;
}

无重复字符的最长子串

/*思路：
使用滑动窗口算法来完成这个题
1、初始时让左右指针同时在0位置
2、进入循环后判断右指针上的值，是不是在[left,right)之间的
字符串中存在
3、如果存在左指针++
4、如果不存在，更新窗口大小到maxLen中
5、直到右指针越界为止，返回maxLen即可。
比如：abcabcbb
1、left = 0，right=0
2、遍历所有的字符，看右指针right上的值是a，现在左右指针还没有形成窗口
所以，直接给right++，更新maxLne为0
3、再次进入循环后，s[right]是b，窗口是a，所以b在a中也不存在
所以，直接给right++，更新maxLen为1
4、在进入循环后，s[rigth] 是c，窗口是ab，c不在ab中存在，
所以，直接给right++，更新maxLen为3
5、在进入循环后，s[right] 是a，窗口是abc，a在abc中存在，
所以，更新left++，窗口更新为bca后，更新maxLen为3
6、依次类推下去，就可以求出字符串中的最长无重复子串*/
public class Main {
public static int lengthOfLongestSubstring(String s) {
int sLen = s.length();
if (sLen == 1) return 1;
int l = 0;
int r = 0;
int maxLen = 0;
while (r < sLen) {
for (int i = l; i < r; i++) {
if (s.charAt(r) == s.charAt(i)) {
l = i + 1;
break;
}
}
r++;
maxLen = Math.max(maxLen, r - l);
}
return maxLen;
}
public static void main(String[] args) {
String s = "abcabcbb";
System.out.println(lengthOfLongestSubstring(s));
}
}

被围绕的区域

public class Main {
/**
* 题目含义：将X包围的O,用X替换掉。
* 思路：使用深度优先算法，递归四个方向是否全被包围，
* 如果包围了就给区域内设置为A（做标记）
* 写代码方便点，不用去new
* 肯定不能这样写了，new对象的方式去写
* 内存放到堆中，不会发生栈溢出这些问题
*/
//可以不设置也行，自己写的时候就这样了，就没改
private static int m;//存储数组的行数，为了递归中不用再传参了
private static int n;//存储数组的列数，为了递归中不用再传参了
public static void calc(char[][] board) {
m = board.length;
n = board[0].length;
/* 重点是这里：从边界上的'O'点开始递归进入：
如果有O，然后进入递归开始查找，
如果所有的边界都没有O,那么说明二维数组是被X包围的*/
for (int i = 0; i < m; i++) {
dfs(i, 0, board);//递归左边界,最左边的，是的
dfs(i, n - 1, board);//递归右边界
}
// 先找寻边界上的'O'点,然后开始进行改变状态
for (int i = 0; i < n; i++) {
dfs(0, i, board);//递归上边界
dfs(m - 1, i, board);//递归下边界
}
//更新数据，将为A的地方更新为O，A代表已经递归过了,将为O的更新为X，
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'A') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
//深度优先算法的代码
private static void dfs(int row, int col, char[][] board) {
//递归退出条件：行和列不在范围内，二维数组的值不为O，不是0就结束递归
//就是边界上不是O的，结束递归。不一定时候边界，就是整个二维数组中
//这个是退出递归
if (row >= m || col >= n || row < 0 || col < 0 || board[row][col] !=
'O') {
return;
}
board[row][col] = 'A';//改状态，是否递归过，
// 就是个标记位，给A没啥特殊含义，写成B也可以
//下次就不走了，不递归了
//四个方向去递归
dfs(row + 1, col, board);
dfs(row - 1, col, board);
dfs(row, col + 1, board);
dfs(row, col - 1, board);
}
public static void main(String[] args) {
char [][] board={{'X','X','X','O','X','X','X','X'},
{'X','O','O','X','O','X','O','O'},
{'X','O','X','X','O','O','O','X'},
{'X','X','X','O','X','X','X','X'},
{'O','O','O','X','X','X','X','X'},
{'X','O','X','X','X','X','X','X'},};
calc(board);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
System.out.print(board[i][j]+" ");
}
System.out.println();
}
}
}