国产精品视频区,日韩人妻一区

142. 環(huán)形鏈表 II

我的思路

①fast = l + ak + x
②slow = l + bk + x
③fast = 2 * slow
2l + 2bk + 2x = l + ak + x ==> l = (a - 2b)k - x
所以：slow從相遇點出發(fā)，ptr從head出發(fā)，在入口處相遇
如圖所示（圖掛了）

139. 單詞拆分

題解思路

1.使用unordered_set存儲dict（因為set有find功能）
2.遍歷字符串s.
3.遍歷j從 0到i - 1,看是否在dict里面有對應的字符串.有,則dp[j] = true;

需要注意的是,必須是外循環(huán)遞增i,內循環(huán)再遞增j < i,我本來打算i = 0, j > i,這樣的話需要從右往左遍歷(應該).

128. 最長連續(xù)序列

題解思路

1.將數組放到unordered_set里去重
2.遍歷數組,如果存在比當前數大1的,計數+1,tmpnum++直到沒有為止
3.計算max
一個減少時間復雜度的小skill，如果存在比nums[i]小1的就continue了,因為在連續(xù)序列的最小數那里已經計算過了,比如說[1,2,3,4].到2的時候,1那里已經計算過整個len了,所以綜合起來時間復雜度為O(n)

unordered_set的count的平均時間復雜度為O(1),最壞為O(n),可以去了解下為什么
https://en.cppreference.com/w/cpp/container/unordered_set/count

使用異或

124. 二叉樹中的最大路徑和

題解思路

1.遞歸，使用全局變量存儲max。
2.節(jié)點存儲到當前節(jié)點的最大值，root.val + max(leftmax, rightmax)
3.max 為root.val + leftmax + rightmax,

121. 買賣股票的最佳時機

我的思路

使用迭代的minnum，maxprofit

我的思路2：動態(tài)規(guī)劃

dp[i] 表示當前最大利潤，dp[i] = max(dp[i - 1], prices[i] - minnum);
我覺得反而復雜了

114. 二叉樹展開為鏈表

題解思路

cur右側移到左側的最右側，沒有左側的右側，移到左側

while (cur != nullptr) {
     if (cur -> left != nullptr) {
          TreeNode* pre = cur -> left;
          while(pre -> right != nullptr) {
              pre = pre -> right;
          }
          pre -> right = cur -> right;
          cur -> right = cur -> left;
          cur -> left = nullptr;
     }
     cur = cur -> right;
}

105. 從前序與中序遍歷序列構造二叉樹

我的思路

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int inleft, int preleft, int len) {
        TreeNode* root;
        if (len <= 0) {
            return nullptr;
        }
        if (len > 0) {
            root = new TreeNode(preorder[preleft]);
        }

        int index = inleft;
        for (; index < len + index; ++index) {
            if (preorder[preleft] == inorder[index]) {
                break;
            }
        }
        root -> left = buildTree(preorder, inorder, inleft, preleft + 1, index - inleft);
        root -> right = buildTree(preorder, inorder, index + 1, preleft + index - inleft + 1, len - 1 - index + inleft);
        return root;
    }

注意細節(jié)，我在計算rightpreleft的時候使用len - 1 - preleft來計算了，忽略了right的長度

104. 二叉樹的最大深度

我的思路

基礎遞歸

if (root == nullptr)      return 0;
return max(maxDepth(root -> left), maxDepth(root -> right)) + 1;

101. 對稱二叉樹

我的思路

使用兩個dfs得到兩個vector，因為空這個內容無法用數字代替，所以把數字轉化為string類型，空用其他符號表示
比對兩個vector
當然最后沒有做，因為我覺得有些問題。

題解思路1：遞歸

在一個dfs內同時搜索左右兩邊，同時進行，傳入左右兩個節(jié)點。

題解思路2：迭代

迭代用隊列來做.

98. 驗證二叉搜索樹

我的思路

中序遍歷，使用vec存。我打算用pre 和cur來做的，結果都是bug,改了一下，改好了
改前

