Simon Lai's Blog
  • 首頁
  • 歸檔
  • 分類
  • 標籤
  • 關於

380. Insert Delete GetRandom O(1) - Medium

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

377. Combination Sum IV - Medium

前往題目 想法 會不會是用backtracking? 思路 利用array當作cache base case是0,因為只有一種組合是0 接著疊代1~target,逐步建立cache 每個循環裡面要再看一次所有的nums並相加,因為先前的加起來才是當前的組合總數 可以看這個discussion的解釋,非常清楚 Code class Solution { public int
2024-01-25
Leetcode > Medium
#Leetcode #心得 #Array #Dynamic Programming

227. Basic Calculator II - Medium

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

153. Find Minimum in Rotated Sorted Array - Medium

前往題目 想法 binary search找到第一組大變小的就是最小的數字了 思路 binary search 如果中間比右指針小那代表是在正常的順序上,所以往左找 不然就是往右找了 這題我一開始嘗試用recursion來寫binary search失敗了😂 Codeclass Solution { public int findMin(int[] nums) {
2024-01-24
Leetcode > Medium
#Leetcode #心得 #Array #Binary Search

61. Rotate List - Medium

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

16. 3Sum Closest - Medium

前往題目 想法 應該可以轉換2sum來做,但不知道有沒有更好的方法 思路沒有更好的方法了,只能$O(N^2)$ 三個一組來看 固定第一個,後兩個binary search 每次都計算差,有更小就加到答案裡去(不要加成difference) Codeclass Solution { public int threeSumClosest(int[] nums, int tar
2024-01-23
Leetcode > Medium
#Leetcode #心得 #Array #Two Pointers #Sorting

977. Squares of a Sorted Array

前往題目 想法 直接一個一個平方,然後用comparator的方式排進新的array 中間一定是最小的,2 pointers應該可以用 思路 2 pointers,大的先加入答案,直到最小值 反向加入,回傳時就不用額外的操作反轉array Code class Solution { public int[] sortedSquares(int[] nums) {
2024-01-22
Leetcode > Easy
#Leetcode #心得 #Array #Two Pointers #Sorting

572. Subtree of Another Tree - Easy

前往題目 想法 找subRoot在原樹的位置 找到後直接開始檢查兩樹是否一樣 思路 檢查兩樹的是否為空,subRoot樹空代表一定是true,因為null是所有樹的子樹;而root樹空如果subRoot樹也為空,那也是true 往左右子樹前進,每次都檢查是否兩樹為相同樹 Time: $O(M * N)$ 因為每個節點都檢查是否為相同樹 Code (WA)明明簡單,但好像沒那麼簡單…不知道哪裡
2024-01-22
Leetcode > Easy
#Leetcode #心得 #Binary Tree #Depth-First Search #Tree #String Matching #Hash Function

70. Climbing Stairs - Easy

前往題目 想法 在想要用dp,但是關係式想不出來 思路 最後兩個一定都是1種方法能走到 以他們為基準向前就能推出答案 下面i還是從0開始因為沒有差別,沒有用到i Code class Solution { public int climbStairs(int n) { // Pointer int one = 1, two = 1
2024-01-21
Leetcode > Easy
#Leetcode #心得 #Math #Dynamic Programming #Memoization

238. Product of Array Except Self - Medium

前往題目 想法 想不出不用除法怎麼解 思路 利用prefix和postfix sum 先疊代一次建構prefix sum 再由後往前直接建構答案 看不懂的話可以把postfix sum和prefix sum各列出來,就可以發現只要把任何一個位置的postfix以及同位置的prefix sum乘起來就是答案 Code class Solution { public int[
2024-01-21
Leetcode > Medium
#Leetcode #心得 #Array #Prefix Sum
1…2324252627…36

搜尋

Hexo Fluid