溢出模式
- 有符号整数溢出是未定义行为，可能导致负数或错误结果
long long M = 9223372036854775807;
cout << M + 1;
//最大值 + 1 (通常变成最小值): -9223372036854775808
long long m=-9223372036854775808;
cout << m - 1;
//最小值 - 1 (通常变成最大值): 9223372036854775807
- 无符号整数溢出是定义良好的模运算
unsigned int M = 4294967295;
cout << M + 1;
//最大值 + 1 (模运算后): 0
unsigned int m=0;
cout << m-1;
//0 - 1 (模运算后): 4294967295
-
有符号整形溢出通常编译器有警告，而unsigned溢出通常无警告
-
有符号整形溢出后比较无意义，而unsigned溢出后比较仍有效
-
这就是为什么在很多需要处理大编号的图论/树问题中，更倾向于使用 unsigned
例题
求二叉树最大 “ 宽度 ”
leetcode 662
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。
将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
思路：
- 看成完全二叉树，给每个结点编号(根节点编号1)
- 左儿子编号=父亲 * 2
- 右儿子编号=父亲 * 2 + 1
- bfs 层序遍历 ：当前层宽度 = 最右侧编号 - 最左侧编号 + 1
- 不断更新答案即可
层数可以达到上千2^1000,所以我一开始直接无脑Bigint, 极其抽象
后来发现unsigned long long 居然过了？又试了一下unsigned int,也过了……
我们计算 最右侧编号 - 最左侧编号 + 1时只需要它们的相对大小，而宽度不会超过int
即使溢出，由于取模机制，相对大小不变
class Solution {
public:int widthOfBinaryTree(TreeNode* root) {unsigned int ans=0;if(root==nullptr)return ans;queue<pair<TreeNode*,unsigned int>>qu;qu.push(pair(root,1));while(qu.size()){int m;//最左编号int siz=qu.size();for(int i=1;i<=siz;i++){auto cur=qu.front();qu.pop();if(i==1)m=cur.second;//最左if(i==siz)ans=max(ans,cur.second-m+1);//最右if(cur.first->left){//非空qu.push({cur.first->left,cur.second*2});}if(cur.first->right){//非空qu.push({cur.first->right,cur.second*2+1});}}}return ans;}
};