KKCompany面試解題

一、前言

這幾天連假友人遠距解題的期間，我也順便看了他所解的題目並便用TS拿來解。該解題方式使用Codility產生題目，這次我們是限時2小時，總共4題。

二、題目

第一題 - 找出字串中重複兩次的字元

該題目表明每筆 字串S 除了答案之外，其他字元都不會重複，字元長度為2~27，只使用小寫。

範例：

1. S = “aba”, 答案要return “a”

2. S = “zz”, 答案要return “z”

3. S = “codility”, 答案要return “i”

解題思路：

• 其實這題只要用一個array，用loop去逐個塞入字元到陣列裏頭，塞入前可以判斷該字元是否存在，如果有，可以直接返回答案了。

• 我使用ES6的Set，分別用add()、has()，去作上述的操作。

解答：

const solution_1 = (string: string): string => {

    // 創建set去儲存char值
    let i:number = 0, stringLength: number = string.length, char: string = '';
    let set: Set<string> = new Set();
     
    // 逐字檢查
    for(; i < stringLength; i++) {
        char = string[i];
        // 如果有重複就返回
        if (set.has(char)) return char;
        // 沒有重複就加入set
        else set.add(char);
    }
    return char;
}

console.log(solution_1("aba"))  // a
console.log(solution_1("zz"))   // z
console.log(solution_1("codility")) //i

第二題 - 重複字元的最小刪除成本

該題目在上有LeetCode 1578，他給定一個 字串S 和一個 陣列cost，其中 cost[i] 是從 字串S 中刪除 字元i的成本。
該題目想要把鄰近兩個相同字元刪除，並去計算刪除的最小成本是多少。

範例：

1. S = “abccbd” && C = [1, 2, 3, 4, 5], 答案要return 2，處理後的字串是”abcbd”(但沒有要求return)

2. S = “aabbcc” && C = [1, 2, 1, 2, 1, 2], 答案要return 3，處理後的字串是”abc”(但沒有要求return)

3. S = “aaaa” && C = [3, 4, 5, 6], 答案要return 12，處理後的字串是”a”(但沒有要求return)

解題思路：

• 使用loop去判斷 字元string[i] 和 隔壁字元string[(i + 1)] 是否相等，不相等就i++。

• 如果相等的話，比較大小，並累加到 答案answer 之中。

  • 比較大小的話，我直接把最小值的cost都往左邊塞，這樣只要取左邊的值就好，後續多個重複字元(aaabbb)的話也不會算錯。

    • Ex. array[i] > array[(i + 1)] => 4 > 3，將兩個cost值SWAP(array[i], array[(i + 1)])

解答：

const solution_2 = (string: string, array: number[] = []): number => {
    let i: number = 0, stringLength: number = string.length, answer:number = 0;

    for (; (i + 1) <= stringLength; ++i) {
        if (string[i] != string[(i + 1)]) continue;
        if (array[i] > array[(i + 1)]) {
            // SWAP(array[i], array[(i + 1)])
            array[(i + 1)] = [array[i], array[i] = array[(i + 1)]][0]
        }
        answer += array[i];
    }
    
    return answer;
}

console.log(solution_2("aabaa", [1, 2, 3, 4, 1]))   // 2
console.log(solution_2("aabbcc", [1, 2, 3, 4, 1, 6]))   // 5
console.log(solution_2("aabbaacc", [1, 2, 3, 5, 4, 1, 8, 9]))   // 13
console.log(solution_2("bbbaaa", [4, 9, 3, 8, 8, 9]))   // 23
console.log(solution_2("abc", [1, 2, 3]))   // 0
console.log(solution_2("aaabbbabbbb", [3,5,10,7,5,3,5,5,4,8,1]))    // 26

第三題 - 簡單版踩地雷

這題與Leetcode 529. Minesweeper上的題目不同，相對比較簡單，主要是給定一個 長度N 形成N * N的陣列，並且在給定 行數R陣列 和 列數C陣列，來去分別對應他的炸彈位置，並且用 字元'B' 來表示。
然後我們還必須要判斷每個座標點上鄰近的8個格子的炸彈數量是多少，並用數字去標記。

範例：

1. N = 3 && R = [2, 1, 0, 2] && C = [0, 2, 1, 2]，這是一個3*3的陣列，(2, 0)、(1, 2)、(0, 1)、(2, 2)就是炸彈放置的位置，答案要return
   1B2
   24B
   B3B

2. N = 5 && R = [2, 3, 2, 3, 1, 1, 3, 1] && C = [3, 3, 1, 1, 1, 2, 2, 3]，答案要return
   12321
   2BBB2
   3B8B3
   2BBB2
   12321

3. N = 2 && R = I && C = I，答案要return
   00
   00

解題思路：

• 我先建立一個預設值為0的N*N的陣列，再判斷炸彈位置，並以’B’取代。

• 然後就用loop在陣列中逐個元素計算鄰近8個位置的炸彈數，並以number標記，如果該元素已經是’B’炸彈了，就不處理。

• 最後再把陣列轉換成字串。

解答：

