DEV Community: vc7

Day 3: Mull It Over | Advent of Code 2024 | Swift | 中文

vc7 — Tue, 03 Dec 2024 15:36:03 +0000

題目

https://adventofcode.com/2024/day/3

第一部分

今天的題目可以用正規表示式，根據提議可以分兩層

先找出 mul(數字,數字) ，而數字為 1~3 位數
- 正規表示式： mul\(\d{1,3},\d{1,3}\)
將找出來的字串，再吻合出兩個數字
- 正規表示式： \d{1,3}
把兩個數字相乘
把所有的乘積加總起來

func multiplications(string: String) -> Int {
    let basePattern = /mul\(\d{1,3},\d{1,3}\)/
    let numberPattern = /\d{1,3}/
    // 1. 找出 mul(數字,數字)
    let matches = string.matches(of: basePattern).map { String($0.output) }
    return matches
        .map {
            // 2., 3. 找出吻合的兩個數字並相乘
            $0.matches(of: numberPattern).compactMap{ Int($0.output) }.reduce(into: 1, *=)
        }
        // 4. 加總
        .reduce(into: 0, +=)
}

第二部分

第二部分加上一個變形，當遇到 don't() 的時候，接下來的 mul 不能被加總，當遇到 do() 的時候，接下來的 mul 就都能被加總。

