98. Validate Binary Search Tree - Medium

前往題目 搬運一下之前寫過的 想法 要檢查數值，還要檢查是否是BST 紀錄擁有子樹的node的數值，然後檢查左邊，比較數值，有錯就直接結束；右邊也是一樣 檢查是否是BST得用height，左右子樹的高度差不能超過1 思路 Recursion檢查每個node是否小於等於最小值，或是否大於等於最大值，如果有就是false Code 嘗試寫了，但邏輯有誤，沒有考慮到左子樹有可能會比右子樹的某一項
Leetcode > Medium
#Leetcode #心得 #Binary Search Tree #Binary Tree #Depth-First Search #Tree

155. Min Stack - Medium

前往題目 想法 題目要求每個方法都要O(1)時間，如果用一般的stack來做的話那push，pop，和top都可以輕易做到。但是還有一個getMin，他要回傳stack中最小的數，如果只用一個int來追蹤的話那萬一這個最小值被pop了，就不知道下一個最小值是多少了，在哪裡都有可能。所以這裡應該需要一個PriorityQueue來儲存 但是這樣又有一個問題，pop的時候中間值可能不見了，那就還要再
Leetcode > Medium
#Leetcode #心得 #Stack #Design

409. Longest Palindrome - Easy

前往題目 想法 存每個字母的數量，最後疊代取出所有偶數還有一個奇數 思路想法對了，實作有些情況沒考慮到 儲存所有字母的counts 疊代這些counts，如果是奇數，注意要把他-1加到結果裡，因為偶數counts是需要的 遇到偶數就直接把count加進去答案 最後回傳的時候如果有一個奇數項，就把他加進去 Codeclass Solution { public int lo
Leetcode > Medium
#Leetcode #心得 #String #Greedy #Hash Table

435. Non-overlapping Intervals - Medium

前往題目 想法 用掃描線，但實作卡住了 思路 用每個array的第一項排序 以第一項為基準開始疊代確認是否相交 如果不相交就更新區間的尾端 如果相交，多一個需要移除，並且取比較小的尾端，這樣可以減低之後再相交的機率 Code // T: O(nlogn) // S: O(1) class Solution { public int eraseOverlapInterval
Leetcode > Medium
#Leetcode #心得 #Array #Greedy #Dynamic Programming #Sorting

380. Insert Delete GetRandom O(1) - Medium

前往題目 想法經過這麼多演算法的洗禮還有自修的演算法課程，總算沒讓自己失望:D以下是分析 如果使用array，insert和remove都需要index，但是傳入的值是value，每次都要花時間搜尋。如果使用Map來儲存映射關係那還要處理array擴增的問題，所以不選這個 如果用LinkedList，insert可以O(1)，但是remove和getRandom都要O(n)，也不方便；就算是d
Leetcode > Medium
#Leetcode #心得 #Array #Math #Hash Table #Randomized #Design

227. Basic Calculator II - Medium

前往題目 想法 用stack，只壓入數字和+-，乘除直接用stack最上層的數字計算就可以 思路沒看到數字不一定是一個digit 疊代整個string 每次判斷是否為數字，如果是則看有多少位，把整串擷取，然後看是什麼operator做相應的計算(如果是整個運算式的第一個數字那就會剛好直接加入) 如果不是數字，也不是空格，那就一定是operator，紀錄 Code這個解法沒有用到stack，
Leetcode > Medium
#Leetcode #心得 #Stack #String #Math

61. Rotate List - Medium

前往題目 想法 找到middle的時候也順便知道這個list有多長，這樣就能算出是哪幾個要接到前面去，或甚至連動都不用動直接回傳 當k=list的長度時候就不用動，剛好一循環 思路大致上自己想出來了，可惜為了存middle讓code變得複雜，但實際上根本不用middle 找到尾巴node和list的長度 然後根據長度就可以算出新的尾巴在哪裡 重新拼接就可以了 Code class Sol
Leetcode > Medium
#Leetcode #心得 #Two Pointers #Linked List