練習題（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

提示：

你可以假設?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 <= 105
s[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;