if (root == nullptr) {
            return;
}
if (root -> val <= pre) {
    flag = false;
}
inorder(root -> left);
pre = root -> val;
inorder(root -> right);

改后

if (root == nullptr) {
            return;
}
inorder(root -> left);
if (root -> val <= pre) {
    flag = false;
}
pre = root -> val;
inorder(root -> right);

96. 不同的二叉搜索樹

題解思路1

遞歸

for (int i = 1; i <= n; ++i) {
    ans += numTrees(i - 1) * numTrees(n - i);
}

題解思路2

記憶化遞歸
把ans存起來

題解思路3

1.n個數組成的不同二叉樹,分解為以1為root,左空右n - 1/以2為root 左1右n - 2/..,這樣n種方式;
2.以i為root的方式有 [i - 1] * [n - i]種

i from 1 to n
j == 0  ==> 左 ans[0] * 右 ans[n]
j == 1 ==> 左 ans[1] * 右 ans[n - 1]
左[j - 1] 右 [n - j]

for (int i = 2; i <= n; ++i) {
    for (int j = 1; j <= i; j++)
        ans[i] += ans[j - 1] * ans[i - j];
    }

84. 柱狀圖中最大的矩形

思路

單調棧

單調棧模板

for (int i = 0; i< nums.size(); ++i) {
    while (!st.empty() && nums[st.top()] > nums[i]) {
        st.pop();
    }
    st.push(i);
}

需要注意的地方

1.[1,2,3,4,5]
在末尾添0
2.[2,1,2]
在頭添0

cur = st.top();
st.pop();
left = st.top() + 1;

79. 單詞搜索

思路

回溯

注意的點

1.在主方法中得到true就返回，算是剪枝
2.走過的路用別的符號表示，例如“0”，使用臨時變量存儲四個方向的返回值，在返回之前把原字符填回去

78. 子集

思路

特點
1.每一個節(jié)點均返回
2.滿足下一個節(jié)點比當前節(jié)點大.

""
1      2      3
2 3    3

思路2

無重復子集符合一下排列,假設n = 3
000 001 010 100 101 110 111

int n = 1 << nums.size();
        for (int i = 0; i < n; ++i) {
            tmp.clear();
            int j = 0;
            while (j < nums.size()) {
                if (i & (1 << j)) {
                    tmp.push_back(nums[j]);
                }
                j++;
            }
            ans.push_back(tmp);
        }

再寫也寫不出來
1.建一個哈希表存t的字母在窗口內的出現次數，通過動態(tài)的窗口內包含字符數目（n = t.size()）來維護窗口
2.開滑
2.1 right滑到第一個完全囊括窗口的右邊
2.1.1 滑過的哈希字母值均減1，如果遇到t中的字母，則n--;
2.2如果n為0了，窗口到位了，開始記錄最短長度
2.2.1 滑左側的，滑一個加一個哈希值，如果加到一個t中的字母,n++,就又開始滑右邊了.

75. 顏色分類

我的思路

sort

思路1

使用left right 和index

while (index <= right) {
    // cout << nums[index] << endl;
    if (nums[index] == 0) {
        if (index != left) {   1  0  2  index ==> [1] left ==>[0]
            swap(nums[index], nums[left]);
        }
        else {
            index++;
        }
        left++;

    }
    else if (nums[index] == 2){
        swap(nums[index], nums[right]);    2  0  1 index ==> [0]  right ==> [2]
        right--;
    }
    else {
        index++;
    }
}

思路2

記錄0,1的數.全部為2,替換為1,替換為0

int num = nums[i];
nums[i] = 2;
if (num < 2) {
    nums[n1] = 1;
    n1++;
}
if (num == 0) {
    nums[n0] = 0;
    n0++;
}

72. 編輯距離

思路

dp[i][j]為word1.substr(0, i) 到word2.substr(0,j)的距離
增 dp[i][j - 1] + 1
刪 dp[i - 1][j] + 1 這一行刪一個相當于上一行增一個,反推
改 dp[i - 1][j - 1] + 1
求min

70. 爬樓梯

