changed 2 years ago  
Published Linked with GitHub

Leetcode刷題學習筆記 – Backtracking

Introduction

131. Palindrome Partitioning
給你一個string找出所有可能的切割方法，讓切割出來的substring都是palindrome。例如: s = "aab"，則返回[["a","a","b"],["aa","b"]]

  • backtracking 可以視為queue裡面有每個可能的答案，
  • 最後條件滿足就把答案存起來，
  • pop掉最後一個，繼續從這個狀態尋找下一個可能
  • 從上面的答案可以知道，一開始我的candidate可能是"a"或是"aa"
  • 所以必須設計一個演算法可以找出candidate的可能性。

列舉所有的結果，利用recursive來拆解問題。













backtrace() {
    if(滿足條件) {
        儲存結果;
        離開;
    }
    
    for(列舉所有可能) {
        儲存新的可能;
        backtrace();
        撤銷新的可能;
    }
}

131. Palindrome Partitioning(Medium)

給你一個string，回傳所有可以切割出來的回文組合。

  1. 一個一個判斷字串是否為palindrome，如果是繼續判斷剩下的substring。
  2. 當全部字串都判斷完了，就儲存結果。
  3. 退掉前一個成功的結果，繼續往下處理。



































bool isPalindrome(string s) {
    auto n = s.length();
    if(n == 0) return true;
    else if(n == 1) return true;
    else {
        for(int i = 0; i < n / 2; ++i) {
            if(s[i] != s[n - i - 1])
                return false;
        }
        return true;
    }
}
    
void helper(vector<vector<string>>& rtn, vector<string>& tmp, string s) {
    if(s.length() == 0)
        rtn.push_back(tmp);
    // 每次增加一個char判斷是否為palindrome
    for(int i = 1; i <= s.length(); ++i) {
        // 如果是，則剩下的substring繼續判斷。
        // 如果不是，則增加string的長度。
        if(isPalindrome(s.substr(0, i))) {
            tmp.push_back(s.substr(0, i));
            helper(rtn, tmp, s.substr(i));
            tmp.pop_back();
        }
    }
}

vector<vector<string>> partition(string s) {
    vector<vector<string>> rtn;
    vector<string> tmp;
    helper(rtn, tmp, s);
        
    return rtn;
}

79. Word Search(Medium)

給你一個vector<vector<char>>> board，找出board中有沒有string word。

  1. 如果word.length() == 1，只要搜尋board中有沒有char和他一樣的。
  2. 如果word.length() == 2，則找到(1)之後，還要繼續往四個方向尋找。必且必須符合, 1)沒有出界，2)沒有訪問過，3)字元一樣
  3. 符合(2)則繼續往下找，直到idx == word.length()全部找完為止。


































class Solution {
    int n, m;
    vector<vector<int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    bool inRange(int y, int x) {
        return (x < 0 || y < 0 || y >= n || x >= m) ? false : true; 
    }
    bool search(vector<vector<char>>& board, string word, int idx, int y, int x, vector<vector<bool>>& v) {
        if(idx == word.length()) return true;
        if(!inRange(y, x) || v[y][x] || board[y][x] != word[idx]) return false;
        else {
            v[y][x] = true;
            bool res{false};
            for(auto& dir : dirs)
                // 四個方向的board[y][x]是否和word[idx + 1]一樣？
                res |= search(board, word, idx + 1, y + dir[0], x + dir[1], v);
            v[y][x] = false;
            return res;
        }
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size();
        m = board[0].size();
        vector<vector<bool>> v(n, vector<bool>(m));
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                // board[i][j]和word[0]是否一樣
                if(search(board, word, 0, i, j, v))
                   return true;
            }
        }
        return false;
    }
};

47. Permutations II

給你一個vector<int> nums其中的數字有可能會重複，回傳所有不重複的排列。

參考leetcode給的解答

47

  1. 因為數字有重複，所以先對數字做統計。
  2. 以前的backtracking都是對vector，現在改對map。
class Solution {
    void helper(unordered_map<int, int>& m, vector<int>& cur, vector<vector<int>>& rtn, int sz) {
        if(cur.size() == sz) {
            rtn.push_back(cur);
            return;
        }
        for(auto& item : m) {
            if(item.second == 0) continue;
            cur.push_back(item.first);
            item.second--;
            helper(m, cur, rtn, sz);
            item.second++;
            cur.pop_back();
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int sz = nums.size();
        unordered_map<int, int> m; // value, cnt
        for(auto& n : nums) m[n]++;
        vector<vector<int>> rtn;
        vector<int> cur;
        helper(m, cur, rtn, sz);
        return rtn;
    }
};

1066. Campus Bikes II

在2D平面上(XY座標)，有vector<vector<int>> workers和vector<vector<int>> bikes。每個worker必須分配一台bike，試找出最少的Manhattan distances的分配法。其中\(Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|\)

  1. 一開始覺得要用Greedy，但是怎樣寫都有錯誤。
  2. 最簡單的方法就是暴力解，每台bike(M)都有可能分配給worker(N)，所以有\(M^N\)的解法。
  3. 這邊的暴力解就是使用backtracking，因為固定worker的順序，只要針對bike做排列即可。如下面的解法。
  4. 固定一個變數，就是worker會依序分配，然後遍歷剩下bike的所有可能性。
  5. 其中使用一個int來表示分配過的bike，因為題目給定bike最多只有10台。





















class Solution {
    int minans{INT_MAX};
    int dist(vector<int>& w, vector<int>& b) {
        return abs(w[0] - b[0]) + abs(w[1] - b[1]);
    }
    void dfs(vector<vector<int>>& w, vector<vector<int>>& b, int u, int idx, int cur) {
        if(idx == w.size()) {
            minans = min(minans, cur);
            return;
        }
        for(int i = 0; i < b.size(); ++i) {
            if((u & (1 << i)) == 0)
                dfs(w, b, u | 1 << i, idx + 1, cur + dist(w[idx], b[i]));
        }
    }
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        dfs(workers, bikes, 0, 0, 0);
        return minans;
    }
};
  1. 但是這種解法的time complexity不是很好，因為會有很多重複計算的過程。
  2. 因為當mask一樣的時候，表示剩下的bikes是一樣的。workers是依序取的，所以表示剩下的worker也是一樣的。
    例如:mask = 0011，表示index = 0, 1的腳踏車已經被取走
    works = 0–>1, 或是 1–>0 順序不重要，剩下works = 2, 3
    所以答案一樣，不用重新計算。
  3. 所以我們可以用mask當成index來查詢是否有重複計算。
  4. 這題可以當成是一個模板，所有用暴力解來分配的題目都可以這樣解。





















class Solution {
    int dist(vector<int>& w, vector<int>& b) {
        return abs(w[0] - b[0]) + abs(w[1] - b[1]);
    }
    int dfs(vector<vector<int>>& w, vector<vector<int>>& b, int mask, int idx) {
        if(idx == w.size()) return 0;
        if(~mem[mask]) return mem[mask];
        int minans{INT_MAX};
        for(int i = 0; i < b.size(); ++i) {
            if(!(mask & (1 << i)))
                minans = min(minans, dfs(w, b, mask | 1 << i, idx + 1) + dist(w[idx], b[i]));
        }
        return mem[mask] = minans;
    }
    vector<int> mem;
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        mem.resize(pow(2, bikes.size()), -1);
        return dfs(workers, bikes, 0, 0);
    }
};
tags: leetcode 刷題
Select a repo