Yee42069

@PeterLei

Joined on Nov 10, 2022

  • 題目:https://leetcode.com/problems/power-of-four/description/ 描述:判斷輸入的數字是否為4的次方數 解題思路:標準解法是使用對數基底變換方法,不過這題也可以看作判斷是否為2的次方數的延伸題,4的次方數跟2的次方數一樣用二進位制表示只會有1個位元為1,不過這次這些1只會出現在奇數位上,額外再用一個mask來判斷1是否出現在奇數位即可 程式碼: class Solution { public boolean isPowerOfFour(int n) {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/power-of-three/description/ 描述:判斷輸入的數字是否為3的次方數 解題思路(1):用對數的基底變換計算,如果i = log10(n) / log10(3)的i為整數的話代表n為3的次方數 程式碼: class Solution { public boolean isPowerOfThree(int n) {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/power-of-two/description/ 描述:判斷輸入的數字是否是2的n次方數 解題思路:有個方法能快速找出正整數n是否為2的n次方數/只有一個位元為1:將n與n-1進行位元AND運算,結果為0則n即為2的n次方數/只有一個位元為1 程式碼: class Solution { public boolean isPowerOfTwo(int n) {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/reverse-bits/ 描述:將32位元的unsigned int中的位元順序顛倒後回傳結果的值 解題思路:詳細解答來源,用分治法(divide and conquer)每次將處理範圍中左半與右半邊的位元值互換,對一個有2^n位元的數字總共只需要換n次即可 程式碼: public class Solution { // you need treat n as an unsigned value
     Like  Bookmark
  • 題目:https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/ 描述:實作RandomizedSet類別,其中的函式要能新增&刪除數字以及隨機回傳一個數字,所有函式的平均時間複雜度需要是O(1),存入的數字能夠重複出現 解題思路:與380題類似但這次需要處理重複元素,所以在HashMap中改用HashSet來儲存多個相同數字的位置,此外邏輯相同 程式碼: class RandomizedCollection { private List<Integer> set;
     Like  Bookmark
  • 題目:https://leetcode.com/problems/insert-delete-getrandom-o1/ 描述:實作RandomizedSet類別,其中的函式要能新增&刪除數字以及隨機回傳一個數字,所有函式的平均時間複雜度需要是O(1),所有存入的數字都不重複 解題思路:題目時間複雜度要求所有操作都要是平均O(1),使用HashMap或HashSet的增減、查詢都是O(1),但隨機取出元素需要用到iterator所以是O(n),相對的用陣列就能O(1)時間隨機取出元素 因此我們混用2個資料結構,使用HashMap來紀錄數字在陣列中的位置,使用陣列紀錄&隨機取出元素,並且增減時都只在陣列最尾端操作以保證增減元素也是O(1) 程式碼:
     Like  Bookmark
  • 題目:https://leetcode.com/problems/bulls-and-cows/ 描述:1A2B猜數字遊戲,輸入會有猜的數字guess與解答數字secret,回傳猜的數字是幾A幾B 解題思路:猜測的數字會分為A(bull)跟B(Cow)2種,A的計算方法就是直接計算相同位置出現相同數字的次數,B的計算方法則先分別計算2個數字中除A以外出現的各個數字出現的頻率,再逐個比較猜測的數字與答案的出現頻率計算 程式碼: class Solution { public String getHint(String secret, String guess) {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/longest-palindrome/ 描述:給一串包含大小寫字母的字串,找出使用這個字串中的字元所能排出的最長的回文長度,大小寫要區分為不同的字元 解題思路:要讓回文增長需要相同的2個字母,所以只要用Set紀錄出現過的字母,出現2次時就讓回文長度+2,最後因為回文正中間能夠額外有一個單獨的字母,要再判斷有沒有剩餘的多的字母能讓回文長度再+1 程式碼: class Solution { public int longestPalindrome(String s) {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/isomorphic-strings/ 描述:判斷2個字串是否同構(isomorphic)。如果將一個字串中每個特定字元轉換成另一個特定字元後能夠與另一個字串相同,則這2個字串即為同構 解題思路:因為同構每個特定字元只能對應另一個特定字元且不能重複對應,所以只要用map將第一次出現的對應記錄下來,判斷有出現的字元在另一個字串是否有正確對應即可 程式碼: class Solution { public boolean isIsomorphic(String s, String t) {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/single-number/ 描述:找出輸入的陣列中唯一一個沒有重複出現第二次的數字,時間複雜度與空間複雜度的限制分別為O(n)跟O(1) 解題思路(1):用HashSet紀錄出現過的數字,如果數字重複出現就從set中移除,最後set最後剩下的唯一一個元素就是只出現過一次的數字 程式碼: class Solution { public int singleNumber(int[] nums) {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/find-players-with-zero-or-one-losses/description/ 描述:輸入許多比賽勝負結果的資料,分別找出完全沒輸過以及正好輸一場的選手們的編號,輸出結果的編號需要遞增排序好 解題思路:要找出現頻率就是map出場的時間,用HashMap紀錄所有出場選手的敗場次數,再將次數為0跟1的資料找出並排序後輸出即可 程式碼:(HashMap) class Solution { public List<List<Integer>> findWinners(int[][] matches) {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/last-stone-weight/ 描述:輸入許多石頭對應的重量,每次拿重量最重的2顆石頭互砸會剩下重量相減後的一顆石頭,算出最後剩的一顆石頭的重量,石頭沒有剩則回傳0 解題思路:要有效率的找出最大的2顆石頭可以使用排序,但是每次2顆最大的石頭砸完後還是得要把新的石頭排到對應的位置,這樣的時間複雜度會是(每次砸完重新排序的)O(nlogn)乘上(一共要砸的次數)O(n)的O(n^2logn) 因此我們改用更快的heap,heap插入新元素的時間複雜度為O(logn),取出最大值為O(1),每次取出石頭砸完再將剩的石頭放回去heap,時間複雜度就能降為(每次砸完放回去的)O(logn)乘上(一共要砸的次數)O(n)的O(nlogn) 程式碼: class Solution {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/find-median-from-data-stream/ 描述:實作MedianFinder class,其中addNum()加入新元素,findMedian()找出目前輸入的元素中的中位數 class MedianFinder { public MedianFinder() { }
     Like  Bookmark
  • 題目:https://leetcode.com/problems/linked-list-cycle/ 描述:輸入一個鏈結串列的head,判斷該鏈結串列是否存在指標迴圈(cycle) 解題思路:使用Fast-slow pointer法,類似時鐘上不同速度的指針一定會在某個地方重疊,利用2個前進速度不同的指標,如果鏈結串列中有迴圈2個指標一定會在某個時間點重疊。 程式碼: /** * Definition for singly-linked list.
     Like  Bookmark
  • 題目:https://leetcode.com/problems/valid-palindrome/ 描述:給定一個字串,辨識該字串是否為回文,如果該字串在將所有字母轉為小寫後並移除其中的非字母數字(non-alphanumeric)的字元後,正寫反寫都一樣的話即為回文 解題思路:用two pointer,先將字串的字母轉為小寫,2個pointer分別從字串頭尾開始向中間移動比較2個pointer位置的字元是否相同,遇到非字母數字就跳過 程式碼: class Solution { public boolean isPalindrome(String s) {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/remove-duplicates-from-sorted-array/ 描述:給定一個遞增排序的陣列,調整陣列讓陣列前k個元素為陣列中出現的k個數字,回傳值為k。空間複雜度限制O(1),所有對陣列元素的操作只能在輸入的陣列中進行(in-place) 解題思路:用two pointer法,一個pointer用來找尋新的數字,一個pointer用來放置找到的數字 程式碼: class Solution { public int removeDuplicates(int[] nums) {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/is-subsequence/ 描述:判斷字串s是否是字串t的子序列(Subsequence),如果透過不停消除字串t中的某個字元能讓t變成s的話則s即為t的子序列 解題思路:子序列的字元順序會跟原始序列中一樣,所以使用two pointer從2個字串開頭開始逐個比較字元是否相同,如果最後s的字元都有比較完畢則s就是t的子序列 程式碼: class Solution { public boolean isSubsequence(String s, String t) {
     Like  Bookmark
  • 題目:https://leetcode.com/problems/linked-list-cycle-ii/ 描述:給定一個鏈結串列,找出串列中迴圈(cycle)開始的node,如果沒有迴圈則回傳null 解題思路:跟141一樣的找迴圈問題,但需要找到迴圈開始的node讓問題變複雜多了。假設用原本的2個快慢pointer方法,最後2個pointer會在圖中2的node上碰面,但我們要找的是圖中1的node 這時慢的pointer走了x+a的步數,快的pointer則走了x+2a+b的步數,由快的比慢的走多一倍步數可以得到2(x+a)=x+2a+b,稍微化簡後就能得出x=b,只要從head走b的步數就能找到1的所在位置了。這時就那麼剛好,從2個pointer碰面的node 2再走b步也會走到node 1的位置,換言之,只要在2個pointer碰面後,讓1個pointer從head開始每次走1格,另1個pointer繼續從node 2位置也每次走1格,這2個pointer下次碰面的位置就會剛好是迴圈開始的node 1了 程式碼:
     Like  Bookmark
  • 題目:https://leetcode.com/problems/middle-of-the-linked-list/ 描述:給定一個鏈結串列,回傳鏈結串列最中間的node,如果有2個最中間的node則回傳其中第2個node 解題思路:用2個前進速度分別為1步跟2步的node遍歷鏈結串列,當走的快的到達尾端時走的慢的就會正好在中間位置 程式碼: /** * Definition for singly-linked list.
     Like  Bookmark
  • 題目:https://leetcode.com/problems/reverse-linked-list/ 描述:給定一個鏈結串列,回傳一個與之順序顛倒的鏈結串列 解題思路:這種問題畫圖模擬迭代過程應該是最簡單直覺也最好的方式,比較會卡住的部分是找出需要用多少個node來確保能順利迭代,以這題而言就需要3個(包含輸入給的head) 程式碼: /** * Definition for singly-linked list.
     Like  Bookmark