【原】數(shù)據(jù)結(jié)構(gòu)與算法：05 Leetcode同步練習(xí)（一）

老馬的程序人生 2020-09-14

展開全文

題目01：兩數(shù)之和
題目02：刪除排序數(shù)組中的重復(fù)項(xiàng)
題目03：移除元素
題目04：最大子序和
題目05：盛最多水的容器
題目06：搜索旋轉(zhuǎn)排序數(shù)組
題目07：數(shù)組中的第K個(gè)最大元素
題目08：除自身以外數(shù)組的乘積
題目09：尋找兩個(gè)有序數(shù)組的中位數(shù)
題目10：缺失的第一個(gè)正數(shù)

題目01：兩數(shù)之和

題號(hào)：1
難度：簡(jiǎn)單
https:///problems/two-sum/

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè)整數(shù)，并返回他們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。

示例1:

給定 nums = [2, 7, 11, 15], target = 9

因?yàn)?nbsp;nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

示例2：

給定 nums = [230, 863, 916, 585, 981, 404, 316, 785, 88, 12, 70, 435, 384, 778, 887, 755, 740, 337, 86, 92, 325, 422, 815, 650, 920, 125, 277, 336, 221, 847, 168, 23, 677, 61, 400, 136, 874, 363, 394, 199, 863, 997, 794, 587, 124, 321, 212, 957, 764, 173, 314, 422, 927, 783, 930, 282, 306, 506, 44, 926, 691, 568, 68, 730, 933, 737, 531, 180, 414, 751, 28, 546, 60, 371, 493, 370, 527, 387, 43, 541, 13, 457, 328, 227, 652, 365, 430, 803, 59, 858, 538, 427, 583, 368, 375, 173, 809, 896, 370, 789], target = 542

因?yàn)?nbsp;nums[28] + nums[45] = 221 + 321 = 542，所以返回 [28, 45]

參考代碼：

思路：直接利用暴力匹配算法。

執(zhí)行結(jié)果：通過
執(zhí)行用時(shí)：432 ms, 在所有 C# 提交中擊敗了 65.82% 的用戶
內(nèi)存消耗：30.8 MB, 在所有 C# 提交中擊敗了 8.67% 的用戶

