leetcode hot100(第二部分) + python(c++)
生活随笔
收集整理的這篇文章主要介紹了
leetcode hot100(第二部分) + python(c++)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
50-1. 乘積最大子數組
思路1:找到狀態轉移方程:
maxf[i]:表示在i處最大連乘數
minf[i]:表示在i處最小連乘數
maxf[i] = max(nums[i],nums[i]*minf[i-1],nums[i]*maxf[i-1])
minf[i] = min(nums[i],nums[i]*minf[i-1],nums[i]*maxf[i-1])
思路2:優化版 由于第 i?個狀態只和第 i - 1個狀態相關，可以只用兩個變量來維護 i - 1時刻的狀態，一個維護 max, 一個維護 min
class Solution:def maxProduct(self, nums):min_value = nums[0]max_value = nums[0]res = nums[0]for i in range(1, len(nums)):mx = max_valuemn = min_valuemax_value = max(nums[i], nums[i]*mx, nums[i]*mn)min_value = min(nums[i], nums[i]*mx, nums[i]*mn)print('==max_value:', max_value)print('==min_value:', min_value)res = max(max_value, res)print('==res:', res) nums = [2,3,-2,4] sol = Solution() sol.maxProduct(nums)50-2.三個數的最大乘積
思路:從小到大排序，如果都是正數則結果是最后三個相乘，如有正有負，結果有可能就是前兩個相乘在乘以最后一個正數
class Solution:def maximumProduct(self, nums):nums = sorted(nums)return max(nums[-1]*nums[-2]*nums[-3], nums[0]*nums[1]*nums[-1])# nums = [1, 2, 3, 4] nums = [-1, -2, 1, 2, 3] sol = Solution() sol.maximumProduct(nums)51. 最小棧
class MinStack:def __init__(self):"""initialize your data structure here."""self.stack = []def push(self, x: int) -> None:self.stack.append(x)def pop(self) -> None:self.stack.pop()def top(self) -> int:return self.stack[-1]def min(self) -> int:return min(self.stack)# Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.min()c++實現:
class MinStack { public:stack<int> stack_A;stack<int> min_stack;/** initialize your data structure here. */MinStack() {}void push(int x) {stack_A.push(x);if(min_stack.empty() || min_stack.top()>=x){min_stack.push(x);}}void pop() {if(stack_A.top() == min_stack.top()){min_stack.pop();}stack_A.pop();}int top() {return stack_A.top();}int min() {return min_stack.top();} };/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(x);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->min();*/52.多數元素
排序:
class Solution:def majorityElement(self, nums: List[int]) -> int:return sorted(nums)[len(nums)//2]投票法(最優解):
class Solution:def majorityElement(self, nums: List[int]) -> int:votes = 0for num in nums:if votes == 0:x = numif num == x:votes += 1else:votes -= 1# print('==x:', x)# print('==votes:', votes)return x53-1.打家劫舍
class Solution(object):def rob(self, nums):""":type nums: List[int]:rtype: int"""if len(nums)==0:return 0if len(nums)<2:return max(nums)opt = [0]*len(nums)opt[0] = nums[0]opt[1] = max(nums[0],nums[1])for i in range(2, len(nums)):opt[i] = max(opt[i-2]+nums[i],opt[i-1])print('=opt:', opt)return max(opt)nums = [2,7,9,3,1] sol = Solution() sol.rob(nums)53-2. 打家劫舍 II
class Solution(object):def rob(self, nums):""":type nums: List[int]:rtype: int"""if len(nums)==0:return 0if len(nums)<=2:return max(nums)opt1 = [0] * len(nums)opt2 = [0] * len(nums)#不搶第一家opt1[0] = 0opt1[1] = nums[1]#不搶最后一家opt2[0] = nums[0]opt2[1] = max(nums[:2])for i in range(2,len(nums)):opt1[i]=max(opt1[i-2]+nums[i], opt1[i-1])print(opt1)for i in range(2, len(nums)-1):opt2[i] = max(opt2[i - 2] + nums[i], opt2[i - 1])print(opt2)return max(opt1[-1],opt2[-2]) nums=[1,2,3,1] sol = Solution() res = sol.rob(nums) print('res:') print(res)53-3. 打家劫舍 III
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def helper(self,node):if node is None:return 0, 0choose_l_value,no_choose_l_value = self.helper(node.left)choose_r_value,no_choose_r_value = self.helper(node.right)return node.val+no_choose_l_value+no_choose_r_value, max(choose_l_value,no_choose_l_value)+max(choose_r_value,no_choose_r_value)def rob(self, root: TreeNode) -> int:return max(self.helper(root))54.島嶼數量
思路：遞歸 也就是求1的連通域個數,從１開始進行遍歷,將遍歷過得1依次置位0,遍歷的次數就是連通域個數
# 求1的連通域個數,從１開始進行遍歷,將遍歷過得1依次置位0,遍歷的次數就是連通域個數 class Solution:def helper(self, i, j, h, w):if i < 0 or i >= h or j < 0 or j >= w or self.grid[i][j] == "0":returnself.grid[i][j] = "0"self.helper(i - 1, j, h, w)self.helper(i + 1, j, h, w)self.helper(i, j-1, h, w)self.helper(i, j+1, h, w)def numIslands(self, grid):if len(grid) == 0:return []self.grid = gridh, w = len(grid), len(grid[0])nums = 0for i in range(h):for j in range(w):if self.grid[i][j] == "1":nums += 1self.helper(i, j, h, w)print('==self.grid:', self.grid)print('==nums:', nums)return numsgrid = [["1", "1", "1", "1", "0"],["1", "1", "0", "1", "0"],["1", "1", "0", "0", "0"],["0", "0", "0", "0", "0"] ]sol = Solution() sol.numIslands(grid)?c++實現:
class Solution { public:vector<vector<char>> grid;int h;int w;void help(int i, int j){if(i < 0 || i > this->h - 1 || j < 0 || j > this->w - 1 || this->grid[i][j] == '0'){return ;}this->grid[i][j] = '0';help(i - 1, j);help(i + 1, j);help(i, j - 1);help(i, j + 1);}int numIslands(vector<vector<char>>& grid) {this->grid = grid;this->h = grid.size();this->w = grid[0].size();int res = 0;for(int i = 0; i < this->h; i++){for(int j = 0; j < this->w; j++){if(this->grid[i][j] == '1'){res += 1;}help(i, j);}}return res;} };55.反轉鏈表
思路１：雙指針?
class Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""# 申請兩個節點，pre和 cur，pre指向Nonepre = Nonecur = head# 遍歷鏈表，while循環里面的內容其實可以寫成一行while cur:# 記錄當前節點的下一個節點tmp = cur.next# 然后將當前節點指向precur.next = pre# pre和cur節點都前進一位pre = curcur = tmpreturn prec++實現:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/ class Solution { public:ListNode* reverseList(ListNode* head) {ListNode* pre = nullptr;ListNode* temp = head;while(head){temp = head->next;head->next = pre;pre = head;head = temp;}return pre;} };思路2.遞歸法
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def reverseList(self, head: ListNode) -> ListNode:# pre = None# cur = head# while cur:# node = cur.next# cur.next = pre# pre = cur# cur = node# return preif head is None or head.next is None:return headnew_node = self.reverseList(head.next)print('head.val',head.val)head.next.next = headhead.next = Nonereturn new_node56-1.?課程表
標題思路:對于這種從圖找拓撲排序?,只有有向無環圖能夠找到,將入度為0的節點先進入隊列,在利用bfs進行出隊處理,此時將出隊的節點的下一個節點的度進行減一計數,同時遍歷的節點數進行加一,最終節點都進行了遍歷,則說明找到了拓撲排序.
思路1:用鄰接列表
class Solution:def canFinish(self, numCourses, prerequisites):indegrees = [0] * numCourses # 入度列表print('==indegrees:', indegrees)adjacency = [[] for i in range(numCourses)] # 鄰接列表 存儲節點的下一個節點print('=adjacency:', adjacency)#得到入度和每個課程的鄰接列表for cur, pre in prerequisites:indegrees[cur] += 1adjacency[pre].append(cur)print('====indegrees:', indegrees)print('====adjacency:', adjacency)quene = []# 如果度為0 就進入隊列for i in range(len(indegrees)):if indegrees[i] == 0:quene.append(i)print('==quene:', quene)num_nodes = 0while quene:node = quene.pop(0)num_nodes += 1for next_node in adjacency[node]:indegrees[next_node] -= 1 # 找出下一個點相應的度-1if indegrees[next_node] == 0: # 入度為0quene.append(next_node)print('==num_nodes:', num_nodes)return num_nodes == numCourses# numCourses, prerequisites = 2, [[1, 0]] # numCourses, prerequisites = 2, [[1, 0], [0, 1]] numCourses, prerequisites = 6, [[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]] sol = Solution() res = sol.canFinish(numCourses, prerequisites) print('res:', res)思路2:用鄰接矩陣的bfs
class Solution:def canFinish(self, numCourses, prerequisites):indegrees = [0] * numCourses # 度列表adjacency = [[0 for i in range(numCourses)] for i in range(numCourses)] # 鄰接矩陣 表示節點之間關系print('==init adjacency:', adjacency)for cur, pre in prerequisites:indegrees[cur] += 1adjacency[pre][cur] = 1print('==init adjacency complete:', adjacency)print('==init indegrees complete:', indegrees)quene = []for i in range(len(indegrees)):if indegrees[i] == 0:quene.append(i)print('==quene:', quene)num_nodes = 0while quene:node = quene.pop()num_nodes += 1for j in range(numCourses):if adjacency[node][j] == 1:next_node = jadjacency[node][j] -= 1indegrees[next_node] -= 1if indegrees[next_node] == 0:quene.append(next_node)print('==num_nodes:', num_nodes)return num_nodes == numCourses# numCourses = 2 # prerequisites = [[0, 1]] numCourses = 4 prerequisites = [[1, 0], [2, 0], [3,1],[3,2]] sol = Solution() sol.canFinish(numCourses, prerequisites)56-2:課程表 II
思路：有向無環圖，ＢＦＳ遍歷?
class Solution:def canFinish(self, numCourses, prerequisites):indegrees = [0] * numCourses # 入度列表print('==indegrees:', indegrees)adjacency = [[] for i in range(numCourses)] # 鄰接列表print('=adjacency:', adjacency)#得到入度和每個課程的鄰接列表for cur, pre in prerequisites:indegrees[cur] += 1adjacency[pre].append(cur)print('====indegrees:', indegrees)print('====adjacency:', adjacency)quene = []# 如果度為0 就進入隊列for i in range(len(indegrees)):if indegrees[i] == 0:quene.append(i)print('==quene:', quene)num_nodes = 0learn_node = []while quene:node = quene.pop(0)print('=======node', node)learn_node.append(node)num_nodes += 1for next_node in adjacency[node]:indegrees[next_node] -= 1 # 找出下一個點相應的度-1if indegrees[next_node] == 0: # 入度為0quene.append(next_node)print('==num_nodes:', num_nodes)return learn_node if num_nodes == numCourses else []# numCourses, prerequisites = 2, [[1, 0]] # numCourses, prerequisites = 2, [[1, 0], [0, 1]] numCourses, prerequisites = 6, [[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]] sol = Solution() res = sol.canFinish(numCourses, prerequisites) print('res:', res)思路2:用鄰接矩陣的bfs
class Solution:def canFinish(self, numCourses, prerequisites):indegrees = [0] * numCourses # 度列表adjacency = [[0 for i in range(numCourses)] for i in range(numCourses)] # 鄰接矩陣 表示節點之間關系print('==init adjacency:', adjacency)for cur, pre in prerequisites:indegrees[cur] += 1adjacency[pre][cur] = 1print('==init adjacency complete:', adjacency)print('==init indegrees complete:', indegrees)quene = []for i in range(len(indegrees)):if indegrees[i] == 0:quene.append(i)print('==quene:', quene)num_nodes = 0learn_nodes = []while quene:node = quene.pop()learn_nodes.append(node)num_nodes += 1for j in range(numCourses):if adjacency[node][j] == 1:next_node = jadjacency[node][j] -= 1indegrees[next_node] -= 1if indegrees[next_node] == 0:quene.append(next_node)print('==num_nodes:', num_nodes)print('=learn_nodes:', learn_nodes)return learn_nodes if num_nodes == numCourses else []# numCourses = 2 # prerequisites = [[0, 1]] numCourses = 4 prerequisites = [[1, 0], [2, 0], [3,1],[3,2]] sol = Solution() sol.canFinish(numCourses, prerequisites)57.實現 Trie (前綴樹)
思路:利用字典存儲每個單詞，同時用特殊字符結尾。
class Trie:def __init__(self):"""Initialize your data structure here."""self.root = {}self.word_end = -1def insert(self, word):"""Inserts a word into the trie."""curNode = self.rootfor c in word:if c not in curNode:curNode[c] = {}curNode = curNode[c]curNode[self.word_end] = True# print('==curNode:', curNode)def search(self, word):"""Returns if the word is in the trie."""curNode = self.rootfor c in word:if c not in curNode:return FalsecurNode = curNode[c]if self.word_end not in curNode:return Falsereturn Truedef startsWith(self, prefix):"""Returns if there is any word in the trie that starts with the given prefix."""curNode = self.rootfor c in prefix:if c not in curNode:return FalsecurNode = curNode[c]return Trueword = 'apple' prefix = 'ad' obj = Trie() obj.insert(word='apple') obj.insert(word='add') # obj.insert(word='app') print('tree:', obj.root) param_2 = obj.search(word) print('search res:', param_2) param_3 = obj.startsWith(prefix) print('==param_3:', param_3)58.數組中的第K個最大元素
思路：排序 取第ｋ個值就可
class Solution:def quicksort(self, arr):if len(arr) <= 1:return arrprivot = arr[len(arr) // 2]left = [i for i in arr if i < privot]middle = [i for i in arr if i == privot]right = [i for i in arr if i > privot]# left = [arr[i] for i in range(len(arr)) if arr[i] < privot]# middle = [arr[i] for i in range(len(arr)) if arr[i] == privot]# right = [arr[i] for i in range(len(arr)) if arr[i] > privot]return self.quicksort(left) + middle + self.quicksort(right)def findKthLargest(self, nums, k):return self.quicksort(nums)[::-1][k-1]# nums = [3, 2, 1, 5, 6, 4] # k = 2 nums = [3,2,3,1,2,4,5,5,6] k = 4 sol = Solution() res = sol.findKthLargest(nums, k) print('res:', res)思路2:topk問題用最小堆?
class Solution:def findKthLargest(self, nums, k):arr = []heapq.heapify(arr)for i in range(k):heapq.heappush(arr, nums[i])for i in range(k, len(nums)):heapq.heappush(arr, nums[i])heapq.heappop(arr)print('==arr:', arr)return arr[0]arr = [3,2,1,5,6,4] k = 2 sol = Solution() sol.findKthLargest(arr, k)59.最大正方形
思路:題目既然求最大正方形面積，那就先由2*2正方形拓展更大即可，也就是可以用動態規劃來存儲左上角，左邊，上邊的最小值，也是正方形邊長
１．轉移方程為 dp[i][j] = min(dp[i-1][j],dp[i][j-1].dp[i-1][j-1])+1
２．初始化邊界條件為: dp[:][0] = matrix[:][0] dp[0][:] = matrix[0][:]
class Solution:def maximalSquare(self, matrix):max_side = 0h,w = len(matrix),len(matrix[0])dp = [[0 for i in range(w)] for i in range(h)]print('初始化dp',np.array(dp))for i in range(h):dp[i][0] = int(matrix[i][0])max_side = max(max_side, dp[i][0])for i in range(w):dp[0][i] = int(matrix[0][i])max_side = max(max_side, dp[0][i])print('初始化邊界dp',np.array(dp))for i in range(1,h):for j in range(1,w):if matrix[i][j]=='1':dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1max_side = max(max_side, dp[i][j])print('轉移好dp',np.array(dp))return max_side**2matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] # matrix = [["0","1"],["1","0"]] sol = Solution() res= sol.maximalSquare(matrix) print(res)60.翻轉二叉樹
思路:遞歸遍歷左右子樹進行交換即可
# 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 root is None:return Noneleft = self.invertTree(root.left)right = self.invertTree(root.right)root.left = rightroot.right = leftreturn rootc++實現:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { public:TreeNode* invertTree(TreeNode* root) {if(root == nullptr){return nullptr;}TreeNode* left = invertTree(root->left);TreeNode* right = invertTree(root->right);root->left = right;root->right = left;return root;} };61.請判斷一個鏈表是否為回文鏈表
利用列表將列表值進行拷貝，在判斷是否是回文字符串
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def isPalindrome(self, head: ListNode) -> bool:stack= []while head:stack.append(head.val)head = head.nextreturn stack==stack[::-1]c++實現:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/ class Solution { public:bool isPalindrome(ListNode* head) {vector<int> res;while(head){res.push_back(head->val);head = head->next;}int left=0;int right=res.size()-1;while(left<right){if(res[left]==res[right]){left+=1;right-=1;}else{return false;}}return true;} };62:二叉樹的最近公共祖先
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root is None or root==p or root==q:#遞歸終止條件 節點為空 或者節點等于p,q其中之一return rootleft = self.lowestCommonAncestor(root.left, p, q)#遍歷左子樹right = self.lowestCommonAncestor(root.right, p, q)#遍歷右子樹if left is None:#左子樹為空 就去右子樹 return rightif right is None:#右子樹為空 就去左子樹 return leftreturn root#左右子樹都不為空 說明找到了節點c++實現:
代碼段 小部件
63.除自身以外數組的乘積
思路１：超時
#超時時間復雜度O(N) class Solution:def productExceptSelf(self, nums):output = len(nums)*[0]for i in range(len(nums)):temp = 1for j in nums[:i]:temp*=jfor j in nums[i+1:]:temp*=joutput[i] = temp# print('==output:', output)return outputnums = [1, 2, 3, 4] sol = Solution() sol.productExceptSelf(nums)思路２：利用空間換時間
1.借用左右數組來存儲值，L[i]代表i左邊的乘積值,R[i]代表i右邊的乘積值
2.最終i處的值為L[i]*R[i]
class Solution:def productExceptSelf(self, nums):length = len(nums)L,R,output = [0]*length,[0]*length,[0]*lengthL[0] = 1for i in range(1, length):L[i] = L[i-1]*nums[i-1]print('==L:', L)R[length-1] = 1for i in range(length-2, -1, -1):print('==i:', i)R[i] = R[i + 1] * nums[i + 1]print('==R:', R)for i in range(length):output[i] = L[i]*R[i]return outputnums = [1, 2, 3, 4] sol = Solution() sol.productExceptSelf(nums)64.滑動窗口最大值
思路1.超時O(n*k)
class Solution:def maxSlidingWindow(self, nums, k):#時間復雜度O(Nk)超時了res = []for i in range(len(nums)-k+1):res.append(max(nums[i:i+k]))return res思路2:
動態規劃：時間復雜度O(N)
1.將數組分成k+1個，剩下的一個可能不足;?
2.left數組存儲每個拆分的從左到右的值,對于left來說每個塊最右邊元素最大;
3.right數組存儲每個拆分的從右到左的值,對于right來說每個塊最左邊元素最大;
4.最后在利用left和right求最大值,max(left[i],right(j)) i每個塊最右邊元素索引,j每個塊最左邊元素索引
思路3:雙端隊列:用一個隊列一直存儲更新最大值
# 雙端隊列:用一個隊列一直存儲更新最大值 class Solution:def maxSlidingWindow(self, nums, k):length = len(nums)if length == 0:return []res = []quene = []for j in range(length):i = j-k+1if i > 0 and quene[0] == nums[i-1]:#當要左移掉的元素等于quene頭部元素,那么quene就移除頭部元素quene.pop(0)while quene and quene[-1] < nums[j]:#保持quene里面都是單調遞減的,且頭部元素最大quene.pop()quene.append(nums[j])print('==quene:', quene)if i >= 0:res.append(quene[0])return resnums = [1, 3, -1, -3, 5, 3, 6, 7] k = 3 sol = Solution() res = sol.maxSlidingWindow(nums, k) print(res)c++代碼:
class Solution { public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> res;deque<int> queue_A;for(int i=0;i<nums.size();i++){int j=i-k+1;if(j>0 && nums[j-1]==queue_A.front()){queue_A.pop_front();}while (queue_A.size() && queue_A.back()<nums[i]){queue_A.pop_back();}queue_A.push_back(nums[i]);if(j>=0){res.push_back(queue_A.front());} }return res;} };65.搜索二維矩陣 II
class Solution:def find(self,number,matrix):rows=len(matrix)#行數cols=len(matrix[0])#列數if rows<0 and cols<0:return Falsecol=0row=rows-1while row>=0 and col<cols:if matrix[row][col]<number:col+=1elif matrix[row][col]>number:row-=1else:return True#找到return False#沒找到 if __name__ == '__main__':matrix = [[1, 3, 5, 6],[2, 5, 8, 12],[4, 9, 10, 17],[6, 11, 11, 18]]sol=Solution()print(sol.find(17,matrix))66.?完全平方數
?
思路:可看成M(n) = M(n-1k)+1,這里就可以用回溯當成求子集問題,但是容易超出時間限制．
1.回溯
#公式為 M(n) = M(n - k) + 1 import math class Solution(object):def numSquares(self, n):square_nums = [i**2 for i in range(1, int(math.sqrt(n))+1)]print('==square_nums:', square_nums)res = []track = []def minNumSquares(k,track):""" recursive solution """# bottom cases: find a square numberif k in square_nums:track.append(k)res.append(track)#滿足選擇條件return 1min_num = float('inf')# Find the minimal value among all possible solutionsfor square in square_nums:if k < square:break# 滿足選擇列表store = track.copy()track.append(square)#做選擇new_num = minNumSquares(k-square, track) + 1#回溯track = store#撤消選擇min_num = min(min_num, new_num)return min_numreturn minNumSquares(n, track), res n = 3 sol = Solution() numbers, res = sol.numSquares(n) print('個數:', numbers, res)2.對于遞歸這種,其實都是可以用dp來減少計算量
#公式為 M(n) = M(n - k) + 1 class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""square_nums = [i ** 2 for i in range(0, int(math.sqrt(n)) + 1)]print('square_nums==:', square_nums)dp = [float('inf')] * (n + 1)# bottom casedp[0] = 0for i in range(1, n + 1):for square in square_nums:if i < square:#小于平方的數 就breakbreakprint('==square:', square)dp[i] = min(dp[i], dp[i - square] + 1)print('==dp:', dp)return dp[-1] n = 4 sol = Solution() numbers = sol.numSquares(n) print('個數:', numbers)c++實現:
class Solution { public:int numSquares(int n) {vector<int> dp(n+1, INT_MAX);vector<int> nums;for(int i=1; i < int(sqrt(n)) + 1; i++){nums.push_back(pow(i, 2));}dp[0] = 0;for(int i = 1; i < n+1; i++){for(int j=0; j < nums.size(); j++){if(i < nums[j]){break;}dp[i] = min(dp[i], dp[i - nums[j]] + 1);}}return dp[n];} };67.移動零
思路1:移０法
class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""n = len(nums)i=0while 0 in nums:nums.remove(0)i+=1nums.extend([0]*i)return nums思路２:指針記錄非0索引
class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""idx = 0 n = len(nums)for i in range(len(nums)):if nums[i]!=0:nums[idx] = nums[i]idx+=1nums[idx:] = (n - idx )*[0]return nums思路3:指針 交換數字
class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""idx = 0n = len(nums)for i in range(len(nums)):if nums[i]!=0:nums[idx], nums[i] = nums[i], nums[idx]idx+=1# print(idx)# print(nums)# nums[idx:] = (n - idx )*[0]return nums思路4:優化特殊非０元素
class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""idx = 0n = len(nums)for i in range(len(nums)):if nums[i]!=0:if i!=idx:nums[idx], nums[i] = nums[i], nums[idx]idx+=1else:idx +=1# print(idx)# print(nums)# nums[idx:] = (n - idx )*[0]return nums68.尋找重復數
思路:對于上述題目示例１，將數組值作為索引，會發現陷入無窮循環，而無窮循環的起始點就是重復出現的數，故構成一個環，所以就想到用快慢指針進行解決，如下圖所示,A是起點，Ｂ是環開始點，Ｃ是相遇點，快指針是慢指針速度的兩倍。
在Ｃ點相遇以后，在從起始點和Ｃ點用相同速度奔跑，就在Ｂ點相遇了，即可以得到重復的數字。
class Solution:def findDuplicate(self, nums: List[int]) -> int:fast = 0slow = 0while True:# print('==fast:', fast)# print('==slow:', slow)fast = nums[nums[fast]]slow = nums[slow]if fast == slow:breakstart = 0while True:start = nums[start]fast = nums[fast]if start ==fast:break# print(start)return start69.最長遞增子序列的個數
思路:利用dp,一個數組存儲向上遞增的長度,一個數組存儲相同長度序列的個數
class Solution:def findNumberOfLIS(self, nums):if nums ==[]:return(0)n = len(nums)opt_length = [1]*nopt_counter = [1]*nfor i in range(1, n):for j in range(i):if nums[j] < nums[i]:if opt_length[j]+1 > opt_length[i]:# 代表第一次遇到最長子序列opt_length[i] = 1+opt_length[j]opt_counter[i] = opt_counter[j]elif opt_length[j]+1 == opt_length[i]:# 代表已經遇到過最長子序列opt_counter[i] = opt_counter[i]+opt_counter[j]# print('====opt_length:', opt_length)# print('====opt_counter:', opt_counter)tmp = max(opt_length)res = sum([opt_counter[i] for i in range(n) if opt_length[i] == tmp])return (res)sol = Solution() nums = [1, 3, 5, 4, 7] res = sol.findNumberOfLIS(nums) print('===res:', res)70. 刪除無效的括號
思路:回溯
class Solution:def removeInvalidParentheses(self, s: str) -> List[str]:if not s:return [""]if s[0] not in "()":return [s[0]+i for i in self.removeInvalidParentheses(s[1:])]if len(s) < 2:return [""]if s[0] == ")":return self.removeInvalidParentheses(s[1:])res = set(self.removeInvalidParentheses(s[1:]))for i in range(1, len(s)):if s[i] == ")":a, b = set(self.removeInvalidParentheses(s[1:i])), set(self.removeInvalidParentheses(s[i+1:]))res |= {f"({i}){j}" for i in a for j in b}p = len(max(res, key=len))return [i for i in res if len(i) == p]71-1.零錢兌換
?思路：找準狀態狀轉移方程,f代表選擇銀幣的函數，則f(11)=f(11-1)+1或f(11)=f(11-2)+1或f(11)=f(11-5)+1,則一般方程為:
f(money) = min(f(money), f(money-coin)+1)
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:#狀態轉移方程f(money) = min(f(money),f(money-coin)+1)f = [float('inf')] * (amount + 1)f[0] = 0# print('==f:', f)for i in range(1, amount + 1):for coin in coins:if i - coin >= 0:f[i] = min(f[i], f[i - coin] + 1)# print('==f:', f)return f[-1] if f[-1]!=float('inf') else -171-2:零錢兌換 II
思路1:回溯 會超時
# 組合問題 回溯 超時 class Solution:def backtrace(self, amount, start, coins, track):if amount == 0: # 終止條件# self.res.append(track)self.res+=1returnfor i in range(start, len(coins)): # 選擇條件if coins[i] > amount:continue# store = track.copy()# track.append(coins[i])self.backtrace(amount - coins[i], i, coins, track)# track = storedef change(self, amount, coins):self.res = 0#[]coins = sorted(coins)self.backtrace(amount, 0, coins, [])return self.res# amount = 5 # coins = [2] amount = 5 coins = [1, 2, 5] # amount = 500 # coins = [3,5,7,8,9,10,11] sol = Solution() res = sol.change(amount, coins) print('==res:', res)思路２:當成完全背包問題，用dp
#dp[i][j] 硬幣為i 金額為j的組合數 import numpy as np class Solution:def change(self, amount, coins):if len(coins) == 0:if amount == 0:return 1else:return 0dp = [[0 for i in range(amount+1)] for j in range(len(coins))]print('==np.array(dp):', np.array(dp))dp[0][0] = 1for j in range(coins[0], amount+1, coins[0]):dp[0][j] = 1print('==np.array(dp):', np.array(dp))for i in range(1, len(coins)):print('==coins[i]:', coins[i])for j in range(amount+1):dp[i][j] = dp[i - 1][j]#不選if j >= coins[i]:#選 注意與0 1背包有一點不同dp[i][j] += dp[i][j - coins[i]]print('==np.array(dp):', np.array(dp))return dp[-1][-1]amount = 5 coins = [1, 2, 5] sol = Solution() sol.change(amount, coins)72.比特位計數
思路：
#思路:計算n的時候n-1計算過了 #n&n-1 就是抹掉二進制n最右邊的1 class Solution:def countBits(self, num):#動態規劃res = [0]*(num+1)for i in range(1, num+1):res[i] = res[i & i-1] + 1return resnum = 5 sol = Solution() res = sol.countBits(num) print('==res:', res)73.前 K 個高頻元素
思路:hash字典
class Solution:def topKFrequent(self, nums, k):dict_ = {}for num in nums:dict_[num] = dict_.get(num, 0)+1print('==dict_:', dict_)sort_dict = sorted(dict_.items(), key=lambda x:(x[-1], x[0]), reverse=True)return [sort_dict[j][0] for j in range(k)]# nums = [1,1,1,2,2,3] # k = 2 nums = [-1, -1] k = 1 # nums = [1, 2] # k = 2sol = Solution() res = sol.topKFrequent(nums, k) print('==res:', res)?74.字符串解碼
思路:棧
class Solution:def decodeString(self, s):stack = [] # (str, int) 記錄之前的字符串和括號外的上一個數字num = 0res = "" # 實時記錄當前可以提取出來的字符串for c in s:if c.isdigit():num = num * 10 + int(c)elif c == "[":stack.append((res, num))res, num = "", 0elif c == "]":top = stack.pop()print('===top:', top)res = top[0] + res * top[1]print('==res:', res)else:res += creturn res# s = "3[a]2[bc]" s = "3[a2[c]]" sol = Solution() res = sol.decodeString(s) print('res:', res)75.除法求值
思路:并查集
# 并查集 class Solution:def __init__(self):self.f = {} # 每個節點的依次關系self.d = {} # 每個節點的值 將根節點值置為1def find(self, x): # 查找與你連通的最上面一位self.f.setdefault(x, x)self.d.setdefault(x, 1)if self.f[x] == x:return xelse:t = self.f[x]self.f[x] = self.find(t)self.d[x] *= self.d[t]return self.f[x]def union(self, A, B, value): # 合并集a, b = self.find(A), self.find(B)if a != b:self.f[a] = bself.d[a] = self.d[B] / self.d[A] * value# print('===f===:', f)# print('===d===:', d)def check(self, x, y):if x not in self.f or y not in self.f:return -1.0a, b = self.find(x), self.find(y)# print('==a, b:', a, b)if a != b: # 如果不在同一條線上就返回-1return -1.0return self.d[x] / self.d[y]def calcEquation(self, equations, values, queries):for i, nums in enumerate(equations):self.union(nums[0], nums[1], values[i])print('===f:', self.f)print('===d:', self.d)res = []for x, y in queries:res.append(self.check(x, y))return resequations = [["a", "b"], ["b", "c"]] values = [2.0, 3.0] queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]# equations = [["a","b"]] # values = [2.0] # queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] sol = Solution() res = sol.calcEquation(equations, values, queries) print('==res:', res)76.根據身高重建隊列
思路：按身高由高到低進行排序,身高相等時按索引從小排序
#新建一個隊列按照索引進行插入
#思路:按身高由高到低進行排序,身高相等時按索引從小排序 #新建一個隊列按照索引進行插入 class Solution:def reconstructQueue(self, people):people = sorted(people, key=lambda x: (-x[0], x[1]))print('===people:', people)output = []for p in people:print('===p:', p)output.insert(p[1], p)print('==output:', output)return output people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] sol = Solution() sol.reconstructQueue(people)77-1.目標和
思路2：動態規劃 dp[i][j]表示到i為止，數字和為j的方案數，下面以兩個例子為例
# dp[i][j] = dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]] class Solution:def findTargetSumWays(self, nums, S):sum_ = sum(nums)if abs(S) > sum_:return 0opt = [[0 for i in range(2 * sum_ + 1)] for i in range(len(nums))]print(np.array(opt))##nums = [0,0,0,0,0,0,0,0,1]# S = 1if nums[0] == 0: # 邊界條件opt[0][sum_] = 2else:opt[0][sum_ - nums[0]] = 1opt[0][sum_ + nums[0]] = 1print(np.array(opt))for i in range(1, len(nums)):for j in range(2 * sum_ + 1):l = j - nums[i] if j - nums[i] > 0 else 0r = j + nums[i] if j + nums[i] < 2 * sum_ + 1 else 0opt[i][j] = opt[i - 1][l] + opt[i - 1][r]# print('===print(np.array(opt)):', np.array(opt))return opt[-1][sum_ + S]# nums = [1, 1, 1, 1, 1] # S = 3 # nums = [1000] # S = 1000 nums = [0, 0, 0, 0, 0, 0, 0, 0, 1] S = 1 sol = Solution() res = sol.findTargetSumWays(nums, S) print('==res:', res)77-2.分割等和子集
思路１:
（１）轉換成0 1背包問題，找到數組和的一半的子集
（２）dp[i][j]表示到i為止和為j是否存在
（３）dp[i][j] = dp[i-1][j] 不選擇nums[i]
（４）dp[i][j] = dp[i-1][j-nums] 選擇nums[i]
（５）如果 j<nums[i] dp[i][j] = dp[i-1][j]
以[1,2,3,6]為例
#轉換成0 1背包問題 找到數組和的一半的子集 #到i為止和為j是否存在 #dp[i][j] = dp[i-1][j]#不選擇nums[i] #dp[i][j] = dp[i-1][j-nums]#選擇nums[i] #如果 j<nums[i] dp[i][j] = dp[i-1][j] class Solution:def canPartition(self, nums):# nums = sorted(nums)# print('==nums:', nums)n = len(nums)if n<2:#數組長度無法劃分return Falsesum_ = sum(nums)max_value = max(nums)if sum_ % 2==1:#奇數的話沒法拆分return Falsetarget = sum_//2if max_value>target:#最大值大于一半了 不滿足條件return Falsedp = [[False for i in range(target+1)] for i in range(n)]print('===np.array(dp):', np.array(dp))for i in range(n):#不選取任何正整數，則被選取的正整數等于 00dp[i][0] = Truedp[0][nums[0]] = True#i==0 只有一個正整數 nums[0] 可以被選取for i in range(1,n):for j in range(1, target+1):if j<nums[i]:#j<nums[i]dp[i][j] = dp[i-1][j]else:#不選擇nums[i]與選擇nums[i]dp[i][j] = dp[i - 1][j] or dp[i - 1][j-nums[i]]print('===np.array(dp):', np.array(dp))return dp[-1][target] # nums = [1, 5, 11, 5] nums = [1, 2, 3, 6] sol = Solution() res = sol.canPartition(nums) print('==res:', res)思路２：優化版 用一維數組替代，只不過采用逆序
其中dp[j] = dp[j] || dp[j - nums[i]] 可以理解為 dp[j] （新）= dp[j] （舊） || dp[j - nums[i]] （舊），如果采用正序的話 dp[j - nums[i]]會被之前的操作更新為新值
import numpy as np #轉換成0 1背包問題 找到數組和的一半的子集 #優化版 #dp[j] = [j]#不選擇nums[i] #dp[j] = dp[j-nums]#選擇nums[i] # #如果 j<nums[i] dp[i][j] = dp[i-1][j] class Solution:def canPartition(self, nums):# nums = sorted(nums)# print('==nums:', nums)n = len(nums)if n<2:#數組長度無法劃分return Falsesum_ = sum(nums)max_value = max(nums)if sum_ % 2==1:#奇數的話沒法拆分return Falsetarget = sum_//2if max_value>target:#最大值大于一半了 不滿足條件return Falsedp = [False for i in range(target+1)]print('===np.array(dp):', np.array(dp))#不選取任何正整數dp[0] = Truedp[nums[0]] = True#i==0 只有一個正整數 nums[0] 可以被選取for i in range(1, n):for j in range(target, 0, -1):if j<nums[i]:#j<nums[i]dp[j] = dp[j]else:#不選擇nums[i]與選擇nums[i]dp[j] = dp[j] or dp[j-nums[i]]print('===np.array(dp):', np.array(dp))return dp[-1] # nums = [1, 5, 11, 5] nums = [1, 2, 3, 6] sol = Solution() res = sol.canPartition(nums) print('==res:', res)78-1.路徑總和
1.遞歸法?
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution(object):def hasPathSum(self, root, sum):""":type root: TreeNode:type sum: int:rtype: bool"""if not root:return Falseif not root.left and not root.right and root.val==sum:return Truesum -=root.valreturn self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)c++實現:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { public:bool hasPathSum(TreeNode* root, int targetSum) {if(root == nullptr){return false;}if (root->left == nullptr && root->right == nullptr && targetSum==root->val){return true;}targetSum -=root->val;return hasPathSum(root->left,targetSum) || hasPathSum(root->right,targetSum);} };2.利用棧--DFS
class Solution(object):def hasPathSum(self, root, sum):""":type root: TreeNode:type sum: int:rtype: bool"""# # #遞歸終止條件 # if root is None:# return False# if root.left is None and root.right is None and root.val == sum:# return True# sum = sum - root.val# # print('===sum:', sum)# return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum) if not root:return Falsequene = [(root, root.val)]while quene:node,value = quene.pop()if node.left is None and node.right is None and value==sum:return Trueif node.left is not None:quene.append((node.left,value+node.left.val))if node.right is not None:quene.append((node.right,value+node.right.val)) # print('==quene:',quene)return False3.利用隊列--BFS
class Solution(object):def hasPathSum(self, root, sum):""":type root: TreeNode:type sum: int:rtype: bool"""# # #遞歸終止條件 # if root is None:# return False# if root.left is None and root.right is None and root.val == sum:# return True# sum = sum - root.val# # print('===sum:', sum)# return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum) if not root:return Falsequene = [(root, root.val)]while quene:node,value = quene.pop(0)if node.left is None and node.right is None and value==sum:return Trueif node.left is not None:quene.append((node.left,value+node.left.val))if node.right is not None:quene.append((node.right,value+node.right.val)) # print('==quene:',quene)return False78-2:路徑總和 II
思路：回溯 這種里面要調用兩層回溯的 track就不要放在遞歸函數里面了
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def dfs(self, node, sum_):if node is None:return 0store = self.track.copy()self.track.append(node.val)# print('==self.track:', self.track)if node.left is None and node.right is None and sum_==node.val: self.res.append(self.track)sum_ -= node.valself.dfs(node.left, sum_)self.dfs(node.right, sum_)# self.track.pop()self.track = storedef pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:self.res = []self.track = []self.dfs(root, sum)return self.resc++實現:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { public:vector<vector<int>> res;vector<int> track;void dfs(TreeNode* root, int targetSum){if(root==nullptr){return ;}vector<int> store;store = track;track.push_back(root->val); if(root->left==nullptr && root->right==nullptr && targetSum==root->val){res.push_back(track);}targetSum -= root->val;dfs(root->left, targetSum);dfs(root->right, targetSum);track = store;}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {dfs(root, targetSum);return res;} };78-3:路徑總和 III
思路：用一個列表存儲從節點開始的數字和
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right #用列表記錄從每一個節點開始的和 class Solution:def dfs(self, node, sum_list, sum):if node is None:return 0 sum_list = [num+node.val for num in sum_list]sum_list.append(node.val)for num in sum_list:if num==sum:self.res+=1self.dfs(node.left, sum_list, sum)self.dfs(node.right, sum_list, sum)def pathSum(self, root: TreeNode, sum: int) -> int:self.res = 0self.dfs(root, [], sum)return self.resc++實現:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { public:int res;void dfs(TreeNode* node, vector<int> num_list, int sum){if(node == nullptr){return ;}for (int i=0; i<num_list.size(); i++){num_list[i] += node->val;} num_list.push_back(node->val);for(int i=0; i<num_list.size(); i++){if(num_list[i]==sum){res++;}}dfs(node->left, num_list, sum);dfs(node->right, num_list, sum);}int pathSum(TreeNode* root, int sum) {vector<int> num_list;dfs(root, num_list, sum);return res;} };79.找到所有數組中消失的數字
思路1:hash
#利用hash存儲出現過得數字 class Solution:def findDisappearedNumbers(self, nums):dict_ = {}for num in nums:dict_[num] = dict_.get(num, 0)+1print('==dict_:', dict_)res =[]for i in range(1, len(nums)+1):if i not in dict_:res.append(i)return res nums = [4,3,2,7,8,2,3,1] sol = Solution() res = sol.findDisappearedNumbers(nums) print('==res:', res)思路2:原地修改
#利用list原地進行修改 class Solution:def findDisappearedNumbers(self, nums):for i in range(len(nums)):index = abs(nums[i]) - 1if nums[index] > 0:nums[index] *= -1print('==nums:', nums)res =[]for i in range(len(nums)):if nums[i]>0:res.append(i+1)return res nums = [4,3,2,7,8,2,3,1] # nums = [1, 3, 3, 4, 5] sol = Solution() res = sol.findDisappearedNumbers(nums) print('==res:', res)80.漢明距離
思路:通過異或取得不同數的 在向右移動 依次與1進行& 獲得1的個數
#思路:通過異或取得不同數的 在向右移動 依次與1進行& 獲得1的個數 class Solution:def hammingDistance(self, x, y):res = x ^ y#異或取得不同的數 異或 相同為0 不同為1# print('==res:', res)dis = 0while res:#向右移位# print('==res&1:', res&1)if res&1:dis+=1res = res>>1# print('==res:', res)return dis x = 1 y = 4 sol = Solution() sol.hammingDistance(x, y)81.把二叉搜索樹轉換為累加樹?
思路：其實就是逆中序遍歷，利用二叉搜索樹的特點，跟節點值更新為右孩子和根節點值之和，左孩子值更新為根節點與左孩子值之和。
1.迭代法：
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def convertBST(self, root: TreeNode) -> TreeNode:stack = []node = rootvalue = 0while stack or node:while node:#把跟節點與右子樹節點依次壓進棧 實現逆中序遍歷stack.append(node)node = node.rightprint('==stack:', stack)node = stack.pop()print('==node:',node)value += node.valnode.val = valueprint('==node.left:', node.left)node = node.leftreturn root2.遞歸法：
其中res存儲逆中序遍歷(右根左)的值，便于查看
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def helper(self, node):if node:self.helper(node.right)# self.res.append(node.val)self.value+=node.valnode.val = self.valueself.helper(node.left)def convertBST(self, root: TreeNode) -> TreeNode:# self.res =[]self.value = 0self.helper(root)return rootc++實現:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { public:int res = 0;void help(TreeNode* node){if(node == nullptr){return ;}help(node->right);res += node->val;node->val = res;help(node->left);}TreeNode* convertBST(TreeNode* root) {help(root);return root;} };82.二叉樹的直徑
思路:遞歸函數用來獲取每一層深度，然后在分別對左右子樹深度求和，這里要注意的是最長直徑不一定過根節點，所有要用一個變量存儲遍歷每個節點時的最大直徑．
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def get_depth(self, node):if node is None:return 0l = self.get_depth(node.left)r = self.get_depth(node.right)self.max_value = max(self.max_value, l+r)return max(l,r)+1def diameterOfBinaryTree(self, root: TreeNode) -> int:self.max_value = 0if root is None:return 0self.get_depth(root)return self.max_valuec++實現:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:int max_value=0;int help(TreeNode* node){if(!node){return 0;}int l = help(node->left);int r = help(node->right);max_value = max(max_value, l+r);return max(l,r)+1;}int diameterOfBinaryTree(TreeNode* root) {help(root);return max_value;} };?83.和為K的子數組
思路１：枚舉（超時） Ｏ(n2)
class Solution:def subarraySum(self, nums, k):res=0for i in range(len(nums)):tmp = 0for j in range(i,len(nums)):tmp+=nums[j]if tmp==k:res+=1print('=res:',res)return res# nums = [1,1,1] # k = 2 nums = [1,-1,0] k = 0 sol = Solution() sol.subarraySum(nums, k)思路２：hash,利用字典的key值存儲累加和，value值存儲出現次數
#利用字典 key存儲累加的數字 value為出現的次數 class Solution:def subarraySum(self, nums, k):count_dict = {}count, sum_ = 0, 0for num in nums:sum_+=numif sum_==k:count+=1if sum_-k in count_dict:count+=count_dict[sum_-k]if sum_ in count_dict:count_dict[sum_]+=1else:count_dict[sum_]=1print('==count_dict:', count_dict)print('count:', count)return countnums = [1, 1, 1] k = 2 # nums = [1, -1, 1] # k = 0 sol = Solution() sol.subarraySum(nums, k)84.最短無序連續子數組
思路1：單調遞增棧
class Solution:def findUnsortedSubarray(self, nums):#找到遞增的拐點stack = []left = len(nums)-1for i in range(len(nums)):while stack and nums[i] < nums[stack[-1]]:index = stack.pop()left = min(left, index)stack.append(i)print('==stack:', stack)print('left:', left)#找到逆序遞增的拐點stack = []right = 0for i in range(len(nums)-1, -1, -1):while stack and nums[i] > nums[stack[-1]]:index = stack.pop()right = max(right, index)stack.append(i)print('==right:', right)return right-left+1 if right-left>0 else 0nums = [2, 6, 4, 8, 10, 9, 15] # nums = [2, 1, 6] # nums = [1, 2] # nums = [2, 1] # nums = [5, 4, 3, 2, 1] sol = Solution() res = sol.findUnsortedSubarray(nums) print('======res:', res)思路2:排序
class Solution:def findUnsortedSubarray(self, nums: List[int]) -> int:# print('==nums:', nums)sort_nums = sorted(nums)# print('==sort_nums:', sort_nums)left = len(nums) - 1right = 0for i in range(len(nums)):if nums[i] != sort_nums[i]:left = min(left, i)right = max(right, i)# print('==left:', left)# print('==right:', right)return right - left + 1 if right - left > 0 else 085.合并二叉樹
思路:采用前序遍歷訪問二叉樹，如果節點其一為none，就返回另一個
1.遞歸法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:if t1 is None:return t2if t2 is None:return t1t1.val+=t2.valt1.left = self.mergeTrees(t1.left,t2.left)t1.right = self.mergeTrees(t1.right,t2.right)return t12.迭代法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:if t1 is None:return t2stack= [(t1,t2)]while stack:t = stack.pop()if t[0] is None or t[1] is None:continuet[0].val +=t[1].valif t[0].left is None:t[0].left = t[1].leftelse:stack.append((t[0].left, t[1].left))if t[0].right is None:t[0].right = t[1].rightelse:stack.append((t[0].right, t[1].right))return t1c++實現:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 == nullptr){return root2;}if(root2 == nullptr){return root1;}root1->val += root2->val;root1->left = mergeTrees(root1->left, root2->left);root1->right = mergeTrees(root1->right, root2->right);return root1;} };86.任務調度器
思路： 貪心 填桶法?
class Solution(object):def leastInterval(self, tasks, n):""":type tasks: List[str]:type n: int:rtype: int"""length = len(tasks)if length <= 1:return lengthprint('===length:', length)# 用于記錄每個任務出現的次數task_dict = {}for task in tasks:#不存在task時 返回0task_dict[task] = task_dict.get(task,0)+1print('==task_dict:', task_dict)# 按任務出現的次數從大到小排序task_sort = sorted(task_dict.items(), key=lambda x: x[1], reverse=True)print('==task_sort:', task_sort)# # 出現最多次任務的次數max_task_count = task_sort[0][1]# 至少需要的最短時間res = (max_task_count - 1) * (n + 1)for sort in task_sort:if sort[1] == max_task_count:res += 1print('==res:', res)# # 如果結果比任務數量少，則返回總任務數return res if res >= length else lengthtasks = ["A","A","A","B","B","B"] n = 2 # n = 0 sol = Solution() sol.leastInterval(tasks, n)87-1.回文子串
思路１：兩層for循環遍歷進行判斷是否是回文字符串即可，超出時間限制
#雙層for循環超出時間限制 class Solution:def judge_palindrome(self, s):l = 0r = len(s) -1while l<=r:if s[l]==s[r]:l+=1r-=1else:return Falsereturn Truedef countSubstrings(self, s):res=0for i in range(len(s)):# print('==i:', i)for j in range(i, len(s)):# print('==j', j)# print('==s[i:j+1]:', s[i:j+1])if self.judge_palindrome(s[i:j+1]):res += 1return res# s = "abc" s = "aaa" sol = Solution() res = sol.countSubstrings(s) print('==res:', res)思路2,中心枚舉，專門用self.res存儲 left與righe索引方便查看，，最后求和就是會文字符串的個數。
import numpy as np class Solution:def helper(self,left,right,s):while left>=0 and right<len(s) and s[left]==s[right]:self.res[left][right]=1self.fin_res+=1left-=1right+=1def countSubstrings(self, s):self.res = [[0 for i in range(len(s)) ] for i in range(len(s))]self.fin_res = 0for i in range(len(s)):self.helper(i,i,s)self.helper(i,i+1,s)print(np.array(self.res))return self.fin_ress = "aaa" sol = Solution() sol.countSubstrings(s)87-2：回文串分割 IV
思路:中心枚舉 用一個矩陣存儲回文字符串左右索引的值，最后看看是不是分為三段即可
import numpy as np class Solution:def helper(self,left,right,s):while left>=0 and right<len(s) and s[left]==s[right]:self.res[left][right] = 1left-=1right+=1def checkPartitioning(self, s):length = len(s)self.res = [[0 for _ in range(length)]for _ in range(length)]for i in range(length):self.helper(i, i, s)self.helper(i, i+1, s)print(np.array(self.res))for i in range(length):for j in range(i+1, length):if self.res[0][i] and self.res[i+1][j] and self.res[j+1][length-1]:return Truereturn False# s = "abcbdd" s = "bcbddxy" # s = "juchzcedhfesefhdeczhcujzzvbmoeombv" sol = Solution() res = sol.checkPartitioning(s) print('==res:', res)87-3.最長回文子串
class Solution:def helper(self,left,right,s):while left>=0 and right<len(s) and s[left]==s[right]:left-=1right+=1if len(s[left+1:right])>len(self.res):self.res = s[left+1:right]def longestPalindrome(self, s: str) -> str:self.res = ''for i in range(len(s)):self.helper(i,i,s)self.helper(i,i+1,s)return self.res88-1.單調遞增的數字
class Solution(object):def monotoneIncreasingDigits(self, N):""":type N: int:rtype: int"""digits = []A = list(map(int, str(N)))# print('==A:', A)for i in range(len(A)):for d in range(1, 10):# print('==digits + [d] * (len(A) - i):', digits + [d] * (len(A) - i))if digits + [d] * (len(A) - i) > A:digits.append(d - 1)breakelse:digits.append(9)# print('==digits:', digits)return int("".join(map(str, digits)))88-2:每日溫度
思路：單調遞增棧
class Solution:def dailyTemperatures(self, T):#單調遞增棧res = [0]*len(T)stack = []for i in range(len(T)):while stack and T[i] > T[stack[-1]]:res[stack[-1]] = i - stack[-1]stack.pop()print('==stack', stack)print('==res:', res)stack.append(i)return res T = [73, 74, 75, 71, 69, 72, 76, 73] sol = Solution() sol.dailyTemperatures(T) 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的leetcode hot100(第二部分) + python(c++)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 模式识别与机器学习笔记（二）机器学习的基
- 下一篇： 怎样把MySQL的编码方式改为utf8？