7.28 进制交换|迭代器模式|map|子集按位或|带参递归
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的场景（题目隐含约束）