public class Solution 
{
    public int[] TwoSum(int[] nums, int target) 
    {
        int[] result = new int[2];
        for (int i = 0; i < nums.Length - 1; i++)
        {
            int find = target - nums[i];
            for (int j = i + 1; j < nums.Length; j++)
            {
                if (find == nums[j])
                {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }
}

題目02：刪除排序數(shù)組中的重復(fù)項(xiàng)

題號(hào)：26
難度：簡(jiǎn)單
https:///problems/remove-duplicates-from-sorted-array/

給定一個(gè) 排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。

不要使用額外的數(shù)組空間，你必須在 原地修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。

示例 1:

給定數(shù)組 nums = [1,1,2], 
函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2。 
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

示例 2:

給定 nums = [0,0,1,1,1,2,2,3,3,4],
函數(shù)應(yīng)該返回新的長(zhǎng)度 5, 并且原數(shù)組 nums 的前五個(gè)元素被修改為 0, 1, 2, 3, 4。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

說明:

為什么返回?cái)?shù)值是整數(shù)，但輸出的答案是數(shù)組呢?

請(qǐng)注意，輸入數(shù)組是以“引用”方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的。

你可以想象內(nèi)部操作如下:

// nums 是以“引用”方式傳遞的。也就是說，不對(duì)實(shí)參做任何拷貝
int len = removeDuplicates(nums);

// 在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的。
// 根據(jù)你的函數(shù)返回的長(zhǎng)度, 它會(huì)打印出數(shù)組中該長(zhǎng)度范圍內(nèi)的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

參考代碼：

思路：雙索引法，就是一個(gè)快索引一個(gè)慢索引，j快i慢，當(dāng)nums[j] == nums[i]時(shí)，j++就可以跳過重復(fù)項(xiàng)，不相等時(shí)，讓i++并讓nums[i] = nums[j]，把值復(fù)制過來繼續(xù)執(zhí)行到末尾即可，時(shí)間復(fù)雜度為O(n)。

執(zhí)行結(jié)果：通過
執(zhí)行用時(shí)：300 ms, 在所有 C# 提交中擊敗了 64.43% 的用戶
內(nèi)存消耗：33.5 MB, 在所有 C# 提交中擊敗了 5.48% 的用戶

public class Solution 
{
    public int RemoveDuplicates(int[] nums) 
    {
        if (nums.Length < 2)
            return nums.Length;
            
        int i = 0;
        for (int j = 1; j < nums.Length; j++)
        {
            if (nums[j] != nums[i])
            {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;        
    }
}

題目03：移除元素

題號(hào)：27
難度：簡(jiǎn)單
https:///problems/remove-element/

給定一個(gè)數(shù)組nums和一個(gè)值val，你需要原地移除所有數(shù)值等于val的元素，返回移除后數(shù)組的新長(zhǎng)度。

不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。

元素的順序可以改變。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

示例 1:

給定 nums = [3,2,2,3], val = 3,

函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且 nums 中的前兩個(gè)元素均為 2。

你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

示例 2:

給定 nums = [0,1,2,2,3,0,4,2], val = 2,

函數(shù)應(yīng)該返回新的長(zhǎng)度 5, 并且 nums 中的前五個(gè)元素為 0, 1, 3, 0, 4。

注意這五個(gè)元素可為任意順序。

你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

示例 3:

輸入：[] value = 0

輸出：0

示例 4:

輸入：[1] value = 1

輸出：0

示例 5:

輸入：[4,5] value = 5

輸出：1

說明:

為什么返回?cái)?shù)值是整數(shù)，但輸出的答案是數(shù)組呢?

請(qǐng)注意，輸入數(shù)組是以“引用”方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的。

你可以想象內(nèi)部操作如下:

// nums 是以“引用”方式傳遞的。也就是說，不對(duì)實(shí)參作任何拷貝
int len = removeElement(nums, val);

// 在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的。
// 根據(jù)你的函數(shù)返回的長(zhǎng)度, 它會(huì)打印出數(shù)組中該長(zhǎng)度范圍內(nèi)的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

參考代碼：

思路：雙索引法，利用雙索引i和j，i為慢索引拖后，j為快索引向前沖。如果nums[j]!=val，將num[j]的值賦給num[i]，循環(huán)結(jié)束后，i指針前面的元素，即為需要保留的元素，從而達(dá)到了移除元素的目的，時(shí)間復(fù)雜度為 O(n)。

執(zhí)行結(jié)果：通過
執(zhí)行用時(shí)：272 ms, 在所有 C# 提交中擊敗了 94.41% 的用戶
內(nèi)存消耗：29.9 MB, 在所有 C# 提交中擊敗了 5.21% 的用戶

public class Solution 
{
    public int RemoveElement(int[] nums, int val) 
    {
        int i = 0;
        for (int j = 0; j < nums.Length; j++)
        {
            if (nums[j] != val)
            {
                nums[i] = nums[j];
                    i++;
            }
        }
        return i;  
    }
}

題目04：最大子序和

題號(hào)：53
難度：簡(jiǎn)單
https:///problems/maximum-subarray/

給定一個(gè)整數(shù)數(shù)組nums，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

示例 1:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

示例 2:

輸入: [-2,1],
輸出: 1

進(jìn)階:

如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為O(n)的解法，嘗試使用更為精妙的分治法求解。

參考代碼：

思路：利用暴力算法。

狀態(tài)：通過
執(zhí)行用時(shí): 596 ms, 在所有 C# 提交中擊敗了 14.18% 的用戶
內(nèi)存消耗: 24.5 MB, 在所有 C# 提交中擊敗了 5.88% 的用戶

public class Solution {
    public int MaxSubArray(int[] nums) {
        int len = nums.Length;
        if (len == 0)
            return 0;
        if (len == 1)
            return nums[0];
        int max = int.MinValue;

        for (int i = 0; i < len; i++)
        {
            int sum = nums[i];
            if (sum > max)
            {
                max = sum;
            }
            for (int j = i + 1; j < len; j++)
            {
                sum += nums[j];
                if (sum > max)
                {
                    max = sum;
                }
            }
        }
        return max;        
    }
}

題目05：盛最多水的容器

題號(hào)：11
難度：中等
https:///problems/container-with-most-water/

給定n個(gè)非負(fù)整數(shù)a1，a2，...，an，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn)(i, ai)。在坐標(biāo)內(nèi)畫n條垂直線，垂直線i 的兩個(gè)端點(diǎn)分別為(i, ai)和(i, 0)。找出其中的兩條線，使得它們與x軸共同構(gòu)成的容器可以容納最多的水。

