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從相遇點(diǎn)出發(fā)，ptr從head出發(fā)，在入口處相遇
如圖所示（圖掛了）
141. 環(huán)形鏈表
我的思路
使用快慢指針渠鸽，相遇則有環(huán)
139. 單詞拆分
題解思路
1.使用unordered_set存儲(chǔ)dict（因?yàn)閟et有find功能）
2.遍歷字符串s.
3.遍歷j從 0到i - 1,看是否在dict里面有對(duì)應(yīng)的字符串.有,則dp[j] = true;
需要注意的是,必須是外循環(huán)遞增i,內(nèi)循環(huán)再遞增j < i,我本來(lái)打算i = 0, j > i,這樣的話需要從右往左遍歷(應(yīng)該).
128. 最長(zhǎng)連續(xù)序列
題解思路
1.將數(shù)組放到unordered_set里去重
2.遍歷數(shù)組,如果存在比當(dāng)前數(shù)大1的,計(jì)數(shù)+1,tmpnum++直到?jīng)]有為止
3.計(jì)算max
一個(gè)減少時(shí)間復(fù)雜度的小skill，如果存在比nums[i]小1的就continue了,因?yàn)樵谶B續(xù)序列的最小數(shù)那里已經(jīng)計(jì)算過(guò)了,比如說(shuō)[1,2,3,4].到2的時(shí)候,1那里已經(jīng)計(jì)算過(guò)整個(gè)len了,所以綜合起來(lái)時(shí)間復(fù)雜度為O(n)
- unordered_set的count的平均時(shí)間復(fù)雜度為O(1),最壞為O(n),可以去了解下為什么
https://en.cppreference.com/w/cpp/container/unordered_set/count
136. 只出現(xiàn)一次的數(shù)字
我的思路
使用異或
124. 二叉樹(shù)中的最大路徑和
題解思路
1.遞歸福扬，使用全局變量存儲(chǔ)max毅贮。
2.節(jié)點(diǎn)存儲(chǔ)到當(dāng)前節(jié)點(diǎn)的最大值昆咽，root.val + max(leftmax, rightmax)
3.max 為root.val + leftmax + rightmax,
121. 買(mǎi)賣(mài)股票的最佳時(shí)機(jī)
我的思路
- 使用迭代的minnum驾凶，maxprofit
我的思路2：動(dòng)態(tài)規(guī)劃
dp[i] 表示當(dāng)前最大利潤(rùn)璧眠，dp[i] = max(dp[i - 1], prices[i] - minnum);
我覺(jué)得反而復(fù)雜了
114. 二叉樹(shù)展開(kāi)為鏈表
題解思路
cur右側(cè)移到左側(cè)的最右側(cè)补疑，沒(méi)有左側(cè)的右側(cè)丢间，移到左側(cè)
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. 從前序與中序遍歷序列構(gòu)造二叉樹(shù)
我的思路
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;
}
注意細(xì)節(jié)，我在計(jì)算rightpreleft的時(shí)候使用len - 1 - preleft來(lái)計(jì)算了，忽略了right的長(zhǎng)度
104. 二叉樹(shù)的最大深度
我的思路
基礎(chǔ)遞歸
if (root == nullptr) return 0;
return max(maxDepth(root -> left), maxDepth(root -> right)) + 1;
102. 二叉樹(shù)的層序遍歷
我的思路
BFS
可以嘗試使用DFS<棧>實(shí)現(xiàn)
101. 對(duì)稱(chēng)二叉樹(shù)
我的思路
- 使用兩個(gè)dfs得到兩個(gè)vector秸应，因?yàn)榭者@個(gè)內(nèi)容無(wú)法用數(shù)字代替祸挪，所以把數(shù)字轉(zhuǎn)化為string類(lèi)型，空用其他符號(hào)表示
- 比對(duì)兩個(gè)vector
當(dāng)然最后沒(méi)有做票顾，因?yàn)槲矣X(jué)得有些問(wèn)題番刊。
題解思路1：遞歸
- 在一個(gè)dfs內(nèi)同時(shí)搜索左右兩邊熔吗，同時(shí)進(jìn)行，傳入左右兩個(gè)節(jié)點(diǎn)驱还。
題解思路2： 迭代
迭代用隊(duì)列來(lái)做.
98. 驗(yàn)證二叉搜索樹(shù)
我的思路
中序遍歷，使用vec存铝侵。我打算用pre 和cur來(lái)做的灼伤，結(jié)果都是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. 不同的二叉搜索樹(shù)
題解思路1
遞歸
for (int i = 1; i <= n; ++i) {
ans += numTrees(i - 1) * numTrees(n - i);
}
題解思路2
記憶化遞歸
把a(bǔ)ns存起來(lái)
題解思路3
1.n個(gè)數(shù)組成的不同二叉樹(shù),分解為以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];
}
94. 二叉樹(shù)的中序遍歷
我的思路
- 不會(huì)吧不會(huì)吧不會(huì)有人中序遍歷還不能bug-free吧（指我調(diào)了很久的命名）
85. 最大矩形
思路
84的拓展咪鲜，每一層加下來(lái)
84. 柱狀圖中最大的矩形
思路
單調(diào)棧
單調(diào)棧模板
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. 單詞搜索
思路
回溯
注意的點(diǎn)
1.在主方法中得到true就返回狐赡，算是剪枝
2.走過(guò)的路用別的符號(hào)表示，例如“0”疟丙，使用臨時(shí)變量存儲(chǔ)四個(gè)方向的返回值颖侄，在返回之前把原字符填回去
78. 子集
思路
- 特點(diǎn)
1.每一個(gè)節(jié)點(diǎn)均返回
2.滿足下一個(gè)節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)大.
""
1 2 3
2 3 3
思路2
無(wú)重復(fù)子集符合一下排列,假設(shè)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);
}
76. 最小覆蓋子串
思路
再寫(xiě)也寫(xiě)不出來(lái)
1.建一個(gè)哈希表存t的字母在窗口內(nèi)的出現(xiàn)次數(shù)鸟雏，通過(guò)動(dòng)態(tài)的窗口內(nèi)包含字符數(shù)目（n = t.size()）來(lái)維護(hù)窗口
2.開(kāi)滑
2.1 right滑到第一個(gè)完全囊括窗口的右邊
2.1.1 滑過(guò)的哈希字母值均減1，如果遇到t中的字母览祖，則n--;
2.2如果n為0了孝鹊，窗口到位了，開(kāi)始記錄最短長(zhǎng)度
2.2.1 滑左側(cè)的展蒂，滑一個(gè)加一個(gè)哈希值又活，如果加到一個(gè)t中的字母,n++,就又開(kāi)始滑右邊了.
75. 顏色分類(lèi)
我的思路
- 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的數(shù).全部為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這一行刪一個(gè)相當(dāng)于上一行增一個(gè),反推 - 改
dp[i - 1][j - 1] + 1
求min
70. 爬樓梯
我的思路
- 像斐波那契那樣迭代，遞歸超時(shí)
64. 最小路徑和
我的思路
grid[i][j] = grid[i][j] + min(grid[i - 1][j], grid[i][j - 1]);
62. 不同路徑
我的思路
- 從右下向左上,垓格子的路徑數(shù)量等于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時(shí)就只能走1步,max(nums[i], num[i - 1] - 1)如果還沒(méi)到最后一位就到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]能不能覆蓋最后一個(gè)下標(biāo)
需要注意的是柳骄，遍歷的右邊界是cover，能到達(dá)的最遠(yuǎn)的地方箕般。
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分類(lèi)
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就有資本暫時(shí)減去num為后面更大的sum做準(zhǔn)備
- 小于0不如等待下一個(gè)大于0的num
- 使用max取的每個(gè)階段的sum的最大值
if (sum > 0) {
sum += num;
}
else {
sum = num;
}
ans = max(ans, sum);
思路2 動(dòng)態(tài)規(guī)劃
-
dp[i - 1]表示到i - 1為止的最大連續(xù)子數(shù)組的和 - 那么在
i時(shí),如果dp[i - 1] < 0則dp[i] = nums[i]反之則dp[i] = dp[i - 1] + nums[i] - 因?yàn)橹挥星昂箨P(guān)系,所以可以?xún)?yōu)化成如下
dp = dp > 0 ? dp + nums[i] : nums[i];
ans = max(ans, dp);
49. 字母異位詞分組
我的思路
sort string 得到string vec鍵值對(duì)
unordered_map<string, vector<string> > m;
for (string& str : strs) {
string s = str;
sort(s.begin(), s.end());
m[s].push_back(str);
}
值得注意的地方↓
第三行代碼直接都進(jìn)行初始化了
unordered_map<string, vector<string> > m;
s = str;
m[s].push_back(str); //直接都進(jìn)行初始化了耐薯。
48. 旋轉(zhuǎn)圖像
我的思路
- 由外向內(nèi)層序處理
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
- 先右上-左下翻轉(zhuǎn)，再左右對(duì)稱(chēng)翻轉(zhuǎn)
46. 全排列
思路1
-
[1,2,3]的全排列是1+[2,3]的全排列 + (2+ [1,2]) + (3 + [1,2]) - 使用continue和find來(lái)跳過(guò)已經(jīng)使用過(guò)的數(shù)
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,但是時(shí)間很長(zhǎng)丝里，內(nèi)存很大曲初。
遇到的問(wèn)題
在引用的情況下使用sort函數(shù)導(dǎo)致答案出錯(cuò)。
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();
}
}
改進(jìn)思路
增加一個(gè)下標(biāo)變量杯聚，不往回加譬如[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. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
我的想法
二分查找械媒，一次找left一次找right
- 具體邊界條件列一列看一看奇數(shù)偶數(shù)目锭。
- 找左邊界的時(shí)候，=放在right那纷捞，right大膽移 left = mid+1小心移
1,8,8,8,8,8,8,8,8最后分析一下1,81,8,8的情況痢虹，發(fā)現(xiàn)沒(méi)有問(wèn)題 最后left == right - 找右邊界的時(shí)候, = 放在left那,left大膽移
1,8,8,8,8,8,8,8,9，分析一下主儡，發(fā)現(xiàn)陷入循環(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. 最長(zhǎng)有效括號(hào)
思路1
- 正向逆向結(jié)合
- 左向右移動(dòng)，篩出無(wú)效右括號(hào)
())()() - 右向左移動(dòng)糜值，篩出無(wú)效左括號(hào)
((((())()()
左向右有效括號(hào)長(zhǎng)度:
1.為左括號(hào)丰捷，lcnt++，為右括號(hào)寂汇，rcnt++病往；
2.lcnt == rcnt； left有效括號(hào) == cnt * 2骄瓣；
3.rcnt > lcnt rcnt = lcnt = 0;
右向左同理
取max
思路2
正常人沒(méi)法想出這種思路
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()) {//只有新的無(wú)匹配右括號(hào)出現(xiàn)才會(huì)有空的情況
st.push(i);
}
else {
maxlen = max(maxlen, i - st.top());
}
}
}
棧底是最后一個(gè)沒(méi)有被匹配的右括號(hào)的下標(biāo)
42. 接雨水
思路1
- 動(dòng)態(tài)規(guī)劃停巷，交叉區(qū)域
思路2
- 移動(dòng)最短邊
31. 下一個(gè)排列
思路：
三個(gè)步驟
1.找到從右往左的第一對(duì)降序pair
2.找到右側(cè)第一個(gè)比left大的數(shù)，swap
3.將left右側(cè)翻轉(zhuǎn)
