双指针算法思想——OJ例题扩展算法解析思路

        大家好！上一期我发布了关于双指针的OJ平台上的典型例题思路解析，基于上一期的内容，我们这一期从其中内容扩展出来相似例题进行剖析和运用，一起来试一下吧！

目录

一、 基于移动零的举一反三

题一：27. 移除元素 - 力扣（LeetCode）

运行代码： 

1. 双指针初始化

2. 遍历数组

3. 处理非 val 元素

4. 处理 val 元素

5. 返回结果

6. 时间复杂度

7. 空间复杂度

代码总结

示例

题二：2460. 对数组执行操作 - 力扣（LeetCode）

基本大体思路：

第一部分：应用特定规则修改数组元素

思路：

示例：

第二部分：将所有非零元素移动到数组的前部

思路：

示例：

第三部分：返回结果——返回修改后的数组 nums。

总结

示例运行

二、基于快乐数的举一反三

题一：2460. 对数组执行操作 - 力扣（LeetCode）

运行代码： 

1. 初始化快慢指针

2. 处理特殊情况

3. 遍历链表

4. 遍历结束

5. 算法原理

6. 时间复杂度

7. 示例

8. 总结

题二：258. 各位相加 - 力扣（LeetCode）

运行代码：

2. 内层循环：计算数位和

3. 返回结果

4. 示例

5. 时间复杂度

题三： 263. 丑数 - 力扣（LeetCode）

运行代码： 

1. 处理特殊情况

2. 定义质因数数组

3. 循环去除质因数

4. 判断最终结果

总结

题四：1945. 字符串转化后的各位数字之和 - 力扣（LeetCode）

 运行代码:

问题分析

代码思路

第一步：字母转换为数字字符串

第二步：数字求和操作

第三步：返回结果

代码实现的关键点

步骤：

时间复杂度分析

题五：2457. 美丽整数的最小增量 - 力扣（LeetCode）

思路：

 运行代码：

题六：2507. 使用质因数之和替换后可以取到的最小值 - 力扣（LeetCode）

 运行代码：

问题分析

代码思路

第一步：质因数分解

第二步：替换为质因数之和

第三步：返回结果

代码实现的关键点

1. sumOfPrimeFactors 函数

2. smallestValue 函数

示例运行

步骤：

时间复杂度分析

题七：2520. 统计能整除数字的位数 - 力扣（LeetCode）

 运行代码：

代码思路

第一步：初始化

第二步：逐位提取数字

第三步：返回结果

代码实现的关键点

1. 逐位提取数字

2. 判断是否能整除

3. 边界条件

示例运行

步骤：

时间复杂度分析

---

一、 基于移动零的举一反三

题一：27. 移除元素 - 力扣（LeetCode）

运行代码： 

class Solution {
public:int removeElement(vector<int>& nums, int val) {int left=0;int right=0;while(right<nums.size()){if(nums[right]!=val){  swap(nums[left],nums[right]);left++;}right++;}return left;}
};

1. 双指针初始化

• left 指针：用于指向当前可以放置非 val 元素的位置。

• right 指针：用于遍历数组，寻找非 val 的元素。

2. 遍历数组

• 使用 while 循环遍历数组，right 指针从数组的起始位置开始，逐步向右移动。

• 在遍历过程中，right 指针会检查当前元素是否等于 val。

3. 处理非 val 元素

• 如果 nums[right] 不等于 val，说明这个元素应该保留在数组中。

• 将这个元素与 nums[left] 交换，确保所有非 val 的元素都集中在数组的左侧。

• 交换后，left 指针向右移动一位，指向下一个可以放置非 val 元素的位置。

4. 处理 val 元素

• 如果 nums[right] 等于 val，则不做任何操作，right 指针继续向右移动，跳过这个元素。

5. 返回结果

• 当 right 指针遍历完整个数组后，left 指针的位置即为移除所有 val 元素后数组的新长度。

• 返回 left 的值。

6. 时间复杂度

• 该算法的时间复杂度为 O(n)，其中 n 是数组的长度。因为每个元素最多被访问一次。

7. 空间复杂度

• 该算法的空间复杂度为 O(1)，因为它只使用了常数个额外的变量（left 和 right 指针）。

代码总结

• 通过双指针技巧，代码高效地将所有非 val 元素移动到数组的前部，并返回新数组的长度。