const solution_3 = (N: number, Rows: number[], Cols: number[]): string => {
    let i: number = 0, j: number = 0, bombNums: number = 0, answer: string = '';
    let array2D: Array<Array<number | string>> = new Array(N);

    // 使用0來填滿N * N的陣列
    for(i = 0; i < N; i++) {
        array2D[i] = new Array(N)
        array2D[i] = Array.apply(null, array2D[i]).map(() => 0)
    }

    //加入Bomb座標
    for(i = 0; i < Rows.length; i++) array2D[Rows[i]][Cols[i]] = 'B';

    //開始判斷四面八方有沒有Bomb
    for(i = 0;i < N; i++) {
        j = 0;
        for(;j < N; j++) {
            bombNums = 0;
            if(array2D[i][j] === 'B') continue;

            if(i - 1 >= 0) if(array2D[i - 1][j] === 'B') bombNums++;
            if(j - 1 >= 0) if(array2D[i][j - 1] === 'B') bombNums++;
            if(i + 1 < N) if(array2D[i + 1][j] === 'B') bombNums++;
            if(j + 1 < N) if(array2D[i][j + 1] === 'B') bombNums++;

            if(i - 1 >= 0 && j - 1 >= 0) if(array2D[i - 1][j - 1] === 'B') bombNums++;
            if(i - 1 >= 0 && j + 1 < N) if(array2D[i - 1][j + 1] === 'B') bombNums++;
            if(i + 1 < N && j - 1 >= 0) if(array2D[i + 1][j - 1] === 'B') bombNums++;
            if(i + 1 < N && j + 1 < N) if(array2D[i + 1][j + 1] === 'B') bombNums++;
            array2D[i][j] = bombNums;
        }    
    }

    // 陣列轉換String
    array2D.forEach((item: Array<number | string>) => {
        answer += item.join("") + '\n';
    })

    return answer
}

console.log(solution_3(3, [2,1,0,2], [0,2,1,2]))
// 1B2
// 24B
// B3B
console.log(solution_3(5, [2, 3, 2, 3, 1, 1, 3, 1], [3, 3, 1, 1, 1, 2, 2, 3]))
// 12321
// 2BBB2
// 3B8B3
// 2BBB2
// 12321
console.log(solution_3(2, [], []))
// 00
// 00

第四題 - 找出矩陣中分數相加的最大值

這題主要會給定一個帶有分數 二維陣列A，該陣列為 N*M的大小(N和M可以不相等)，我們必須判斷該矩陣中哪兩個值相加為最大值。
但有一個規則是相加的兩個座標中，行座標 或 列座標 都不可以相等。

範例：

1. A = [[1, 4], [2, 3]]，A[0][0] + A[1][1] = 4，A[0][1]+A[1][0] = 6，答案要return 6

	0	1
0	1	4
1	2	3

2. A = [[15, 1, 5], [16, 3, 8], [2, 6, 4]]，A[0][0] + A[2][1] = 23(max)，答案要return 23

	0	1	2
0	15	1	5
1	16	3	8
2	2	6	4

3. A = [[12, 12], [12, 12], [0, 7]]，A[1][0] + A[0][1] = 24，答案要return 24

	0	1
0	12	12
1	12	12
2	0	7

解題思路：

• 二為陣列要用loop去逐個判斷並相加我覺得處理起來有點複雜，所以我先將二維轉成一維陣列，並在轉成一維的同時儲存他的 座標值(i,j)。

• 因為要取相加最大值，所以一維陣列由大到小排序，再用loop去相加，如果比answer大，那就儲存在answer。

  • 如果i或j其中一個座標相同，則不處理相加。

解答：

const solution_4 = (A: number[][]): number => {
    // 定義型別
    // iLength行數，jLength列數，answer最大值
    let i: number = 0, j: number = 0, tmp: number = 0, iLength: number = A.length, jLength: number = A[0].length, answer: number = 0;
    interface flatObject {
        value: number;
        i: number;
        j: number;
    }
    let flatArray: flatObject[] = [];
    

    // 將二維扁平化成一維，儲存i和j的key
    for(;i < iLength; i++) {
        j = 0;
        for(;j < jLength; j++) {
            flatArray.push({ value: A[i][j], i: i, j: j })
            // from: [[12, 12], [12, 12], [0, 7]]
            // 
            // to:
            // [
            //     { value: 12, i: 0, j: 0 },
            //     { value: 12, i: 0, j: 1 },
            //     { value: 12, i: 1, j: 0 },
            //     { value: 0, i: 2, j: 0 },
            //     { value: 7, i: 2, j: 1 },
            // ]
        }    
    }

    // 將一維做排序，大到小
    flatArray = flatArray.sort((a: flatObject, b: flatObject) => b.value - a.value)
    
    i = 0;
    for(;i <= iLength; i++) {
        j = 0;
        for(;j <= jLength; j++) {
            // 這裡面是作相加的操作，因為不能與行或列的key相等的值相加
            // 
            // 相加
            // Ex. 這兩個值中，i和j都不相等，所以可以相加
            //     { value: 12, i: 0, j: 0 },
            //     { value: 12, i: 1, j: 1 },
            // 
            // 不相加
            // Ex. 這兩個值中，i是相等的，所以不能使用
            //     { value: 12, i: 0, j: 0 },
            //     { value: 12, i: 0, j: 1 },
            // Ex. 這兩個值中，j是相等的，所以不能使用
            //     { value: 12, i: 0, j: 0 },
            //     { value: 12, i: 1, j: 0 },
            if(flatArray[i].i === flatArray[j].i || flatArray[i].j === flatArray[j].j) continue;
            tmp = flatArray[i].value + flatArray[j].value

            // 相加後儲存最大值，跑迴圈直到結束
            if(answer < tmp) {
                answer = tmp
            }
        }    
    }

    return answer;
}

console.log(solution_4([[12, 12], [12, 12], [0, 7]]))   // 24
console.log(solution_4([[1, 2, 14], [8, 3, 15]]))   // 22
console.log(solution_4([[1, 4], [2, 3]]))   // 6