1輪轉數組

給定一個整數數組?nums，將數組中的元素向右輪轉?k?個位置，其中?k?是非負數。

示例 1:

輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉 1 步: [7,1,2,3,4,5,6]
向右輪轉 2 步: [6,7,1,2,3,4,5]
向右輪轉 3 步: [5,6,7,1,2,3,4]

示例?2:

輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋: 
向右輪轉 1 步: [99,-1,-100,3]
向右輪轉 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

思路：

1. 對于給定的 k，先將其對數組長度取模，以處理 k 大于數組長度的情況。

2. 首先將整個數組進行反轉，此時原數組中的最后 k 個元素會被移動到數組的開頭。

3. 然后再將前 k 個元素進行反轉，將其移動到數組末尾，此時數組中的元素順序已經符合旋轉后的要求。

4. 最后，對數組中剩余的元素進行反轉，以將其移動到數組的前面。

代碼：

class Solution {
public:void rotate(vector<int>& nums, int k) {// 對 k 取模，以處理 k 大于數組長度的情況k = k % nums.size();// 將整個數組反轉reverse(nums.begin(), nums.end());// 反轉前 k 個元素，將它們移動到數組末尾reverse(nums.begin(), nums.begin() + k);// 反轉剩余元素，將它們移到數組前面reverse(nums.begin() + k, nums.end());}
};

2反轉字符串中的單詞

給你一個字符串?s?，請你反轉字符串中?單詞?的順序。

單詞?是由非空格字符組成的字符串。s?中使用至少一個空格將字符串中的?單詞?分隔開。

返回?單詞?順序顛倒且?單詞?之間用單個空格連接的結果字符串。

注意：輸入字符串?s中可能會存在前導空格、尾隨空格或者單詞間的多個空格。返回的結果字符串中，單詞間應當僅用單個空格分隔，且不包含任何額外的空格。

示例 1：

輸入：s = "the sky is blue"
輸出："blue is sky the"

示例 2：

輸入：s = " ?hello world ?"
輸出："world hello"
解釋：反轉后的字符串中不能存在前導空格和尾隨空格。

示例 3：

輸入：s = "a good ? example"
輸出："example good a"
解釋：如果兩個單詞間有多余的空格，反轉后的字符串需要將單詞間的空格減少到僅有一個。

提示：

• 1 <= s.length <= 104
• s?包含英文大小寫字母、數字和空格?' '
• s?中?至少存在一個?單詞

思路：

1. reverse?函數用于翻轉字符串的指定區間，采用左閉右閉的區間寫法。
2. removeExtraSpaces?函數用于去除字符串中的多余空格，通過定義快指針和慢指針，將冗余空格移除。
3. reverseWords?函數首先調用?removeExtraSpaces?去除多余空格，然后將整個字符串進行翻轉。
4. 遍歷字符串，當遇到空格或字符串末尾時，表示一個單詞結束，對該單詞進行翻轉。
5. 最后返回翻轉后的字符串。

代碼：

class Solution {
public:void reverse(string& s, int start, int end){ //翻轉，區間寫法：左閉右閉 []for (int i = start, j = end; i < j; i++, j--) {swap(s[i], s[j]);}}
void removeExtraSpaces(string& s) {int slowIndex = 0, fastIndex = 0; // 定義快指針，慢指針// 去掉字符串前面的空格while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {fastIndex++;}for (; fastIndex < s.size(); fastIndex++) {// 去掉字符串中間部分的冗余空格if (fastIndex - 1 > 0&& s[fastIndex - 1] == s[fastIndex]&& s[fastIndex] == ' ') {continue;} else {s[slowIndex++] = s[fastIndex];}}if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格s.resize(slowIndex - 1);} else {s.resize(slowIndex); // 重新設置字符串大小}
}string reverseWords(string s) {removeExtraSpaces(s); //去除多余空格，保證單詞之間之只有一個空格，且字符串首尾沒空格。reverse(s, 0, s.size() - 1);int start = 0; //removeExtraSpaces后保證第一個單詞的開始下標一定是0。for (int i = 0; i <= s.size(); ++i) {if (i == s.size() || s[i] == ' ') { //到達空格或者串尾，說明一個單詞結束。進行翻轉。reverse(s, start, i - 1); //翻轉，注意是左閉右閉 []的翻轉。start = i + 1; //更新下一個單詞的開始下標start}}return s;}
};

3尋找數組的中心下標

給你一個整數數組?nums?，請計算數組的?中心下標?。

數組?中心下標?是數組的一個下標，其左側所有元素相加的和等于右側所有元素相加的和。

如果中心下標位于數組最左端，那么左側數之和視為?0?，因為在下標的左側不存在元素。這一點對于中心下標位于數組最右端同樣適用。

如果數組有多個中心下標，應該返回?最靠近左邊?的那一個。如果數組不存在中心下標，返回?-1?。

示例 1：

輸入：nums = [1, 7, 3, 6, 5, 6]
輸出：3
解釋：
中心下標是 3 。
左側數之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右側數之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

輸入：nums = [1, 2, 3]
輸出：-1
解釋：
數組中不存在滿足此條件的中心下標。

示例 3：

輸入：nums = [2, 1, -1]
輸出：0
解釋：
中心下標是 0 。
左側數之和 sum = 0 ，（下標 0 左側不存在元素），
右側數之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

提示：

• 1 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

思路：

1. 遍歷一遍數組，計算數組所有元素的總和。
2. 定義左半部分的和和右半部分的和，初始值均為0。
3. 遍歷數組，累加左半部分的和，并計算右半部分的和。
4. 若左半部分和右半部分相等，則當前索引為中心索引，返回該索引值。
5. 若遍歷結束仍未找到中心索引，則返回 -1。

代碼：

class Solution {
public:int pivotIndex(vector<int>& nums) {int sum=0;for(int num:nums) sum+=num; // 計算數組總和int leftsum=0; // 左半部分的和int rightsum=0; // 右半部分的和for(int i=0;i<nums.size();i++){leftsum +=nums[i]; // 左半部分累加當前元素rightsum = sum-leftsum + nums[i]; // 總和減去左半部分，再加上當前元素，得到右半部分的和if(leftsum==rightsum) return i; // 如果左半部分和右半部分相等，則當前索引為中心索引} return -1; // 若不存在中心索引，則返回 -1}
};

4在排序數組中查找元素的第一個和最后一個位置

給你一個按照非遞減順序排列的整數數組?nums，和一個目標值?target。請你找出給定目標值在數組中的開始位置和結束位置。

如果數組中不存在目標值?target，返回?[-1, -1]。

你必須設計并實現時間復雜度為?O(log n)?的算法解決此問題。

示例 1：

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

示例?2：

輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]

示例 3：

輸入：nums = [], target = 0
輸出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109?<= nums[i]?<= 109
• nums?是一個非遞減數組
• -109?<= target?<= 109

思路：

尋找target在數組里的左右邊界，有如下三種情況：

• 情況一：target 在數組范圍的右邊或者左邊，例如數組{3, 4, 5}，target為2或者數組{3, 4, 5},target為6，此時應該返回{-1, -1}
• 情況二：target 在數組范圍中，且數組中不存在target，例如數組{3,6,7},target為5，此時應該返回{-1, -1}
• 情況三：target 在數組范圍中，且數組中存在target，例如數組{3,6,7},target為6，此時應該返回{1, 1}

1. 尋找左邊界和右邊界：我們可以通過兩次二分查找來找到目標值在數組中的左邊界和右邊界。對于尋找左邊界，我們調整二分查找的條件，當?nums[middle] >= target?時更新右邊界，當?nums[middle] < target?時更新左邊界；對于尋找右邊界，我們調整二分查找的條件，當?nums[middle] > target?時更新右邊界，當?nums[middle] <= target?時更新左邊界。

2. 情況判斷：根據左右邊界的情況，我們可以判斷出目標值在數組中的情況。如果左右邊界中任一為-2，則表示目標值不存在，返回{-1, -1}；如果左右邊界相差大于1，則表示目標值存在且范圍大于1，返回范圍內的左右邊界；如果左右邊界相差為1或未找到目標值，則返回{-1, -1}。

代碼：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int leftBorder = getLeftBorder(nums, target); // 獲取左邊界int rightBorder = getRightBorder(nums, target); // 獲取右邊界// 情況一：沒有找到目標值，返回{-1, -1}if (leftBorder == -2 || rightBorder == -2) return {-1, -1};// 情況三：找到了目標值并且范圍大于1，返回范圍內的左右邊界if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};// 情況二：找到了目標值但范圍為1或未找到，返回{-1, -1}return {-1, -1};}
private:int getRightBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int rightBorder = -2; // 記錄一下rightBorder沒有被賦值的情況while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] > target) {right = middle - 1;} else { // 尋找右邊界，nums[middle] == target的時候更新leftleft = middle + 1;rightBorder = left;}}return rightBorder;}int getLeftBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int leftBorder = -2; // 記錄一下leftBorder沒有被賦值的情況while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] >= target) { // 尋找左邊界，nums[middle] == target的時候更新rightright = middle - 1;leftBorder = right;} else {left = middle + 1;}}return leftBorder;}
};