JavaScript 網站技術

刷題到底是在刷什麼 1864 Minimum Number of Swaps to Make the Binary String Alternating

me
林彥成
2021-12-11 | 3 min.
文章目錄
  1. 1. 刷題是什麼?
  2. 2. 刷題準備
  3. 3. 刷題預備知識
  4. 4. 刷題語言
  5. 5. 刷題技巧
  6. 6. Leet Code 1864 範例解析

刷題是什麼?

軟體工程師在職涯上想要更進一步的過程中，刷題成為了無可避免的體驗，那刷題可以帶給工程師什麼好處?

  • 快速確認需求結果
  • 設計邏輯和演算法
  • 有效運用資料結構
  • 考慮完整邊界條件
  • 測試案例處理優化

實務上，目前工作了六年多快七年，刷題的技能還是沒鍛鍊起來，其實刷題鍛鍊的是靈活度以及創意發想的能力，但在工作領域上大多只是需要熟悉特定領域，解決差異不大的問題然後有穩定的產出。

刷題對於特定領域的知識並沒有太大的幫助，譬如前端來說還是需要自行補齊三大框架的設計概念和運用方法，後端也是要多看看大公司都是怎麼設計 API 的。

刷題準備

刷題之前需要找一個平台或參加解題活動

  • Leet Code: 業界常見刷題平台，免費註冊就可以開始解題
  • Advent of Code: 由一位國外開發者創立每年固定會舉辦的程式挑戰活動，從 12/1 開始到聖誕節結束，目前開始參加還來得及還有機會獲得禮物喔

刷題預備知識

如果先只求能解題，其實只需要了解很必備的知識即可。

  • 基本的迴圈、判斷、函式
  • 資料結構的知識，像是 linked list、stack、queue
  • 物件用法

刷題語言

實際上是屬於解謎遊戲，所以任何語言都能夠進行刷題，挑選自己習慣好上手的就可以了。

刷題技巧

由於目標是參加面試並通過，所以在鍛鍊上就是依照面試流程準備和練習即可，通常面試的流程會是

  1. 出題目
  2. 彼此溝通對題目的認知
  3. 提出預期解決的方式
  4. 實作
  5. 驗證
  6. 時間、空間複雜度理解與說明
    • 時間複雜度 (Time Complexity): 執行的次數，通常會看最大也就是 Big O
    • 空間複雜度 (Space Complexity): 變數空間使用量
  7. 優化寫法

開始寫的過程中通常會先用直觀暴力的方法來解決，像我這樣剛開始練習刷題的人可能寫完就謝天了，但以準備面試來說通常面試官會跟你討論時間或是空間運用上有沒有更好的解法。

通常那些解法如果常常去看解答的話是很快可以說出來跟應用，不過個人是覺得不用為了這個去當考試機器，反而可以透過跟面試官的討論去一起想出來更好的答案，畢竟未來當同事時也是要一起討論解決方案，以我四年前去群暉面試白板題的經驗來說，優化這個環節其實對方都不會刁難，會是以引導的方式一起把解答寫出來。

Leet Code 1864 範例解析

刷題的流程以 Leet Code 為例，1864 Minimum Number of Swaps to Make the Binary String Alternating 就會看到題目敘述如下:

Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible.

The string is called alternating if no two adjacent characters are equal. For example, the strings “010” and “1010” are alternating, while the string “0100” is not.

Any two characters may be swapped, even if they are not adjacent.

理解題目:

1864 這題，題目的意思是要我們計算最少的交換次數，讓一個字串可以變成 0 跟 1 交叉。如果是面試的情境，可以問看看對方是否題目都是確定一定能夠排成交叉的情況，如果 0 跟 1 的個數不剛好怎麼處理?

解決方式跟步驟:

  1. 計算 0 跟 1 的個數，看最終會是 0 開頭或是 1 開頭或是都可以
  2. 計算 10、01、00、11 的個數
  3. 統計 10、01 的交換次數
  4. 統計 00、11 的交換次數

驗證答案:

預設的測試案例通常比較少，所以考慮不周全的情況下就會錯誤，所以需要補上測試案例與預期結果。

案例次數
1110001
0100
1110-1
1001
00101111

底下就附上這題我的解答，寫的也不是特別好 XD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
var minSwaps = function (s) {
  let countMinSwaps = 0;

  function getStatics(chars) {
    // 分組
    let count0 = 0;
    let count1 = 0;
    let count10 = 0;
    let count01 = 0;
    let count00 = 0;
    let count11 = 0;
    let countSame = 0;

    for (let index = 1; index <= chars.length - 1; index += 2) {
      const nowPair = `${chars[index - 1]}${chars[index]}`;
      if (nowPair === "01") {
        count01 += 1;
        count0 += 1;
        count1 += 1;
      }

      if (nowPair === "10") {
        count10 += 1;
        count0 += 1;
        count1 += 1;
      }

      if (nowPair === "00") {
        count00 += 1;
        count0 += 2;
      }

      if (nowPair === "11") {
        count11 += 1;
        count1 += 2;
      }
    }

    // 奇數沒分組到的補上統計
    if (chars.length % 2 === 1) {
      if (chars[chars.length - 1] === "0") count0 += 1;
      if (chars[chars.length - 1] === "1") count1 += 1;
    }

    countSame = Math.max(count00, count11);

    if (chars.length < 4) {
      if (count0 === 2 || count1 === 2) {
        countMinSwaps = 1;
      }
    }

    return {
      count0,
      count1,
      count10,
      count01,
      countSame,
    };
  }

  const chars = s.split("");
  const { count0, count1, count10, count01, countSame } = getStatics(chars);

  if (
    count0 - count1 !== 0 &&
    count0 - count1 !== 1 &&
    count0 - count1 !== -1
  ) {
    countMinSwaps = -1;
  } else if (
    chars[0] === chars[chars.length - 1] ||
    (chars.length >= 4 && chars[0] !== chars[chars.length - 1])
  ) {
    if (count0 === count1) {
      countMinSwaps = Math.min(count10, count01) + countSame;
    } else if (count0 > count1) {
      countMinSwaps = count10 + countSame;
    } else {
      countMinSwaps = count01 + countSame;
    }
  }

  return countMinSwaps;
};

console.log(
  minSwaps(
    "11110100110010101011100100101011111101101001101100100011011100000010100101011011101100011111010101011011010011001010110111011001001110101100110100110001001010111001110101011001101110100100000100000101000101101001101011010000010000010011011001010101110001011001011001010110101001010111100100110100110000100101111000101001101101100001011011001100000010001101101000010100100011101110010111111"
  )
);
喜歡這篇文章，請幫忙拍拍手喔 🤣

站內搜尋
其他相關文章
最新的文章
share