📝前言說明:
- 本專欄主要記錄本人的基礎算法學習以及LeetCode刷題記錄,按專題劃分
- 每題主要記錄:(1)本人解法 + 本人屎山代碼;(2)優質解法 + 優質代碼;(3)精益求精,更好的解法和獨特的思想(如果有的話)
- 文章中的理解僅為個人理解。如有錯誤,感謝糾錯
🎬個人簡介:努力學習ing
📋本專欄:C++刷題專欄
📋其他專欄:C語言入門基礎,python入門基礎,C++學習筆記,Linux
🎀CSDN主頁 愚潤澤
視頻
- 69. x 的平方根
- 個人解
- 35. 搜索插入位置
- 個人解
- 852. 山脈數組的峰頂索引
- 個人解
- 162. 尋找峰值
- 個人解
- 153. 尋找旋轉排序數組中的最小值
- 個人解
- 優質解
- LCR 173. 點名
- 個人解
69. x 的平方根
個人解
思路:
- 確定答案區間:
[0, min(x, 46341)]
(46341 是 2^31 - 1 的平方根 + 1) - 問題轉換成:找平方 <= x 的右端點(因為題目向下取整)
mid
選取判斷:因為向下取整,left = mid
會死循環
用時:
屎山代碼:
class Solution {
public:int mySqrt(int x) {int left = 0, right = min(x, 46341);while(left < right) {unsigned int mid = left + (right - left + 1) / 2;if(mid * mid <= x)left = mid;elseright = mid - 1;}return left;}
};
時間復雜度:O(n)
空間復雜度:O(1)
35. 搜索插入位置
個人解
思路:
- 題目意思:有
target
就返回target
,沒有就返回>target
的第一個位置 - 總結一下:就是返回
>= target
的第一個位置 - 細節處理:模擬三種情況:1,正常找到
target
或者正常在數組中間插入;2,全部值都小于target
;3,全部值都大于target
(在這道題中要特殊處理全小于target
的情況)
用時:5:00
屎山代碼:
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < target)left = mid + 1;elseright = mid;}// 特殊處理全小于target的情況if(nums[right] >= target)return right;elsereturn nums.size();}
};
時間復雜度:O(logN)
空間復雜度:O(1)
852. 山脈數組的峰頂索引
個人解
思路:
- 二段性:每次和右邊的數比較
- 右邊的數不存在 / 右邊的數 <= 當前數:山峰肯定在
[left, mid]
- 右邊的數 > 當前數:山峰肯定在
[mid + 1, right]
用時:5:00
屎山代碼:
class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 0, right = arr.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(mid + 1 == arr.size() || arr[mid + 1] <= arr[mid])right = mid;elseleft = mid + 1;}return right;}
};
時間復雜度:O(logN)
空間復雜度:O(1)
162. 尋找峰值
個人解
思路:
- 這道題的提示3:
nums[i] != nums[i + 1]
,太重要了(保證了一定有一個峰值) - 每次和右側數字比較
> 右側的數字
:峰值一定在[left ,mid]
(mid
有可能是峰值)< 右側的數字
:峰值一定在[mid + 1, right]
用時:10:00(一開始沒看到提示3)
屎山代碼:
class Solution {
public:int findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[mid + 1])right = mid;elseleft = mid + 1;}return right;}
};
時間復雜度:O(logN)
空間復雜度:O(1)
153. 尋找旋轉排序數組中的最小值
個人解
思路:
- 利用數組的有序性二分,找最小
- 但是問題在于:這里在翻轉以后可能出現兩段數組!一段數組上查找的時候,要判斷最小值會不會出行在另一段數組上
- 如何判斷呢?如果真的有兩段數組,則第二段數組的最大值一定是
nums[n-1]
,如果當前nums[mid] < nums[n - 1]
代表在正確的數組上查找了,反之就是在錯誤的數組上查找了,要讓left
移動到右邊
用時:15:00
屎山代碼:
class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size();int left = 0, right = n - 1;while(left < right){int mid = left + (right - left) / 2;if(mid + 1 == n || (nums[mid] < nums[mid + 1] && nums[mid] < nums[n - 1]))right = mid;elseleft = mid + 1;}return nums[right];}
};
時間復雜度:O(log n)
空間復雜度:O(1)
優質解
看了官方題解以后想到的:
- 如果翻轉了,產生了兩個數組,則最小值,一定在第二個數組上!!!
- 并且,前一個數組的元素都大于第二個數組的元素
- 那我們的比較基準就可以和最后一個值進行比較
> nums[n-1]
:數組錯了,答案一定在[mid + 1, right]
< nums[n-1]
:答案一定在[left, mid]
,mid
也有可能是答案
代碼:
class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size();int left = 0, right = n - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < nums[n - 1])right = mid;elseleft = mid + 1;}return nums[right];}
};
LCR 173. 點名
個人解
思路:
- 因為數組是升序排序的,且學號從0開始,利用學號和下標對應的特點,找出缺失值在哪一遍
- mid == records[mid] ,則缺失值在 [mid + 1, right]
- mid > records[left, mid]
- 特殊判斷,最后一個同學缺席
用時:7:00
屎山代碼:
class Solution {
public:int takeAttendance(vector<int>& records) {int n = records.size();if(records[n - 1] == n - 1)return n;int left = 0, right = n - 1;while(left < right){int mid = left + (right - left) / 2;if(mid == records[mid])left = mid + 1;elseright = mid;}return records[right] - 1;}
};
時間復雜度:O(log n)
空間復雜度:O(1)
🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助,那簡直是太酷啦!
若有不足,還請大家多多指正,我們一起學習交流!
📢公主,王子:點贊👍→收藏?→關注🔍
感謝大家的觀看和支持!祝大家都能得償所愿,天天開心!!!