我的思路

像斐波那契那樣迭代，遞歸超時

64. 最小路徑和

我的思路

grid[i][j] = grid[i][j] + min(grid[i - 1][j], grid[i][j - 1]);

62. 不同路徑

我的思路

從右下向左上,垓格子的路徑數量等于right + down

56. 合并區(qū)間

我的思路

sort
cur[left][right] = [0][1]
while : right > [i + 1][1] ==> right = max(right, [i + 1][1]) 向右延展right

55. 跳躍游戲

我的思路

例如nums[0] == 2那么到i = 1時就只能走1步,max(nums[i], num[i - 1] - 1)如果還沒到最后一位就到0.，就到不了了

for (int i = 1; i < nums.size() - 1; ++i) {
    nums[i] = max(nums[i - 1] - 1, nums[i]);
    if (nums[i] == 0) {
        return false;
    }
}
return true;

題解思路

看i + nums[i]能不能覆蓋最后一個下標
需要注意的是，遍歷的右邊界是cover，能到達的最遠的地方。

int cover = 0;
for (int i = 0; i <= cover; ++i) {
     cover = max(cover, i + nums[i]);
     if (cover >= nums.size() - 1) return true;
}

53. 最大子序和

我的思路

~~我是傻逼~~

按nums[i] > 0 或< 0分類

for (int i = 1; i < nums.size(); ++i) {
// cout << "cur " << cur << " maxnum " << maxnum << endl;
if (nums[i] > 0) {
    if (maxnum < 0) {
        cur = nums[i];
        maxnum = cur;
    }
    else {
        cur = max(cur + nums[i], nums[i]);
        maxnum = max(maxnum, cur);
    }
}
else {
    if (cur + nums[i] > 0) {
        cur += nums[i];
    }
    else {
        cur = nums[i];
        maxnum = max(maxnum, cur);
    }
}
}

思路1

按sum分.

我大于0就有資本暫時減去num為后面更大的sum做準備
小于0不如等待下一個大于0的num
使用max取的每個階段的sum的最大值

if (sum > 0) {
    sum += num;
}
else {
    sum = num;
}
ans = max(ans, sum);

思路2 動態(tài)規(guī)劃

dp[i - 1] 表示到i - 1為止的最大連續(xù)子數組的和
那么在i時,如果dp[i - 1] < 0 則 dp[i] = nums[i]反之則dp[i] = dp[i - 1] + nums[i]
因為只有前后關系,所以可以優(yōu)化成如下

dp = dp > 0 ? dp + nums[i] : nums[i];
ans = max(ans, dp);

49. 字母異位詞分組

我的思路

sort string 得到string vec鍵值對

unordered_map<string, vector<string> > m;
for (string& str : strs) {
    string s = str;
    sort(s.begin(), s.end());
    m[s].push_back(str);
}

值得注意的地方↓
第三行代碼直接都進行初始化了

unordered_map<string, vector<string> > m;
s = str;
m[s].push_back(str); //直接都進行初始化了。

48. 旋轉圖像

我的思路

由外向內層序處理

matrix[layer][layer + index] = matrix[layer + slen - index][layer];
matrix[layer + slen - index][layer] = matrix[layer + slen][layer + slen - index];
matrix[layer + slen][layer + slen - index] = matrix[layer + index][layer + slen];
matrix[layer + index][layer + slen] = tmp;

思路2

先右上-左下翻轉，再左右對稱翻轉

46. 全排列

思路1

[1,2,3]的全排列是1+[2,3]的全排列 + (2+ [1,2]) + (3 + [1,2])
使用continue和find來跳過已經使用過的數

        for (int i = 0; i < nums.size(); ++i) {
            auto it = find(tmp.begin(), tmp.end(), nums[i]);
            if (it != tmp.end()) continue;
            tmp.push_back(nums[i]);
            dfs(nums);
            tmp.pop_back();
        }

思路2

https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
交換法

