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
提示：
- 你可以假设
nums中的所有元素是不重复的。 n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
思路：
- 确定初始搜索区间：将左边界
left设置为数组起始索引，右边界right设置为数组末尾索引。 - 使用循环进行搜索：只要左边界
left小于或等于右边界right，就继续搜索。这是因为当左边界和右边界相等时，区间仍然有效，可能存在目标值。 - 计算中间索引：通过
left + ((right - left) / 2)来计算中间索引，这样做是为了防止整数溢出，与直接使用(left + right) / 2相比更安全。 - 比较中间值和目标值：将中间索引对应的值与目标值进行比较。
- 根据比较结果更新搜索区间：
- 如果中间值大于目标值，则目标值在左侧，更新右边界为
middle - 1。 - 如果中间值小于目标值，则目标值在右侧，更新左边界为
middle + 1。 - 如果中间值等于目标值，则找到目标值，直接返回中间索引。
- 如果中间值大于目标值，则目标值在左侧，更新右边界为
- 若循环结束仍未找到目标值，则返回 -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)/2if (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] == targetreturn 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 <= 105s[i]都是 ASCII 码表中的可打印字符
思路：
- 使用循环遍历字符串，每次步长为 2k，以便处理每个分段。
- 对于每个分段：
- 如果剩余字串长度大于等于 k，则反转前 k 个字符。
- 如果剩余字串长度小于 k，则反转剩余所有字符。
- 将反转后的字符串返回。
代码：
class Solution {
public:string reverseStr(string s, int k) {for(int i=0;i<s.size();i+=2*k){ // 每次移动步长为 2kif(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。
思路：
解题思路主要集中在字符串的遍历和替换过程：
-
遍历字符串并统计数字个数： 使用一个循环遍历输入的字符串，每当遇到一个数字字符，就将计数器
count加一。 -
扩充字符串大小： 统计完数字个数后，需要将字符串的大小扩充，以便容纳替换后的 “number”。由于每个数字都会替换成 “number”，所以字符串大小需要增加
count * 5。 -
从后往前替换数字为 “number”： 从原始字符串的末尾开始向前遍历，如果遇到数字字符，则依次将 “number” 替换进去；如果遇到非数字字符，则直接复制到新字符串中。这里需要维护好原始字符串和新字符串的索引关系，确保替换操作正确进行。
-
输出替换后的字符串： 完成替换后，输出新的字符串即可。
代码：
#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的前一个节点，在循环中起到了记录已经反转部分的作用。
每次循环中的操作主要包括：
- 将
temp指针指向cur的下一个节点，以便在修改cur->next后能找到下一个节点。 - 将
cur->next指向pre，实现当前节点的反转。 - 更新
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->nextcur->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;
