企业官网建设流程全解析

1.各位相加

给定一个非负整数num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

示例 1:

输入:num =38输出:2解释:各位相加的过程为：38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 由于 2 是一位数，所以返回 2。

示例 2:

输入:num =0输出:0

提示：

0 <= num <= 231 - 1

方法一：暴力

#include <bits/stdc++.h> using namespace std; int addDigits(int num) { while (num >= 10) { int sum = 0; while (num > 0) { sum += num % 10; num /= 10; } num = sum; } return num; } int main() { int num; cin >> num; cout << addDigits(num) << endl; return 0; }

复杂度分析

时间复杂度：O(log(n))。

空间复杂度：O(1)。

方法二：数学

#include <bits/stdc++.h> using namespace std; int addDigits(int num) { return (num - 1) % 9 + 1; } int main() { int num; cin >> num; cout << addDigits(num) << endl; return 0; }

复杂度分析

时间复杂度：O(1)。

空间复杂度：O(1)。

2.数组异或操作

给你两个整数，n和start。

数组nums定义为：nums[i] = start + 2*i（下标从 0 开始）且n == nums.length。

请返回nums中所有元素按位异或（XOR）后得到的结果。

示例 1：

输入：n = 5, start = 0输出：8解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。 "^" 为按位异或 XOR 运算符。

示例 2：

输入：n = 4, start = 3输出：8解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.

示例 3：

输入：n = 1, start = 7输出：7

示例 4：

输入：n = 10, start = 5输出：2

提示：

• 1 <= n <= 1000
• 0 <= start <= 1000
• n == nums.length

方法一：暴力

#include <bits/stdc++.h> using namespace std; int xorOperation(int n, int start) { int ans = 0; for (int i = 0; i < n; ++i) { ans ^= (start + i * 2); } return ans; } int main() { int n, start; cin >> n >> start; cout << xorOperation(n, start) << endl; return 0; }

复杂度分析

• 时间复杂度：O(n)。这里用一重循环对 n 个数字进行异或。

• 空间复杂度：O(1)。这里只是用了常量级别的辅助空间。

方法二：数学

#include <bits/stdc++.h> using namespace std; // 函数：计算 0 ⊕ 1 ⊕ 2 ⊕ ... ⊕ s 的结果（前缀异或） // 利用异或运算的性质，每连续4个整数异或结果为0，可以O(1)计算 int S(int s) { if (s < 0) return 0; // 处理 s = -1 的情况（当 start = 0 时 s-1 = -1） if (s % 4 == 0) return s; // 4k: 0⊕1⊕...⊕4k = 4k if (s % 4 == 1) return 1; // 4k+1: 结果 = 1 if (s % 4 == 2) return s + 1; // 4k+2: 结果 = 4k+3 return 0; // 4k+3: 结果 = 0 } // 函数：计算 nums[i] = start + 2*i 的异或和 // 利用数学优化，时间复杂度 O(1) int xorOperation(int n, int start) { // 将每个数除以2（右移1位），分离出最低位 // 原式: (2s) ⊕ (2(s+1)) ⊕ ... ⊕ (2(s+n-1)) 再处理最低位的 e int s = start >> 1; // s = start / 2，整数除法 // 计算高位部分的异或：s ⊕ (s+1) ⊕ ... ⊕ (s+n-1) // 区间异或 = 前缀异或(s+n-1) ⊕ 前缀异或(s-1) int ans = S(s - 1) ^ S(s + n - 1); // 处理最低位 e // 只有当 n 为奇数 且 start 为奇数时，最低位的异或结果才是 1 int e = 0; if (n % 2 && start % 2) e = 1; // 高位结果左移1位（相当于乘以2），再加上最低位 ans = ans * 2 + e; return ans; } int main() { int n, start; cin >> n >> start; cout << xorOperation(n, start) << endl; return 0; }

算法核心思想

1. 分离最低位：start + 2*i = 2*(start/2 + i) + (start%2)

2. 高位部分：计算连续整数的异或(s) ⊕ (s+1) ⊕ ... ⊕ (s+n-1)，用前缀异或s(x)实现

3. 区间异或 = 前缀异或(s+n-1) ⊕ 前缀异或(s-1)，ans = S(s - 1) ^ S(s + n - 1)

4. 低位部分：只有当n和start都是奇数时，最低位异或结果才为 1

5. 最终公式：xorOperation(n,start)=2⋅(S(s+n−1)⊕S(s−1))+(e*(n mod 2)*(start mod 2))

异或运算基本性质

1. 自反性：x⊕x=0

2. 交换律：x⊕y=y⊕x

3. 结合律：(x⊕y)⊕z=x⊕(y⊕z)

4. 消去律：x⊕y⊕y=x

5. 连续四个整数异或为 0： ∀i∈Z, (4i)⊕(4i+1)⊕(4i+2)⊕(4i+3)=0

前缀异或函数 S(m)

定义： S(m)=0⊕1⊕2⊕⋯⊕m

利用连续四个整数异或为 0 的性质推导：

• 若 m=4k：S(4k)=4k
• 若 m=4k+1：S(4k+1)=1
• 若 m=4k+2：S(4k+2)=4k+3
• 若 m=4k+3：S(4k+3)=0

即：

区间异或公式

L⊕(L+1)⊕⋯⊕R=S(R)⊕S(L−1)

推导： 因为 S(R)=[0⊕1⊕⋯⊕(L−1)]⊕[L⊕(L+1)⊕⋯⊕R]， 两边同时异或 S(L−1)，即可得到区间异或公式。

3. 2的幂

给你一个整数n，请你判断该整数是否是 2 的幂次方。如果是，返回true；否则，返回false。

如果存在一个整数x使得n == 2x，则认为n是 2 的幂次方。

示例 1：

输入：n = 1输出：true解释：20 = 1

示例 2：

输入：n = 16输出：true解释：24 = 16

示例 3：

输入：n = 3输出：false

提示：

• -231 <= n <= 231 - 1

进阶：你能够不使用循环/递归解决此问题吗？

#include <bits/stdc++.h> using namespace std; // 方法一：利用 n & (n-1) 清除最低位的1 // 2的幂次方二进制只有一个1，清除后应为0 bool isPowerOfTwo1(int n) { if(n > 0 && (n & (n - 1)) == 0) return true; return false; } // 方法二：利用 n & (-n) 获取最低位的1 // 2的幂次方的二进制只有一个1，所以最低位的1就是它本身 bool isPowerOfTwo2(int n) { if(n > 0 && (n & (-n)) == n) return true; return false; } int main() { int n; cin >> n; // 使用第一种方法 // cout << isPowerOfTwo1(n) << endl; // 使用第二种方法 cout << isPowerOfTwo2(n) << endl; return 0; }

两种方法的原理说明：

方法一：n & (n-1)
对于 2 的幂次方（如 8 = 1000₂），n-1 = 0111₂

n & (n-1) = 1000₂ & 0111₂ = 0

非 2 的幂次方（如 6 = 0110₂），n-1 = 0101₂

n & (n-1) = 0110₂ & 0101₂ = 0100₂ ≠ 0

方法二：n & -n
-n 在计算机中用补码表示，等于 ~n + 1

n & -n 得到的是 n 的二进制中最低位的 1 所代表的值

对于 2 的幂次方（如 8 = 1000₂），n & -n = 8

对于非 2 的幂次方（如 6 = 0110₂），n & -n = 2 ≠ 6

两种方法都是 O(1) 时间复杂度，不使用循环/递归，满足进阶要求。