void dfs(vector<int>& nums, int index) {
    if (index == nums.size()) {
        ans.push_back(nums);
        return;
    }
    for (int i = index; i < nums.size(); ++i) {
        swap(nums[index], nums[i]);
        dfs(nums, index + 1);
        swap(nums[index], nums[i]);
}

39. 組合總和

我的思路

使用dfs,但是時間很長，內存很大。

遇到的問題
在引用的情況下使用sort函數導致答案出錯。

void dfs(vector<int>& tmp, vector<int>& candidates, int target) {
    if (target == 0) {
        sortans.push_back(tmp);
        return;
    }
    if (target < 0) {
        return;
    }
    for (int i = 0; i < candidates.size(); i++) {
        tmp.push_back(candidates[i]);
        dfs(tmp, candidates, target - candidates[i]);
        tmp.pop_back();
    }
}

改進思路

增加一個下標變量，不往回加譬如[2,3,5] ,3分支就不加2了。也減少了去重操作，速度快了很多

    void dfs(vector<int>& tmp, vector<int>& candidates, int target, int startIndex) {
        if (target == 0) {
            ans.push_back(tmp);
            return;
        }
        if (target < 0) {
            return;
        }
        for (int i = startIndex; i < candidates.size(); i++) {
            tmp.push_back(candidates[i]);
            dfs(tmp, candidates, target - candidates[i], i);
            tmp.pop_back();
        }
    }

34. 在排序數組中查找元素的第一個和最后一個位置

我的想法

二分查找，一次找left一次找right

具體邊界條件列一列看一看奇數偶數。
找左邊界的時候，=放在right那，right大膽移 left = mid+1小心移 1,8,8,8,8,8,8,8,8 最后分析一下1,8 1,8,8的情況，發(fā)現沒有問題最后left == right
找右邊界的時候, = 放在left那,left大膽移1,8,8,8,8,8,8,8,9，分析一下，發(fā)現陷入循環(huán)，我們讓mid靠右

while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
    left = mid + 1;
}
else if (nums[mid] >= target) {
    right = mid;
  }
}

32. 最長有效括號

思路1

正向逆向結合
左向右移動，篩出無效右括號())()()
右向左移動，篩出無效左括號((((())()()

左向右有效括號長度:
1.為左括號，lcnt++，為右括號，rcnt++；
2.lcnt == rcnt； left有效括號 == cnt * 2；
3.rcnt > lcnt rcnt = lcnt = 0;
右向左同理
取max

思路2

正常人沒法想出這種思路

stack<int> st;
st.push(-1);
int len = s.size();
int maxlen = 0;
int cntr = 0, cntl = 0;
for (int i = 0; i < len; ++i) {
    if (s[i] == '(') {
        st.push(i);
    }
    else {
        st.pop();
        if (st.empty()) {//只有新的無匹配右括號出現才會有空的情況
            st.push(i);
        }
        else {
            maxlen = max(maxlen, i - st.top());
        }
    }
}

棧底是最后一個沒有被匹配的右括號的下標

42. 接雨水

思路1

動態(tài)規(guī)劃，交叉區(qū)域

思路2

移動最短邊

31. 下一個排列

思路：

三個步驟
1.找到從右往左的第一對降序pair
2.找到右側第一個比left大的數，swap
3.將left右側翻轉

TOP100

我的思路

我的思路

題解思路

題解思路

我的思路

使用異或

題解思路

我的思路

我的思路2：動態(tài)規(guī)劃

題解思路

我的思路

我的思路

我的思路

我的思路

題解思路1：遞歸

題解思路2： 迭代

我的思路

題解思路1

題解思路2

題解思路3

我的思路

思路

思路

需要注意的地方

思路

注意的點

思路

思路2

思路

我的思路

思路1

思路2

思路

我的思路

我的思路

我的思路

我的思路

我的思路

題解思路

我的思路

思路1

思路2 動態(tài)規(guī)劃

我的思路

我的思路

思路2

思路1

思路2

我的思路

改進思路

我的想法

思路1

思路2

思路1

思路2

思路：

相關閱讀更多精彩內容

友情鏈接更多精彩內容

題解思路2：迭代