Try   HackMD

Leetcode Notes

34. Find First and Last Position of Element in Sorted Array

  • 難度：medium
  • 題意：給一遞增陣列，再給一數字，找出該數字們所在陣列中的開始與結束位置
  • 範例：
    • Input: [5, 7, 7, 8, 8, 10], target = 8
    • Output: [3, 4]
    • Input: [5, 7, 7, 8, 8, 10], target = 6
    • Output: [-1, -1]
      • Input: [], target = 8
    • Output: [-1, -1]
  • 限制：
    • 演算法要求 O(log n)
    • 陣列長度 0 ~
      105
  • 想法：
    • 因為題目要求 O(log n)，大概只剩 Binary search 可行
    • Tree search methods 因為還要建樹 O(n)，時間也會超過
  • 程式碼



















vector<int> searchRange(vector<int>& nums, int target)
{
    int f = BinarySearch(nums, target);
    return (f >= nums.size() || nums[f] != target) ? vector<int>(2, -1) : vector<int>{f, BinarySearch(nums, target+1)-1};
}

int BinarySearch(vector<int>& nums, int target)
{
    int min = 0;
    int max = nums.size();

    while ( min < max )
    {
        int middle = ( max + min ) / 2;
        (nums[middle] < target) ? min = middle + 1 : max = middle;
    }

    return max;
}
  • 分析:
    • 2 次的 binary search
      • Time: c * log n –> 2 * log n –> O(log n)
  • 解釋:
    • 利用第一次 binary search 找 target 的開頭
    • 利用開頭判斷條件是否符合 (數字是否存在 或 為空陣列)
    • 符合後，再進入 binary search 找 target + 1 的開頭
    • 此時 target + 1 的開頭 -1 就會是 target 的結尾
  • NOTE:
    • 一般的 binary search 不一定找得到最左邊的 target
    • 因此要在條件上處理
      • if (arr[middle] < target) { min = middle + 1 }
      • else { max = middle }
    • 意思就是每次找到的 target，只縮右邊一半，保證 開頭 一定會被 [min, max] 包住
    • 同理，演算法也可以改成 找結尾的 binary search

53. Maximum Subarray

  • 難度：medium
  • 題意：給一串陣列，找出一連續子陣列，其和最大
  • 範例：
    • Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    • Output: 6
    • Explanation: [4, -1, 2, 1]
  • 限制：
    • 數字
      −104       ~
      104
    • 陣列長度 1 ~
      105
  • 想法：
    • 子陣列什麼時候到達最大值
      • 當新增的數字加進來使得總和變小
      • [4, -1, 2, -1] + [-5] –> smaller
    • 如何確保子陣列增長 –> Dynamic programming
      • 每次都把加到前一個數，其最大的值存起來，確保下次新增的數字使用前一次加到的最大值
      • 舉例
        • 加到 index 0 –> 子陣列 == [-2] 最大值 == -2
        • 加到 index 1 –> 子陣列 == [-2, 1] 最大值 == 1
          • 解釋: (-2 + 1) < 1，代表子陣列的頭從 1 開始往後加 比 從 -2 開始還來的大，因此可以捨去 -2
        • 加到 index 2 –> 子陣列 == [1, -3] 最大值 == -2
        • 加到 index 3 –> 子陣列 == [1, -3, 4] 最大值 == 4
          • 解釋: (1 + -3 + 4) < 4，代表子陣列的頭從 4 開始往後加 比 從 1 + -3 開始還來的大，因此可以捨去 1, -3
        • 加到 index 4 –> 子陣列 == [4, -1] 最大值 == 3
        • 加到 index 5 –> 子陣列 == [4, -1, 2] 最大值 == 5
        • 加到 index 6 –> 子陣列 == [4, -1, 2, 1] 最大值 == 6
        • 加到 index 7 –> 子陣列 == [4, -1, 2, 1, -5] 最大值 == -1
        • 加到 index 8 –> 子陣列 == [4, -1 ,2, 1, -5, 4] 最大值 == 3
  • 程式碼














int maxSubArray(vector<int>& nums)
{
    int size = nums.size();
    int max = nums[0];

    for (int i = 1; i < size; i++)
    {
        int temp = nums[i-1] + nums[i];
        nums[i] = temp > nums[i] ? temp : nums[i];
        max = nums[i] > max ? nums[i] : max;
    }

    return max;
}
  • 分析:
    • time O(n) –> for loop 1 to n
    • space O(1) –> constant space
  • 目前沒有想到其他解法，我有看到別人使用 Kadane's algorithm，他的概念是
    • 假設最大子陣列 [a, y, b]
    • 則陣列 [a, y, b, x] 之最大子陣列，必為包含或不包含 [a, y, b] 之陣列，即 不可能發生 [y, b, x] > [a, y, b, x]

