訓(xùn)練營任務(wù)

第一章 數(shù)組part01

今日任務(wù)

數(shù)組理論基礎(chǔ)，704. 二分查找，27. 移除元素

詳細(xì)布置

數(shù)組理論基礎(chǔ)

文章鏈接：https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

題目建議： 了解一下數(shù)組基礎(chǔ)，以及數(shù)組的內(nèi)存空間地址，數(shù)組也沒那么簡單。

704. 二分查找

題目建議： 大家能把 704 掌握就可以，35.搜索插入位置 和 34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置 ，如果有時(shí)間就去看一下，沒時(shí)間可以先不看，二刷的時(shí)候在看。

先把 704寫熟練，要熟悉 根據(jù) 左閉右開，左閉右閉 兩種區(qū)間規(guī)則 寫出來的二分法。

題目鏈接：https://leetcode.cn/problems/binary-search/

文章講解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html

視頻講解：https://www.bilibili.com/video/BV1fA4y1o715

27. 移除元素

題目建議： 暴力的解法，可以鍛煉一下我們的代碼實(shí)現(xiàn)能力，建議先把暴力寫法寫一遍。 雙指針法 是本題的精髓，今日需要掌握，至于拓展題目可以先不看。

題目鏈接：https://leetcode.cn/problems/remove-element/

文章講解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html

視頻講解：https://www.bilibili.com/video/BV12A4y1Z7LP

數(shù)組基礎(chǔ)理論

https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

二分查找

二分查找關(guān)鍵點(diǎn)，區(qū)間設(shè)置定義與邊界條件

二分查找涉及的很多的邊界條件，邏輯比較簡單，但就是寫不好。例如到底是 while(left < right) 還是 while(left <= right)，到底是right = middle呢，還是要right = middle - 1呢？

大家寫二分法經(jīng)常寫亂，主要是因?yàn)?strong>對區(qū)間的定義沒有想清楚，區(qū)間的定義就是不變量。要在二分查找的過程中，保持不變量，就是在while尋找中每一次邊界的處理都要堅(jiān)持根據(jù)區(qū)間的定義來操作，這就是循環(huán)不變量規(guī)則。

寫二分法，區(qū)間的定義一般為兩種，左閉右閉即[left, right]，或者左閉右開即[left, right)。

下面我用這兩種區(qū)間的定義分別講解兩種不同的二分寫法。

二分法第一種寫法

第一種寫法，我們定義 target 是在一個(gè)在左閉右閉的區(qū)間里，也就是[left, right] （這個(gè)很重要非常重要）。

區(qū)間的定義這就決定了二分法的代碼應(yīng)該如何寫，因?yàn)槎xtarget在[left, right]區(qū)間，所以有如下兩點(diǎn)：

• while (left <= right) 要使用 <= ，因?yàn)閘eft == right是有意義的，所以使用 <=
• if (nums[middle] > target) right 要賦值為 middle - 1，因?yàn)楫?dāng)前這個(gè)nums[middle]一定不是target，那么接下來要查找的左區(qū)間結(jié)束下標(biāo)位置就是 middle - 1
  例如在數(shù)組：1,2,3,4,7,9,10中查找元素2，如圖所示：
  [圖片上傳失敗...(image-4ac6c8-1712762842790)]

二分法第二種寫法

如果說定義 target 是在一個(gè)在左閉右開的區(qū)間里，也就是[left, right) ，那么二分法的邊界處理方式則截然不同。

有如下兩點(diǎn)：

• while (left < right)，這里使用 < ,因?yàn)閘eft == right在區(qū)間[left, right)是沒有意義的
• if (nums[middle] > target) right 更新為 middle，因?yàn)楫?dāng)前nums[middle]不等于target，去左區(qū)間繼續(xù)尋找，而尋找區(qū)間是左閉右開區(qū)間，所以right更新為middle，即：下一個(gè)查詢區(qū)間不會(huì)去比較nums[middle]

在數(shù)組：1,2,3,4,7,9,10中查找元素2，如圖所示：（注意和方法一的區(qū)別）

[圖片上傳失敗...(image-d0b3f1-1712762842790)]

文章講解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html

視頻講解：https://www.bilibili.com/video/BV1fA4y1o715

題目

704. 二分查找

力扣題目鏈接(opens new window)

