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的场景（题目隐含约束）