說明：你不能傾斜容器，且n的值至少為 2。

圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。

示例:

輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49

參考代碼：

思路：利用雙索引的方法。

以0-7走到1-7這一步為例，解釋為什么放棄0-6這一分支：

用h(i)表示第i條線段的高度，S(ij)表示第i條線段和第j條線段圈起來的面積。

已知 h(0) < h(7)，從而S(07) = h(0) * 7。

有S(06) = min(h(0), h(6)) * 6。

當(dāng)h(0) <= h(6)，有S(06) = h(0) * 6；
當(dāng)h(0) > h(6)，有S(06) = h(6) * 6，S(06) < h(0) * 6。

由此可知，S(06)必然小于S(07)。

把每一棵子樹按照同樣的方法分析，很容易可以知道，雙索引法走的路徑包含了最大面積。

狀態(tài)：通過
50 / 50 個(gè)通過測(cè)試用例
執(zhí)行用時(shí): 144 ms, 在所有 C# 提交中擊敗了 99.64% 的用戶
內(nèi)存消耗: 26.6 MB, 在所有 C# 提交中擊敗了 5.45% 的用戶

public class Solution 
{
    public int MaxArea(int[] height) 
    {
        int i = 0, j = height.Length - 1;
        int max = int.MinValue;
        while (i < j)
        {
            int temp = (j - i) * Math.Min(height[i], height[j]);
            if (temp > max)
            {
                max = temp;
            }
            if (height[i] < height[j])
            {
                i++;
            }
            else
            {
                j--;
            }
        }
        return max;        
    }
}

題目06：搜索旋轉(zhuǎn)排序數(shù)組

題號(hào)：33
難度：中等
https:///problems/search-in-rotated-sorted-array/

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。

( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。

搜索一個(gè)給定的目標(biāo)值，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引，否則返回 -1 。

你可以假設(shè)數(shù)組中不存在重復(fù)的元素。

你的算法時(shí)間復(fù)雜度必須是O(log n)級(jí)別。

示例 1:

輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4

示例 2:

輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1

示例 3:

輸入: nums = [5,1,3], target = 5
輸出: 0

示例 4:

輸入: nums = [4,5,6,7,8,1,2,3], target = 8
輸出: 4

示例 5:

輸入: nums = [3,1], target = 1
輸出: 1

參考代碼：

思路：利用二分法。

狀態(tài)：通過
執(zhí)行用時(shí): 128 ms, 在所有 C# 提交中擊敗了 97.17% 的用戶
內(nèi)存消耗: 23.8 MB, 在所有 C# 提交中擊敗了 12.00% 的用戶

public class Solution 
{
    public int Search(int[] nums, int target) 
    {
        int i = 0, j = nums.Length - 1;
        while (i <= j)
        {
            int mid = (i + j) / 2;
            if (nums[mid] == target)
                return mid;

            if (nums[mid] >= nums[i])
            {
                //左半部分有序
                if (target > nums[mid])
                {
                    i = mid + 1;
                }
                else
                {
                    if (target == nums[i])
                        return i;

                    if (target > nums[i])
                        j = mid - 1;
                    else
                        i = mid + 1;
                }
            }
            else
            {
                if (target < nums[mid])
                {
                    j = mid - 1;
                }
                else
                {
                    if (target == nums[j])
                        return j;
                    if (target < nums[j])
                        i = mid + 1;
                    else
                        j = mid - 1;
                }
            }
        }
        return -1;        
    }
}

題目07：數(shù)組中的第K個(gè)最大元素

題號(hào)：215
難度：中等
https:///problems/kth-largest-element-in-an-array/

在未排序的數(shù)組中找到第 k 個(gè)最大的元素。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。

示例 1:

輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5

示例 2:

輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4

說明:

你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長(zhǎng)度。

參考代碼：

思路：利用排序的方法。

狀態(tài)：通過
執(zhí)行用時(shí): 152 ms, 在所有 C# 提交中擊敗了 76.47% 的用戶
內(nèi)存消耗: 24.6 MB, 在所有 C# 提交中擊敗了 5.55% 的用戶

public class Solution
{
    public int FindKthLargest(int[] nums, int k)
    {
        nums = nums.OrderBy(a => a).ToArray();
        return nums[nums.Length - k];
    }
}

題目08：除自身以外數(shù)組的乘積

題號(hào)：238
難度：中等
https:///problems/product-of-array-except-self/

給定長(zhǎng)度為n的整數(shù)數(shù)組nums，其中n > 1，返回輸出數(shù)組output，其中output[i]等于 nums中除nums[i]之外其余各元素的乘積。

示例:

輸入: [1,2,3,4]
輸出: [24,12,8,6]

說明: 請(qǐng)不要使用除法，且在O(n) 時(shí)間復(fù)雜度內(nèi)完成此題。

進(jìn)階：

你可以在常數(shù)空間復(fù)雜度內(nèi)完成這個(gè)題目嗎？（出于對(duì)空間復(fù)雜度分析的目的，輸出數(shù)組不被視為額外空間。）

參考代碼：

思路：乘積 = 當(dāng)前數(shù)左邊的乘積 * 當(dāng)前數(shù)右邊的乘積

                [1, 2, 3, 4]
   左邊的乘積    [1, 1, 2, 6]
   右邊的乘積    [24,12,4, 1]
結(jié)果 = 左*右     [24,12,8, 6]

狀態(tài)：通過
執(zhí)行用時(shí): 304 ms, 在所有 C# 提交中擊敗了 100.00% 的用戶
內(nèi)存消耗: 34.6 MB, 在所有 C# 提交中擊敗了 100.00% 的用戶

public class Solution
{
    public int[] ProductExceptSelf(int[] nums)
    {
        int len = nums.Length;
        int[] output1 = new int[len];//正向乘積
        int[] output2 = new int[len];//反向乘積
        output1[0] = 1;
        output2[len - 1] = 1;
        for (int i = 1; i < len; i++)
        {
            output1[i] = output1[i - 1]*nums[i - 1];
            output2[len - i - 1] = output2[len - i]*nums[len - i];
        }
        for (int i = 0; i < len; i++)
        {
            output1[i] *= output2[i];
        }
        return output1;
    }
}

題目09：尋找兩個(gè)有序數(shù)組的中位數(shù)

題號(hào)：4
難度：困難
https:///problems/median-of-two-sorted-arrays/

給定兩個(gè)大小為m和n的有序數(shù)組nums1和nums2。

請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù)，并且要求算法的時(shí)間復(fù)雜度為O(log(m + n))。

你可以假設(shè)nums1和nums2不會(huì)同時(shí)為空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

則中位數(shù)是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

則中位數(shù)是 (2 + 3)/2 = 2.5

參考代碼：

思路：利用二分策略。