• 这种方法避免了使用额外的空间，直接在原数组上进行操作，是一种原地修改的算法。

示例

假设 nums = [3, 2, 2, 3]，val = 3，代码的执行过程如下：

1. left = 0, right = 0，nums[0] = 3（等于 val），right++。

2. left = 0, right = 1，nums[1] = 2（不等于 val），交换 nums[0] 和 nums[1]，数组变为 [2, 3, 2, 3]，left++，right++。

3. left = 1, right = 2，nums[2] = 2（不等于 val），交换 nums[1] 和 nums[2]，数组变为 [2, 2, 3, 3]，left++，right++。

4. left = 2, right = 3，nums[3] = 3（等于 val），right++。

5. 遍历结束，返回 left = 2，表示新数组的长度为 2，且前两个元素 [2, 2] 是移除 val 后的结果。

题二：2460. 对数组执行操作 - 力扣（LeetCode）

基本大体思路：

1. 应用特定规则修改数组元素：如果相邻的两个元素相等，则将左边的元素乘以 2，右边的元素置为 0。

2. 将所有非零元素移动到数组的前部：保持非零元素的相对顺序，并将所有 0 移动到数组的末尾。

以下是代码的思路解析：

---

第一部分：应用特定规则修改数组元素

for (int i = 0; i < n - 1; i++) 
{int left = i, right = i + 1;if (nums[left] == nums[right]) {nums[left] *= 2;nums[right] = 0;} else {continue;}
}

思路：

1. 遍历数组：

   • 使用一个 for 循环遍历数组，从索引 0 到 n-2（因为需要比较当前元素和下一个元素）。

   • 定义两个指针 left 和 right，分别指向当前元素和下一个元素。

2. 检查相邻元素是否相等：

   • 如果 nums[left] == nums[right]，则将 nums[left] 的值乘以 2，并将 nums[right] 置为 0。

   • 如果相邻元素不相等，则跳过，继续遍历。

示例：

假设 nums = [1, 1, 2, 2]：

• 遍历到 i = 0 时，nums[0] == nums[1]，因此 nums[0] *= 2（变为 2），nums[1] = 0，数组变为 [2, 0, 2, 2]。

• 遍历到 i = 2 时，nums[2] == nums[3]，因此 nums[2] *= 2（变为 4），nums[3] = 0，数组变为 [2, 0, 4, 0]。

第二部分：将所有非零元素移动到数组的前部

int dest = -1, cur = 0;
while (cur < nums.size()) 
{if (nums[cur]) {dest++;swap(nums[dest], nums[cur]);cur++;} else {cur++;}
}

思路：

1. 双指针初始化：

   • dest 指针：用于指向当前可以放置非零元素的位置，初始值为 -1。

   • cur 指针：用于遍历数组，初始值为 0。

2. 遍历数组：

   • 使用 while 循环遍历数组，cur 指针从 0 开始，逐步向右移动。

3. 处理非零元素：

   • 如果 nums[cur] 是非零元素，则将 dest 指针向右移动一位，并交换 nums[dest] 和 nums[cur]。

   • 这样可以将所有非零元素移动到数组的前部，同时保持它们的相对顺序。

4. 处理零元素：

   • 如果 nums[cur] 是零元素，则跳过，cur 指针继续向右移动。

示例：

假设经过第一部分操作后，nums = [2, 0, 4, 0]：

• dest = -1, cur = 0，nums[0] = 2（非零），dest++（变为 0），交换 nums[0] 和 nums[0]（数组不变），cur++。

• dest = 0, cur = 1，nums[1] = 0（零），跳过，cur++。

• dest = 0, cur = 2，nums[2] = 4（非零），dest++（变为 1），交换 nums[1] 和 nums[2]，数组变为 [2, 4, 0, 0]，cur++。

• dest = 1, cur = 3，nums[3] = 0（零），跳过，cur++。

• 遍历结束，数组变为 [2, 4, 0, 0]。

第三部分：返回结果——返回修改后的数组 nums。

总结

1. 时间复杂度：

   • 第一部分遍历数组一次，时间复杂度为 O(n)。

   • 第二部分遍历数组一次，时间复杂度为 O(n)。

   • 总时间复杂度为 O(n)。

