LeetCode初級算法訓練-排序和搜尋(完成)

簡介

上一篇 : LeetCode初級算法訓練-樹

下一篇 : LeetCode初級算法訓練-動态規劃

本來想重國中級和企業面試算法開始的，但是最後還是選擇從基礎的開始，因為我們并不是為了刷題而刷題，而是在刷題過程中鍛煉一種算法思維，在大量的訓練之後形成一種對算法的獨特見解，培養那種對算法的的敏感度，看到題目，大腦中可以浮現一個解題藍圖，而且從初級開始慢慢建立信心，而且這也是在為後邊複雜算法的解題思路打基礎。

LeetCode初級算法簡介

如果你也想訓練自己的算法思維，也可以加入我，從初級算法開始，開啟你的算法之旅：初級算法。

自己的一些思考：不要在看完題目後直接就看答案，然後去背題，這樣行成的算法記憶是不牢固的，一定要有自己的思考；而且不要一開始就在IDEA上邊去寫，一定試着自己在leetCode提供的白闆上邊寫一遍最後在放到IDEA上邊去執行看有什麼問題，以便鞏固你的基礎API的使用和熟練度；還有一點就是大膽些，不是面試我們試錯成本低，盡可能把我們的想法融入到代碼中

因篇幅問題，部落格中隻列出示例和自己的解題答案，詳細可以直接點選題目檢視。

合并兩個有序數組

給你兩個有序整數數組 nums1 和 nums2，請你将 nums2 合并到 nums1 中，使 nums1 成為一個有序數組。

說明:

初始化 nums1 和 nums2 的元素數量分别為 m 和 n 。

你可以假設 nums1 有足夠的空間（空間大小大于或等于 m + n）來儲存 nums2 中的元素。

示例:

輸入:

nums1 = [1,2,3,0,0,0], m = 3

nums2 = [2,5,6], n = 3

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

這邊

第一種方式比較容易想到但是時間複雜度比較慢。沒有利用兩個資料有序的特點。

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    System.arraycopy(nums2, 0, nums1, m, n);
    Arrays.sort(nums1);
  }
}
           

第二種方式是建立一個新數組把nums1的資料移到nums3中，用雙指針比對兩個數組中的資料插入到nums1中，最後把剩下的資料copy到nums1中。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums3 = new int[m];
        System.arraycopy(nums1, 0, nums3, 0, m);

        int p = 0;
        int p1 = 0, p2 = 0;

        while (p1 < m && p2 < n) {
            nums1[p++] = nums3[p1] <= nums2[p2] ? nums3[p1++] : nums2[p2++];
        }

        if (p1 < m)
            System.arraycopy(nums3, p1, nums1, p1 + p2, m + n - p1 - p2);
        if (p2 < n)
            System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
    }
}
           

第一個錯誤的版本

第一個錯誤的版本

你是産品經理，目前正在帶領一個團隊開發新的産品。不幸的是，你的産品的最新版本沒有通過品質檢測。由于每個版本都是基于之前的版本開發的，是以錯誤的版本之後的所有版本都是錯的。

假設你有 n 個版本 [1, 2, …, n]，你想找出導緻之後所有版本出錯的第一個錯誤的版本。

你可以通過調用 bool isBadVersion(version) 接口來判斷版本号 version 是否在單元測試中出錯。實作一個函數來查找第一個錯誤的版本。你應該盡量減少對調用 API 的次數。

示例:

給定 n = 5，并且 version = 4 是第一個錯誤的版本。

調用 isBadVersion(3) -> false

調用 isBadVersion(5) -> true

調用 isBadVersion(4) -> true

是以，4 是第一個錯誤的版本。

利用二分搜尋，當左邊界和有邊界相等，那個數就是我們找的數。

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(isBadVersion(mid)){
                right = mid;
            } else{
                left = mid + 1;
            }
        }
        return left;
    }

}
           

22 / 22 個通過測試用例

狀态：通過

執行用時：16 ms

記憶體消耗：36.6 MB

二分都用了 16ms更何況從頭開始周遊。