找出所有的 do() don't() mul(數字,數字)
- 正規表示式： (do\(\)|don't\(\)|mul\(\d{1,3},\d{1,3}\))
走訪吻合的結果
- 設定一個可否加總的 flag 並預設為 true
- 遇到 do() 則為 true
- 遇到 don't() 則為 true
- 其他預設則都是 mul(數字,數字) ，當 flag 為 true 時，就像第一部分一樣相乘後加總

func modMultiplications(string: String) -> Int {
    let basePattern = /(do\(\)|don't\(\)|mul\(\d{1,3},\d{1,3}\))/
    let numberPattern = /\d{1,3}/

    let matches = string.matches(of: basePattern).map { $0.output.0 }

    var flag = true
    var result = 0

    for match in matches {
        if match == "do()" {
            flag = true
        } else if match == "don't()" {
            flag = false
        } else if flag {
            result += match.matches(of: /\d+/).compactMap { Int($0.output) }.reduce(into: 1, *=)
        }
    }

    return result
}

結語

如果有寫錯或有建議請留言讓我知道。如果有找到更好的解法，我會再多發一篇補充。

Day 2: Red-Nosed Reports | Advent of Code 2024 | Swift | 中文

vc7 — Mon, 02 Dec 2024 16:30:31 +0000

題目

https://adventofcode.com/2024/day/2

第一部分

題目會給像是這樣的數組。以每一行為單位，需要判斷這一行是不是「安全」。最後回傳「安全」的個數。

安全的條件

數組是單一方向的「遞增」或「遞減」
- 只要當其中一個數的增減方向和其他數字不同，就判定為不安全
兩元素的差必須介於 1 ~ 3 （包含 1, 3）之間

以題目的數組為例：

7 6 4 2 1 // 安　全 | 遞減 | 兩元素之差都在 1 到 3 之間
1 2 7 8 9 // 不安全 | 遞增 | 2 和 7 的差是 5
9 7 6 2 1 // 不安全 | 遞減 | 6 和 2 的差是 4
1 3 2 4 5 // 不安全 | 遞增 | 2 相對於 3 是減
8 6 4 4 1 // 不安全 | 遞減 | 4 和 4 的差是 0
1 3 6 7 9 // 安　全 | 遞增 | 兩元素之差都在 1 到 3 之間

判斷「安全」程式碼

func isSafe(row: [Int]) -> Bool {
    let isIncrease = row[1] > row[0]

    for index in 1..<row.count {
        let previous = row[index - 1]
        let current = row[index]
        let diff = current - previous
        if (isIncrease && (diff < 1 || diff > 3)) ||
           (!isIncrease && (diff > -1 || diff < -3)) {
            return false
        }
    }

    return true
}

主要程式碼

func safeReport(with puzzle: String) -> Int {
    // 1. 格式化資料源
    let puzzle = puzzle
        .components(separatedBy: "\n")
        .map { row in
            row
                .components(separatedBy: " ")
                .compactMap(Int.init)
        }

    // 2. 初始化計數用的變數
    var result = 0

    // 3. 走訪 puzzle 的每一行
    for row in puzzle {
        result += isSafe(row: row) ? 1 : 0
    }

    return result
}

複雜度分析

令所有數值數量為 n

時間複雜度： O(n)
空間複雜度： O(n)

第二部分

因為科學家發現依照原先的判斷方式安全率太低了，於是想出一個辦法：

如果可以只移除一個元素就可以變成「安全」的話，就視為是個安全的數組

解法

暴力解，如果一行數祖先被判定為「不安全」，就進行以下處理和判斷：

逐一移除一個元素
傳入 isSafe 判斷
只要在走訪過程中有發現只要有一個移除方式被視為安全，則提早結束，將 result 加上 1

程式碼

func alteredSafeReport(with puzzle: String) -> Int {
    let puzzle = puzzle
        .components(separatedBy: "\n")
        .map { row in
            row
                .components(separatedBy: " ")
                .compactMap(Int.init)
        }

    var result = 0

    for row in puzzle {
        if isSafe(row: row) {
            result += 1
        } else {
+           for index in 0..<row.count {
+               var localRow = row
+               localRow.remove(at: index)
+               if isSafe(row: localRow) {
+                   result += 1
+                   break
+               }
            }
        }
    }

    return result
}

複雜度分析

令所有數值為 n * m ，m 為最長 column 數。

時間複雜度： O(nxmxm)
- 在矯正不合格為合格的過程為 O(mxm)
空間複雜度： O(nxm)

結語

如果有寫錯或有建議請留言讓我知道。如果有找到更好的解法，我會再多發一篇補充。

Day 1: Historian Hysteria | Advent of Code 2024 | Swift | 中文

vc7 — Mon, 02 Dec 2024 03:10:52 +0000

引子

看了 Advent of Code 要開始的推文一直猶豫要不要跳進來；因為往年年末無論是自己上 Qiita 開坑，或是鐵人賽到最後不是失敗就是都很累。

不過因為最後東看西看，最近也有在做 LeetCode POTD ，雖然晚了一天還是決定來做了

題目

https://adventofcode.com/2024/day/1

題目形式

分成兩個部分

Part 1 - 算出星星之間的距離總和
Part 2 - 算出相似值

資料整形

藉由觀察，資料源以 \n 分行，並用 三個空格 分隔左右半邊

`puzzle` 的宣告方式

官方會根據不同的帳號提供不一樣的 puzzle ，這邊我直接複製貼到 Xcode 去執行。請自行替換自己的 puzzle 。

let puzzle = """
3   4
4   3
2   5
1   3
3   9
3   3
"""

程式碼

在這裡就把資料源通過 兩次分割 以及轉型整理成兩個整數陣列：

func grouping(with puzzle: String) -> (left: [Int], right: [Int]) {
    puzzle
        // 分行
        .components(separatedBy: "\n")
        .map {
            /// !!!: 為求文章表示簡潔，這裡不做 error handling
            /// 1) 分隔字串 -> 2) 轉型成整數
            $0.components(separatedBy: "   ").compactMap(Int.init)
        }
        .reduce(into: (left: [Int](), right: [Int]())) {
            $0.left.append($1[0])
            $0.right.append($1[1])
        }
}

為了可讀性，也可以另外宣告一個結構來替代 tupple 。

第一部分

前半一大段其實都在說故事，沒有解題的關鍵資訊（笑）

題意

數列分 左數列 和 右數列，題目要求個字排列之後，算出數值之間的總和 - 最小和最小的距離、第二小和第二小的距離，以此類推到最大和最大的距離。

當計算距離的相減後有可能會是負值，因此在加總前可以使用 abs 方法取絕對值作為距離。

程式碼

func totalDistance(with puzzle: String) -> Int {
    var (left, right) = grouping(with: puzzle)
    left.sort()
    right.sort()

    var sum = 0

    for index in 0..<left.count {
        sum += abs(right[index] - left[index])
    }

    return sum
}

執行

let puzzle = """
  ... 省略
"""

let result = totalDistance(with: puzzle)

result 及為結果

複雜度分析

時間複雜度 O(nlogn)
- O(nlogn + n) -> O(nlogn)
  - 排序 - O(nlogn)
  - 走訪 - O(n)
空間複雜度 O(n)
- 有建立 2 個陣列來存放，省略常數項後為 O(n)

第二部分

題意

計算相對於 左 半邊數列的相似度，算出每一行的 當前值 * 出現次數 後再加總。以官方的範例為例：

左半邊數列

3 => 右數列中出現 3 次 => 3 * 3 = 9
4 => 右數列中出現 1 次 => 4 * 1 = 4
2 => 右數列中出現 0 次 => 2 * 0 = 0
1 => 右數列中出現 0 次 => 1 * 0 = 0
3 => 右數列中出現 3 次 => 3 * 3 = 9
3 => 右數列中出現 3 次 => 3 * 3 = 9

總和：

9 + 4 + 0 + 0 + 9 + 9 = 31

資料結構與想法

首先，先用 hash map 來計數每個數字在右數列中的出現次數。

接著再走訪左數列，再邊用題目提供的算式把總和算出來。

程式碼

func similarity(with puzzle: String) -> Int {
    let (left, right) = grouping(with: puzzle)
    var map = [Int: Int]()

    for number in right {
        map[number, default: 0] += 1
    }

    var sum = 0

    for number in left {
        sum += number * map[number, default: 0]
    }

    return sum
}

或是加總的地方也可以用 reduce

func simularity(puzzle: String) -> Int {
    let (left, right) = grouping(with: puzzle)
    var map = [Int: Int]()

    for number in right {
        map[number, default: 0] += 1
    }

    // 改寫的部分
    return left.reduce(into: 0) {
        $0 += $1 * map[$1, default: 0]
    }
}

執行

let puzzle = """
  ... 省略
"""

let result = similarity(with: puzzle)

result 及為結果

複雜度分析

時間複雜度 O(n)
- 這個部分都只有線性走訪
空間複雜度 O(n)
- 左右數列： O(2n) -> O(n)
- 計數用的 hash map：最壞情形就是每個數值都不一樣 -> O(n)

結語

以上，希望能 Advent of Code 2024 能做完。

如果有寫錯或有建議請留言讓我知道。如果有找到更好的解法，我會再多發一篇補充。

387. First Unique Character in a String - Java 練習 - HashMap （中文解釋）

vc7 — Sun, 01 Dec 2024 13:08:10 +0000

題目

資料結構

Hash Map

思路

將字串逐字元走訪，並用 HashMap 計數
因為要取得「第一個」只有一個的字元，所以再將字串逐字元走訪一次，從計數用的 HashMap 取出次數。當遇到 1 的時候就回傳該字元。

程式碼

以 GhG 為主。

class Solution {
    // Function to find the first non-repeating character in a string.
    static char nonRepeatingChar(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();

        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for (char c : s.toCharArray()) {
            if (map.get(c) == 1) {
                return c;
            }
        }

        return '$';
    }
}

複雜度

令 n 為字串長度。

時間複雜度： O(n)
- 線性走訪兩次 - O(2n) -> O(n)
空間複雜度： O(n)
- 最壞的情形是建立 key 值為 n 個的 HashMap

242. Valid Anagram - Java 練習 - HashMap （中文解釋）

vc7 — Sat, 30 Nov 2024 06:46:22 +0000

題目

題意

Anagram 的意思是「相同字母異序詞」（維基）。

題目會提供兩個字串，需要判斷這兩個字串是不是 anagram 。

解法

這篇先用自己直觀想到的想法解。

想法

因為只需要考慮出現次數而不需要考慮次數，因此可以用 Hash Map 來記數。 Key 為字元， value 為次數。

流程

第一想法是，各自計算出各自的 hash map 再比較
先統計第一個字串的 hash map 再用第二個字串腳去第一個字串的. hash map
- 如果剩餘的 hash map 有非零，就代表兩個字串不一樣

程式碼

class Solution {
    // Function is to check whether two strings are anagram of each other or not.
    public static boolean areAnagrams(String s1, String s2) {
        Map<Character, Integer> map = new HashMap<>();

        for (Character x : s1.toCharArray()) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        for (Character x: s2.toCharArray()) {
            map.put(x, map.getOrDefault(x, 0) - 1);
        }

        for (Integer count: map.values()) {
            if (count != 0) { return false; }
        }

        return true;
    }
}

LeetCode in Swift - 2924. Find Champion II （中文解釋）

vc7 — Tue, 26 Nov 2024 14:07:36 +0000

題目

資料結構

Graph
Tree

題意

給一個數值 n ，代表有一系列從 0 到 n - 1 的隊伍。以及一個 edges 陣列代表各隊的強弱關係。

這個強弱關係是一個 DAG (Directed Acyclic Graph, 有向無環圖) ，意味著從任意點出發，無法透過任何邊回到該點。詳見維基百科。

也就是當隊伍 0 比 1 強時，比 1 還弱的隊伍只會比 0 ，不會比 0 強。

找出冠軍

當一個隊伍沒有任何隊伍比他強時，就可以視為冠軍。以圖學的角度來說，就是 尋找這個 DAG 的所有根節點 (root nodes) 。

回傳

當冠軍只有唯一的一隊時，回傳該隊，否則回傳 -1 。

Routine

知道題意和該解決什麼問題後，就來制定 routine 。

準備初始資料集

根據 n 建立一個 set ，預設所有隊伍都是冠軍。

Routine - 走訪 edges

因為條件是「沒有比較強的隊伍」就可以視為冠軍，所以每一次走訪時，只要在「弱隊」的那個位置就可以從 set 中剔除，

回傳

走訪完成後，當 set 中只有一個隊伍時，就可以回傳該隊伍。否則回傳 -1 ；完成處理。

程式碼

class Solution {
    func findChampion(_ n: Int, _ edges: [[Int]]) -> Int {
        // 1. 準備資料及，預設大家都是冠軍
        var champions = Set(0..<n)

        // 2. Routine - 移除輸家
        for edge in edges {
            champions.remove(edge[1])
        }

        // 3. 根據題目條件回傳結果
        return champions.count == 1 ? champions.removeFirst() : -1
    }
}

複雜度分析

如題目的限制，令邊數為 m

時間複雜度： O(n + m)
- 備註： Swift 中 Set 的 remove, removeFirst 的複雜度皆為 O(1) ，因為內部為類 dictionary 實作。
空間複雜度： O(n)
- 冠軍列表，長度為 n

結語

以上，如果有什麼回饋，歡迎在留言區跟我說，謝謝！

LeetCode in Swift - 773. Sliding Puzzle （中文解釋）

vc7 — Mon, 25 Nov 2024 16:57:30 +0000

題目

2024/11/25 的每日一題

資料結構

BFS / 廣度優先搜尋
Backtracking / 回溯法

題意

方法會傳入一個二維陣列，這裡就叫他數字板。我們必須要判斷這個二維陣列在多次移動後會不會成為以下的排列。可以的話，回傳移動的次數；否則回傳 -1

[[1, 2, 3],
 [4, 5, 0]]

想法

處理方式

根據題意得知

需要透過列舉出各種移動結果，來看哪個結果符合我們的預期。
- 對策：
  - 當需要 列舉所有可能性 ，就可以使用 backtracking / 回溯法。
  - 根據探索的方式，發現可以用廣度優先搜尋為基底，根據接下來的需求進行變形
由於只有空白 (0) 的地方可以被移動進去，因此每一次移動都是以 0 的位置為基準
- 在每一次的走訪後需要紀錄 0 新的位置
根據題意，必須回傳「移動過幾次」
- 因此當每一次生成新的數字板時，必須記錄當下的深度
- 一次深度代表一次的移動
由於移動過程中 board 的排列會重複，因此當遇到重複的時候需要跳過
- 需要有個 visited Set 來紀錄已經走訪過的 board 排列

資料結構整形

因為二維陣列不容易進行存取和更新，考慮到易讀性，在開始處理前可以降一個維度成為一維陣列，進行 swapping 時的寫法會比較簡潔。

[[1, 2, 3], -> [1, 2, 3, 4, 0, 5]
 [4, 0, 5]]

let board = board.reduce(into: [Int]()) { $0.append(contentsOf: $1 )}

探索路線

在 backtracking 列舉的過程中，我們必須要根據能和當下 0 交換的位置生成新的數字板。

二維陣列對照到一維陣列的 indices

 [0][1][2]     [0][1][2][3][4][5] 
-----------    ------------------
[[1, 2, 3], -> [1, 2, 3, 4, 0, 5]
 [4, 0, 5]]
-----------
 [3][4][5]

路線表 / 對照表

0 的位置	能交換的位置	二維陣列中的相對位置
`[0]`	`1`, `3`	右、下
`[1]`	`0`, `2`, `4`	左、右、下
`[2]`	`1`, `5`	左、下
`[3]`	`0`, `4`	上、右
`[4]`	`1`, `3`, `5`	上、左、右
`[5]`	`2`, `4`	上、左

為了易讀性的資料結構

根據以上的說明可以知道每一次的走訪需要三個資訊

0 的位置
數字板的樣子
當前深度或移動次數

為了易讀性，與其使用大於等於 3 個元素的 tuple ，我宣告了一個結構：

struct Item {
    /// 0 的位置
    let index: Int
    /// 數字板的樣子
    let board: [Int]
    /// 當前深度或移動次數
    let depth: Int
}

Routine

在文章一開始有提到會使用 BFS 為基礎演算法解題，因此會有一個主要的 queue 來暫存每一層列舉的結果。

準備

Queue - 儲存列舉的結果。用來進行 BFS 走訪的主資料結構。
Visited - 儲存已經走訪過的數字板排列。

走訪過程

取出 queue ("dequeue") 中第一個物件來處理。

提前結束條件

當前物件的 board 為預期結果時，回傳當前的深度（移動次數）。

列舉

根據當前的 index 從「路線表」找出對應的新位置。
根據所有新位置生成新的數字板
- 當新的數字板有在 visited 出現過，跳過不處理
- 沒出現過的話
  - 把新的 0 的位置、數字板樣式、加 1 後的深度組合起來存入 queue
  - 把新的數字板樣式存入 visited

走訪完成 - Queue 為空

當這個 queue 為空時，代表沒有沒有達成「提前結束條件」，也就意味著傳入的二維陣列無論如何移動都無法達成 [1, 2, 3, 4, 5, 0] ，因此回傳 -1 。

程式碼

接下來就可以根據以上的說明和 routine 來寫成程式碼了：

class Solution {
    /// 路線圖。因為這是靜態不需要改變，因此可以宣告為 member property 。
    private let routes = [
        [1, 3],
        [0, 2, 4],
        [1, 5],
        [0, 4],
        [1, 3, 5],
        [2, 4]
    ]
    /// 預期結果。因為這是靜態不需要改變，因此可以宣告為 member property 。
    private let target = [1, 2, 3, 4, 5, 0]

    /// LeetCode 的進入點
    func slidingPuzzle(_ board: [[Int]]) -> Int {

        // MARK: - 1. 初始處理

        /// 把二維陣列降為一維陣列，作為初始數字板
        let board = board.reduce(into: [Int]()) { $0.append(contentsOf: $1 )}
        /// 取得初始數字板 0 的所在位置
        /// 根據題目限制這邊理應不會失敗，若失敗了視為無法達成題目要求回傳 -1 。
        guard let index = board.firstIndex(of: 0) else { return -1 }

        // MARK: - 2. BFS 的準備

        var queue = [Item(index: index, board: board, depth: 0)]
        var visited: Set<[Int]> = [board]

        // MARK: - 3. Routine

        while !queue.isEmpty {
            let item = queue.removeFirst()
            guard item.board != target else { return item.depth }

            // 根據新位置列舉
            for next in routes[item.index] {
                var board = item.board
                board[next] = item.board[item.index]
                board[item.index] = item.board[next]

                // 只處理未出現過的數字板
                if !visited.contains(board) {
                    queue.append(Item(index: next, board: board, depth: item.depth + 1))
                    visited.insert(board)
                }
            }
        }

        // MARK: - 4. End of Routine

        return -1
    }

    // MARK: Data Type

    struct Item {
        let index: Int
        let board: [Int]
        let depth: Int
    }
}

結語

這題難是難在拆解題意，和怎麼把題意套進 BFS 來解。因為需要講解清楚的環節很多，所以花了很多時間想該怎麼寫會比較好。

以上，如果有什麼回饋，歡迎在留言區跟我說，謝謝！

LeetCode in Swift - 1975. Maximum Matrix Sum （中文解釋）

vc7 — Sun, 24 Nov 2024 08:53:07 +0000

題目

2024/11/24 的每日一題

資料結構與演算法

矩陣
貪婪
數學

題意

可以挑任意兩個數字都乘以 -1 ，已達到整個矩陣所有元素的和為最大值

意味著

負數能變正數，正數能為負數
Greedy - 可以先加總所有元素值的絕對值作為總和
- 當負數為 偶數 個時，透過無限次數的 -1 轉換，能夠都轉為正數，這時候就可以直接回傳
- 當負數為 奇數 個時，一定會有一個負數會落單，這時候我們會希望落單的負數是最大，換言之是絕對值最 小 的負數。因為當絕對值越大，越能貢獻總和成為更大的數。
  - 接著回傳的總和必須扣掉這個數兩次，一次是 扣掉絕對值 ，一次是 加上負數值
挑負數值
- 當負數值只剩下一個的時後，必須要考慮像是這樣的 case ，當最小正數比負數的絕對值還要小
  - 最小正數 1, 負數 -3
  - 因為負數變成絕對值後能貢獻的值比較大，這時候就可以呼應 1. 把最小正數轉換乘負數 -1 ，令其成為「落單的負數」。

Routine

解析完題意後，就可以來制定 routine 該做什麼事。這題的 routine 就只有一件事情： 走訪矩陣的每個元素 。

走訪矩陣

走訪矩陣需要先準備這幾個變數：

總和
最小絕對值
負數的個數

走訪過程

把元素的絕對值加到 總和
為了「落單的負數」比較和更新 最小絕對值
當前元素為負值時，進行 負數的個數 += 1

後處理

當負數個數為偶數 → 回傳 總和 不做其他運算
當負數個數為奇數 → 把多加了的 最小絕對值 從 總和 扣掉一次後，再加上負值的 最小絕對值。

程式碼

class Solution {
    func maxMatrixSum(_ matrix: [[Int]]) -> Int {
        var sum = 0
        var minimum = Int.max
        var negativeCount = 0

        for row in matrix {
            for column in row {
                sum += abs(column)
                minimum = min(minimum, abs(column))

                if column < 0 {
                    negativeCount += 1
                }
            }
        }

        guard negativeCount % 2 != 0 else {
            return sum
        }

        // sum - absolute min + the negative min
        return sum - minimum - minimum
    }
}

複雜度分析

依題目，陣列大小為 n x n

時間複雜度： O(nxn) 或 O(n^2)
- 線性走訪矩陣，元素個數為 n x n
空間複雜度： O(1)
- 雖然宣告了三個變數為 O(3) ，但是表示時可寫成 O(1)

結語

以上，如果有什麼回饋，歡迎在留言區跟我說，謝謝！

LeetCode in Swift - 1072. Flip Columns For Maximum Number of Equal Rows

vc7 — Sat, 23 Nov 2024 10:02:43 +0000

Problem

Data Structure

Hash map

Approach and the Routine

Base on the problem and the examples, a flip means, if there is a 0 will become 1 and if there is a 0 will become 1.

Normalize the rows

Because we only have to find the maximum number of all 0s and all 1s rows after a certain flipping of columns, which means we have to find the most appeared pattern.

01 -> 11 (Satisfied)
10 -> 00 (Satisfied)

For example, after one flip of the column [0], we can get 2 rows are satisfied, so we can considering they are the same pattern.

01 -> 01
10 -> 01 (Normalized)

To Count the appearance

We can use hash map to do the work, pattern as the key and count as the value.

// Routine 1st
01 -> [0, 1] -> [[0, 1]: 1]
10

// Routine 2st
01 
10 -> [0, 1] -> [[0, 1]: 2]

Code

class Solution {
    func maxEqualRowsAfterFlips(_ matrix: [[Int]]) -> Int {
        // [pattern: count]
        var map = [[Int]: Int]()

        for row in matrix {
            let base = row[0]
            let pattern = row.map { $0 == base ? 0 : 1 }
            map[pattern, default: 0] += 1
        }

        return map.values.max() ?? 0
    }
}

End of the post

That's it!

Please leave comment if you have any comments, thanks for your reading!

LeetCode in Swift - 1957. Delete Characters to Make Fancy String

vc7 — Thu, 21 Nov 2024 14:56:50 +0000

Problem

Idea and the routine

Create a result string for use through the routine.

Go through and count the appearance of characters
- If current character is NOT as same as the previous character
  - Reset count to 1
  - Append to the result string
- If count is 1 and current character is as same as the previous character
  - Count += 1
  - Append to the result string
- If appearance is >= 2
  - Do anything. Since the count is reaching the limit, so it's no meaning to add 1 to it when there is no additional purpose or requirement.

Code

class Solution {
    func makeFancyString(_ s: String) -> String {
        var string = ""
        /// Init with 0 as a placeholder
        var previous: Character = "0"
        var count = 0

        for c in s {
            if c != previous {
                previous = c
                count = 1
                string.append(c)
            } else if count < 2 {
                string.append(c)
                count += 1
            }
        }
        return string
    }
}

Complexity

n as length of the given string s

Time Complexity: O(n)
- Linear traversal
Space Complexity: O(n)
- Copying to a new string as the same length at the worst case.

In place and two flags

Next time.

Runtime Note

I tried to use var characters: [Character] and return String(result), in the end I using string directly because as result this way is faster as LeetCode perspective.

End of the post

That's it!

Please leave comment if you have any comments, thanks for your reading!

LeetCode in Swift - 66. Plus One

vc7 — Wed, 20 Nov 2024 15:03:50 +0000

Problem

https://leetcode.com/problems/plus-one
https://leetcode.cn/problems/plus-one （中文）

Data Structure

Array

Intuition

Travel through from the last item.

Routine

If number is less than 9, plus 1 then return the digits
- The last digit (1st step):
  - Initial plus 1
- Other digits:
  - Carry from the digit on the right (index + 1)
- Early exist: No need to carry to the next digit, can early exist.
If number is >= 9 means needed to carry
- Set to 0
- Continue

End of routine

When go through every digits without return, means we have a carry from the highest digit, so that we have to insert a 1 to the digits[0]

Code

class Solution {
    func plusOne(_ digits: [Int]) -> [Int] {
        var index = digits.count - 1
        var digits = digits

        while index >= 0 {
            if digits[index] < 9 {
                digits[index] += 1
                return digits
            }
            digits[index] = 0
            index -= 1
        }

        digits.insert(1, at: 0)
        return digits
    }
}

Complexity

Time Complexity: O(n)
- Linear travel of the array.
Space Complexity: O(n)
- * Need to copy an array for mutable purpose. If not consider this can be O(1)

End of post

That's it!

Please leave comment if you have any comments, thanks for your reading!

LeetCode in Swift - 21. Merge Two Sorted Lists

vc7 — Tue, 19 Nov 2024 14:10:12 +0000

Problem

Data Structure

Linked List

Intuition

Create a dummy node to hold the result linked list, then compare the values of the two linked lists' heads, put the smaller one to the tail of the result linked list. Then move the head of the linked list to the next node.

Code

class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {

        var list1 = list1
        var list2 = list2

        // 1. Prepare the nodes for as the result linked list
        var result: ListNode? = ListNode()
        var tail: ListNode? = result

        // 2. Routine
        while let one = list1?.val,
              let two = list2?.val {
            if one < two {
                tail?.next = list1
                list1 = list1?.next
            } else {
                tail?.next = list2
                list2 = list2?.next
            }
            tail = tail?.next
        }

        // 3. Process the remaining
        tail?.next = list1 ?? list2

        return result?.next
    }
}

Routine

Time to stop

When any of list1 or list2 is already nil, means only both are not nil then started the routine.

while let one = list1?.val, let two = list2?.val

Process

Set the smaller node to the tail

Process the remaining

When exist the while loop, there will be two cases

list1 or list2 is nil
list1 and list2 are nil

So that here we can utilize optional chain to let Swift to do the job.

tail?.next = list1 ?? list2

Returns

return result?.next

Complexity

Time Complexity - O(m + n)
- m is length of list1, n is length of list2
Space Complexity - O(1)

End of post

That's it!

Please leave comment if you have any comments, thanks for your reading!

DEV Community: vc7

Day 3: Mull It Over | Advent of Code 2024 | Swift | 中文

題目

第一部分

第二部分

結語

Day 2: Red-Nosed Reports | Advent of Code 2024 | Swift | 中文

題目

第一部分

安全的條件

判斷「安全」程式碼

主要程式碼

複雜度分析

第二部分

解法

程式碼

複雜度分析

結語

Day 1: Historian Hysteria | Advent of Code 2024 | Swift | 中文

引子

題目

題目形式

資料整形

puzzle 的宣告方式

程式碼

第一部分

題意

程式碼

執行

複雜度分析

第二部分

題意

資料結構與想法

程式碼

執行

複雜度分析

結語

387. First Unique Character in a String - Java 練習 - HashMap （中文解釋）

題目

資料結構

思路

程式碼

複雜度

242. Valid Anagram - Java 練習 - HashMap （中文解釋）

題目

題意

解法

想法

流程

程式碼

LeetCode in Swift - 2924. Find Champion II （中文解釋）

題目

資料結構

題意

找出冠軍

回傳

Routine

準備初始資料集

Routine - 走訪 edges

回傳

程式碼

複雜度分析

結語

LeetCode in Swift - 773. Sliding Puzzle （中文解釋）

題目

資料結構

題意

想法

處理方式

資料結構整形

探索路線

二維陣列對照到一維陣列的 indices

路線表 / 對照表

為了易讀性的資料結構

Routine

準備

走訪過程

提前結束條件

列舉

走訪完成 - Queue 為空

`puzzle` 的宣告方式