华为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 := memorycnt,_ := strconv.Atoi(string(b))temp := 0i := 0max := 0if cnt == 0 {fmt.Println(FindMax(memory))return}for {if i >= len(memory) { break}for j := i;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 = jif 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; }}