©2020-2024 ioDraw All rights reserved,
Privacy Policy
华为od一面面试算法
在看题目之前，谈谈对于面试时手撸算法的看法，如果在面试之前刷了几百+的leetcode,那么只要好好总结一下，我觉得面试的算法是完全可以做出来的；但是如果没有刷到那么多，我们怎么能够发挥好？我觉得首先对于每种类型的题目，例如链表类的、数组类的、二叉树类的、排序类的、字符串类的、双指针、这些每种类型的题目刷几道，对于解题思路就能能大致把握；面试做题还是蛮考研心理素质的，所以还是只有多刷题提升自己的底气。
一、题目
//某系统中有一空间连续的内存，被划分成多个大小相同的内存块。内存的使用状态记录在字符串 memory 中，每个内存块的状态用字符 x 或 . 表示，其中：
//· . 表示该内存块空闲； //· x 表示该内存块被使用，x 为小写字母。 //现在可释放其中 最多 cnt 个内存块（即字符串中的 x 变成
.），以获得一块空间连续的、且 最长的 空闲内存，请计算并返回该最长空闲内存的内存块数量。 //示例 1： //输入： //memory =
"..x..x..xx..." //cnt = 2 //输出：8 //解释： // //将 memory[2] 与 memory[5] 的内存块释放，可获得从
memory[0] 到 memory[7]、长度为 8 的连续空闲内存； //将 memory[5] 与 memory[8] 的内存块释放，可获得从
memory[3] 到 memory[8]、长度为 6 的连续空闲内存； //将 memory[8] 与 memory[9] 的内存块释放，可获得从
memory[6] 到 memory[12]、长度为 7 的连续空闲内存； //其他释放方式获得的连续空闲内存都小于 8； //因此返回 8。 //示例 2：
//输入： //memory = "....x." //cnt = 3 //输出：6 //示例 3： //输入： //memory =
"xx.x..xx....x..." //cnt = 0 //输出：4 //提示：0 <= cnt <= memory.length <= 10^5
分析：首先这道题采用双指针，我们先拆解，也就是一个字符串连续.最大值，然后就是替换x;将替换后的字符串带入求最大的函数中，即可求解。有了思路之后，编码就比较简单了，但是仍然需要考虑一些边界问题，保证代码健壮。
go 语言版本
func main() { in := bufio.NewReader(os.Stdin) b,_,_ := in.ReadLine() memory :=
string(b) b,_,_ = in.ReadLine() newMemory := memory cnt,_ := strconv.Atoi(string
(b)) temp := 0 i := 0 max := 0 if cnt == 0 { fmt.Println(FindMax(memory)) return
} for { if i >= len(memory) { break } for j := i;j < len(memory);j++ { if fmt.
Sprintf("%c",memory[j]) == "x" { memory = memory[0:j]+"."+memory[j+1:] temp++ if
temp== cnt { max = int(math.Max(float64(FindMax(memory)),float64(max))) temp =
0 memory = newMemory break } } } if temp < cnt { max = int(math.Max(float64(
FindMax(memory)),float64(max))) temp = 0 memory = newMemory } i++ } fmt.Println(
max) } //找连续最大 func FindMax(str string) int { i := 0 j := 0 max := 0 for { if i
>= len(str) { break } temp := 0 if fmt.Sprintf("%c",str[i]) == "." { j = i } for
{ if j >= len(str) { break } if str[i] == str[j] && fmt.Sprintf("%c",str[i]) ==
"." { temp++ j++ }else { break } } max = int(math.Max(float64(max),float64(temp)
)) i = j if i < len(str) && fmt.Sprintf("%c",str[i]) != "." { i++ j = i } }
return max }
java 版本
public class Main { public static void main(String[] args) { Scanner sc = new
Scanner(System.in); String memory = sc.nextLine(); String newMemory = memory;
char[] ch = memory.toCharArray(); int cnt = sc.nextInt(); if (cnt == 0) { System
.out.println(findMax(memory)); return; } int temp = 0; int res = 0; int j = 0;
while(j < ch.length) { for(int i = j;i<ch.length;i++) { if (ch[i] == 'x') { ch[i
] = '.'; temp++; } if (temp == cnt) { res = Math.max(findMax(String.valueOf(ch))
,res); temp = 0; ch = newMemory.toCharArray(); } } if (temp < cnt) { res = Math.
max(findMax(String.valueOf(ch)),res); temp = 0; ch = newMemory.toCharArray(); }
j++; } System.out.println(res); return; } public static int findMax(String s) {
char[] ch = s.toCharArray(); int i = 0,j = 0,max = 0; while(i < ch.length) { int
temp= 0; if (ch[i] == '.') { j = i; } while(j < ch.length) { if(ch[i] == ch[j]
&& ch[i] == '.') { temp++; j++; }else { break; } } max = Math.max(temp,max); i++
; } return max; } }