2. 空间复杂度：

   • 只使用了常数个额外变量（dest 和 cur），空间复杂度为 O(1)。

3. 功能：

   • 代码实现了对数组的原地修改，满足题目要求。

示例运行

假设输入 nums = [1, 1, 2, 2]：

1. 第一部分操作后，数组变为 [2, 0, 4, 0]。

2. 第二部分操作后，数组变为 [2, 4, 0, 0]。

3. 返回 [2, 4, 0, 0]。

二、基于快乐数的举一反三

题一：2460. 对数组执行操作 - 力扣（LeetCode）

运行代码： 

class Solution {
public:bool hasCycle(ListNode *head) {ListNode* slow=head;ListNode* fast=head;if(head==nullptr||head->next==nullptr){return false;}while(fast!=nullptr&&fast->next!=nullptr){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}return false;}
};

1. 初始化快慢指针

• slow 是慢指针，每次移动一步。

• fast 是快指针，每次移动两步。

• 初始时，两个指针都指向链表的头节点 head。

2. 处理特殊情况

• 如果链表为空（head == nullptr）或只有一个节点（head->next == nullptr），则链表不可能有环，直接返回 false。

3. 遍历链表

• 使用 while 循环遍历链表，条件是 fast != nullptr && fast->next != nullptr。

  • 这个条件确保快指针可以安全地移动两步（避免访问空指针）。

• 在每次循环中：

  • 慢指针 slow 移动一步：slow = slow->next。

  • 快指针 fast 移动两步：fast = fast->next->next。

• 如果快慢指针相遇（slow == fast），说明链表中有环，返回 true。

4. 遍历结束

• 如果快指针到达链表末尾（fast == nullptr 或 fast->next == nullptr），说明链表中没有环，返回 false。

5. 算法原理

• 快慢指针的核心思想：

  • 如果链表中有环，快指针最终会追上慢指针（因为快指针每次比慢指针多走一步）。

  • 如果链表中没有环，快指针会先到达链表末尾。

6. 时间复杂度

• 时间复杂度：O(n)，其中 n 是链表的节点数。

  • 如果链表中无环，快指针会先到达链表末尾，遍历次数为 n/2。

  • 如果链表中有环，快慢指针会在环内相遇，遍历次数小于 n。

• 空间复杂度：O(1)，只使用了常数个额外空间（两个指针）。

7. 示例

假设链表如下：

​

• 初始时，slow 和 fast 都指向节点 3。

• 移动过程：

  • slow 移动到 2，fast 移动到 0。

  • slow 移动到0，fast 移动到 2。

  • slow 移动到-4，fast 移动到 -4。

• slow == fast，说明链表有环，返回 true。

8. 总结

• 这段代码通过快慢指针高效地判断链表中是否存在环。

• 快慢指针算法是解决链表环检测问题的经典方法，具有时间复杂度 O(n) 和空间复杂度 O(1) 的优势。

题二：258. 各位相加 - 力扣（LeetCode）

运行代码：

class Solution {
public:int addDigits(int num) {while(num>=10){int sum=0;while(num>0){sum+=num%10;num/=10;}num=sum;}return num;}
};

 1. 外层循环：判断是否需要继续计算

• 如果 num 大于或等于 10，说明 num 还不是个位数，需要继续计算数位和。

• 如果 num 小于 10，说明已经得到结果，直接返回 num。

2. 内层循环：计算数位和

• sum 初始化：

  • 每次外层循环开始时，sum 初始化为 0，用于累加 num 的各个数位。

• 内层循环逻辑：

  • 使用 while (num > 0) 循环，逐位取出 num 的个位数，并累加到 sum 中。

  • 每次取出个位数后，将 num 除以 10，去掉已经处理的个位数。

• 更新 num：

  • 内层循环结束后，将 sum 赋值给 num，继续外层循环的判断。

3. 返回结果

• 当 num 小于 10 时，跳出外层循环，返回 num，即为最终的结果。

4. 示例

假设输入 num = 38，代码的执行过程如下：

1. 第一次外层循环：

   • num = 38（大于等于 10），进入内层循环。

   • 内层循环：

     • sum += 8（38 % 10），sum = 8，num = 3（38 / 10）。

     • sum += 3（3 % 10），sum = 11，num = 0（3 / 10）。

   • 内层循环结束，num = sum = 11。