中位數(shù)：用來將一個(gè)集合劃分為兩個(gè)長(zhǎng)度相等的子集，其中一個(gè)子集中的元素總是大于另一個(gè)子集中的元素。

由于題目要求時(shí)間復(fù)雜度為O(log(m + n))，所以不能從兩個(gè)有序數(shù)組的首尾挨個(gè)遍歷來找到中位數(shù)（復(fù)雜度 O(m + n)）；而是要通過二分策略，通過每次比較，能夠直接按比例的刷掉一組數(shù)字，最后找到中位數(shù)（復(fù)雜度O(log(m + n))）。

nums1: [a1,a2,a3,...am]
nums2: [b1,b2,b3,...bn]

[nums1[:i],nums2[:j] | nums1[i:], nums2[j:]]

nums1 取 i 個(gè)數(shù)的左半邊
nums2 取 j = (m+n+1)/2 - i 的左半邊

只要保證左右兩邊 個(gè)數(shù) 相同，中位數(shù)就在 | 這個(gè)邊界旁邊產(chǎn)生，從而可以利用二分法找到合適的i。

狀態(tài)：通過
執(zhí)行用時(shí): 160 ms, 在所有 C# 提交中擊敗了 99.18% 的用戶
內(nèi)存消耗: 26.8 MB, 在所有 C# 提交中擊敗了 5.05% 的用戶

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.Length;
        int n = nums2.Length;
        if (m > n)
            return FindMedianSortedArrays(nums2, nums1);

        int k = (m + n + 1)/2;
        int left = 0;
        int right = m;
        while (left < right)
        {
            int i = (left + right)/2;
            int j = k - i;
            if (nums1[i] < nums2[j - 1])
                left = i + 1;
            else
                right = i;
        }
        int m1 = left;
        int m2 = k - left;
        int c1 = Math.Max(m1 == 0 ? int.MinValue : nums1[m1 - 1],
            m2 == 0 ? int.MinValue : nums2[m2 - 1]);

        if ((m + n)%2 == 1)
            return c1;

        int c2 = Math.Min(m1 == m ? int.MaxValue : nums1[m1],
            m2 == n ? int.MaxValue : nums2[m2]);
        return (c1 + c2)*0.5;        
    }
}

題目10：缺失的第一個(gè)正數(shù)

題號(hào)：41
難度：困難
https:///problems/first-missing-positive/

給定一個(gè)未排序的整數(shù)數(shù)組，找出其中沒有出現(xiàn)的最小的正整數(shù)。

示例1:

輸入: [1,2,0]
輸出: 3

示例2:

輸入: [3,4,-1,1]
輸出: 2

示例3:

輸入: [7,8,9,11,12]
輸出: 1

示例4:

輸入: [1,1]
輸出: 2

實(shí)例5:

輸入: []
輸出: 1

說明:

你的算法的時(shí)間復(fù)雜度應(yīng)為O(n)，并且只能使用常數(shù)級(jí)別的空間。

參考代碼：

思路：把數(shù)組進(jìn)行一次“排序”，“排序”的規(guī)則是：如果這個(gè)數(shù)字i落在“區(qū)間范圍里”，i就應(yīng)該放在索引為i - 1的位置上。

執(zhí)行結(jié)果：通過
執(zhí)行用時(shí)：100 ms, 在所有 C# 提交中擊敗了 93.75% 的用戶
內(nèi)存消耗：24.2 MB, 在所有 C# 提交中擊敗了 97.44% 的用戶

public class Solution {
    public int FirstMissingPositive(int[] nums) {
        int len = nums.Length;
        for (int i = 0; i < len; i++)
        {
            while (nums[i] != i + 1 && nums[i] <= len && nums[i] > 0 && nums[i] != nums[nums[i] - 1])
            {
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }
        for (int i = 0; i < len; i++)
        {
            if (nums[i] != i + 1)
            {
                return i + 1;
            }
        }
        return len + 1; //nums.Length = 0    
    }
}