Leetcode-一篇帖子就够啦
生活随笔
收集整理的這篇文章主要介紹了
Leetcode-一篇帖子就够啦
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
# 注：下面按照算法類別由淺入深，把下面羅列的這些題刷完，并且多看這些題不同的解法(國際版mostvotes)，看懂之后估計就不會有太大的問題啦~
整體框架
數據結構: 一維：基礎: 數組array(string)，鏈表linked list高級 : 棧stack，隊列queue，雙端隊列deque，集合set，映射 map(hash or map), etc二維：基礎：樹tree，圖graph高級: 二叉搜索樹binary search tree(red-black tree,AVL)，堆heap，并查集disjoint set，字典樹Trie特殊:位運算Bitwise，布隆過濾器BloomFilterLRU Cache算法:遞歸Recursion搜索Search: 深度優先搜索Depth first search，廣度優先搜索Breadth first search動態規劃 Dynamic Programming二分查找 Binary Search貪心 Greedy數組&鏈表部分
一、數組部分
數組的常見寫法: Java,C++: int a[50] ;? Python: list = []??
注：高級數據語言可以不指定類型語言
數組底層硬件實現，有一個內存管理器，每當申請一個數組時，計算機會在內存中開辟一段連續的地址，每一個地址都可以直接通過內存管理器直接訪問，訪問任意一個位置，時間復雜度都是一致的都是O(1)
數組的插入和刪除都需要O(n)的時間復雜度
看一下Java源碼，數組插入和刪除的操作過程:
http://developer.classpath.org/doc/java/util/ArrayList-source.html329: /**330: * Appends the supplied element to the end of this list.331: * The element, e, can be an object of any type or null.332: *333: * @param e the element to be appended to this list334: * @return true, the add will always succeed335: */336: public boolean add(E e)337: {338: modCount++;339: if (size == data.length)340: ensureCapacity(size + 1);341: data[size++] = e;342: return true;343: }數組添加一個元素e,modCount是一個計數器，ensureCapacity保證數組的容量，末尾插入一個元素e345: /**346: * Adds the supplied element at the specified index, shifting all347: * elements currently at that index or higher one to the right.348: * The element, e, can be an object of any type or null.349: *350: * @param index the index at which the element is being added351: * @param e the item being added352: * @throws IndexOutOfBoundsException if index < 0 || index > size()353: */354: public void add(int index, E e)355: {356: checkBoundInclusive(index);357: modCount++;358: if (size == data.length)359: ensureCapacity(size + 1);360: if (index != size)361: System.arraycopy(data, index, data, index + 1, size - index);362: data[index] = e;363: size++;364: }指定位置index處插入元素e, checkBoundInclusive-檢查是都越界，ensureCapacity保證數組容量，arraycopy-對數組序列進行移動463: /**464: * Checks that the index is in the range of possible elements (inclusive).465: *466: * @param index the index to check467: * @throws IndexOutOfBoundsException if index > size468: */469: private void checkBoundInclusive(int index)470: {471: // Implementation note: we do not check for negative ranges here, since472: // use of a negative index will cause an ArrayIndexOutOfBoundsException,473: // a subclass of the required exception, with no effort on our part.474: if (index > size)475: throw new IndexOutOfBoundsException("Index: " + index + ", Size: "476: + size);477: }checkBoundInclusive檢查是否越界160: /**161: * Guarantees that this list will have at least enough capacity to162: * hold minCapacity elements. This implementation will grow the list to163: * max(current * 2, minCapacity) if (minCapacity > current). The JCL says164: * explictly that "this method increases its capacity to minCap", while165: * the JDK 1.3 online docs specify that the list will grow to at least the166: * size specified.167: *168: * @param minCapacity the minimum guaranteed capacity169: */170: public void ensureCapacity(int minCapacity)171: {172: int current = data.length;173: 174: if (minCapacity > current)175: {176: E[] newData = (E[]) new Object[Math.max(current * 2, minCapacity)];177: System.arraycopy(data, 0, newData, 0, size);178: data = newData;179: }180: }ensureCapacity-確保數組的容量數組的刪除操作和插入操作同理，也會用到相應的函數366: /**367: * Removes the element at the user-supplied index.368: *369: * @param index the index of the element to be removed370: * @return the removed Object371: * @throws IndexOutOfBoundsException if index < 0 || index >= size()372: */373: public E remove(int index)374: {375: checkBoundExclusive(index);376: E r = data[index];377: modCount++;378: if (index != --size)379: System.arraycopy(data, index + 1, data, index, size - index);380: // Aid for garbage collection by releasing this pointer.381: data[size] = null;382: return r;383: } 二、鏈表部分(Linked List) 鏈表部分彌補前面數組部分的缺點(插入和刪除時間復雜度過高)每一個元素都需要定義一個class，頭指針用head表示，尾指針用tail表示，最后一個元素next指針指向空，因為沒有next指針啦；如果tail 的next指針指向head時，為循環鏈表 Java-Linked List源碼： http://developer.classpath.org/doc/java/util/LinkedList-source.html 鏈表的插入和刪除操作沒有引起鏈表的群移操作，也不需要復制元素 操作 時間復雜度(linkedList vs Array) prepend(前向插入) O(1) vs O(1) append(后向插入) O(1) vs O(1) lookup(查詢) O(n) vs O(1) insert(插入) O(1) vs O(n) delete(刪除) O(1) vs O(n) 從圖中可以看出，查詢操作時間復雜度為O(n)，也是鏈表的問題所在，所以可以看出并沒有一種完美的數據結構，根據不同的需求用相應的數據結構即可三、跳表常見于redis中，鏈表的缺點在于查詢時間復雜度為O(n)，對鏈表查詢進行加速，中心思想-空間換時間原始鏈表-時間復雜度：O(n) 簡單優化：添加頭尾指針 ，多添加指針會更快一級索引加速，速度可以加快，還可以增加第二級索引，更快加快速度，通常增加log2n級索引，跳表時間復雜度為logn。例如一個鏈表原始長度為1024，按照原始查詢方式需要查1024次，如果按照跳表進行查詢，只需要查詢10次。增加和刪除操作，跳表需要更新一次。跳表的時間復雜度為O(logn)，空間復雜度為O(n)。redis應用跳表參考鏈接：https://redisbook.readthedocs.io/en/latest/internal- datastruct/skiplist.html四、實戰題目題目1：Leetcode-283-移動零給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾， 同時保持非零元素的相對順序。示例:輸入: [0,1,0,3,12] 輸出: [1,3,12,0,0] 說明:必須在原數組上操作，不能拷貝額外的數組。 盡量減少操作次數。解法一:雙指針從前到后進行遍歷，遇到不是0的元素往前移，0元素放在后面class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""j = 0for i in range(len(nums)):if nums[i]!=0:nums[j] = nums[i]if i!=j:nums[i] = 0j += 1效率: 提交時間 提交結果 執行用時 內存消耗 語言 幾秒前 通過 52 ms 14.5 MB Python3解法二：遍歷數組，構建一個索引，遇到不是零的元素，則添加到數組前面， 直到遍歷完數組，index-至數組末尾添加0 class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""index = 0for i in range(len(nums)):if nums[i]!=0:nums[index] = nums[i]index +=1for i in range(index,len(nums)):nums[i] = 0性能： 提交時間 提交結果 執行用時 內存消耗 語言 幾秒前 通過 88 ms 14.4 MB Python3Most votes: // Shift non-zero values as far forward as possible // Fill remaining space with zerospublic void moveZeroes(int[] nums) {if (nums == null || nums.length == 0) return;int insertPos = 0;for (int num: nums) {if (num != 0) nums[insertPos++] = num;}while (insertPos < nums.length) {nums[insertPos++] = 0;} }# in-place def moveZeroes(self, nums):zero = 0 # records the position of "0"for i in xrange(len(nums)):if nums[i] != 0:nums[i], nums[zero] = nums[zero], nums[i]zero += 1題目2Leetcode-11-盛最多水的容器給定 n 個非負整數 a1，a2，...，an，每個數代表坐標中的一個點 (i, ai) 。 在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。 找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。 說明：你不能傾斜容器，且 n 的值至少為 2。圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下， 容器能夠容納水（表示為藍色部分）的最大值為 49。 示例: 輸入: [1,8,6,2,5,4,8,3,7] 輸出: 49解法一、暴力解法: class Solution:def maxArea(self, height: List[int]) -> int:max_area = 0for i in range(len(height)):for j in range(i+1,len(height)):max_area = max(max_area,min(height[j],height[i])*(j-i))return max_area性能：超時解法二、雙指針 數組左側一個指針，右側一個指針，兩個指針向中間移動，直到兩者相遇； 算指針高度較小的指針的高度，指針移動。 class Solution:def maxArea(self, height: List[int]) -> int:i,j,max_area = 0,len(height)-1,0while i<j:if height[i] < height[j]:max_area = max(max_area,height[i]*(j-i))i += 1else:max_area = max(max_area,height[j]*(j-i))j -= 1return max_area提交時間 提交結果 執行用時 內存消耗 語言 幾秒前 通過 232 ms 14.7 MB Python3MostVotes: class Solution(object):def maxArea(self, height):""":type height: List[int]:rtype: int"""MAX = 0 x = len(height) - 1y = 0while x != y:if height[x] > height[y]:area = height[y] * (x - y)y += 1else:area = height[x] * (x - y)x -= 1MAX = max(MAX, area)return MAXint maxArea(vector<int>& height) {int water = 0;int i = 0, j = height.size() - 1;while (i < j) {int h = min(height[i], height[j]);water = max(water, (j - i) * h);while (height[i] <= h && i < j) i++;while (height[j] <= h && i < j) j--;}return water; }題目3Leetcode-70-爬樓梯假設你正在爬樓梯。需要 n 階你才能到達樓頂。 每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個正整數。示例 1： 輸入：2 輸出：2 解釋：有兩種方法可以爬到樓頂。 1. 1 階 + 1 階 2. 2 階 # 解法 class Solution:# 只保存最近的三個值def climbStairs(self, n: int) -> int:if n<=2:return nelse:f1,f2,f3 = 1,2,3for i in range(3,n+1):f3 = f1 + f2f1 = f2f2 = f3return f3時間復雜度O(n)，空間復雜度為O(1)Time Submitted Status Runtime Memory Language 28 minutes ago Accepted 104 ms 13 MB python 官方給出兩個比較新穎的解法：Binets方法 && 斐波那契公式，詳見 https://leetcode-cn.com/problems/climbing-stairs/solution /pa-lou-ti-by-leetcode/ 題目4Leetcode-15-三數之和精選題解(https://leetcode-cn.com/problems/3sum/solution/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/):排序 + 雙指針 本題的難點在于如何去除重復解。算法流程： 特判，對于數組長度 nn，如果數組為 nullnull 或者數組長度小于 3，返回 []。 對數組進行排序。 遍歷排序后數組： 若 nums[i]>0nums[i]>0：因為已經排序好，所以后面不可能有三個數加和等于 0，直接返回結果。 對于重復元素：跳過，避免出現重復解 令左指針 L=i+1，右指針 R=n-1，當 L<R時，執行循環： 當 nums[i]+nums[L]+nums[R]==0，執行循環，判斷左界和右界是否和下一位置重復，去除重復解。并同時將 L,R 移到下一位置，尋找新的解 若和大于 0，說明 nums[R]太大，RR 左移 若和小于 0，說明 nums[L]太小，LL 右移 復雜度分析 時間復雜度：O(n^2),數組排序O(NlogN),遍歷數組O(N),雙指針遍歷O(n),總體O(NlogN)+O(n)+O(n)*O(n) => O(n^2) 空間復雜度: O(1)class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:n=len(nums)res=[]if(not nums or n<3):return []nums.sort()res=[]for i in range(n):if(nums[i]>0):return resif(i>0 and nums[i]==nums[i-1]):continueL=i+1R=n-1while(L<R):if(nums[i]+nums[L]+nums[R]==0):res.append([nums[i],nums[L],nums[R]])while(L<R and nums[L]==nums[L+1]):L=L+1while(L<R and nums[R]==nums[R-1]):R=R-1L=L+1R=R-1elif(nums[i]+nums[L]+nums[R]>0):R=R-1else:L=L+1return res提交時間 提交結果 執行用時 內存消耗 語言 幾秒前 通過 1508 ms 16.6 MB Python3題目5Leetcode-206-反轉鏈表反轉一個單鏈表。示例:輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL 進階: 你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題？解法一：雙指針迭代 思想，申請兩個指針，一個指針指向空，一個指針指向頭結點，然后遍歷鏈表，每個元素指向空指針方向 class Solution:def reverseList(self, head: ListNode) -> ListNode:pre = Nonecur = headwhile cur:item = cur.nextcur.next = prepre = curcur = itemreturn pre時間復雜度為O(n),空間復雜度為O(1) 提交時間 提交結果 執行用時 內存消耗 語言 幾秒前 通過 36 ms 14.2 MB Python3遞歸-精選題解(https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/) class Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""# 遞歸終止條件是當前為空，或者下一個節點為空if(head==None or head.next==None):return head# 這里的cur就是最后一個節點cur = self.reverseList(head.next)# 這里請配合動畫演示理解# 如果鏈表是 1->2->3->4->5，那么此時的cur就是5# 而head是4，head的下一個是5，下下一個是空# 所以head.next.next 就是5->4head.next.next = head# 防止鏈表循環，需要將head.next設置為空head.next = None# 每層遞歸函數都返回cur，也就是最后一個節點return cur題目6Leetcode-24-兩兩交換鏈表中的節點給定一個鏈表，兩兩交換其中相鄰的節點，并返回交換后的鏈表。 你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。示例: 給定 1->2->3->4, 你應該返回 2->1->4->3.class Solution:def swapPairs(self, head: ListNode) -> ListNode:if not head or not head.next:return headfirst_node = headsecond_node = head.nextfirst_node.next = self.swapPairs(second_node.next)second_node.next = first_nodereturn second_node 題目7Leetcode-141-環形鏈表給定一個鏈表，判斷鏈表中是否有環。為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。 解法一：ListNode放在集合里，遍歷列表，如果元素出現在集合里，則表示構成環 class Solution:def hasCycle(self, head: ListNode) -> bool:set_ = set()while head:if head in set_:return Trueset_.add(head)head = head.nextreturn False提交時間 提交結果 執行用時 內存消耗 語言 幾秒前 通過 48 ms 16.5 MB Python3解法二：快慢指針class Solution:def hasCycle(self, head: ListNode) -> bool:if not head or not head.next:return Falsei,j = head,head.nextwhile j and j.next:if i==j:return Truei,j = i.next,j.next.nextreturn False提交時間 提交結果 執行用時 內存消耗 語言 幾秒前 通過 76 ms 16.3 MB Python3 題目8Leetcode-142-環形鏈表 II給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。class Solution:def detectCycle(self, head: ListNode) -> ListNode:se = set()node = headwhile node is not None:if node in se:return nodeelse:se.add(node)node = node.nextreturn node 提交時間 提交結果 執行用時 內存消耗 語言 幾秒前 通過 60 ms 16.8 MB Python3 題目9Leetcode-25-K 個一組翻轉鏈表給你一個鏈表，每 k 個節點一組進行翻轉，請你返回翻轉后的鏈表。 k 是一個正整數，它的值小于或等于鏈表的長度。 如果節點總數不是 k 的整數倍，那么請將最后剩余的節點保持原有順序。 示例 : 給定這個鏈表：1->2->3->4->5 當 k = 2 時，應當返回: 2->1->4->3->5 當 k = 3 時，應當返回: 3->2->1->4->5 說明 : 你的算法只能使用常數的額外空間。 你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換 優選解法-參考https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/kge-yi-zu-fan-zhuan-lian-biao-by-powcai/ 題目10Leetcode-26-刪除排序數組中的重復項給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。 不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。 示例 1: 給定數組 nums = [1,1,2], 函數應該返回新的長度 2, 并且原數組 nums 的前兩個元素被修改為 1, 2。 你不需要考慮數組中超出新長度后面的元素class Solution:def removeDuplicates(self, nums: List[int]) -> int:if len(nums) == 0:return 0i = 0for j in range(1,len(nums)):if nums[i]!=nums[j]:i +=1nums[i] = nums[j]return i + 1提交時間 提交結果 執行用時 內存消耗 語言 幾秒前 通過 88 ms 14.9 MB Python3 題目11Leetcode-189-旋轉數組給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。示例 1: 輸入: [1,2,3,4,5,6,7] 和 k = 3 輸出: [5,6,7,1,2,3,4] 解釋: 向右旋轉 1 步: [7,1,2,3,4,5,6] 向右旋轉 2 步: [6,7,1,2,3,4,5] 向右旋轉 3 步: [5,6,7,1,2,3,4]class Solution:def rotate(self, nums: List[int], k: int) -> None:"""Do not return anything, modify nums in-place instead."""n = len(nums)k %= nfor i in range(k):nums.insert(0,nums.pop()) 題目12Leetcode-21-合并兩個有序鏈表將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。 示例： 輸入：1->2->4, 1->3->4 輸出：1->1->2->3->4->4 class Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:if l1 is None:return l2elif l2 is None:return l1elif l1.val < l2.val:l1.next = self.mergeTwoLists(l1.next,l2)return l1else:l2.next = self.mergeTwoLists(l1,l2.next)return l2 題目13Leetcode-88-合并兩個有序數組給定兩個有序整數數組 nums1 和 nums2，將 nums2 合并到 nums1 中，使得 num1 成為一個有序數組。 說明: 初始化 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:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""nums1[:] = sorted(nums1[:m] + nums2[:n])時間復雜度O(n+m)log(n+m),空間復雜度O(1)方法二： class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""res = []p1,p2 = 0,0nums1[:] = nums1[:m]while p1 < m and p2 < n:if nums1[p1] < nums2[p2]:res.append(nums1[p1])p1 += 1else:res.append(nums2[p2])p2 += 1if p1 < m:res[p1+p2:] = nums1[p1:]if p2 < n:res[p1+p2:] = nums2[p2:]nums1[:] = res[:]時間復雜度O(n+m),空間復雜度O(m)方法三: class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""p1,p2,p = m-1,n-1,m+n-1while p1 >= 0 and p2 >= 0:if nums1[p1] < nums2[p2]:nums1[p] = nums2[p2]p2 -= 1else:nums1[p] = nums1[p1]p1 -= 1p -= 1nums1[:p2+1] = nums2[:p2+1] 時間復雜度O(m+n),空間復雜度O(1) 題目14Leetcode-1-兩數之和給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，并返回他們的數組下標。 你可以假設每種輸入只會對應一個答案。但是，你不能重復利用這個數組中同樣的元素。 示例: 給定 nums = [2, 7, 11, 15], target = 9 因為 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:map_ = {}for idx,num in enumerate(nums):map_[num] = idxfor i,num in enumerate(nums):j = map_.get(target-num)if j is not None and i!=j:return [i,j] 題目15Leetcode-66-加一給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。 最高位數字存放在數組的首位， 數組中每個元素只存儲單個數字。 你可以假設除了整數 0 之外，這個整數不會以零開頭。示例 1: 輸入: [1,2,3] 輸出: [1,2,4] 解釋: 輸入數組表示數字 123。 class Solution:def plusOne(self, digits: List[int]) -> List[int]:return list(map(int, list(str(int(''.join(map(str, digits))) + 1))))棧、隊列部分
一、棧和隊列的優先特性
Stack & Queue 關鍵點
Stack: 先入后出：添加、刪除皆為O(1)
Queue: 先入先出：添加、刪除皆為O(1)
查詢為O(n),元素是無序的
雙端隊列(Deque)：棧和隊列的結合體，可以從最前面或者最后面push或pop出來,插入和刪除是O(1)，查詢是O(n)
Stack、Queue、Deque的工程實現
Java?Stack?源碼:http://developer.classpath.org/doc/java/util/Stack-source.htmlJava?Queue?源碼:http://fuseyism.com/classpath/doc/java/util/Queue-source.html 1、Leetcode-20-有效的符號給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。 有效字符串需滿足： 左括號必須用相同類型的右括號閉合。 左括號必須以正確的順序閉合。 注意空字符串可被認為是有效字符串。class Solution:def isValid(self, s: str) -> bool:dic = {'(':')','{':'}','[':']','a':'a'}res = ['a']if len(s) == 0:return Trueif len(s)%2==1:return Falsefor ch in s:if ch in dic:res.append(ch)elif dic[res.pop()]!=ch:return Falsereturn len(res)==1提交時間 提交結果 執行用時 內存消耗 語言 幾秒前 通過 20 ms 13.2 MB Python3Mostvotes class Solution:# @return a booleandef isValid(self, s):stack = []dict = {"]":"[", "}":"{", ")":"("}for char in s:if char in dict.values():stack.append(char)elif char in dict.keys():if stack == [] or dict[char] != stack.pop():return Falseelse:return Falsereturn stack == []2、Leetcode-155-最小棧設計一個支持 push，pop，top 操作，并能在常數時間內檢索到最小元素的棧。push(x) -- 將元素 x 推入棧中。 pop() -- 刪除棧頂的元素。 top() -- 獲取棧頂元素。 getMin() -- 檢索棧中的最小元素 class MinStack:def __init__(self):"""initialize your data structure here."""self.stack_1,self.stack_2 = [],[]def push(self, x: int) -> None:self.stack_1.append(x)if len(self.stack_2) ==0 or x<= self.stack_2[-1]:self.stack_2.append(x)else:self.stack_2.append(self.stack_2[-1])def pop(self) -> None:if self.stack_1:self.stack_2.pop()return self.stack_1.pop()def top(self) -> int:if self.stack_1:return self.stack_1[-1]def getMin(self) -> int:if self.stack_2:return self.stack_2[-1]3、Leetcode-84-柱狀圖中最大的矩形給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。 求在該柱狀圖中，能夠勾勒出來的矩形的最大面積輸入: [2,1,5,6,2,3] 輸出: 10精選題解: (https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhao-liang-bian-di-yi-ge-xiao-yu-ta-de-zhi-by-powc/)class Solution:def largestRectangleArea(self, heights: List[int]) -> int:stack = []heights = [0] + heights + [0]res = 0for i in range(len(heights)):while stack and heights[stack[-1]] > heights[i]:tmp = stack.pop()res = max(res, (i - stack[-1] - 1) * heights[tmp])stack.append(i)return res4、Leetcode-239-滑動窗口的最大值給定一個數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字。滑動窗口每次只向右移動一位。 返回滑動窗口中的最大值class Solution(object):def maxSlidingWindow(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""if len(nums) * k == 0:return []return [max(nums[i:i+k]) for i in range(0,len(nums)-k+1)]Mostvotes可查看:https://leetcode.com/problems/sliding-window-maximum/discuss/?currentPage=1&orderBy=most_votes&query=5、Leetcode-641-設計循環雙端隊列設計實現雙端隊列。 你的實現需要支持以下操作：MyCircularDeque(k)：構造函數,雙端隊列的大小為k。 insertFront()：將一個元素添加到雙端隊列頭部。如果操作成功返回 true。 insertLast()：將一個元素添加到雙端隊列尾部。如果操作成功返回 true。 deleteFront()：從雙端隊列頭部刪除一個元素。如果操作成功返回 true。 deleteLast()：從雙端隊列尾部刪除一個元素。如果操作成功返回 true。 getFront()：從雙端隊列頭部獲得一個元素。如果雙端隊列為空，返回 -1。 getRear()：獲得雙端隊列的最后一個元素。 如果雙端隊列為空，返回 -1。 isEmpty()：檢查雙端隊列是否為空。 isFull()：檢查雙端隊列是否滿了。Mostvotes: (https://leetcode.com/problems/design-circular-deque/discuss/154055/python3-using-list-easy-to-understand) class MyCircularDeque:def __init__(self, k):"""Initialize your data structure here. Set the size of the deque to be k.:type k: int"""self._size = 0self._front, self._rear = 0, 0self._capacity = kself._data = [-1] * kdef insertFront(self, value):"""Adds an item at the front of Deque. Return true if the operation is successful.:type value: int:rtype: bool"""if self.isFull():return Falseif self.isEmpty():self._data[self._front] = valueelse:self._front = (self._front - 1) % self._capacityself._data[self._front] = valueself._size += 1return Truedef insertLast(self, value):"""Adds an item at the rear of Deque. Return true if the operation is successful.:type value: int:rtype: bool"""if self.isFull():return Falseif self.isEmpty():self._data[self._rear] = valueelse:self._rear = (self._rear + 1) % self._capacityself._data[self._rear] = valueself._size += 1return Truedef deleteFront(self):"""Deletes an item from the front of Deque. Return true if the operation is successful.:rtype: bool"""if self.isEmpty():return Falseself._data[self._front] = -1self._front = (self._front + 1) % self._capacityself._size -= 1if self.isEmpty():self._rear = self._frontreturn Truedef deleteLast(self):"""Deletes an item from the rear of Deque. Return true if the operation is successful.:rtype: bool"""if self.isEmpty():return Falseself._data[self._rear] = -1self._rear = (self._rear - 1) % self._capacityself._size -= 1if self.isEmpty():self._front = self._rearreturn Truedef getFront(self):"""Get the front item from the deque.:rtype: int"""return self._data[self._front]def getRear(self):"""Get the last item from the deque.:rtype: int"""return self._data[self._rear]def isEmpty(self):"""Checks whether the circular deque is empty or not.:rtype: bool"""return self._size == 0def isFull(self):"""Checks whether the circular deque is full or not.:rtype: bool"""return self._size == self._capacity6、Leetcode-42-接雨水給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。 下面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）Mostvotes https://leetcode.com/problems/trapping-rain-water/discuss/17554/Share-my-one-pass-Python-solution-with-explainationdef trap(self, bars):if not bars or len(bars) < 3:return 0volume = 0left, right = 0, len(bars) - 1l_max, r_max = bars[left], bars[right]while left < right:l_max, r_max = max(bars[left], l_max), max(bars[right], r_max)if l_max <= r_max:volume += l_max - bars[left]left += 1else:volume += r_max - bars[right]right -= 1return volume哈希表、映射、集合部分
哈希表(Hash table)，也叫散列表，是根據關鍵碼值(key value)而直接進行訪問的數據結構。它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做哈希表(或散列表)。
哈希表復雜度分析：插入、刪除、大部分情況下時間復雜度都是O(1)，最壞????情況哈比表的長度比較小，導致多次哈希碰撞，時間復雜度退化成O(n)
1、Leetcode-242-有效的字母異位詞給定兩個字符串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的字母異位詞。 示例 1: 輸入: s = "anagram", t = "nagaram" 輸出: true 示例 2: 輸入: s = "rat", t = "car" 輸出: false 說明: 你可以假設字符串只包含小寫字母。解法: 1、暴力，sorted，兩個字符串是否相等 O(NlogN) 2、hash,map --> 統計每個字符的頻次class Solution:def isAnagram(self, s: str, t: str) -> bool:dict_1 = {}dict_2 = {}for item in s:dict_1[item] = dict_1.get(item,0) + 1for item in t:dict_2[item] = dict_2.get(item,0) + 1return dict_2 == dict_1提交時間 提交結果 執行用時 內存消耗 語言 幾秒前 通過 56 ms 13.5 MB Python32、Leetcode-49-字母異位詞分組給定一個字符串數組，將字母異位詞組合在一起。字母異位詞指字母相同，但排列不同的字符串。 示例: 輸入: ["eat", "tea", "tan", "ate", "nat", "bat"], 輸出: [["ate","eat","tea"],["nat","tan"],["bat"] ] 說明： 所有輸入均為小寫字母。 不考慮答案輸出的順序。class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:import collectionsdic = collections.defaultdict(list)for c in strs:count = [0] * 26for _ in c:count[ord(_) - ord('a')] += 1dic[tuple(count)].append(c)return dic.values()樹、二叉樹、二叉搜索樹部分
二維數據結構-樹和圖，區別是否構成環
鏈表是特殊化的樹，樹是特殊化的圖
二叉樹遍歷 Pre-order/In-order/Post-order
1、前序(Pre-order):根-左-右
2、中序(In-order):?左-根-右
3、后序(Post-order): 左-右-根
二叉搜索樹(Binary Search Tree)，查詢等操作時間復雜度都是log(n)，最壞情況是變成鏈表形式復雜度變為O(n)
二叉搜索樹，也稱有序二叉樹、排序二叉樹，是指一顆空樹或者具有下列性質的二叉樹：
左子樹所有節點的值均小于它的根節點的值
右子樹所有節點的值均大于它的根節點的值
重復：左右子樹也分別為二叉查找樹
泛型遞歸、樹的遞歸
遞歸
遞歸-循環
通過函數體來進行的循環
Python 代碼模板def recursion(level,param1,param2,...):# 終止條件if level > MAX_LEVEL:process_resultreturn# 過程邏輯process(level,data...)# 下一層self.recursion(level+1,p1,..思維要點: 1、不要人肉遞歸 2、拆解可重復解決的問題(重復子問題) 3、數學歸納法思維1、Leetcode-70-爬樓梯 假設你正在爬樓梯。需要 n 階你才能到達樓頂。 每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？ 注意：給定 n 是一個正整數。 示例 1： 輸入：2 輸出：2 解釋：有兩種方法可以爬到樓頂。 1. 1 階 + 1 階 2. 2 階 示例 2： 輸入：3 輸出：3 解釋：有三種方法可以爬到樓頂。 1. 1 階 + 1 階 + 1 階 2. 1 階 + 2 階 3. 2 階 + 1 階class Solution:# 只保存最近的三個值def climbStairs(self, n: int) -> int:if n<=2:return nelse:f1,f2,f3 = 1,2,3for i in range(3,n+1):f3 = f1 + f2f1 = f2f2 = f3return f3 2、Leetcode-22-括號生成 給出 n 代表生成括號的對數，請你寫出一個函數，使其能夠生成所有可能的并且有效的括號組合。例如，給出 n = 3，生成結果為： ["((()))","(()())","(())()","()(())","()()()" ]class Solution:def generateParenthesis(self, n: int) -> List[str]:result = []def recursion(s='',left=0,right=0):if len(s)==2*n:result.append(s)if left < n:recursion(s + '(',left+1,right)if left > right:recursion(s + ')',left,right+1)recursion()return result 3、Leetcode-226-翻轉二叉樹 翻轉一棵二叉樹。 示例： 輸入：4/ \2 7/ \ / \ 1 3 6 9 輸出：4/ \7 2/ \ / \ 9 6 3 1 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def invertTree(self, root: TreeNode) -> TreeNode:if not root:return Noneroot.left,root.right = root.right,root.leftself.invertTree(root.left)self.invertTree(root.right)return root 4、Leetcode-98-驗證二叉搜索樹給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。 假設一個二叉搜索樹具有如下特征： 節點的左子樹只包含小于當前節點的數。 節點的右子樹只包含大于當前節點的數。 所有左子樹和右子樹自身必須也是二叉搜索樹。 示例 1: 輸入:2/ \1 3 輸出: true # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def isValidBST(self, root: TreeNode) -> bool:def helper(node,lower = float("-inf"),upper = float("inf")):if not node:return Trueval = node.valif val <= lower or val >= upper:return Falseif not helper(node.left,lower,val):return Falseif not helper(node.right,val,upper):return Falsereturn Truereturn helper(root)時間復雜度為O(N),空間復雜度為O(N) 5、Leetcode-104-二叉樹的最大深度給定一個二叉樹，找出其最大深度。 二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。 class Solution:def maxDepth(self, root: TreeNode) -> int:if not root:return 0return max(self.maxDepth(root.left) + 1, self.maxDepth(root.right)+1) 時間復雜度為O(n),空間復雜度為O(logn),logn為樹的高度 6、Leetcode-111-二叉樹的最小深度 給定一個二叉樹，找出其最小深度。 最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。 說明: 葉子節點是指沒有子節點的節點。 示例: 給定二叉樹 [3,9,20,null,null,15,7],3/ \9 20/ \15 7 返回它的最小深度2方法1： class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0if not root.left:return self.minDepth(root.right) + 1if not root.right:return self.minDepth(root.left) + 1return min(self.minDepth(root.left),self.minDepth(root.right)) + 1方法2： class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0children = [root.left,root.right]if not any(children):return 1min_d = float("inf")for c in children:if c:min_d = min(self.minDepth(c),min_d)return min_d + 1時間復雜度為O(n)，空間復雜度為O(logn) 7、Leetcode-297-二叉樹的序列化與反序列化 序列化是將一個數據結構或者對象轉換為連續的比特位的操作，進而可以將轉換后的數據存儲在一個文件或者內存中，同時也可以通過網絡傳輸到另一個計算機環境，采取相反方式重構得到原數據。 請設計一個算法來實現二叉樹的序列化與反序列化。這里不限定你的序列 / 反序列化算法執行邏輯，你只需要保證一個二叉樹可以被序列化為一個字符串并且將這個字符串反序列化為原始的樹結構。 示例: 你可以將以下二叉樹：1/ \2 3/ \4 5序列化為 "[1,2,3,null,null,4,5]" 官方題解(https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/er-cha-shu-de-xu-lie-hua-yu-fan-xu-lie-hua-by-leet/) # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec:def serialize(self, root):"""Encodes a tree to a single string.:type root: TreeNode:rtype: str"""def rserialize(root,string):if root is None:string += "None,"else:string += str(root.val) + ","string = rserialize(root.left,string)string = rserialize(root.right,string)return stringreturn rserialize(root,"")def deserialize(self, data):"""Decodes your encoded data to tree.:type data: str:rtype: TreeNode"""def rdeserialize(l):if l[0] == "None":l.pop(0)return Noneroot = TreeNode(l[0])l.pop(0)root.left = rdeserialize(l)root.right = rdeserialize(l)return rootdata_list = data.split(',')root = rdeserialize(data_list)return root時間復雜度為O(n),空間復雜度為O(n) # Your Codec object will be instantiated and called as such: # codec = Codec() # codec.deserialize(codec.serialize(root)) 8、Leetcode-236-二叉樹的最近公共祖先 給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。 百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。” 例如，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]示例 1: 輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 輸出: 3 解釋: 節點 5 和節點 1 的最近公共祖先是節點 3。官方題解(https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetcod/) # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def __init__(self):self.ans = Nonedef lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':def recurse_tree(current_node):if not current_node:return Falseleft = recurse_tree(current_node.left)right = recurse_tree(current_node.right)mid = current_node == p or current_node == qif mid + left + right >= 2:self.ans = current_nodereturn mid or left or rightrecurse_tree(root)return self.ans時間復雜度O(n),空間復雜度O(n)9、Leetcode-105-從前序與中序遍歷序列構造二叉樹 根據一棵樹的前序遍歷與中序遍歷構造二叉樹。 注意: 你可以假設樹中沒有重復的元素。 例如，給出 前序遍歷 preorder = [3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7] 返回如下的二叉樹：3/ \9 20/ \15 7class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:if len(inorder) == 0:return Noneroot = TreeNode(preorder[0])mid = inorder.index(preorder[0])root.left = self.buildTree(preorder[1:mid+1],inorder[:mid])root.right = self.buildTree(preorder[mid+1:],inorder[mid+1:])return root 10、Leetcode-77-組合給定兩個整數 n 和 k，返回 1 ... n 中所有可能的 k 個數的組合。 示例: 輸入: n = 4, k = 2 輸出: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4], ] class Solution:def combine(self, n: int, k: int) -> List[List[int]]:def backtrack(first = 1,curr = []):if len(curr) == k:output.append(curr[:])for i in range(first,n+1):curr.append(i)backtrack(i+1,curr)curr.pop()output = []backtrack()return output 11、Leetcode-46-全排列給定一個沒有重復數字的序列，返回其所有可能的全排列。 示例: 輸入: [1,2,3] 輸出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]class Solution:def permute(self, nums: List[int]) -> List[List[int]]:def backtrack(first=0):if first == n:output.append(nums[:])for i in range(first,n):nums[first],nums[i] = nums[i],nums[first]backtrack(first+1)nums[i],nums[first] = nums[first],nums[i]n = len(nums)output = []backtrack()return output分治、回溯部分
分治、回溯是遞歸的一種，本質是將重復性問題分解以及最后組合每個子問題的結果
分治代碼模板： def divide_conquer(problem,param1,param2,...):# 遞歸終止條件if problem is None:print_resultreturn# 準備數據data = prepare_data(problem)subproblems = split_problem(problem,data)# 分治 子問題subresult1 = self.divide_conquer(subproblems[0],p1,...)subresult2 = self.divide_conquer(subproblems[1],p1,...)subresult3 = self.divide_conquer(subproblems[2],p1,...)..... # 收集子結果產生最后的結果result = process_result(subresult1,subresult2,..)# 清除當前層的狀態回溯，是簡單的一層一層去試探1、Leetcode-50-Pow(x,n) 實現 pow(x, n) ，即計算 x 的 n 次冪函數。 示例 1: 輸入: 2.00000, 10 輸出: 1024.00000 示例 2: 輸入: 2.10000, 3 輸出: 9.26100class Solution:def myPow(self, x: float, n: int) -> float:def helper(x,n):if n==0:return 1.0if n%2==0:return helper(x*x,n/2)else:return helper(x*x,(n-1)/2)*xif n<0:n = -nreturn 1/helper(x,n)return helper(x,n) 2、Leetcode-78-子集 給定一組不含重復元素的整數數組 nums，返回該數組所有可能的子集（冪集）。 說明：解集不能包含重復的子集。 示例: 輸入: nums = [1,2,3] 輸出: [[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[] ] class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:results = [[]]for num in nums:newsets = []for subset in results:new_subset = subset + [num]newsets.append(new_subset)results.extend(newsets)return resultsclass Solution:def subsets(self, nums: List[int]) -> List[List[int]]:res = [[]]for i in nums:res = res + [[i] + num for num in res]return res 3、Leetcode-169-多數元素給定一個大小為 n 的數組，找到其中的多數元素。多數元素是指在數組中出現次數大于 ? n/2 ? 的元素。 你可以假設數組是非空的，并且給定的數組總是存在多數元素。示例 1: 輸入: [3,2,3] 輸出: 3 分治法class Solution:def majorityElement(self, nums: List[int]) -> int:def majority_element_rec(first,end):if first == end:return nums[first]mid = (end-first)//2 + firstleft = majority_element_rec(first,mid)right = majority_element_rec(mid+1,end)if left == right:return leftleft_count = sum([1 for i in range(first,end+1) if nums[i]==left])right_count = sum([1 for i in range(first,end+1) if nums[i]==right])return left if left_count > right_count else rightreturn majority_element_rec(0,len(nums)-1)時間復雜度O(nlogn),空間復雜度O(n) 4、Leetcode-17-電話號碼的字母組合 給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。 給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。class Solution:def letterCombinations(self, digits: str) -> List[str]:phone = {"2":["a","b","c"],"3":["d","e","f"],"4":["g","h","i"],"5":["j","k","l"],"6":["m","n","o"],"7":["p","q","r","s"],"8":["t","u","v"],"9":["w","x","y","z"]}output = []def backtrack(combinations,next_digits):if len(next_digits)==0:output.append(combinations)else:for letter in phone[next_digits[0]]:backtrack(combinations + letter,next_digits[1:])if digits:backtrack("",digits)return output 5、Leetcode-51-N皇后問題 n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。 給定一個整數 n，返回所有不同的 n 皇后問題的解決方案。 每一種解法包含一個明確的 n 皇后問題的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。 示例: 輸入: 4 輸出: [[".Q..", // 解法 1"...Q","Q...","..Q."],["..Q.", // 解法 2"Q...","...Q",".Q.."] ] 解釋: 4 皇后問題存在兩個不同的解法。 官方題解(https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode/) class Solution:def solveNQueens(self, n: int) -> List[List[str]]:def could_place(row, col):return not (cols[col] + hill_diagonals[row - col] + dale_diagonals[row + col])def place_queen(row, col):queens.add((row, col))cols[col] = 1hill_diagonals[row - col] = 1dale_diagonals[row + col] = 1def remove_queen(row, col):queens.remove((row, col))cols[col] = 0hill_diagonals[row - col] = 0dale_diagonals[row + col] = 0def add_solution():solution = []for _, col in sorted(queens):solution.append('.' * col + 'Q' + '.' * (n - col - 1))output.append(solution)def backtrack(row = 0):for col in range(n):if could_place(row, col):place_queen(row, col)if row + 1 == n:add_solution()else:backtrack(row + 1)remove_queen(row, col)cols = [0] * nhill_diagonals = [0] * (2 * n - 1)dale_diagonals = [0] * (2 * n - 1)queens = set()output = []backtrack()return output深度優先搜索、廣度優先搜索
遍歷搜索：在樹(圖/狀態集)中尋找特定節點
搜索-遍歷：
-
每個節點都要訪問一次
-
每個節點僅僅要訪問一次
-
對于節點的訪問順序不限：深度優先、廣度優先
二分查找部分
二分查找的前提
1、目標函數單調性(單調遞增或遞減)
2、存在上下界(bound)
3、能夠通過索引訪問(index accessible)
代碼模板: left,right = 0,len(array)-1 while left <= right:mid = (left + right)/2if array[mid] == target:# find the targetbreak or return resultelif array[mid] < target:left = mid + 1else:right = mid - 11、Leetcode-69-x的平方根 實現 int sqrt(int x) 函數。 計算并返回 x 的平方根，其中 x 是非負整數。 由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。 示例 1: 輸入: 4 輸出: 2二分查找法 class Solution:def mySqrt(self, x: int) -> int:left,right = 0,x//2 + 1while left < right:mid = left + (right-left+1)//2if mid*mid > x:right = mid -1else:left = mid return left牛頓法 class Solution:def mySqrt(self, x: int) -> int:r = xwhile r*r > x:r = (r+x//r)//2return r2、Leetcode-367-有效的完全平方數 給定一個正整數 num，編寫一個函數，如果 num 是一個完全平方數，則返回 True，否則返回 False。 說明：不要使用任何內置的庫函數，如 sqrt。 示例 1： 輸入：16 輸出：True 示例 2： 輸入：14 輸出：False class Solution:def isPerfectSquare(self, num: int) -> bool:x = numwhile x*x>num:x = (x + num//x)//2if x*x==num:return Truereturn False3、Leetcode-33-搜索旋轉排序數組 假設按照升序排序的數組在預先未知的某個點上進行了旋轉。( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。搜索一個給定的目標值，如果數組中存在這個目標值，則返回它的索引，否則返回 -1 。 你可以假設數組中不存在重復的元素。 你的算法時間復雜度必須是 O(log n) 級別。示例 1: 輸入: nums = [4,5,6,7,0,1,2], target = 0 輸出: 4 class Solution:def search(self, nums: List[int], target: int) -> int:left,right = 0,len(nums)-1while left < right:mid = left + (right - left)//2if nums[0] <= nums[mid] and (target > nums[mid] or target < nums[0]):left = mid + 1elif(target > nums[mid] and target < nums[0]):left = mid + 1else:right = midif left == right and nums[left] == target: return leftreturn -1 4、編寫一個高效的算法來判斷 m x n 矩陣中，是否存在一個目標值。該矩陣具有如下特性： 每行中的整數從左到右按升序排列。 每行的第一個整數大于前一行的最后一個整數。 示例 1:輸入: matrix = [[1, 3, 5, 7],[10, 11, 16, 20],[23, 30, 34, 50] ] target = 3 輸出: true class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:if len(matrix)==0:return Falsei,row,col = 0,len(matrix)-1,len(matrix[0])-1while i <= row and 0 <=col:if matrix[i][col]>target:col -= 1elif matrix[i][col]==target:return Trueelse:i += 1return False 5、Leetcode-153-尋找旋轉數組中的最小值 假設按照升序排序的數組在預先未知的某個點上進行了旋轉。 ( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。 請找出其中最小的元素。 你可以假設數組中不存在重復元素。 示例 1: 輸入: [3,4,5,1,2] 輸出: 1 示例 2: 輸入: [4,5,6,7,0,1,2] 輸出: 0 class Solution:def findMin(self, nums: List[int]) -> int:if len(nums) == 1:return nums[0]left,right = 0,len(nums)-1if nums[right] > nums[0]:return nums[0]while left <= right:mid = left + (right - left)//2if nums[mid] > nums[mid+1]:return nums[mid+1]if nums[mid-1] > nums[mid]:return nums[mid]if nums[mid] > nums[0]:left = mid + 1else:right = mid - 1貪心算法部分
貪心算法是一種在每一步選擇中都采取在當前狀態下最好或最優的選擇，從而希望導致結果是全局最好或最優的算法。簡單地說，問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解，這種子問題最優解成為最優子結構。貪心算法與動態規劃的不同在于它對每個子問題的解決方案都作出選擇不能回退。動態規劃則會保存以前的運算結果，并根據以前的結果對當前進行選擇，有回退功能。
1、Leetcode-455-分發餅干 假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。對每個孩子 i ，都有一個胃口值 gi ，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j ，都有一個尺寸 sj 。如果 sj >= gi ，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值。 注意： 你可以假設胃口值為正。 一個小朋友最多只能擁有一塊餅干。 示例 1: 輸入: [1,2,3], [1,1] 輸出: 1 解釋: 你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。 雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。 所以你應該輸出1。 貪心算法 class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:g.sort()s.sort()child = 0cookie = 0while child < len(g) and cookie < len(s):if g[child] <= s[cookie]:child += 1cookie += 1return child2、Leetcode-122-買股票的最佳時機II 給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。 設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。 注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。示例 1:輸入: [7,1,5,3,6,4] 輸出: 7 解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。class Solution:def maxProfit(self, prices: List[int]) -> int:total = 0for i in range(len(prices)-1):if prices[i+1] > prices[i]:total += (prices[i+1]-prices[i])return total3、Leetcode-55-跳躍游戲 給定一個非負整數數組，你最初位于數組的第一個位置。 數組中的每個元素代表你在該位置可以跳躍的最大長度。 判斷你是否能夠到達最后一個位置。示例 1: 輸入: [2,3,1,1,4] 輸出: true 解釋: 我們可以先跳 1 步，從位置 0 到達 位置 1, 然后再從位置 1 跳 3 步到達最后一個位置。class Solution:def canJump(self, nums: List[int]) -> bool:endLength = len(nums) - 1for i in range(len(nums)-1,-1,-1):if nums[i] + i >= endLength:endLength = ireturn endLength == 04、Leetcode-860-檸檬水找零在檸檬水攤上，每一杯檸檬水的售價為 5 美元。 顧客排隊購買你的產品，（按賬單 bills 支付的順序）一次購買一杯。 每位顧客只買一杯檸檬水，然后向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元。 注意，一開始你手頭沒有任何零錢。 如果你能給每位顧客正確找零，返回 true ，否則返回 false 。示例 1： 輸入：[5,5,5,10,20] 輸出：true 解釋： 前 3 位顧客那里，我們按順序收取 3 張 5 美元的鈔票。 第 4 位顧客那里，我們收取一張 10 美元的鈔票，并返還 5 美元。 第 5 位顧客那里，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。 由于所有客戶都得到了正確的找零，所以我們輸出 true。class Solution:def lemonadeChange(self, bills: List[int]) -> bool:five,ten = 0,0for bill in bills:if bill == 5:five += 1elif bill == 10:if not five:return Falsefive -= 1ten += 1else:if five and ten:five -= 1ten -= 1elif five>=3:five -= 3else:return Falsereturn True5、Leetcode-874-模擬行走機器人機器人在一個無限大小的網格上行走，從點 (0, 0) 處開始出發，面向北方。該機器人可以接收以下三種類型的命令： -2：向左轉 90 度 -1：向右轉 90 度 1 <= x <= 9：向前移動 x 個單位長度 在網格上有一些格子被視為障礙物。 第 i 個障礙物位于網格點 (obstacles[i][0], obstacles[i][1]) 如果機器人試圖走到障礙物上方，那么它將停留在障礙物的前一個網格方塊上，但仍然可以繼續該路線的其余部分。 返回從原點到機器人的最大歐式距離的平方。 示例 1：輸入: commands = [4,-1,3], obstacles = [] 輸出: 25 解釋: 機器人將會到達 (3, 4)class Solution:def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:dx,dy,x,y = 0,1,0,0distance = 0obs_dict = {}for obs in obstacles:obs_dict[tuple(obs)] = 0for com in commands:if com == -2:dx,dy = -dy,dxelif com == -1:dx,dy = dy,-dxelse:for j in range(com):next_x = x + dxnext_y = y + dyif (next_x,next_y) in obs_dict:breakx,y = next_x,next_ydistance = max(distance,x*x+y*y)return distance6、Leetcode-45-跳躍游戲II 給定一個非負整數數組，你最初位于數組的第一個位置。 數組中的每個元素代表你在該位置可以跳躍的最大長度。 你的目標是使用最少的跳躍次數到達數組的最后一個位置。示例: 輸入: [2,3,1,1,4] 輸出: 2 解釋: 跳到最后一個位置的最小跳躍數是 2。從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達數組的最后一個位置。class Solution:def jump(self, nums: List[int]) -> int:if nums.count(1) == len(nums):return len(nums)-1def fun(n):if not n:return 0for k,v in enumerate(n):if v + k >= len(n):return fun(n[:k]) + 1return fun(nums[:-1])動態規劃部分
動態規劃和遞歸或者分治沒有根本上的區別(關鍵看有無最優的子結構)
共性：找到重復子問題
差異性：最優子結構、中途可以淘汰次優解
Bottom Up- 自底向上 F[n] = F[n-1] + F[n-2] a[0] = 0, a[1] = 1 for i in range(2,n+1):a[i] = a[i-1] + a[i-2]a[n] 0,1,1,2,3,5,8,13狀態轉移方程(DP方程) opt[i,j] = opt[i+1,j] + opt[i,j+1] 完整邏輯: if a[i,j]='空地':opt[i,j] = opt[i+1,j] + opt[i,j+1] else opt[i,j]=0動態規劃關鍵點: 1、最優子結構 opt[n] = best_od(opt[n-1],opt[n-2],...) 2、存儲中間狀態: opt[i] 3、遞推公式: Fib: opt[i] = opt[n-1] + opt[n-2] 二維路徑: opt[i,j] = opt[i+1][j] + opt[i][j+1](且判斷a[i,j]是否空地)1、Leetcode-62-不同路徑 一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）。 機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）。 問總共有多少條不同的路徑？ 示例 1: 輸入: m = 3, n = 2 輸出: 3 解釋: 從左上角開始，總共有 3 條路徑可以到達右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右 方法：動態規劃 思路：第一行 + 第一列都是在邊界，所以只能為1 + 動態方程class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[0]*n]*mfor i in range(m):dp[i][0] = 1for j in range(n):dp[0][j] = 1for i in range(1,m):for j in range(1,n):dp[i][j] = dp[i-1][j] + dp[i][j-1]return dp[-1][-1] 2、Leetcode-1143-最長公共子序列給定兩個字符串 text1 和 text2，返回這兩個字符串的最長公共子序列。 一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。兩個字符串的「公共子序列」是這兩個字符串所共同擁有的子序列。 若這兩個字符串沒有公共子序列，則返回 0。 示例 1: 輸入：text1 = "abcde", text2 = "ace" 輸出：3 解釋：最長公共子序列是 "ace"，它的長度為 3 class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:if not text1 or not text2:return 0m,n = len(text1),len(text2)dp = [[0]*(n+1) for _ in range(m+1)]for i in range(1,m+1):for j in range(1,n+1):if text1[i-1] == text2[j-1]:dp[i][j] = 1 + dp[i-1][j-1]else:dp[i][j] = max(dp[i-1][j],dp[i][j-1])return dp[m][n] 3、Leetcode-120-三角形最小路徑和給定一個三角形，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結點上。 例如，給定三角形： [[2],[3,4],[6,5,7],[4,1,8,3] ] 自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11） class Solution:def minimumTotal(self, triangle: List[List[int]]) -> int:"""dp[i][j] = triangle[i][j] + min(dp[i+1][j],dp[i+1][j+1])"""dp = trianglefor i in range(len(triangle)-2,-1,-1):for j in range(len(triangle[i])):dp[i][j] += min(dp[i+1][j],dp[i+1][j+1])return dp[0][0] 4、Leetcode-53-最大子序和給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。 示例: 輸入: [-2,1,-3,4,-1,2,1,-5,4], 輸出: 6 解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。class Solution:def maxSubArray(self, nums: List[int]) -> int:for i in range(1,len(nums)):nums[i] = max(nums[i-1],0) + nums[i]return max(nums) 5、Leetcode-152-乘積最大子序列 給定一個整數數組 nums ，找出一個序列中乘積最大的連續子序列（該序列至少包含一個數）。 示例 1: 輸入: [2,3,-2,4] 輸出: 6 解釋: 子數組 [2,3] 有最大乘積 6。 示例 2: 輸入: [-2,0,-1] 輸出: 0 解釋: 結果不能為 2, 因為 [-2,-1] 不是子數組。 class Solution:def maxProduct(self,nums:List[int])->int:ma,mi,res = nums[0]if nums[i]<0:ma,mi = mi,mafor i in range(len(nums)):ma = max(ma*nums[i],nums[i])mi = min(mi*nums[i],nums[i])res = max(res,ma)return res 6、Leetcode-322-零錢兌換 給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。 示例 1: 輸入: coins = [1, 2, 5], amount = 11 輸出: 3 解釋: 11 = 5 + 5 + 1 class Solution:def coinChange(self, coins: List[int], amount: int) -> int:"""f(n) = min{f(n-k),k in [1,2,5]} + 1"""MAX = float("inf")dp = [0] + [MAX] * amountfor i in range(1,amount+1):dp[i] = min([dp[i-c] if i-c >=0 else MAX for c in coins]) + 1return [dp[amount],-1][dp[amount]==MAX] 7、Leetcode-198-打家劫舍 你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。 給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。 示例 1: 輸入: [1,2,3,1] 輸出: 4 解釋: 偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。偷竊到的最高金額 = 1 + 3 = 4 。class Solution:def rob(self, nums: List[int]) -> int:cur,pre = 0,0for num in nums:cur,pre = max(pre + num, cur),curreturn cur 8、Leetcode-213-打家劫舍-II 你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都圍成一圈，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。 給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額 示例 1: 輸入: [2,3,2] 輸出: 3 解釋: 你不能先偷竊 1 號房屋（金額 = 2），然后偷竊 3 號房屋（金額 = 2）, 因為他們是相鄰的。class Solution:def rob(self, nums: List[int]) -> int:def my_rob(nums):cur,pre = 0,0for num in nums:pre,cur = cur,max(pre+num,cur)return curreturn max(my_rob(nums[:-1]),my_rob(nums[1:])) if len(nums)!=1 else nums[0] 動態規劃解決股票系列問題 狀態轉移框架; base case: dp[-1][k][0] = dp[i][0][0] = 0 dp[-1][k][1] = dp[i][0][1] = -float("inf") 狀態轉移方程: dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i])case-1(k=1的情況): Leetcode_121_買賣股票的最佳時機 給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。 如果你最多只允許完成一筆交易（即買入和賣出一支股票），設計一個算法來計算你所能獲取的最大利潤。 注意你不能在買入股票前賣出股票。示例 1: 輸入: [7,1,5,3,6,4] 輸出: 5 解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。class Solution:def maxProfit(self, prices: List[int]) -> int:dp_i_0,dp_i_1 = 0,float("-inf")for i in range(len(prices)):dp_i_0 = max(dp_i_0,dp_i_1 + prices[i])dp_i_1 = max(dp_i_1,-prices[i])return dp_i_0case_2(k=正無窮的情況):Leetcode_122_買賣股票的最佳時機II 給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。 設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。 注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。 示例 1: 輸入: [7,1,5,3,6,4] 輸出: 7 解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。分析: 在k=正無窮的情況下，上述狀態轉移方程 dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i]) 轉化為 dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k][0] - prices[i]) ==> dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i]) code:class Solution:def maxProfit(self, prices: List[int]) -> int:dp_i_0,dp_i_1 = 0,-float("inf")for i in range(len(prices)):temp = dp_i_0dp_i_0 = max(dp_i_0,dp_i_1 + prices[i])dp_i_1 = max(dp_i_1,temp - prices[i])return dp_i_0case_3(添加手續費):Leetcode_714_買賣股票最佳時機含手續費 給定一個整數數組 prices，其中第 i 個元素代表了第 i 天的股票價格 ；非負整數 fee 代表了交易股票的手續費用。 你可以無限次地完成交易，但是你每次交易都需要付手續費。如果你已經購買了一個股票，在賣出它之前你就不能再繼續購買股票了。 返回獲得利潤的最大值。 示例 1: 輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2 輸出: 8 解釋: 能夠達到的最大利潤: 在此處買入 prices[0] = 1 在此處賣出 prices[3] = 8 在此處買入 prices[4] = 4 在此處賣出 prices[5] = 9 總利潤: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.class Solution:def maxProfit(self, prices: List[int], fee: int) -> int:n = len(prices)dp_i_0,dp_i_1 = 0,-float("inf")for price in prices:item = dp_i_0dp_i_0 = max(dp_i_0,dp_i_1+price)dp_i_1 = max(dp_i_1,dp_i_0-price-fee)return dp_i_0case_4(隔一天才能購買):Leetcode_309_最佳買賣股票時機含冷凍期 給定一個整數數組，其中第 i 個元素代表了第 i 天的股票價格 。 設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）: 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。 賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。 示例: 輸入: [1,2,3,0,2] 輸出: 3 解釋: 對應的交易狀態為: [買入, 賣出, 冷凍期, 買入, 賣出]思路: 狀態轉移方程: dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1],dp[i-2][0] - prices[i]) 注：i天購買時，從i-2狀態轉移 class Solution:def maxProfit(self, prices: List[int]) -> int:n = len(prices)dp_i_0,dp_i_1,da_pre = 0,float("-inf"),0for i in range(n):temp = dp_i_0dp_i_0 = max(dp_i_0,dp_i_1 + prices[i])dp_i_1 = max(dp_i_1,da_pre - prices[i])da_pre = tempreturn dp_i_0case_5(k=2情況下):leetcode_123_買賣股票的最佳時機III 給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。 設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。 注意: 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。示例 1: 輸入: [3,3,5,0,0,3,1,4] 輸出: 6 解釋: 在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出，這筆交易所能獲得利潤 = 3-0 = 3 。隨后，在第 7 天（股票價格 = 1）的時候買入，在第 8 天 （股票價格 = 4）的時候賣出，這筆交易所能獲得利潤 = 4-1 = 3 。k = 1,2,狀態轉移方程: dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i]) => p[i][1][0] = max(dp[i-1][1][0],dp[i-1][1][1] + prices[i]) dp[i][1][1] = max(dp[i-1][1][1],dp[i-1][0][0] - prices[i]) p[i][2][0] = max(dp[i-1][2][0],dp[i-1][2][1] + prices[i]) dp[i][2][1] = max(dp[i-1][2][1],dp[i-1][1][0] - prices[i])class Solution:def maxProfit(self, prices: List[int]) -> int:dp_i10,dp_i11,dp_i20,dp_i21 = 0,-float("inf"),0,-float('inf')for price in prices:dp_i10 = max(dp_i10,dp_i11 + price)dp_i11 = max(dp_i11,-price)dp_i20 = max(dp_i20,dp_i21 + price)dp_i21 = max(dp_i21,dp_i10 - price)return dp_i20?
總結
以上是生活随笔為你收集整理的Leetcode-一篇帖子就够啦的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： NLP-基础知识-007(机器学习-朴素
- 下一篇： 更改hive列名