?

lc701.二叉搜索樹插入

void dfs不行

TreeNode* dfs，帶接受參數處理的dfs

當為空的時候，就可以添加插入

if (!root)

? ? ? ? ?{

? ? ? ? ? ? return new TreeNode(val);

? ? ? ? }

插入位置

root->left = insertIntoBST(root->left, val);

class Solution {

public:

? ? TreeNode* insertIntoBST(TreeNode* root, int val)?

? ? {

? ? ? ? // 若根節點為空，直接創建新節點作為根

? ? ? ? if (!root)

? ? ? ? ?{

? ? ? ? ? ? return new TreeNode(val);

? ? ? ? }

? ? ? ??

? ? ? ? // 根據值的大小決定插入左子樹還是右子樹

? ? ? ? if (val < root->val)?

? ? ? ? {

? ? ? ? ? ? root->left = insertIntoBST(root->left, val);

? ? ? ? }?

? ? ? ? else?

? ? ? ? {

? ? ? ? ? ? root->right = insertIntoBST(root->right, val);

? ? ? ? }

? ? ? ? return root;

? ? }

};

聯想：

有序合并兩個鏈表

l1->next=merge(l1->next,l2);

return l1;

?

lc61.鏈表分割點

class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head || !head->next)
return head;

int n=0;
ListNode* tmp=head;
while(tmp)
{
n++;
tmp=tmp->next;
}

k=k%n;
if(k==0) return head;

ListNode* cy=head;
int flag=n-k;
int cnt=0;
ListNode* a;
ListNode* b;
while(head)
{
cnt++;

if(cnt==flag)
{
a=head;
b=head->next;
break;
}

head=head->next;
}

a->next=nullptr;
ListNode* newhead=b;

while(b->next)
{
b=b->next;
}
b->next=cy;

return newhead;
}
};

?

?

迭代器

對比于for循環

for循環一般是以特定順序循環，迭代器是以特定遍歷規則去訪問集合中每個元素，不嚴謹地來說，可以認為for的概念范圍比迭代器小，參考 迭代器模式 ?

不能用for循環遍歷一個 紅黑樹 ?或hash鏈表之類，迭代器是對所有可遍歷數據結構的抽象和封裝。

---

map

在C++中，?std::map?是有序集合，其內部通過紅黑樹實現，會按照鍵（key）的升序自動排序。

獲取?std::map?最后一個元素的方法：

- 使用?rbegin()?函數，它返回指向最后一個元素的反向迭代器，例如：?auto last = map.rbegin();?
- 通過?*last?可訪問該元素（鍵值對），通過?last->first?獲取鍵，?last->second?獲取值。

?

lc82.鏈表刪重

引入flag

return前處理：

newhead->next=nullptr; //截斷尾部可能的殘留

class Solution {
public:
ListNode* deleteDuplicates(ListNode* head)
{
if(!head || !head->next)
return head;

ListNode* newhead=new ListNode(0);
ListNode* ret=newhead;
int flag=-1000;

while(head)
{
if(head->next && head->val==head->next->val)
flag=head->val;

if(head->val!=flag)
{
newhead->next=head;
newhead=newhead->next;
}

head=head->next;
}


newhead->next=nullptr; //截斷尾部可能的殘留
return ret->next;
}
};

?

---

lc190 位運算

?class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t result = 0;
for (int i = 0; i < 32; ++i)
result = (result << 1) + (n >> i & 1);
return result;
}
};

lc2044.子集按位或

計算最大按位或的子集數量

class Solution {
public:
int countMaxOrSubsets(vector<int>& nums) {
int max_or = 0;
int count = 0;
int n = nums.size();

// 遍歷所有子集（共2^n個）
for (int mask = 1; mask < (1 << n); ++mask) {
int current_or = 0;
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
current_or |= nums[i];
}
}

// 更新最大或值和計數
if (current_or > max_or)

? ? ? ? ? {
max_or = current_or;
count = 1;
}

? ? ? ? ? ?else if (current_or == max_or)

? ? ? ? ? ?{
count++;
}
}
return count;
}
};


主要修改說明：

1.聚焦子集按位或計算
2.?使用位運算遍歷所有非空子集（掩碼?mask?從1開始，避免空集）
3.?計算每個子集的按位或值，追蹤最大值并統計出現次數
4.?時間復雜度O(n·2?)，適用于n≤20的場景（題目隱含約束）

?