記一次華為機試
介紹
華為機試分為 3 題，兩題 100 分，一題 200 分，壓線 150 分算你過，時間150分鐘，支持多語言環(huán)境（?？途W(wǎng)），考試時需全程打開攝像頭，電腦屏幕分享，手機打開某小程序（可用計算器）不退出，可用本地 IDE, 會有一些測試題給你熟悉環(huán)境預(yù)熱的。
備注： 由于腦容量有限，題目具體的描述筆者已經(jīng)記不清了，但是一些考點還是記憶猶新，遂記錄分享下。做機考這幾點很重要， 第一點是你要看明白它的輸入輸出是什么？第二點是要快，比如說你明知道有現(xiàn)成的意大利炮可以轟它，咱就不要自己造個土炮了，挺浪費時間的，畢竟機考的本質(zhì)其實是刷人， 第三點就是心態(tài)一定要好，你會做的你要盡量 100%把它做出來，遇到不會的智商題，那也就聽天由命了。
消消樂（字符串）
描述
給定一個只包含大小寫字母的字符串（大小寫敏感），若相鄰兩個元素相等則消除，直到最后字符串消除不了了，輸出消消樂后字符串的長度，若遇到非大小寫字母以外的字符，則輸出0。
示例
輸入：mMbccbc
輸出：3
解釋：cc消掉，然后bb消掉，最后剩余mMc,輸出長度3
題解
這里我是把一些特殊情況單獨拎出來處理，然后創(chuàng)建了一個字符串res去存最后得到的字符串，然后輸出其長度。
const?readline?=?require('readline');
const?rl?=?readline.createInterface({
??input:?process.stdin,
??output:?process.stdout,
});
rl.on('line',?function?(line)?{
??console.log(solution(line.trim()));
});
function?solution(str)?{
??if?(/[^a-zA-Z]/.test(str))?{
????return?0;
??}
??if?(str.length?===?1)?{
????return?1;
??}
??if?(str.length?===?2)?{
????if?(str[0]?===?str[1])?{
??????return?0;
????}?else?{
??????return?2;
????}
??}
??let?res?=?'';
??let?cur?=?0;
??for?(let?i?=?0;?i?1;?i++)?{
????if?(str[i]?===?str[i?+?1])?{
??????i++;
????}?else?{
??????if?(res.length?>?0?&&?res[res.length?-?1]?===?str[i])?{
????????res?=?res.slice(0,?res.length?-?1);
??????}?else?{
????????res?+=?str[i];
??????}
????}
????cur?=?i;
??}
??cur?=?cur?+?1;
??if?(str[cur])?{
????if?(res[res.length?-?1]?===?str[cur])?{
??????res?=?res.slice(0,?res.length?-?1);
????}?else?{
??????res?+=?str[cur];
????}
??}
??return?res.length;
}
矩陣最大值（二維矩陣）
描述
給定一個n*n的只包含0和1的二維矩陣，請你計算出該矩陣的最大值。計算方式為將每一行的元素組成二進制數(shù)的十進制數(shù)相加，每一行元素可以進行左移右移（實質(zhì)就是求出每行的最大值相加）， 比如說10001向左移一位就是00011。
示例
輸入：
5
1,0,0,0,1
0,0,0,1,1
0,1,0,1,0
1,0,0,1,1
1,0,1,0,1
輸出：
122
解釋：當(dāng)n為5時，即5*5的二維矩陣時，通過相關(guān)左右平移，得到二維矩陣的最大值是122
題解
靈機一動，結(jié)合了parseInt(str, radix)可以將二進制轉(zhuǎn)成十進制數(shù)，求其最大值，最后相加求得矩陣最大值。
const?readline?=?require('readline');
const?rl?=?readline.createInterface({
??input:?process.stdin,
??output:?process.stdout,
});
let?count?=?0;
let?res?=?0;
rl.on('line',?function?(line)?{
??if?(count?===?0)?{
????count?=?+line;
????res?=?0;
??}?else?{
????res?+=?solution(line.trim());
????if?(count?===?1)?{
??????console.log(res);
????}
????count--;
??}
});
function?solution(str)?{
??const?arr?=?str.split(',');
??let?max?=?parseInt(arr.join(''),?2);
??const?len?=?arr.length;
??for?(let?i?=?1;?i?????const?tmp?=?parseInt(arr.slice(i,?len).concat(arr.slice(0,?i)).join(''),?2);
????max?=?max?>?tmp???max?:?tmp;
??}
??return?max;
}
樹的剪枝（樹）
描述
給定一棵樹，刪除某個結(jié)點（結(jié)點值唯一）及其下面的子結(jié)點（額，這題是我高度概括的，做的操作就類似于給你一棵叉樹，你用剪刀把某個枝給剪掉去）,并把剩余結(jié)點按從小到大輸出。
示例
輸入：
5
2?10
8?10
3?8
4?8
1?4
8
輸出：
2?10
解釋：表示先輸入5組數(shù)據(jù)，然后每行前面的數(shù)字是子結(jié)點，后面的數(shù)字是父結(jié)點，最后輸入要刪除的結(jié)點8，輸出剩余的結(jié)點（由小到大）
題解
時間關(guān)系，這題就不用樹去求解了吧，考慮到我是個jser,所以我先創(chuàng)建了一個對象obj, 將父結(jié)點以字符串key的形式存儲，將子結(jié)點以數(shù)組value的形式存儲，最后我只需要遞歸出要刪除的值存入removed_arr,然后進行過濾排序即可得出答案。
const?readline?=?require('readline');
const?rl?=?readline.createInterface({
??input:?process.stdin,
??output:?process.stdout,
});
let?obj?=?{};
let?count?=?0;
const?removed_arr?=?[];
rl.on('line',?function?(line)?{
??if?(count?===?0)?{
????count?=?parseInt(line)?+?1;
????obj?=?{};
????removed_arr.length?=?0;
??}?else?{
????if?(count?===?1)?{
??????const?arr?=?[];
??????func(line,?obj);
??????for?(const?key?in?obj)?{
????????if?(key?!==?line?&&?!removed_arr.includes(key))?{
??????????arr.push(key);
????????}
????????arr.push(...obj[key].filter((item)?=>?!removed_arr.includes(item)));
??????}
??????console.log(arr.sort((a,?b)?=>?Number(a)?-?Number(b)).join('?'));
????}?else?{
??????const?[value,?key]?=?line.split('?');
??????if?(obj[key])?{
????????obj[key].push(value);
??????}?else?{
????????obj[key]?=?[value];
??????}
????}
????count--;
??}
});
function?func(key,?obj)?{
??if?(obj[key])?{
????for?(const?val?of?obj[key])?{
??????func(val,?obj);
????}
??}
??removed_arr.push(key);
}
最后
總的來說，菊廠出的試卷題目考點還是分布比較均勻的，數(shù)據(jù)結(jié)構(gòu)和常規(guī)算法一定要好好學(xué)，嗯，我回去補樹去了。。。。。。
說明
本文首發(fā)于 GitHub 倉庫https://github.com/ataola/coding，線上閱讀地址：https://zhengjiangtao.cn/coding/，轉(zhuǎn)載請注明出處，謝謝！