2. 第二次外层循环：

   • num = 11（大于等于 10），进入内层循环。

   • 内层循环：

     • sum += 1（11 % 10），sum = 1，num = 1（11 / 10）。

     • sum += 1（1 % 10），sum = 2，num = 0（1 / 10）。

   • 内层循环结束，num = sum = 2。

3. 外层循环结束：

   • num = 2（小于 10），跳出循环，返回 2。

5. 时间复杂度

• 时间复杂度：O(log n)，其中 n 是输入的数字。

  • 每次外层循环会将 num 减少到其数位和，数位和的规模远小于 num。

  • 内层循环的次数取决于 num 的位数，每次内层循环的时间复杂度为 O(log n)。

• 空间复杂度：O(1)，只使用了常数个额外变量。

题三： 263. 丑数 - 力扣（LeetCode）

运行代码： 

class Solution {
public:bool isUgly(int n) {int arr[]={2,3,5};if(n<=0){return false;}else{for(int i=0;i<3;i++){while(n%arr[i]==0){n/=arr[i];}}return n==1;}}
};

1. 处理特殊情况

• 如果 n 小于或等于 0，直接返回 false，因为丑数必须是正整数。

2. 定义质因数数组

• 定义一个数组 arr，包含 2、3、5 这三个质因数。

3. 循环去除质因数

• 使用一个 for 循环遍历数组 arr 中的每个质因数。

• 对于每个质因数，使用 while 循环不断将 n 除以该质因数，直到 n 不再能被该质因数整除为止。

• 这样做的目的是将 n 中的所有 2、3、5 的质因数全部去除。

4. 判断最终结果

• 如果 n 最终变为 1，说明 n 只包含 2、3、5 这些质因数，因此 n 是丑数，返回 true。

• 如果 n 最终不为 1，说明 n 包含其他质因数，因此 n 不是丑数，返回 false。

总结

• 该算法通过不断去除 n 中的 2、3、5 质因数，最终判断 n 是否变为 1 来判断 n 是否为丑数。

• 时间复杂度为 O(log n)，因为每次除法操作都会减少 n 的大小。

• 空间复杂度为 O(1)，只使用了常数级别的额外空间。

题四：1945. 字符串转化后的各位数字之和 - 力扣（LeetCode）

 运行代码:

class Solution {
public:int getLucky(string s, int k) {string digits;for(auto ch : s){// 将字符转换为对应的数字并追加到digits字符串中digits += to_string(ch - 'a' + 1);}for(int i = 1; i <= k && digits.size() > 1; ++i){int sum = 0;for(auto ch : digits){// 将字符转换为数字并累加sum += stoi(string(1, ch));}// 将累加结果转换为字符串digits = to_string(sum);}// 返回最终结果return stoi(digits);}
};

问题分析

1. 输入：

   • 一个字符串 s，由小写字母组成。

   • 一个整数 k，表示需要进行“数字求和”操作的次数。

2. 转换规则：

   • 将字符串中的每个字母转换为其在字母表中的位置值（a -> 1, b -> 2, ..., z -> 26）。

   • 将这些位置值拼接成一个数字字符串。

3. 操作规则：

   • 对数字字符串中的每一位数字求和，得到一个新的数字。

   • 重复上述操作 k 次，或者直到数字字符串的长度变为 1（即无法继续求和）。

4. 输出：

   • 最终的数字结果。

代码思路

第一步：字母转换为数字字符串

1. 遍历字符串 s 中的每个字符 ch。

2. 将字符 ch 转换为对应的数字：

   • 公式：ch - 'a' + 1。

     • ch - 'a' 得到字符 ch 在字母表中的偏移量（a -> 0, b -> 1, ..., z -> 25）。

     • + 1 将其转换为位置值（a -> 1, b -> 2, ..., z -> 26）。

3. 将数字转换为字符串并追加到 digits 中。

示例：

• 输入 s = "abc"：

  • a -> 1, b -> 2, c -> 3。

  • digits = "123"。

第二步：数字求和操作

1. 进行 k 次求和操作：

   • 每次操作中，遍历 digits 中的每个字符（即数字的每一位）。

   • 将字符转换为数字并累加到 sum 中。

   • 将 sum 转换为字符串，更新 digits。

2. 如果 digits 的长度变为 1，则提前结束循环（因为无法继续求和）。

示例：

• 输入 digits = "123", k = 2：

  • 第一次操作：

    • sum = 1 + 2 + 3 = 6。

    • digits = "6"。

  • 第二次操作：

    • 由于 digits 的长度已经是 1，循环结束。

第三步：返回结果

1. 将最终的 digits 转换为整数并返回。

示例：

• 最终 digits = "6"，返回 6。

代码实现的关键点

1. 字符到数字的转换：

   • 使用 ch - 'a' + 1 将字母转换为对应的数字。

   • 使用 to_string 将数字转换为字符串。

2. 数字求和：

   • 使用 stoi(string(1, ch)) 将字符转换为数字。

   • 使用 to_string(sum) 将求和结果转换回字符串。

3. 循环控制：

   • 最多进行 k 次操作。

   • 如果 digits 的长度变为 1，提前结束循环。

步骤：

1. 字母转换为数字字符串：

   • l -> 12, e -> 5, e -> 5, t -> 20, c -> 3, o -> 15, d -> 4, e -> 5。

   • digits = "12552031545"。

2. 第一次求和操作：

   • sum = 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 = 33。

   • digits = "33"。

3. 第二次求和操作：

   • sum = 3 + 3 = 6。

   • digits = "6"。

4. 返回结果：

   • 6。

时间复杂度分析

1. 字母转换：

   • 遍历字符串 s，时间复杂度为 O(n)，其中 n 是字符串的长度。

2. 数字求和操作：

   • 每次求和操作需要遍历 digits 的所有字符。

   • 最多进行 k 次操作。

   • 最坏情况下，digits 的长度可能很大，但每次求和操作会显著减少其长度。

   • 总体时间复杂度为 O(k * m)，其中 m 是 digits 的最大长度。

题五：2457. 美丽整数的最小增量 - 力扣（LeetCode）

思路：

• 得到当前数字的各位数字之和，如果<=target就直接返回0
• 当前值各位数之和大于了target，那么考虑进行进位，当前数大于，那么个位的数字往上变大更不可能满足条件
• 寻找最小值，末尾为0则最小 所以我们令此时的个位为0，十位进1，同理，如果计算后仍旧大于target，我们将十位变为0，百位进1
• 举例子:123 3
• 123 和为6>3，那么124-129的各位数和不可能小于6,直到进位后130达到4才小于123的6
• 130 和为4>3  那么131-139也不可能小于4，也只有进位后200才小于130的4
• 200 和为2<3，所以200-123的差就是最小增量

 运行代码：

class Solution {
public:int sub(long long n)//位数求和{int sum = 0;while (n > 0){sum += n % 10;n /= 10;}return sum;}long long makeIntegerBeautiful(long long n, int target){if (sub(n) <= target)return 0;long long i = 10;long long t=n;//保存原值while (sub(n) > target){n=n/i;//去掉当前末位(即末位变为0) 第一轮123-> 12       第二轮130->1n++;//进位                      第一轮12+1->13        第二轮1+1->2n*=i;//末尾变为0                第一轮13*10->130       第二轮2*100->200i*=10;//每一次进位             }return n-t;}
};

题六：2507. 使用质因数之和替换后可以取到的最小值 - 力扣（LeetCode）

 运行代码：

class Solution {
public:// 辅助函数：计算 n 的质因数之和int sumOfPrimeFactors(int n) {int sum = 0;// 从最小的质数 2 开始分解for (int i = 2; i * i <= n; i++) {while (n % i == 0) {sum += i; // 累加质因数n /= i;}}// 如果 n 仍然是大于 1 的质数if (n > 1) {sum += n;}return sum;}// 主函数：计算 n 的最小值int smallestValue(int n) {while (true) {int sum = sumOfPrimeFactors(n); // 计算质因数之和if (sum == n) { // 如果 n 已经是质数break;}n = sum; // 替换 n 为质因数之和}return n;}
};

问题分析

1. 输入：

   • 一个正整数 n。

2. 操作规则：

   • 将 n 替换为其质因数之和。

   • 重复上述操作，直到 n 无法再被分解（即 n 是一个质数）。

3. 输出：

   • 最终 n 的最小值（即一个质数）。

代码思路

第一步：质因数分解

1. 对于一个正整数 n，找到其所有质因数。

2. 如果 n 能被某个质因数多次整除，则在求和时，该质因数需要被累加多次。

第二步：替换为质因数之和

1. 将 n 替换为其质因数之和。

2. 重复上述操作，直到 n 是一个质数。

第三步：返回结果

1. 最终 n 的值即为所求的最小值。

代码实现的关键点

1. sumOfPrimeFactors 函数

• 功能：计算整数 n 的所有质因数之和。

• 实现：

  • 从最小的质数 2 开始，逐个检查是否能整除 n。

  • 如果能整除，则将该质因数累加到 sum 中，并将 n 除以该质因数。

  • 重复上述过程，直到 n 变为 1 或无法再被分解。

  • 如果 n 仍然是大于 1 的质数，则将其累加到 sum 中。

2. smallestValue 函数

• 功能：将 n 替换为其质因数之和，直到 n 变为质数。

• 实现：

  • 循环调用 sumOfPrimeFactors，计算 n 的质因数之和。

  • 如果 sum == n，说明 n 已经是质数，退出循环。

  • 否则，将 n 替换为 sum，继续循环。

示例运行

步骤：

1. 第一次分解：

   • 质因数分解：12 = 2 * 2 * 3。

   • 质因数之和：2 + 2 + 3 = 7。

   • 替换 n 为 7。

2. 第二次分解：

   • 7 是质数，无法再分解。

   • 返回 7。

时间复杂度分析

1. 质因数分解：

   • 每次分解的时间复杂度为 O(sqrt(n))。

2. 循环次数：

   • 每次替换 n 为质因数之和，n 的值会显著减小。

   • 最坏情况下，循环次数为 O(log n) 次。

3. 总体时间复杂度：

   • O(sqrt(n) * log n)。

题七：2520. 统计能整除数字的位数 - 力扣（LeetCode）

 运行代码：

class Solution {
public:int countDigits(int num) {int t = num, res = 0;while (t) {if (num % (t % 10) == 0) {res += 1;}t /= 10;}return res;}
};

 问题分析

1. 输入：

   • 一个整数 num。

2. 目标：

   • 计算 num 中有多少位数字能够整除 num 本身。

3. 关键点：

   • 需要逐位提取 num 的数字。

   • 判断每一位数字是否能整除 num。

代码思路

第一步：初始化

1. 使用变量 t 保存 num 的值，避免直接修改 num。

2. 使用变量 res 记录满足条件的数字个数，初始值为 0。

第二步：逐位提取数字

1. 使用 while 循环遍历 t 的每一位数字：

   • t % 10：获取 t 的最后一位数字。

   • t /= 10：去掉 t 的最后一位数字。

2. 对每一位数字进行判断：

   • 如果 num % (t % 10) == 0，说明当前数字能整除 num。

   • 将 res 的值加 1。

第三步：返回结果

1. 循环结束后，res 中存储的就是满足条件的数字个数。

2. 返回 res。

代码实现的关键点

1. 逐位提取数字

• 使用 t % 10 获取当前位的数字。

• 使用 t /= 10 去掉当前位的数字。

2. 判断是否能整除

• 使用 num % (t % 10) == 0 判断当前数字是否能整除 num。

3. 边界条件

• 如果 num 的某一位是 0，则需要跳过，因为除数不能为 0。

  • 在这段代码中，如果 t % 10 == 0，num % 0 会导致运行时错误。因此，代码假设 num 不包含 0。

示例运行

步骤：

1. 初始化：

   • t = 1248，res = 0。

2. 第一次循环：

   • t % 10 = 8。

   • 1248 % 8 == 0，满足条件。

   • res = 1。

   • t = 1248 / 10 = 124。

3. 第二次循环：

   • t % 10 = 4。

   • 1248 % 4 == 0，满足条件。

   • res = 2。

   • t = 124 / 10 = 12。

4. 第三次循环：

   • t % 10 = 2。

   • 1248 % 2 == 0，满足条件。

   • res = 3。

   • t = 12 / 10 = 1。

5. 第四次循环：

   • t % 10 = 1。

   • 1248 % 1 == 0，满足条件。

   • res = 4。

   • t = 1 / 10 = 0。

6. 循环结束，返回 res = 4。

时间复杂度分析

1. 循环次数：

   • while 循环的次数等于 num 的位数，即 O(log num)。

2. 总体时间复杂度：

   • O(log num)。