69. Sqrt(x)

  • 難度：easy
  • 題意：給一數，求其平方根; 若有小數捨去至整數位
  • 範例：
    • Input: 8
    • Output: 2
    • Explanation: 2.82842
  • 限制：
    • 不能使用內建函數 pow, sqrt
    • n: 1 ~
      231−1       (2147483647)
  • 想法：
  • 程式碼




























// for 一個一個慢慢找
int mySqrt(int x)
{
    for (int i = 1; i <= (x / 2) + 1; i++)
    {
        if (x / i == i) return i;
        if (x / i < i) return i - 1;
    }
    return 0;
}

// Binary search
int mySqrt(int x)
{
    if(x == 0) return 0;
    int left = 1, right = x;
    while(left <= right)
    {
        int mid = left + (right - left) / 2;
        if(mid == x / mid)
            return mid;
        else if(mid > x / mid)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return right;
}

70. Climbing Stairs

  • 難度：easy
  • 題意：給 n 階樓梯，一次走一步或兩步，問幾種方法恰好走完樓梯
  • 範例：
    • Input: 3
    • Output: 3
    • Explanation: 1 + 1 + 1 OR 1 + 2 OR 2 + 1
  • 限制：
    • n: 1 ~ 45
  • 想法：
    • 費氏數列 遞迴 (x) –> 儘量不用
    • 公式解
    • 建表法
  • 程式碼



















// 建表法
int climbStairs(int n)
{
    uint stairs[50] = {0, 1, 2};
    for(int i = 3; i < 50; i++)
    {
        stairs[i] = stairs[i-1] + stairs[i-2];
    }
    return stairs[n];
}

// 公式解 
int climbStairs(int n)
{
    double coeff = sqrt(5.0);
    double left = pow((1 + coeff) / 2, n + 1);
    double right = pow((1 - coeff) / 2, n + 1);
    return (int)((double)(left - right) / coeff);
}
  • 公式解可以考慮背一下

74. Search a 2D Matrix

  • 難度：medium
  • 題意：給一二維陣列，確認當中是否存某數，要求 algorithm O(log mn)
  • 範例：
    • Input: [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
    • Output: true
  • 限制：
    • 陣列大小: m 列 n 行
    • m, n: 1 ~ 100
    • matrix[i][j], target:
      −104       ~
      104
  • 想法：
    • 暴力解，肯定行不通，不考慮
    • Binary Search
  • 程式碼



























// Binary Search
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
    int m = matrix.size();
    int n = matrix[0].size();
    return binary_search(matrix, 0, m*n-1, target);
}

bool binary_search(vector<vector<int>>& matrix, int start, int end, int target)
{
    if (start > end)
        return false;

    int n = matrix[0].size();
    int middle = (start + end) / 2;

    int i = middle / n;
    int j = middle % n;

    if (matrix[i][j] > target)
        return binary_search(matrix, start, middle-1, target);
    else if (matrix[i][j] < target)
        return binary_search(matrix, middle+1, end, target);
    else
        return true;
    return false;
}
  • 基本上就把 matrix 攤平做 binary search 而已，沒什麼
  • 搜尋過其他人解答，大部分都是 binary search，大同小異

1346. Check if N and its double exist

  • 難度：easy
  • 題意：給一陣列，確認當中是否存在二數，其一數為另一數的兩倍
  • 範例：
    • Input: [10, 2, 5, 3]
    • Output: true
    • Explanation: arr[0] = arr[2] * 2
  • 限制：
    • 陣列長度: 2 ~ 500
    • arr[i]:
      −103       ~
      103
  • 想法：
    • 暴力解，此題並無限制時間複雜度，且出現 worst case 的機率並不高(猜測)
    • Binary Search，可善用 algorithm library
    • Hash table (STL)
  • 程式碼
























































// 暴力解
bool checkIfExist(vector<int>& arr)
{
    for (int i = 0; i < arr.size(); i++)
    {
        for (int j = 0; j < arr.size(); j++)
        {
            if (i != j && (arr[i] == 2 * arr[j] || arr[j] == 2 * arr[i]))
            {
                return true;
            }
        }
    }
    return false;
}

// Binary Search
bool checkIfExist(vector<int>& arr)
{
    sort(arr.begin() , arr.end());
    int countZero = 0;
    for(int i = 0; i < arr.size(); i++)
    {
        if(arr[i] == 0) countZero++;
        if(binary_search(arr.begin(), arr.end(), 2*arr[i]))
        {
            if(arr[i] == 0 and countZero > 1) return true;
            if(arr[i] != 0) return true;
        } 
    }
    return false;
}

// Hash table
bool checkIfExist(vector<int>& arr)
{
    map<int, int> hash;
    for (int i = 0; i < arr.size(); i++)
        hash[arr[i]]++;
    
    for (int i = 0; i < arr.size(); i++)
    {
        if (arr[i] == 0)
        {
            if (hash[0] > 1) return true;
        }
        else
        {
            if (arr[i] % 2 == 0 && hash.count(arr[i] / 2))
                return true;
            if (hash.count(arr[i] + arr[i]))
                return true;
        }
    }
    return false;
}

其中，0 至少要出現兩次，才算存在其倍數，因此可以把 0 當 special case 處理

  • 解釋 Hash table
    • 第一個 for 先將，所有數字存進 map 中，相當於建一棵樹 O(n)
    • 第二個 for 把每個數字遍歷，一一確認自己是否為 map 中某數的兩倍，或 map 存在其兩倍的數
    • 因為 map.count 為 O(log n)，因此相當於 binary search

141. Linked List Cycle

  1. 找 singly linked list 中是否存在 cycle
  2. 快慢指標？ two pointers
    • 如果有 cycle，fast 會在 loop 中遇到 slow，how ?
    • Floyd
      Assume time: T
      Distance of Fast pointer:
      m+nx+k=2T
      Distance of slow pointer:
      m+ny+k=T
      ⇒m+nx+k=2(m+ny+k)
      ⇒n(x−2y)=m+k
      帶回 T 等式中
      ⇒T=ny+n(x−2y)=n(x−y)
      ⇒       slow pointer 走完 (x - y) 個 cycle 後會遇到 fast pointer
      ⇒       在
      O(x−y)==O(n)       的時間內，可停止循環
    • 停止條件
      • fast 碰到 slow
      • fast 走到最底
    • edge cases
      • head == NULL
      • length == 1
    • analysis
      • time: 如上
        O(n)
      • space: 只要 handle 兩個指標
        O(1)
  3. 使用 hash table 記錄所有節點，看是否出現兩次
    • 用 C++ STL 較方便，以資料結構為單位，不要用 value 當作 key，因為有可能 value 會重複但沒有 cycle
    • 最多 loop
      n+1       次即可確定是否含 cycle
    • 實作 hash table，collision 策略？
      • closed addressing / chaining
        • 允許 table 大小(m) 比資料筆數少，代價就是要 handle 額外空間(array / linked list) 來儲存 collision data
        • best time:
          O(1)
        • worst time:
          O(n)
        • space:
          O(m+n)
      • open addressing
        • 簡單來說，就是找方法 1 to 1 mapping 進 table
        • probing(linear / quadratic)
        • double hashing
        • space:
          O(n)

C++ STL
std::map internally is a Red-Black tree.
std::unordered_map is a Hash Table.
Find times are O(log N) vs O(1) respectively.

142. Linked List Cycle II

  1. 記得考慮 Initial Condition for no node or no cycle
  2. 方法參考 141，取
    n(x−2y)=m+k
    • m+k       是 cycle 的倍數，又 k 與 一部份的 n 重疊，即
      m=ni−k
    • ⇒       也就是
      m→−k       的中點即是 cycle 的起點（該點被兩個 next 所指到）
      • −k         指從 cycle 起點反方向到相遇點的距離（經過
        i         圈）
    • time:
      O(n)
    • space:
      O(1)
  3. 用 set 紀錄 visit 過的 node
    • 如果找到重複的值，該值便是 cycle 起點
    • time:
      O(n)
    • space:
      O(n)

83. Remove Duplicates from Sorted List

Last changed by 
 
paulpeng
假裝我會寫程式
0
277

Read more

筆記

Both apt and apt-get are command line tools. You can use them to manage software packages like applications and libraries on Debian-based Linux servers and server instances. Since Linux is open source, you have several package options to customize it for your requirements. The apt command line tool provides a higher-level user interface for end users with intuitive commands, resulting behaviors, and security features. In contrast, the command apt-get is a low-level interface that communicates more closely with core Linux processes. The apt command is a more user-friendly package manager than apt-get.

Jan 25, 2025
Assignment3: Single-cycle RISC-V CPU

contributed by &lt; paulpeng-popo &gt;

Dec 2, 2023
Assignment2: RISC-V Toolchain

contributed by ???

Oct 31, 2023
Assignment1: RISC-V Assembly and Instruction Pipeline

contributed by &lt; terry23304 &gt;

Oct 10, 2023
Read more from paulpeng
Published on HackMD