练习题（2024/5/12）

1二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

思路：

1. 确定初始搜索区间：将左边界 left 设置为数组起始索引，右边界 right 设置为数组末尾索引。
2. 使用循环进行搜索：只要左边界 left 小于或等于右边界 right，就继续搜索。这是因为当左边界和右边界相等时，区间仍然有效，可能存在目标值。
3. 计算中间索引：通过 left + ((right - left) / 2) 来计算中间索引，这样做是为了防止整数溢出，与直接使用 (left + right) / 2 相比更安全。
4. 比较中间值和目标值：将中间索引对应的值与目标值进行比较。
5. 根据比较结果更新搜索区间：
   • 如果中间值大于目标值，则目标值在左侧，更新右边界为 middle - 1。
   • 如果中间值小于目标值，则目标值在右侧，更新左边界为 middle + 1。
   • 如果中间值等于目标值，则找到目标值，直接返回中间索引。
6. 若循环结束仍未找到目标值，则返回 -1，表示目标值不存在于数组中。

代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

2反转字符串 II

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

• 1 <= s.length <= 105
• s[i] 都是 ASCII 码表中的可打印字符

思路：

1. 使用循环遍历字符串，每次步长为 2k，以便处理每个分段。
2. 对于每个分段：
   • 如果剩余字串长度大于等于 k，则反转前 k 个字符。
   • 如果剩余字串长度小于 k，则反转剩余所有字符。
3. 将反转后的字符串返回。

代码：

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i=0;i<s.size();i+=2*k){ // 每次移动步长为 2k
            if(i+k<=s.size()){ // 如果剩余字串长度大于等于 k，则反转前 k 个字符
                reverse(s.begin()+i,s.begin()+i+k);
            }else{ // 如果剩余字串长度小于 k，则反转剩余所有字符
                reverse(s.begin()+i,s.end());
            }
        }
        return s;
    }
};

3替换数字（第八期模拟笔试）

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"

输入：一个字符串 s,s 仅包含小写字母和数字字符。

输出：打印一个新的字符串，其中每个数字字符都被替换为了number

样例输入：a1b2c3

样例输出：anumberbnumbercnumber

数据范围：1 <= s.length < 10000。

思路：

解题思路主要集中在字符串的遍历和替换过程：

1. 遍历字符串并统计数字个数： 使用一个循环遍历输入的字符串，每当遇到一个数字字符，就将计数器 count 加一。

2. 扩充字符串大小： 统计完数字个数后，需要将字符串的大小扩充，以便容纳替换后的 “number”。由于每个数字都会替换成 “number”，所以字符串大小需要增加 count * 5。

3. 从后往前替换数字为 “number”： 从原始字符串的末尾开始向前遍历，如果遇到数字字符，则依次将 “number” 替换进去；如果遇到非数字字符，则直接复制到新字符串中。这里需要维护好原始字符串和新字符串的索引关系，确保替换操作正确进行。

4. 输出替换后的字符串： 完成替换后，输出新的字符串即可。

代码：

#include <iostream>
using namespace std;

int main() {
    string s; // 定义字符串变量
    while (cin >> s) { // 循环读取输入的字符串
        int sOldIndex = s.size() - 1; // 记录原始字符串最后一个字符的索引
        int count = 0; // 统计数字的个数
        for (int i = 0; i < s.size(); i++) { // 遍历字符串
            if (s[i] >= '0' && s[i] <= '9') { // 如果当前字符是数字
                count++; // 数字个数加一
            }
        }
        // 扩充字符串 s 的大小，也就是将每个数字替换成 "number" 之后的大小
        s.resize(s.size() + count * 5);
        int sNewIndex = s.size() - 1; // 新字符串的最后一个字符的索引
        // 从后往前将数字替换为 "number"
        while (sOldIndex >= 0) { // 从原始字符串的末尾开始遍历
            if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') { // 如果当前字符是数字
                s[sNewIndex--] = 'r'; // 替换为 'r'
                s[sNewIndex--] = 'e'; // 替换为 'e'
                s[sNewIndex--] = 'b'; // 替换为 'b'
                s[sNewIndex--] = 'm'; // 替换为 'm'
                s[sNewIndex--] = 'u'; // 替换为 'u'
                s[sNewIndex--] = 'n'; // 替换为 'n'
            } else { // 如果当前字符不是数字
                s[sNewIndex--] = s[sOldIndex]; // 不变，直接复制
            }
            sOldIndex--; // 原始字符串索引向前移动
        }
        cout << s << endl; // 输出替换后的字符串       
    }
}

4反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

思路：

cur 和 pre 两个指针构成了双指针的思路，用来实现链表的反转。

• cur 指针是当前遍历到的节点，初始时指向头节点 head。
• pre 指针是 cur 的前一个节点，在循环中起到了记录已经反转部分的作用。

每次循环中的操作主要包括：

1. 将 temp 指针指向 cur 的下一个节点，以便在修改 cur->next 后能找到下一个节点。
2. 将 cur->next 指向 pre，实现当前节点的反转。
3. 更新 pre 和 cur 指针，将 pre 移向 cur 的位置，将 cur 移向 temp 的位置

代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

5求关注者的数量

表： Followers

+-------------+------+
| Column Name | Type |
+-------------+------+
| user_id     | int  |
| follower_id | int  |
+-------------+------+
(user_id, follower_id) 是这个表的主键（具有唯一值的列的组合）。
该表包含一个关注关系中关注者和用户的编号，其中关注者关注用户。

编写解决方案，对于每一个用户，返回该用户的关注者数量。

按 user_id 的顺序返回结果表。

查询结果的格式如下示例所示。

示例 1：

输入：
Followers 表：
+---------+-------------+
| user_id | follower_id |
+---------+-------------+
| 0       | 1           |
| 1       | 0           |
| 2       | 0           |
| 2       | 1           |
+---------+-------------+
输出：
+---------+----------------+
| user_id | followers_count|
+---------+----------------+
| 0       | 1              |
| 1       | 1              |
| 2       | 2              |
+---------+----------------+
解释：
0 的关注者有 {1}
1 的关注者有 {0}
2 的关注者有 {0,1}

代码：

select user_id,count(follower_id) followers_count
from Followers 
group by user_id
order by user_id asc;