華為od一面面試算法

在看題目之前，談?wù)剬τ诿嬖嚂r手擼算法的看法，如果在面試之前刷了幾百+的leetcode,那么只要好好總結(jié)一下，我覺得面試的算法是完全可以做出來的；但是如果沒有刷到那么多，我們怎么能夠發(fā)揮好？我覺得首先對于每種類型的題目，例如鏈表類的、數(shù)組類的、二叉樹類的、排序類的、字符串類的、雙指針、這些每種類型的題目刷幾道，對于解題思路就能能大致把握；面試做題還是蠻考研心理素質(zhì)的，所以還是只有多刷題提升自己的底氣。

一、題目

//某系統(tǒng)中有一空間連續(xù)的內(nèi)存，被劃分成多個大小相同的內(nèi)存塊。內(nèi)存的使用狀態(tài)記錄在字符串 memory 中，每個內(nèi)存塊的狀態(tài)用字符 x 或 . 表示，其中：//· . 表示該內(nèi)存塊空閑；//· x 表示該內(nèi)存塊被使用，x 為小寫字母。//現(xiàn)在可釋放其中 最多 cnt 個內(nèi)存塊（即字符串中的 x 變成 .），以獲得一塊空間連續(xù)的、且 最長的 空閑內(nèi)存，請計算并返回該最長空閑內(nèi)存的內(nèi)存塊數(shù)量。//示例 1：//輸入：//memory = “..x..x..xx…”//cnt = 2//輸出：8//解釋：////將 memory[2] 與 memory[5] 的內(nèi)存塊釋放，可獲得從 memory[0] 到 memory[7]、長度為 8 的連續(xù)空閑內(nèi)存；//將 memory[5] 與 memory[8] 的內(nèi)存塊釋放，可獲得從 memory[3] 到 memory[8]、長度為 6 的連續(xù)空閑內(nèi)存；//將 memory[8] 與 memory[9] 的內(nèi)存塊釋放，可獲得從 memory[6] 到 memory[12]、長度為 7 的連續(xù)空閑內(nèi)存；//其他釋放方式獲得的連續(xù)空閑內(nèi)存都小于 8；//因此返回 8。//示例 2：//輸入：//memory = “….x.”//cnt = 3//輸出：6//示例 3：//輸入：//memory = “xx.x..xx….x…”//cnt = 0//輸出：4//提示：0 <= cnt <= memory.length <= 10^5

分析：首先這道題采用雙指針，我們先拆解，也就是一個字符串連續(xù).最大值，然后就是替換x;將替換后的字符串帶入求最大的函數(shù)中，即可求解。有了思路之后，編碼就比較簡單了，但是仍然需要考慮一些邊界問題，保證代碼健壯。

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; }}