[LeetCode] #108 Convert Sorted Array to Binary Search Tree 解題

題目連結

題型解說

這是一題難度為簡單的題目

需要設計一個方法,此方法會傳入一個排序好的陣列 nums

回傳一顆平衡的二元搜尋樹,左右兩邊的層級不能超過 1

解題思路

二元搜尋樹有幾個特性

  1. 不會有重複的值
  2. 左節點數值一定比根節點數值小
  3. 右節點數值一定比根節點數值大
  4. 其他層的節點也要符合以上要求

既然所有的右邊節點一定比根節點大,所有左邊節點一定比根節點小,題目也規定兩邊的層數不能相差超過 1

那麼根節點只能選 nums 的中間值,這邊有個小疑問「如果 nums 是偶數呢?」,是要選左邊那個還是右邊那個?

答案其實無所謂,因為題目有提示說答案不止一種

根節點選擇好了後就能把 nums 拆成左右兩部分,左右兩部分也需要符合 二元搜尋樹 的特性

那一樣選擇中間值拆左右兩部分,所以分析後最適合的解法就是二分搜尋法了

程式碼

Java

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        
        return sortedArrayToBST(nums, 0, nums.length);
    }
    
    private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left == right) {
            return null;
        }
        
        int mid = (left + right) /2;
        
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBST(nums, left, mid);
        node.right = sortedArrayToBST(nums, mid +1, right);
        
        return node;
    }
}
class Solution { // 其他人的二分搜尋法
    public TreeNode sortedArrayToBST(int[] nums) {
		int length = nums.length;
		return generateTree(nums, 0, length - 1);
	}

	private TreeNode generateTree(int[] nums, int low, int high) {
		if (low > high) {
			return null;
		}
		int mid = low + (high - low) / 2;
		TreeNode root = new TreeNode(nums[mid]);
		root.left = generateTree(nums, low, mid - 1);
		root.right = generateTree(nums, mid + 1, high);
		return root;
	}
}

Read more

[LeetCode] #12 Integer to Roman 解題

題目連結 題型解說 這是一題難度為普通的題目 需要設計一個方法,此方法會傳入一個整數 num 要求是把整數轉換成羅馬字母,轉換清單如下 I => 1 V => 5 X => 10 L => 50 C => 100 D => 500 M => 1000 但羅馬字母有一些特殊規則 4 並非 IIII 而是 IV,9 並非 VIIII 而是 IX 這規則同樣可以套用到 40 90 400 900 解題思路 既然知道特殊規則是一樣的,變得是使用的符號,那麼先從 num 取個位數開始 轉換完成後,把 num 除上 10,消除個位數,

By Michael

[LeetCode] #11 Container With Most Water 解題

題目連結 題型解說 這是一題難度為中等的題目 需要設計一個方法,此方法會傳入一個數字陣列 height 陣列中的元素代表每一個柱子的高度 現在需要計算出,該陣列中以某兩隻柱子為邊界,最多可以裝多少水 以範例來說 height = [1,8,6,2,5,4,8,3,7] 最多可以裝 7 * 7 = 49 單位的水 解題思路 計算面積就是底乘上高 底的計算方式為 「右邊柱子的 index」 減去 「左邊柱子的 index」 高就取最短的那一根柱子高度 拿題目給的例子來當範例 建立三個變數 result、left、right left、right 代表左右兩邊的 index result 代表目前最大容量,初始值 0 第一步,找出最短的柱子高度,

By Michael

[LeetCode] #941 Valid Mountain Array 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個數字陣列 arr 判斷陣列中的元素是不是由低到高再從高到低(山形)的排序,且不連續一個以上數字 比如說 [1,2,3,2] 就是一個山形陣列,但 [1,2,2,3,2] 不是,因為有兩個 2 [1,2,3,4,5] 和 [5,4,3,2,1] 也不算是山形陣列,前者只有往上沒有往下,後者相反 解題思路 準備一個數字變數(temp)和布林變數(asc),跑一次迴圈,有可能遇到如下狀況 1. 某個數字與前一個數字相同,這時候直接回傳 false

By Michael

[LeetCode] #944 Delete Columns to Make Sorted 解題

題目連結 題型解說 這是一題難度為簡單的題目 需要設計一個方法,此方法會傳入一個字串陣列 strs 這個陣列中每個字串的長度都相同,字串內容都是小寫英文 需要檢查每個元素的第 N 個字元是不是由小至大排列,並回傳有幾個錯誤排列 比如傳入的陣列長這樣 ["cba","daf","ghi"] 取第一個字元 = cdg 取第二個字元 = bah 取第三個字元 = afi 其中第二組的結果(bah)並不是由小至大排列,故回傳 1 解題思路 這一題就用兩個迴圈各別把字元取出來,並比較是否比上一個字元大(Java 中的字元可以直接比較),如果不是就將結果+1 程式碼 Java class Solution { public int minDeletionSize(String[] strs) { int result = 0; for (int i = 0,

By Michael