構造矩陣
class Solution {
private:
? ? vector<int> empty = {};
? ? // 返回每個數字(-1)所在的序號，可以是行或列, 如果為空則無效
? ? vector<int> topoSort(int k, vector<vector<int>>& conditions)
? ? {
? ? ? ? // 構建一個圖: 范圍1-k，這里故意留一個0空著，后續計算無需額外-1
? ? ? ? vector<vector<int>> g(k+1);
? ? ? ? // 入度: 范圍1-k，這里故意留一個0空著，后續計算無需額外-1
? ? ? ? // vector<int> inDegrees(k+1);
? ? ? ? int inDegrees[k+1];
? ? ? ? memset(inDegrees, 0, sizeof(inDegrees));
? ? ? ? for (vector<int>& condition : conditions)
? ? ? ? {
? ? ? ? ? ? g[condition[0]].push_back(condition[1]);
? ? ? ? ? ? ++inDegrees[condition[1]];
? ? ? ? }
? ? ? ? // 拓撲排序使用隊列
? ? ? ? queue<int> q;
? ? ? ? // 插入入度為0的節點
? ? ? ? for (int i = 1; i <= k; ++i)
? ? ? ? {
? ? ? ? ? ? if (inDegrees[i] == 0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? q.push(i);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 計算找到接點的序號：即優先級順序
? ? ? ? int seq = 0;
? ? ? ? // 返回結果
? ? ? ? vector<int> res(k);
? ? ? ? while (q.size() > 0)
? ? ? ? {
? ? ? ? ? ? int curr = q.front();
? ? ? ? ? ? q.pop();
? ? ? ? ? ? res[curr-1] = seq++;
? ? ? ? ? ? for (int next : g[curr])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (--inDegrees[next] == 0)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? q.push(next);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 找不到則返回空
? ? ? ? return seq == k ? res : empty;
? ? }
public:
? ? vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
? ? ? ? vector<int> rows = topoSort(k, rowConditions);
? ? ? ? vector<int> cols = topoSort(k, colConditions);
? ? ? ? // 一旦發現有空的情況（即無法滿足條件），就可以直接返回空
? ? ? ? if (rows.size() == 0 || cols.size() == 0)
? ? ? ? {
? ? ? ? ? ? return {};
? ? ? ? }
? ? ? ? vector<vector<int>> res(k, vector<int>(k));
? ? ? ? for (int i = 0; i < k; ++i)
? ? ? ? {
? ? ? ? ? ? // 這里需要額外+1，因為編號是 0~k-1
? ? ? ? ? ? res[rows[i]][cols[i]] = i+1;
? ? ? ? }
? ? ? ? return res;
? ? ?}
};
?
雙指針?找規律
要改變的最小次數就等于中值，可以通過兩端做差再除以2得到最小的變化次數，
然后迭代下去即可，具體實參看代碼，時間復雜度O(n)
代碼：
class Solution {
public:
? ? int minOperations(int n) {
? ? ? ? int start = 0;
? ? ? ? int end = n-1;
? ? ? ? int res = 0;
? ? ? ? while(start<end){? ? ?//len長奇偶都無關
? ? ? ? ? ? res+=((end*2-1)-(start*2-1))/2;
? ? ? ? ? ? start++;
? ? ? ? ? ? end--;
? ? ? ? }
? ? ? ? return res;
? ? }
};
算法
1. 計算機編程語言是人類和計算機交流的語言工具。
2. 計算機的本質是狀態機，內存里存儲的所有數據構成了當前的狀態；
3. 數據結構相當于告訴計算機怎么來記錄當前的狀態，算法相當于告訴計算機怎么根據當前的狀態計算出下一個狀態。
4. 空間復雜度就是你需要的必需存儲的狀態最多有多少；
5. 時間復雜度就是從初始狀態到達最終狀態中間需要多少步，這個和算法強相關，是算法關注的事情；
6. 程序在計算過程中，將問題層層分解之后，會有大量的中間過程數據，這個本質上就是記錄問題的中間狀態；中間過程數據就是由你設計的數據結 構來承載。
cpp性能優化
?單線程下, 智能指針作為參數傳遞的時候沒有使用引用 ?每次都拷貝構造 造成了額外的 性能開銷 。
只要是個類型變量都可以傳參，例如share_ptr
?
錯誤貪心 lc3458
class Solution {
public:
? ? bool maxSubstringLength(string s, int k) {
? ? ? ? unordered_map<char,int> hash;
? ? ? ? for(auto c:s)
? ? ? ? ? ? hash[c]++;
? ? ? ? int cnt=0;
? ? ? ? for(auto& [a,b]:hash)
? ? ? ? {
? ? ? ? ? ? if(b==1) cnt++;
? ? ? ? }
? ? ? ? if(cnt>=k) return true;
? ? ? ? else return false;
? ? }
};
?
正確貪心：
class Solution {
public:
? ? bool maxSubstringLength(string s, int K) {
? ? ? ? int n = s.size();
? ? ? ? vector<int> pos[26];
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? int c = s[i] - 'a';
? ? ? ? ? ? pos[c].push_back(i);
? ? ? ? }
? ? ? ? typedef pair<int, int> pii;
? ? ? ? vector<pii> vec;
? ? ? ? // 枚舉每一種子串
? ? ? ? for (int i = 0; i < 26; i++) if (!pos[i].empty()) {
? ? ? ? ? ? // 一開始先用這種字母的范圍作為子串的范圍
? ? ? ? ? ? int l = pos[i][0], r = pos[i].back();
? ? ? ? ? ? bool flag = true;
? ? ? ? ? ? while (flag) {
? ? ? ? ? ? ? ? flag = false;
? ? ? ? ? ? ? ? // 檢查子串里是否出現了其它字母
? ? ? ? ? ? ? ? for (int j = 0; j < 26; j++) {
? ? ? ? ? ? ? ? ? ? int cnt = upper_bound(pos[j].begin(), pos[j].end(), r) - lower_bound(pos[j].begin(), pos[j].end(), l);
? ? ? ? ? ? ? ? ? ? if (cnt > 0 && cnt < pos[j].size()) {
? ? ? ? ? ? ? ? ? ? ? ? // 有一種字母沒有被完全包含，用它的范圍更新子串的范圍
? ? ? ? ? ? ? ? ? ? ? ? l = min(l, pos[j][0]);
? ? ? ? ? ? ? ? ? ? ? ? r = max(r, pos[j].back());
? ? ? ? ? ? ? ? ? ? ? ? flag = true;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? // 得到了這種子串里的最短子串
? ? ? ? ? ? if (l > 0 || r < n - 1) vec.push_back({r, l});
? ? ? ? }
? ? ? ? // leetcode 435. 無重疊區間
? ? ? ? sort(vec.begin(), vec.end());
? ? ? ? int R = -1, cnt = 0;
? ? ? ? for (pii p : vec) if (p.second > R) {
? ? ? ? ? ? R = p.first;
? ? ? ? ? ? cnt++;
? ? ? ? }
? ? ? ? return cnt >= K;
? ? }
};
?