給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target ，寫一個(gè)函數(shù)搜索 nums 中的 target，如果目標(biāo)值存在返回下標(biāo)，否則返回 -1。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9     
輸出: 4       
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4     

示例 2:

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

提示：

• 你可以假設(shè) nums 中的所有元素是不重復(fù)的。
• n 將在 [1, 10000]之間。
• nums 的每個(gè)元素都將在 [-9999, 9999]之間。

力扣題目鏈接

python

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while(left <= right) :
            mid = left + (right -  left) / 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else :
                right = mid - 1
        return -1

c++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } 
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};

35.搜索插入位置

力扣題目鏈接(opens new window)

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

你可以假設(shè)數(shù)組中無重復(fù)元素。

示例 1:

• 輸入: [1,3,5,6], 5
• 輸出: 2

示例 2:

• 輸入: [1,3,5,6], 2
• 輸出: 1

示例 3:

• 輸入: [1,3,5,6], 7
• 輸出: 4

示例 4:

• 輸入: [1,3,5,6], 0
• 輸出: 0

python

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while(left <= right) :
            mid = left + (right - left) / 2
            if nums[mid] == target :
                return mid
            if nums[mid] < target :
                left = mid + 1
            else :
                right = mid - 1
        if nums[mid] > target:
            return mid
        else :
            return mid + 1

c++

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return nums[mid] > target ? mid  : mid + 1;
    }
};

34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

力扣鏈接(opens new window)

給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。

進(jìn)階：你可以設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 的算法解決此問題嗎？

示例 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]

c++

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left  + (right - left) / 2;
            if(nums[mid] == target) {
                left = mid;
                right = mid;
                while (left - 1 >= 0 && nums[left - 1] == target) {
                    left --;
                }
                while (right + 1 <= nums.size() - 1 && nums[right + 1] == target) {
                    right ++;
                }
                return vector<int>{left, right};
            }
            if( nums[mid] < target) {
                left = mid + 1;
                while(left <= right && nums[left] == nums[mid]) {
                    left ++;
                } 
            } else {
                right = mid - 1;
                while (left <= right && nums[right] == nums[mid]) {
                    right --;
                }
            }
        }
        return vector<int>{-1, -1};
    }
};

python

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        left = 0
        right = len(nums) - 1
        while (left <= right) :
            mid = left + (right - left) / 2
            if (nums[mid] == target) :
                left = mid
                right = mid
                while (left - 1 >= 0 and nums[left - 1] == target) :
                    left -= 1
                while (right + 1 <= len(nums) - 1 and nums[right + 1] == target) :
                    right += 1
                return [left, right]
            if (nums[mid] < target) :
                left = mid + 1
                while (left <= right and nums[left] == nums[mid]) :
                    left += 1
            else :
                right = mid - 1 
                while (left <= right and nums[right] == nums[mid]) :
                    right -= 1 
        return [-1, -1]

69.x 的平方根

image.png

c++

class Solution {
public:
    int mySqrt(int x) {
        int left = 0, right = x, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if((long long) mid * mid == x) {
                return mid;
            }
            if ((long long) mid * mid < x) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
};

python

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left = 0
        right = x
        ans = -1
        while (left <= right) :
            mid = left + (right - left) / 2
            if (mid * mid == x) :
                return mid
            if (mid * mid < x) :
                ans = mid
                left = mid + 1
            else :
                right = mid - 1
        return ans

題解

image.png

image.png

image.png

27. 移除元素

題目建議： 暴力的解法，可以鍛煉一下我們的代碼實(shí)現(xiàn)能力，建議先把暴力寫法寫一遍。 雙指針法 是本題的精髓，今日需要掌握，至于拓展題目可以先不看。

題目鏈接：https://leetcode.cn/problems/remove-element/

文章講解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html

視頻講解：https://www.bilibili.com/video/BV12A4y1Z7LP

python

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        left, right = 0, len(nums) 
        while (left < right) :
            if (nums[left] == val) :
                right = right - 1
                tmp = nums[left]
                nums[left] = nums[right]
                nums[right] = tmp
            else :
                left = left + 1
        return right

c++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size();
        while ( left < right ) {
            if (nums[left] == val) {
                right = right - 1;
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            } else {
                left += 1;
            }
        } 
        return right;
    }
};