华为技面三轮面试题
2023-12-17 12:48:48
1. 最长回文子串 -- 中心扩散法
给你一个字符串?s
,找到?s
?中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
class Solution {
//中心扩散
String max = "";
public String longestPalindrome(String s) {
for(int i = 0; i < s.length(); i++){
//回文串是偶数
dfs(s, i ,i);
//回文串是奇数
dfs(s, i, i + 1);
}
return max;
}
void dfs(String s, int left, int right){
String tmp;
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
tmp = s.substring(left, right + 1);
if(tmp.length() > max.length()){
max = tmp;
}
left--;
right++;
}
}
2. 插入后的最大值 -- 逻辑思维能力
给你一个非常大的整数?n
?和一个整数数字?x
?,大整数?n
?用一个字符串表示。n
?中每一位数字和数字?x
?都处于闭区间?[1, 9]
?中,且?n
?可能表示一个?负数?。
你打算通过在?n
?的十进制表示的任意位置插入?x
?来?最大化?n
?的?数值???????。但?不能?在负号的左边插入?x
?。
- 例如,如果?
n = 73
?且?x = 6
?,那么最佳方案是将?6
?插入?7
?和?3
?之间,使?n = 763
?。 - 如果?
n = -55
?且?x = 2
?,那么最佳方案是将?2
?插在第一个?5
?之前,使?n = -255
?。
返回插入操作后,用字符串表示的?n
?的最大值。
输入:n = "-13", x = 2 输出:"-123" 解释:向 n 中插入 x 可以得到 -213、-123 或者 -132 ,三者中最大的是 -123 。
关键:分正负,正数:寻找第一次比高位小插入,负数:寻找第一次比高位大的插入
class Solution {
public String maxValue(String n, int x) {
int len = n.length();
String res = "";
if(!n.substring(0,1).equals("-")){
for(int i = 0; i < n.length(); i++){
String tmp = n.substring(i,i + 1);
//注意integer会自动拆箱,可以直接比较
if(Integer.parseInt(tmp) < x){
res = res + x + n.substring(i);
break;
}
res = res + tmp;
}
if(res.length() == len){
res = res + x;
}
}else{
res = "-";
for(int i = 1; i < n.length(); i++){
String tmp = n.substring(i,i + 1);
if(Integer.parseInt(tmp) > x){
res = res + x + n.substring(i);
break;
}
res = res + tmp;
}
if(res.length() == len){
res = res + x;
}
}
return res;
}
}
3. 水果成篮 -- 滑动窗口
关键:本题的关键不在方法,而在对题目的理解上,读懂题就soeasy,否则gg,我最后是让面试官给我解释清啥意思的,千万别憋着,你就一个劲问。。。题目翻译成人话就是 :找至多包含两种元素的最长子串,返回其长度
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组?fruits
?表示,其中?fruits[i]
?是第?i
?棵树上的水果?种类?。
你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:
- 你只有?两个?篮子,并且每个篮子只能装?单一类型?的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘,你必须从?每棵?树(包括开始采摘的树)上?恰好摘一个水果?。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
- 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。
给你一个整数数组?fruits
?,返回你可以收集的水果的?最大?数目。
示例 1:
输入:fruits = [1,2,1] 输出:3 解释:可以采摘全部 3 棵树。
class Solution {
public int totalFruit(int[] fruits) {
//map<类型,数量>
Map<Integer, Integer> map = new HashMap<>();
int ans = 0;
int x, y;
for(int l = 0, r = 0; r < fruits.length; r++){
//你就往里放
x = fruits[r];
map.put(x, map.getOrDefault(x, 0) + 1);
//超过两种类型就清空一个篮子
while(map.size() > 2){
y = fruits[l++];
map.put(y, map.get(y) - 1);
if(map.get(y) == 0){
map.remove(y);
}
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}
文章来源:https://blog.csdn.net/a546835886/article/details/135042754
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!