python(c++)刷题+剑指offer
生活随笔
收集整理的這篇文章主要介紹了
python(c++)刷题+剑指offer
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
03. 數組中重復的數字
思路:hash
class Solution:def findRepeatNumber(self, nums: List[int]) -> int:dict_ = dict()for i in range(len(nums)):if nums[i] in dict_:return nums[i]else:dict_[nums[i]] = i class Solution { public:int findRepeatNumber(vector<int>& nums) {unordered_map<int, int> dict_;for(int i = 0; i < nums.size(); i++){dict_[nums[i]]++;if(dict_[nums[i]]>1){return nums[i];}}return 0;} };04. 二維數組中的查找
class Solution:def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:h = len(matrix)if h == 0:return Falsew = len(matrix[0])i, j = h-1, 0while i >= 0 and j <= w-1:if matrix[i][j] > target:i -= 1elif matrix[i][j] < target:j += 1else:return Truereturn Falsec++實現:
class Solution { public:bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {if(matrix.size() == 0 || matrix[0].size() == 0){return false;}int h = matrix.size();int w = matrix[0].size();int i = h-1, j = 0;while(i >= 0 && j <= w-1){if(matrix[i][j] > target){i--;}else if(matrix[i][j] < target){j++;}else{return true;}}return false;} };05. 替換空格
class Solution:def replaceSpace(self, s: str) -> str:return s.replace(' ', '%20')c++實現:
class Solution { public:string replaceSpace(string s) {string res = "";for(int i = 0; i < s.size(); i++){if(s[i]==' '){res += "%20";}else{res += s[i];}}return res;} };優化:直接原地修改思路:雙指針法，resize出新的字符長度，當i,j相等時說明找到的都是非空格的此時跳出循環．
class Solution { public:string replaceSpace(string s) {int blank = 0;int s_ori_length = s.size();for(int i = 0; i<s.size(); i++){if(s[i] == ' '){blank++;}}s.resize(s.size() + blank * 2);int s_new_length = s.size();//相等就跳出for(int i = s_new_length - 1, j = s_ori_length - 1; j < i; i--, j-- ){if(s[j] != ' '){s[i] = s[j];}else{s[i - 2] = '%';s[i - 1] = '2';s[i] = '0'; i -= 2;}}return s;} };06. 從尾到頭打印鏈表
方法1:利用棧
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def reversePrint(self, head: ListNode) -> List[int]:# if head:# return self.reversePrint(head.next)+[head.val]# else:# return []res = []while head:res.append(head.val)head = head.nextreturn res[::-1]方法2:遞歸回溯
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:void help(ListNode* node, vector<int>& res){if(node == NULL){return ;}help(node->next, res);res.push_back(node->val);}vector<int> reversePrint(ListNode* head) {vector<int> res;help(head, res);return res;} };07. 重建二叉樹
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:if len(preorder) == 0 or len(inorder) == 0:return Nonenode = TreeNode(preorder[0])middle_index = inorder.index(preorder[0])node.left = self.buildTree(preorder[1:middle_index+1], inorder[:middle_index])node.right = self.buildTree(preorder[middle_index+1:], inorder[middle_index+1:])return nodec++實現:
/*** 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:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.empty() || inorder.empty()){return NULL;}int node_value = preorder[0];int middle_index = 0;for(int i = 0; i < inorder.size(); i++){if(inorder[i] == node_value){middle_index = i;break;}} TreeNode* node = new TreeNode(node_value);vector<int> leftInorder(inorder.begin(), inorder.begin() + middle_index);vector<int> rightInorder(inorder.begin() + middle_index + 1, inorder.end());vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + middle_index + 1);vector<int> rightPreorder(preorder.begin() + middle_index + 1, preorder.end());node->left = buildTree(leftPreorder, leftInorder); node->right = buildTree(rightPreorder, rightInorder); return node;} };09. 用兩個棧實現隊列
python代碼:
class CQueue:def __init__(self):self.stack_A = []self.stack_B = []def appendTail(self, value: int) -> None:self.stack_A.append(value)def deleteHead(self) -> int:if len(self.stack_A) == 0 and len(self.stack_B) == 0:return -1if len(self.stack_B) == 0:while(len(self.stack_A)): temp = self.stack_A.pop() self.stack_B.append(temp)value = self.stack_B.pop()return value# Your CQueue object will be instantiated and called as such: # obj = CQueue() # obj.appendTail(value) # param_2 = obj.deleteHead()c++實現:
class CQueue { public:stack<int> stack_A;stack<int> stack_B;CQueue() {}void appendTail(int value) {stack_A.push(value);}int deleteHead() {if(stack_A.empty() && stack_B.empty()){return -1;}if(stack_B.empty()){while(!stack_A.empty()){stack_B.push(stack_A.top());stack_A.pop();}}int value = stack_B.top();stack_B.pop();return value;} };/*** Your CQueue object will be instantiated and called as such:* CQueue* obj = new CQueue();* obj->appendTail(value);* int param_2 = obj->deleteHead();*/10- II. 青蛙跳臺階問題
python實現:?
class Solution:def numWays(self, n: int) -> int:if n <= 1:return 1 a, b = 1, 1for i in range(2, n + 1):temp = aa = bb = (temp + b) % 1000000007return bc++實現:?
class Solution { public:int numWays(int n) {if(n <= 1){return 1;}int a = 1, b = 1;for (int i = 2; i < n+1; i++){int temp = a;a = b;b = (temp + b) % 1000000007;}return b;} };11. 旋轉數組的最小數字
python代碼:
class Solution:def minArray(self, numbers):# return min(numbers)left, right = 0, len(numbers) - 1while left < right:middle = left + (right - left) // 2if numbers[middle] < numbers[right]:#說明middle是最小值右側元素right = middleelif numbers[middle] > numbers[right]:#說明middle是最小值左側元素left = middle + 1else:right -= 1 #相當就沒法判斷 采取保守right-1即可print('==left:', left)print('===numbers[left]', numbers[left])return numbers[left] # numbers = [1, 2, 3, 4, 5] # numbers = [3, 4, 5, 1, 2] # numbers = [2, 2, 2, 0, 1] # numbers = [2, 2, 2, 0, 1] # numbers = [1, 3, 5] numbers = [1, 3, 3] # numbers = [3, 2, 1, 4, 5] sol = Solution() sol.minArray(numbers)c++代碼:
class Solution { public:int minArray(vector<int>& numbers) {int left = 0;int right = numbers.size() - 1;while(left < right){int middle = left + (right - left) / 2;if(numbers[middle] < numbers[right]){right = middle;}else if(numbers[middle] > numbers[right]){left = middle + 1;}else{right--;}}return numbers[left];} };12. 矩陣中的路徑
思路:與島嶼，水塘類似，只不過添加一個回溯的過程，直接修改board即可，回溯出來還原即可
class Solution:def help(self, i, j, h, w, index):if i<0 or j<0 or i>=h or j>=w or self.word[index] != self.board[i][j]:return Falseif index == len(self.word) - 1:return Trueself.board[i][j] = ''#說明board和word找到相同的 因為不能重復 修改一下boradfor direction in self.directions:new_i, new_j = direction[0] + i, direction[1] + jif self.help(new_i, new_j, h, w, index + 1):return Trueself.board[i][j] = self.word[index]#回溯出去需要還原return Falsedef exist(self, board: List[List[str]], word: str) -> bool:self.board = boardself.word = wordself.directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]h = len(board)w = len(board[0])for i in range(h):for j in range(w):if self.help(i, j, h, w, 0):return Truereturn Falsec++實現:
class Solution { public:int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, -1, 0, 1}; public:bool help(int i, int j, int h, int w, vector<vector<char>>& board, string word, int index){if(i < 0 || i >= h || j < 0 || j >= w || board[i][j] != word[index]){return false;}if (index == word.size() - 1){return true;}board[i][j] = '#';for(int k = 0; k < 4; k++){int new_i = dx[k] + i;int new_j = dy[k] + j;if(help(new_i, new_j, h, w, board, word, index + 1)){return true;}}board[i][j] = word[index];return false;}bool exist(vector<vector<char>>& board, string word) {int h = board.size();int w = board[0].size();for(int i = 0; i<h; i++){for (int j = 0; j < w; j++){if (help(i, j, h, w, board, word, 0)){return true;}}}return false;} };13. 機器人的運動范圍
思路1:bfs 只需要判斷右邊和下邊，因為上邊和左邊已經遍歷過了
class Solution:def digitSum(self, num):count = 0while num:count += num % 10num //= 10return countdef movingCount(self, m: int, n: int, k: int) -> int:#BFSqueue = [(0, 0)]res = set()while len(queue):x, y = queue.pop()#滿足搜索條件if (x,y) not in res and 0<=x<m and 0<=y<n and (self.digitSum(x) + self.digitSum(y)) <= k:res.add((x,y))for (x_, y_) in ((x+1, y), (x, y+1)):queue.append((x_, y_))return len(res)思路2：遞推
view[i][j] = view[i-1][j] or view[j][j-1]
class Solution:def digitSum(self, num):count = 0while num:count += num % 10num //=10return countdef movingCount(self, m: int, n: int, k: int) -> int:#遞推view = set([(0, 0)])for i in range(m):for j in range(n):if ((i - 1, j) in view or (i, j - 1) in view) and (self.digitSum(i) + self.digitSum(j)) <= k:view.add((i, j))return len(view)對于c++不存在列表in的關系，需要換種寫法?
class Solution { public:int digitSum(int num){int count = 0;while(num){count += num % 10;num /= 10;}return count;}int movingCount(int m, int n, int k) {vector<vector<int>> view(m, vector<int>(n, 0));view[0][0] = 1;int res = 0;for (int i = 0; i < m; i++){for(int j = 0; j < n; j++){if ((digitSum(i)+digitSum(j))>k){continue;}if(i-1 >= 0){view[i][j] |= view[i-1][j];} if(j-1 >= 0){view[i][j] |= view[i][j-1];}res += view[i][j];}}return res;} };14- I. 剪繩子
思路:
python:
class Solution:def cuttingRope(self, n: int) -> int:if(n == 2):return 1if(n == 3):return 2res = 1while(n > 4):res *= 3n -= 3res *= nreturn resc++:
class Solution { public:int cuttingRope(int n) {if(n == 2){return 1;}if(n == 3){return 2;}int res = 1;while(n > 4){res *= 3;n -= 3;}res *= n;return res;} };14- II. 剪繩子 II
思路:
盡可能將繩子以長度?33?等分為多段時，乘積最大,原因為https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/mian-shi-ti-14-ii-jian-sheng-zi-iitan-xin-er-fen-f/
class Solution:def cuttingRope(self, n: int) -> int:if n == 2:return 1if n == 3:return 2res = 1;while n > 4:res *= 3res %= 1000000007n -= 3res *= nres %= 1000000007return resc++代碼:
class Solution { public:int cuttingRope(int n) {if(n == 2){return 1;}if(n == 3){return 2;}long res = 1;while(n > 4){res *= 3;res %= 1000000007 ;n -= 3;}res *= n;res %= 1000000007 ;return res;} };15. 二進制中1的個數
思路:一種是通過右移,一種是通過n&n-1不斷減少1
python:
class Solution:def hammingWeight(self, n: int) -> int:res = 0while n:if n & 1:res += 1n >>= 1return resc++實現:通過右移
class Solution { public:int hammingWeight(uint32_t n) {int res = 0;while(n){if(n & 1){res++;}n >>= 1;}return res;} };ｃ++實現: 通過n&=n-1
class Solution { public:int hammingWeight(uint32_t n) {int res = 0;while(n){res++;n &= n - 1;}return res;} };16. 數值的整數次方
思路:遞歸，注意分正負和奇數偶數即可
class Solution:def help(self, x, n):if x == 0:return 0if n == 0:return 1if n == 1:return xtemp = self.help(x, n//2)if n % 2 == 1:return temp * temp * xelse:return temp * tempdef myPow(self, x: float, n: int) -> float:if n > 0:return self.help(x, n)else:return 1 / self.help(x, -n)c++實現:?
class Solution { public:double help(double x, long n){if(x == 0 || x == 1){return x;}if(n == 0){return 1;}if(n == 1){return x;}double temp = help(x, n/2);if(n % 2 == 1){return temp * temp * x;}else{return temp * temp;}}double myPow(double x, long n) {if(n > 0){return help(x, n);}else{return 1./help(x, -n);}} };17. 打印從1到最大的n位數
思路:如果沒有考慮大數的話直接for循環就行
class Solution:def printNumbers(self, n: int) -> List[int]:self.res = []for m in range(1, 10**n):self.res.append(m)return self.res考慮大數的做法，遞歸回溯,用字符串相加的方式就避免了數字超過范圍
class Solution:def backtrace(self, count, track, length):if count == length:#終止條件 位數為lengthself.res.append(int(''.join(track)))returnfor i in range(10):store = track.copy()track.append(str(i))self.backtrace(count + 1, track, length)track = storedef printNumbers(self, n: int) -> List[int]:self.res = []for m in range(1, n + 1):for start_num in range(1, 10):track = [str(start_num)]self.backtrace(1, track, m)return self.resc++實現:
class Solution { public:vector<int> res;void backtrace(int count, vector<char> track, int length){if(count == length){//長度相同 出去string temp_str = "";for (int i = 0; i < track.size(); i++){temp_str += track[i];}int int_str = atoi(temp_str.c_str());res.push_back(int_str);return ;}for(int i=0; i<10; i++){vector<char> store(track);track.push_back(i + '0');backtrace(count + 1, track, length);track = store;}}vector<int> printNumbers(int n) { for(int m = 1; m < n+1; m++){for (int start_num = 1; start_num<10; start_num++){vector<char> track(1, start_num + '0');backtrace(1, track, m);}}return res;} };18. 刪除鏈表的節點
思路:雙指針
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution:def deleteNode(self, head: ListNode, val: int) -> ListNode:if head is None:return headnew_head = ListNode(0)new_head.next = headpre = new_headcur = headwhile cur.val != val:pre = curcur = cur.nextpre.next = cur.nextreturn new_head.nextc++實現:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* deleteNode(ListNode* head, int val) {if(head == NULL){return NULL;}ListNode* new_head = new ListNode(0);new_head->next = head;ListNode* pre = new_head;ListNode* cur = head;while(cur->val != val){pre = cur;cur = cur->next;}pre->next = cur->next;return new_head->next;} };c++遞歸:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* deleteNode(ListNode* head, int val) {if(head == NULL){return NULL;}if(head->val == val){return head->next;}head->next = deleteNode(head->next, val);return head;} };19. 正則表達式匹配
思路:
class Solution:def matches(self, i, j, s, p):if i == 0:return Falseif p[j - 1] == '.':return Truereturn s[i - 1] == p[j - 1]def isMatch(self, s: str, p: str) -> bool:m, n = len(s), len(p)dp = [[False] * (n + 1) for _ in range(m + 1)]dp[0][0] = Truefor i in range(m + 1):for j in range(1, n + 1):if p[j - 1] == '*':dp[i][j] |= dp[i][j - 2]if self.matches(i, j - 1, s, p):dp[i][j] |= dp[i - 1][j]else:if self.matches(i, j, s, p):dp[i][j] |= dp[i - 1][j - 1]return dp[-1][-1]c++:
class Solution { public:bool help(int i, int j, string s, string p){if(i == 0){return false;}if(p[j-1] == '.'){return true;}return s[i-1] == p[j-1];}bool isMatch(string s, string p) {int m = s.size();int n = p.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));dp[0][0] = 1;for(int i = 0; i < m + 1; i++){for (int j = 1; j < n + 1; j++){if(p[j-1] == '*'){dp[i][j] |= dp[i][j-2];if(help(i, j-1, s, p)){dp[i][j] |= dp[i-1][j];}}else{if (help(i, j, s, p)){dp[i][j] |= dp[i-1][j-1];}}}}return dp[m][n];} };20. 表示數值的字符串
python:
class Solution:def isNumber(self, s: str) -> bool:try:float(s)except Exception as e:print('==error:',e)return Falsereturn Truec++實現:
class Solution { public:bool isNumber(string s) {if(s.empty()) return false;while(s.length() > 0 && s[0] == ' ') s.erase(0, 1);while(s.length() > 0 && s[s.length() - 1] == ' ') s.erase(s.length() - 1, 1);if(s.length() == 0) return false;bool isDot = false, isE = false, isNumber = false;for(int i=0; i<s.length(); ++i){if(s[i] >= '0' && s[i] <= '9') isNumber = true;else if(s[i] == 'e' || s[i] == 'E'){if(isE || !isNumber || i == s.length() - 1) return false;s[i] = 'e'; // 將'E'變成'e'isE = true;}else if(s[i] == '+' || s[i] == '-'){if((i > 0 && s[i - 1] != 'e') || (i == s.length() - 1)) return false;}else if(s[i] == '.'){if(isDot || isE || (i == s.length() - 1 && !isNumber)) return false;isDot = true;}else return false;}return true;} };21. 調整數組順序使奇數位于偶數前面
思路：雙指針 奇數放左邊 偶數放右邊
class Solution:def exchange(self, nums: List[int]) -> List[int]:left = 0right = len(nums) - 1while left<right:if nums[left]%2:#奇數左指針就一直右移left += 1continueif nums[right]%2 == 0:#偶數右指針就一直左移right -= 1continuenums[left], nums[right] = nums[right],nums[left]return numsｃ++實現:
class Solution { public:void swap(int &a, int &b){int temp = a;a = b;b = temp;}vector<int> exchange(vector<int>& nums) {int left = 0, right = nums.size() - 1;while(left < right){if(nums[left] % 2){left++;continue;}if(nums[right] % 2 == 0){right--;continue;}swap(nums[left], nums[right]); }return nums;} };22. 鏈表中倒數第k個節點
思路:雙指針
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:node_A = headnode_B = headwhile k:node_A = node_A.nextk -= 1while node_A:node_A = node_A.nextnode_B = node_B.nextreturn node_Bc++實現:?
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* getKthFromEnd(ListNode* head, int k) {ListNode* node_A = head;ListNode* node_B = head;while(k>0){node_A = node_A->next;k--;}while(node_A != NULL){node_A = node_A->next;node_B = node_B->next;}return node_B;} };24. 反轉鏈表
python代碼:
# 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 = Nonecur = headwhile cur:temp = cur.nextcur.next = prepre = curcur = tempreturn prec++實現:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* reverseList(ListNode* head) {ListNode* pre = NULL;ListNode* cur = head;while(cur){ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;} };25. 合并兩個排序的鏈表
python:
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:fake_head_node = ListNode(0)cur = fake_head_nodewhile l1 and l2:if l1.val<l2.val:cur.next = l1l1 = l1.nextelse:cur.next = l2l2 = l2.next cur = cur.nextif l1:cur.next = l1else:cur.next = l2return fake_head_node.nextc++:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* new_head = new ListNode(0);ListNode* node = new_head;while(l1!=NULL && l2 !=NULL){if(l1->val<l2->val){node->next = l1;l1 = l1->next;}else{node->next = l2;l2 = l2->next; }node = node->next;}if (l1!=NULL){node->next = l1;}if(l2!=NULL){node->next = l2;}return new_head->next;} };26. 樹的子結構
思路:
B為空?說明B已經遍歷完成
A為空或者A,?B兩個節點的值不相等則返回false
對A和B節點進行遞歸調用??對A的左右子節點分別進行遞歸調用??可能A的子結構等于B的在深處
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def help(self, A, B):if B is None:#B為空 說明B已經遍歷完成return Trueif (A is None) or (A.val != B.val):#A為空或者A, B兩個節點的值不相等則返回falsereturn Falsereturn self.help(A.left, B.left) and self.help(A.right, B.right)def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:if A is None or B is None:return False#對A和B節點進行遞歸調用 對A的左右子節點分別進行遞歸調用 可能A的子結構在深處return self.help(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)c++實現:
/*** 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:bool help(TreeNode* A, TreeNode* B){if(B == NULL){return true;}if((A == NULL) || (A->val != B->val)){return false;}return help(A->left, B->left) && help(A->right, B->right);}bool isSubStructure(TreeNode* A, TreeNode* B) {if(A == NULL || B == NULL){return false;}return help(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);} };27. 二叉樹的鏡像
思路;其實就是翻轉二叉樹，分別對左右子樹進行交換，遞歸即可，出口是節點為none
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def mirrorTree(self, root: TreeNode) -> TreeNode: if root is None:return Noneleft = self.mirrorTree(root.left)right = self.mirrorTree(root.right)root.right = leftroot.left = rightreturn rootc++實現:
/*** 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:TreeNode* mirrorTree(TreeNode* root) {if(root == NULL){return root;}TreeNode* left = mirrorTree(root->left);TreeNode* right = mirrorTree(root->right);root->left = right;root->right = left;return root;} };28. 對稱的二叉樹
思路:遞歸判斷左右子樹是否相等，找準遞歸出口就行
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def help(self, node1, node2):if node1 == None and node2 == None:return Trueif node1 == None or node2 == None:return Falseif node1.val != node2.val:return Falsereturn self.help(node1.left, node2.right) and self.help(node1.right, node2.left)def isSymmetric(self, root: TreeNode) -> bool:return self.help(root, root)c++實現:
/*** 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:bool help(TreeNode* node1, TreeNode* node2){if(node1 == NULL && node2 == NULL){return true;}if(node1 == NULL || node2 == NULL){return false;}if(node1->val != node2->val){return false;}return help(node1->left, node2->right) && help(node1->right, node2->left);}bool isSymmetric(TreeNode* root) {return help(root, root);} };29. 順時針打印矩陣
思路:從外層到內層循環，終止條件就是左上角索引和右上角索引重合時
class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:h = len(matrix)if h == 0:return []w = len(matrix[0])left = 0right = w - 1top = 0bottom = h - 1res = []while left<=right and top<=bottom:for i in range(left, right + 1):res.append(matrix[top][i])for i in range(top + 1, bottom + 1):res.append(matrix[i][right])if left < right and top < bottom:for i in range(right-1, left-1, -1):res.append(matrix[bottom][i])for i in range(bottom-1, top, -1):res.append(matrix[i][left])left+=1right-=1top+=1bottom-=1# print('==res:',res)return resc++實現:
class Solution { public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> res;int h = matrix.size();if(h<1){return res;}int w = matrix[0].size();int left = 0, top = 0, right = w - 1, bottom = h - 1;while (left <= right && top <= bottom){for (int i = left; i < right+1; i++){res.push_back(matrix[top][i]);}for (int i = top + 1; i < bottom + 1; i++){res.push_back(matrix[i][right]);}if(left<right && top<bottom){for (int i = right - 1; i > left-1; i--){res.push_back(matrix[bottom][i]);}for (int i = bottom - 1; i > top; i--){res.push_back(matrix[i][left]);}}left++;right--;top++;bottom--;// cout<<"res:"<<res<<endl;}return res;} };30. 包含min函數的棧
python:
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();*/31. 棧的壓入、彈出序列
思路:用棧 遇到相等的 就一直出棧
class Solution:def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:stack = []index = 0for i in range(len(pushed)):stack.append(pushed[i])while stack and stack[-1]==popped[index]:stack.pop()index += 1return not stackc++實現:
class Solution { public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> stack_A;int index = 0;for(int i=0; i<pushed.size(); i++){stack_A.push(pushed[i]);while(!stack_A.empty() && stack_A.top() == popped[index]){index++;stack_A.pop();}}return stack_A.empty();} };32 - I. 從上到下打印二叉樹
思路:bfs
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def levelOrder(self, root: TreeNode) -> List[int]:res = []if root is None:return resqueue = [root]while queue:for i in range(len(queue)):node = queue.pop(0)res.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return resc++實現:?
/*** 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:vector<int> levelOrder(TreeNode* root) {vector<int> res;if(root == NULL){return res;}queue<TreeNode*> queue_A;queue_A.push(root);while(!queue_A.empty()){int count = queue_A.size();for(int i=0; i<count; i++){TreeNode* node = queue_A.front();res.push_back(node->val);queue_A.pop();if(node->left){queue_A.push(node->left);}if(node->right){queue_A.push(node->right);}}}return res;} };32 - II. 從上到下打印二叉樹 II
思路:bfs 迭代
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:res = []if not root:return resquene= [root]while quene: temp = []for i in range(len(quene)):node = quene.pop(0)temp.append(node.val) if node.left:quene.append(node.left)if node.right: quene.append(node.right)res.append(temp) return resc++實現:
/*** 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:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if(root == NULL){return res;}queue<TreeNode* > queue_A;queue_A.push(root);while(!queue_A.empty()){vector <int> temp;int count = queue_A.size(); for(int i=0; i<count; i++){TreeNode* node = queue_A.front();temp.push_back(node->val);queue_A.pop();if(node->left){queue_A.push(node->left);}if(node->right){queue_A.push(node->right);}}res.push_back(temp);}return res;} };32 - III. 從上到下打印二叉樹 III
思路:利用隊列 bfs 層次遍歷
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:res = []if root is None:return resquene = [root]while quene:temp = []for i in range(len(quene)):node = quene.pop(0)temp.append(node.val)if node.left:quene.append(node.left)if node.right:quene.append(node.right)if len(res)%2==0:res.append(temp)else:res.append(temp[::-1])return resc++實現:
/*** 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:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if(root == NULL){return res;}queue<TreeNode*> queue_A;queue_A.push(root);while(!queue_A.empty()){vector<int> temp;int count = queue_A.size();for(int i=0; i<count; i++){TreeNode* node = queue_A.front();temp.push_back(node->val);queue_A.pop();if(node->left){queue_A.push(node->left);}if(node->right){queue_A.push(node->right);}}if(res.size() % 2 == 0){res.push_back(temp);}else{reverse(temp.begin(), temp.end());res.push_back(temp);}}return res;} };33. 二叉搜索樹的后序遍歷序列
思路:遞歸根據 后序遍歷 左右根和二叉搜索樹特點
class Solution:def help(self, left, right, postorder):if left>=right:return Truem = leftwhile postorder[m]<postorder[right]:m += 1 #找到根節點p = mwhile postorder[p]>postorder[right]:p += 1 #找到大于根節點的值的索引return p == right and self.help(left, m - 1, postorder) and self.help(m, right-1, postorder)def verifyPostorder(self, postorder: List[int]) -> bool:return self.help(0, len(postorder) - 1, postorder)c++實現:
class Solution { public:bool help(int left, int right, vector<int>& postorder){if(left>=right){return true;}int m = left;while(postorder[m]<postorder[right]){m++;}int p = m;while(postorder[p]>postorder[right]){p++;}return (p == right) && help(left, m-1, postorder) && help(m, right-1, postorder);}bool verifyPostorder(vector<int>& postorder) {return help(0, postorder.size() - 1, postorder);} };35. 復雜鏈表的復制
思路:其實就是深拷貝 ，這里采用dfs。
從頭結點 head 開始拷貝；
由于一個結點可能被多個指針指到，因此如果該結點已被拷貝，則不需要重復拷貝；
如果還沒拷貝該結點，則創建一個新的結點進行拷貝，并將拷貝過的結點保存在哈希表中；
使用遞歸拷貝所有的 next 結點，再遞歸拷貝所有的 random 結點。
python:
""" # Definition for a Node. class Node:def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):self.val = int(x)self.next = nextself.random = random """ #其實就是考驗深拷貝 class Solution:def help(self, node, view):#dfsif node is None:return nodeif node in view:#已經出現過return view[node]new_node = Node(node.val, None, None)view[node] = new_nodenew_node.next = self.help(node.next, view)new_node.random = self.help(node.random, view)return new_nodedef copyRandomList(self, head: 'Node') -> 'Node':view = {}return self.help(head, view)c++:
/* // Definition for a Node. class Node { public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;} }; */ class Solution { public:map<Node*, Node*> view;Node* help(Node* node){if(node == nullptr){return nullptr;}if(view.count(node)){//已經出現過了的節點 返回就行return view[node];}Node* new_node = new Node(node->val);view[node] = new_node;//記錄已經創建的節點new_node->next = help(node->next); new_node->random = help(node->random); return new_node;}Node* copyRandomList(Node* head) {return help(head);} };36. 二叉搜索樹與雙向鏈表
思路:中序遍歷 設定一個前驅節點pre用來形成雙向鏈接
""" # Definition for a Node. class Node:def __init__(self, val, left=None, right=None):self.val = valself.left = leftself.right = right """ class Solution:def help(self, node):#中序遍歷if node is not None:self.help(node.left)#遞歸左子樹if self.pre is not None:self.pre.right, node.left = node, self.pre #pre和node節點形成雙向節點形式else:self.head = node #第一次出現 記錄head節點self.pre = node #保存pre節點 并一直不停更新self.help(node.right)#遞歸右子樹def treeToDoublyList(self, root: 'Node') -> 'Node':if root is None:return self.pre = Noneself.head = Noneself.help(root)self.head.left, self.pre.right = self.pre, self.headreturn self.headc++實現:
/* // Definition for a Node. class Node { public:int val;Node* left;Node* right;Node() {}Node(int _val) {val = _val;left = NULL;right = NULL;}Node(int _val, Node* _left, Node* _right) {val = _val;left = _left;right = _right;} }; */ class Solution { public:Node* pre;Node* head;void help(Node* node) {if(node==NULL){return;}help(node->left);if(pre != NULL) {pre->right = node;node->left = pre;}else{head = node;}pre = node;help(node->right);}Node* treeToDoublyList(Node* root) {if(root == NULL){return NULL;}help(root);head->left = pre;pre->right = head;return head;} };38. 字符串的排列
思路:回溯? 注意有重復字符串 要剪枝? 這里用 view記錄 出現過的
python
class Solution:def backtrace(self, s, view, track):if len(track) == len(s):self.res.append(track)returnfor i in range(len(s)):if view[i]:continueif i>0 and s[i]==s[i-1] and view[i-1]==0:continueview[i] = 1store = tracktrack += s[i]self.backtrace(s, view, track)track = storeview[i] = 0def permutation(self, s: str) -> List[str]:self.res = []s = sorted(s)self.backtrace(s, [0]*len(s), '')return self.resc++實現:
class Solution { public:vector<string> res;void backtrace(string s, vector<int> view, string track){if(s.size() == track.size()){res.push_back(track);return;}for(int i=0; i<s.size(); i++){if(view[i]){continue;}if(i>0 && s[i] == s[i-1] && view[i-1] == 0){continue;}view[i] = 1;string store = track;track += s[i];backtrace(s, view, track);track = store;view[i] = 0;}return;}vector<string> permutation(string s) {vector<int> view(s.size(), 0);sort(s.begin(), s.end());backtrace(s, view, "");return res;} };39. 數組中出現次數超過一半的數字
python代碼:
class Solution:def majorityElement(self, nums: List[int]) -> int:return sorted(nums)[len(nums)//2]c++代碼:
class Solution { public:int majorityElement(vector<int>& nums) {int length = nums.size();sort(nums.begin(), nums.end());return nums[length/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 x40. 最小的k個數
python:
class Solution:def quicksort(self, arr):if len(arr) <= 1:return arrprivit = arr[len(arr)//2]middle = [x for x in arr if x == privit]left = [x for x in arr if x < privit]right = [x for x in arr if x > privit]return self.quicksort(left) + middle + self.quicksort(right)def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:return self.quicksort(arr)[:k]c++實現快排:
class Solution { public:vector<int> quickSort(vector<int>& arr){if(arr.size() <= 1){return arr;}int length = arr.size();int privit = arr[length/2];vector<int> left;vector<int> right;vector<int> middle;for(int i=0; i<length; i++){if(privit == arr[i]){middle.push_back(arr[i]);}else if(privit > arr[i]){left.push_back(arr[i]);}else{right.push_back(arr[i]);}}vector<int> left_sort = quickSort(left);vector<int> middle_sort = middle;vector<int> right_sort = quickSort(right);left_sort.insert(left_sort.end(), middle_sort.begin(), middle_sort.end());left_sort.insert(left_sort.end(), right_sort.begin(), right_sort.end());return left_sort;}vector<int> getLeastNumbers(vector<int>& arr, int k) {vector<int> sort_arr = quickSort(arr);vector<int> res;for(int i=0; i<k; i++){res.push_back(sort_arr[i]);}return res;} };c++調用現成的排序:
class Solution { public:vector<int> getLeastNumbers(vector<int>& arr, int k) {sort(arr.begin(), arr.end());vector<int> res;for(int i=0; i<k; i++){res.push_back(arr[i]);}return res;} };42. 連續子數組的最大和
思路:動態規劃
class Solution:def maxSubArray(self, nums: List[int]) -> int:dp = [0]*len(nums)dp[0] = nums[0]for i in range(1, len(nums)):dp[i] = max(nums[i], dp[i-1]+nums[i])# print(dp)return max(dp)思路:修改數組:
class Solution:def maxSubArray(self, nums: List[int]) -> int:if len(nums)==0:return []res = nums[0]for i in range(1,len(nums)):nums[i] = max(nums[i], nums[i] + nums[i-1])res = max(nums[i], res)return res思路:修改數組2?
class Solution:def maxSubArray(self, nums: List[int]) -> int:for i in range(1,len(nums)):nums[i]+=max(nums[i-1],0)return max(nums)思路:借助一個變量
o(1),0(n)
class Solution:def maxSubArray(self, nums: List[int]) -> int:if len(nums)==0:return []value = nums[0]res = nums[0]for i in range(1,len(nums)):value = max(nums[i], value + nums[i])res = max(value, res)return resc++實現
class Solution { public:int maxSubArray(vector<int>& nums) {int length = nums.size();vector<int> dp(length, 0);dp[0] = nums[0];for (int i=1; i<length; i++){dp[i] = max(nums[i], nums[i] + dp[i-1]);}int maxValue = *max_element(dp.begin(), dp.end());return maxValue;} };44. 數字序列中某一位的數字
思路:
python代碼:
class Solution:def findNthDigit(self, n: int) -> int:base = 9digit_nums = 1while n - base * digit_nums > 0:n -= base * digit_numsbase *= 10digit_nums += 1# print('==n:', n)# 計算target的值idx = n % digit_nums # 注意由于上面的計算，n現在表示digits位數的第n個數字# print('==idx:', idx)if idx == 0:idx = digit_numsnumber = 1for i in range(1, digit_nums):number *= 10# print('==digit_nums:', digit_nums)if idx == digit_nums:number += n // digit_nums - 1else:number += n // digit_nums# print('==number:', number)return int(str(number)[idx-1])c++代碼:
class Solution { public:int findNthDigit(int n) {long base = 9;int digit_nums = 1;while(n - base * digit_nums > 0){n -= base*digit_nums;base *=10;digit_nums++;}int index = n % digit_nums;if(index == 0){index = digit_nums;}long number = 1;for(int i=1;i<digit_nums;i++){number *= 10;}if(index == digit_nums){number += n/digit_nums -1;}else{number += n/digit_nums;}return int(to_string(number)[index - 1])-'0';} };45. 把數組排成最小的數
思路:其實就是排序 這里采用快排? 將合并后偏小的字母移動到左邊? 等于的移動到中間 大于的移動到右邊
class Solution:def minNumber(self, nums: List[int]) -> str:def fast_sort(arr):if len(arr) <= 1:return arrprivot = arr[len(arr)//2]left = [x for x in arr if x + privot < privot + x]middle = [x for x in arr if x == privot or x + privot == privot + x]right = [x for x in arr if x + privot > privot + x]# print('===left===:', left)# print('===right===:', right)# print('====middle:', middle)return fast_sort(left) + middle + fast_sort(right)strs = [str(num) for num in nums]# fast_sort(0, len(strs) - 1)new_strs = fast_sort(strs)# print('==new_strs:', new_strs)return ''.join(new_strs)c++實現:
class Solution { public:vector<string> quickSort(vector<string> strs) {if(strs.size() <= 1){return strs;}vector<string> left;vector<string> middle;vector<string> right;string privit = strs[int(strs.size()/2)];for(int i=0; i<strs.size(); i++){if (strs[i] + privit < privit + strs[i]){left.push_back(strs[i]);} }for(int i=0; i<strs.size(); i++){if ((strs[i] == privit) || (strs[i] + privit == privit + strs[i])){middle.push_back(strs[i]);} }for(int i = 0; i<strs.size(); i++){if (strs[i] + privit > privit + strs[i]){right.push_back(strs[i]);} }vector<string> left_sort = quickSort(left);vector<string> middle_sort = middle;vector<string> right_sort = quickSort(right);left_sort.insert(left_sort.end(), middle_sort.begin(), middle_sort.end());left_sort.insert(left_sort.end(), right_sort.begin(), right_sort.end());return left_sort;}string minNumber(vector<int>& nums) {vector<string> strs;for(int i=0; i<nums.size(); i++){strs.push_back(to_string(nums[i]));}vector<string> new_strs= quickSort(strs);string res;for(int i=0;i<new_strs.size();i++){res += new_strs[i];}return res;} };46. 把數字翻譯成字符串
思路:動態規劃,dp[i] = dp[i-1]+dp[i-2] 滿足1~25之間
class Solution:def translateNum(self, num):if 0<=num<=9:return 1nums = [i for i in str(num)]print(nums)n = len(nums)dp = [0]*ndp[0] = 1if nums[0] == '1' or (nums[0] == '2' and nums[1] <= '5'):dp[1] = 2else:dp[1] = 1for i in range(2, n):if nums[i-1] == '1' or (nums[i-1] == '2' and nums[i] <= '5'):dp[i] = dp[i-1]+dp[i-2]else:dp[i] = dp[i-1]print(dp)return dp[-1] num = 12258 sol = Solution() sol.translateNum(num)壓縮一下空間，復雜度變為o(n)?
class Solution:def translateNum(self, num):if 0<=num<=9:return 1nums = [i for i in str(num)]print(nums)n = len(nums)dp_zero = 1if nums[0]=='1' or (nums[0]=='2' and nums[1] <= '5'):dp_one = 2else:dp_one = 1for i in range(2, n):temp = dp_zerodp_zero = dp_oneif nums[i-1] == '1' or (nums[i-1] == '2' and nums[i] <= '5'):dp_one = temp+dp_zeroprint(dp_one)return dp_one num = 12258 sol = Solution() sol.translateNum(num)c++實現:
class Solution { public:int translateNum(int num) {if(0<=num && num<=9){return 1;}string num_string = to_string(num); int length = num_string.size();vector<int> dp(length, 0);dp[0] = 1;if(num_string[0] == '1' || (num_string[0] == '2' && num_string[1] <= '5')){dp[1] = 2;}else{dp[1] = 1;}for (int i=2; i<length; i++){if(num_string[i-1] == '1' || (num_string[i-1] == '2' && num_string[i] <= '5')){dp[i] = dp[i-1] + dp[i-2];// cout<<"==hahahahahaha=="<<endl;}else{dp[i] = dp[i-1];}}return dp[length-1];} };47. 禮物的最大價值
思路:動態規劃:
python代碼:
class Solution:def maxValue(self, grid: List[List[int]]) -> int:h = len(grid)w = len(grid[0])dp = [[0 for _ in range(w)] for _ in range(h)]# print(np.array(dp))dp[0][0] = grid[0][0]for i in range(1, h):dp[i][0] = dp[i-1][0]+grid[i][0]# print(np.array(dp))for i in range(1, w):dp[0][i] = dp[0][i-1]+grid[0][i]# print(np.array(dp))for i in range(1,h):for j in range(1,w):dp[i][j] = max(dp[i-1][j],dp[i][j-1])+grid[i][j]# print(np.array(dp))return dp[-1][-1]c++實現:
class Solution { public:int maxValue(vector<vector<int>>& grid) {int h = grid.size();int w = grid[0].size();vector<vector<int>> dp(h, vector<int>(w));dp[0][0] = grid[0][0];for (int i=1;i<h;i++){dp[i][0]=dp[i-1][0]+grid[i][0];}for (int i=1;i<w;i++){dp[0][i]=dp[0][i-1]+grid[0][i];}for(int i=1;i<h;i++){for(int j=1;j<w;j++){dp[i][j]= max(dp[i-1][j],dp[i][j-1])+grid[i][j];} }return dp[h-1][w-1];} };48. 最長不含重復字符的子字符串
思路:滑動窗口
python代碼：
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:left,right =0,0dict_ = {}res = 0while right<len(s):dict_[s[right]] = dict_.get(s[right], 0) + 1while dict_[s[right]]>1:dict_[s[left]]-=1left+=1res = max(res, right - left + 1)right+=1# print(res)return resc++實現:
class Solution { public:int lengthOfLongestSubstring(string s) {int left=0;int right = 0;int res=0;map<int,int>dict_;while(right<s.size()){dict_[s[right]]++;while(dict_[s[right]]>1){dict_[s[left]]--; left++;}res = max(res, right-left+1);right+=1;}return res;} };49-1:丑數
思路:判斷是否能整除2,3,5依次整除下去，將不能整除和１進行判斷就知道是否是丑數了
class Solution:def isUgly(self, n: int) -> bool:if n <= 0: return Falsewhile((n % 2) == 0):n /= 2while((n % 3) == 0):n /= 3while((n % 5) == 0):n /= 5return n == 1c++循環實現:
class Solution { public:bool isUgly(int n) {if(n <= 0){return false;}while((n % 2) == 0){n /= 2;}while((n % 3) == 0){n /= 3;}while((n % 5) == 0){n /= 5;}return n == 1;} };c++遞歸實現:
//遞歸寫法 class Solution { public:bool isUgly(int n) {if(n <= 0){return false;}while((n % 2) == 0){return isUgly(n / 2);}while((n % 3) == 0){return isUgly(n / 3);}while((n % 5) == 0){return isUgly(n / 5);}return n == 1;} };49-2.丑數
思路：題目要求的這個數字一定是由單個或者多個2,3,5的乘積，如果從小到大去枚舉在判斷是否由2,3,5乘積組成，工作量會很大，所以考慮用2,3,5從下往上遞推，需要開辟空間為n的數組，采用動態規劃,2,3,5分別有三個索引，如果滿足要求的數字等于2,3,5的倍數乘積，那么就直接將索引加1.
python代碼:
class Solution:def nthUglyNumber(self, n):dp, index_two, index_three, index_five = [1] * n, 0, 0, 0for i in range(1, n):two = dp[index_two] * 2three = dp[index_three] * 3five = dp[index_five] * 5dp[i] = min(two, three, five)if two==dp[i]:index_two+=1if three==dp[i]:index_three+=1if five==dp[i]:index_five+=1print('==dp:', dp)return dp[-1]n = 11 sol = Solution() sol.nthUglyNumber(n)c++代碼:
class Solution { public:int nthUglyNumber(int n) {vector<int> dp(n,1);int index_two=0;int index_three=0;int index_five=0;for (int i=1;i<n;i++){int two = dp[index_two]*2;int three = dp[index_three]*3;int five = dp[index_five]*5;dp[i] = min(min(two, three), five);if (dp[i]==two){index_two++;}if (dp[i]==three){index_three++;}if (dp[i]==five){index_five++;}}return dp[n-1];} };50.第一個只出現一次的字符
思路:
最直接的想法是hash,但是hash具有無序性，就改為字符數組計數
python代碼:
class Solution:def firstUniqChar(self, s: str) -> str:letter_list = [0]*26for i in s:letter_list[ord(i) - ord('a')]+=1# print(letter_list)for i in s:if letter_list[ord(i)-ord('a')]==1:return ireturn " "c++代碼:
class Solution { public:char firstUniqChar(string s) {vector<int> letter_list(26, 0);for(int i=0;i<s.size();i++){letter_list[s[i]-'a']++;}vector<int>::iterator iter= letter_list.begin();for(int i=0;i<s.size();i++){if (iter[s[i]-'a']==1){return s[i];}} return ' ';} };51.數組中的逆序對
思路1:兩層for循環 超時
思路2：歸并排序 在合并的時候順便統計逆序對
class Solution:def mergeSort(self, nums, start, end):if start >= end:returnmid = start + (end - start) // 2self.mergeSort(nums, start, mid)self.mergeSort(nums, mid + 1, end)self.merge(nums, start, mid, end)def merge(self, nums, start, mid, end):i, j, temp = start, mid + 1, []while i <= mid and j <= end:if nums[i] <= nums[j]:temp.append(nums[i])i += 1else:print('==i:', i)print('=== start:', start)print('=== mid:', mid)print('=== end:', end)self.cnt += mid - i + 1temp.append(nums[j])j += 1while i <= mid:temp.append(nums[i])i += 1while j <= end:temp.append(nums[j])j += 1for i in range(len(temp)):nums[start + i] = temp[i]print('==nums:', nums)def reversePairs(self, nums):self.cnt = 0self.mergeSort(nums, 0, len(nums) - 1)print('==after nums:', nums)return self.cntnums = [7,5,6,4] sol = Solution() sol.reversePairs(nums) print(sol.cnt)52.兩個鏈表的第一個公共節點
思路:雙指針 兩個指針輪流走一遍各自的路程，這樣相遇就是公共節點，對于沒有公共節點的情況，所以需要判斷自身節點不是none，而不是.next是none，在去交換指針，否則會陷入無窮循環,而此時輸出就是none。
python
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:first_head = headAsecond_head = headBwhile first_head !=second_head:if first_head is not None:first_head = first_head.next else:first_head = headBif second_head is not None:second_head = second_head.nextelse:second_head = headA# print(first_head)return first_headc++
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *first_node;first_node = headA;ListNode *second_node;second_node= headB;while(first_node != second_node){if(first_node !=NULL){first_node = first_node->next;}else{first_node = headB;}if(second_node !=NULL){second_node = second_node->next;}else{second_node = headA;}}return first_node;} };53-1. 在排序數組中查找數字 I
思路1:hash
class Solution:def search(self, nums, target):dict_={}for i in range(len(nums)):dict_[nums[i]] = dict_.get(nums[i],0)+1print(dict_)return dict_[target] if target in dict_ else 0nums = [5,7,7,8,8,10] target = 8 sol = Solution() sol.search(nums, target)思路2:python 雙指針
class Solution:def search(self, nums, target):left = 0right = len(nums)-1while left<right:middle = left+(right-left)//2if nums[middle] >=target:right=middleelse:left=middle+1res=0for i in range(left,len(nums)):if nums[i]==target:res+=1return resnums = [5,7,7,8,8,10] target = 8 sol = Solution() sol.search(nums, target)思路2:C++?雙指針
#include <map> #include <vector> #include <iostream> #include <string> #include <algorithm> using namespace std;class Solution { public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size()-1;int res=0;while (left<right){int middle = left+(right-left)/2;if (nums[middle]>=target){ right=middle;}else{left=middle+1;}}while (left<nums.size()&&nums[left]==target){ left++;res++;}return res;return 0;} };int main() {Solution *p = new Solution();vector<int> nums;nums = {5,7,7,8,8,10};int target = 8;int res = p->search(nums, target);cout<<"==res:"<<res<<endl;delete p;p=NULL;return 0; }53-2.0～n-1中缺失的數字
思路：雙指針，判斷中值是否等于索引，等于的話說明缺失值在ｍｉｄｄｌｅ右邊，left就變為middle+1,否則在ｍｉｄｄｌｅ左邊,right變為middle-1,最后left的值就是缺失值．?
python代碼
class Solution:def missingNumber(self, nums: List[int]) -> int:left = 0right = len(nums)-1while left<=right:middle =left+(right-left)//2if nums[middle]==middle:#中值等于索引 則說明缺失值在ｍｉｄｄｌｅ右邊left = middle+1else:#中值不等于索引 則說明缺失值在ｍｉｄｄｌｅ左邊right = middle-1return leftc++代碼:
#include <vector> #include <iostream> #include <string> #include <algorithm> using namespace std;class Solution { public:int missingNumber(vector<int>& nums) {int left = 0;int right = nums.size()-1;while (left<=right){int middle = left+(right-left)/2;if (nums[middle]==middle){left = middle+1;}else{right = middle-1;}}return left;} }; int main() {Solution *p = new Solution();vector<int> nums;nums = {0,1,2,3,4,5,6,7,9};int res = p->missingNumber(nums);cout<<"==res:"<<res<<endl;delete p;p=NULL;return 0; }54.二叉搜索樹的第k大節點
?思路：利用二叉搜索樹特點，左子樹值<根節點值<右子樹值，故采用中序遍歷
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def kthLargest(self, root: TreeNode, k: int) -> int:res = []def helper(node):if node is not None:helper(node.left)res.append(node.val)helper(node.right)helper(root)print('res:', res)return res[::-1][k-1]c++代碼:
/*** 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:vector<int> res;void help(TreeNode* node){if (node !=NULL){help(node->left);res.push_back(node->val);help(node->right);}}int kthLargest(TreeNode* root, int k) {help(root);return res[res.size()-k];} };?55-1.二叉樹的深度
遞歸:python代碼
# 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 maxDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0return max(self.maxDepth(root.left),self.maxDepth(root.right))+1c++代碼:
/*** 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 maxDepth(TreeNode* root) {if(root==NULL){return 0;}return max(maxDepth(root->left),maxDepth(root->right))+1;} };?55-2.平衡二叉樹
思路:前序遍歷 求當前節點root的深度差，再去遍歷求左右子節點的深度差
python代碼
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def help(self,node):#計算深度if node is None:return 0return max(self.help(node.left),self.help(node.right))+1def isBalanced(self, root: TreeNode) -> bool:if root is None:return Truereturn abs(self.help(root.left) - self.help(root.right))<=1 and \self.isBalanced(root.left) and self.isBalanced(root.right)c++代碼:
/*** 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 help(TreeNode* node) {if(node == NULL){return 0;}return max(help(node->left),help(node->right))+1;}bool isBalanced(TreeNode* root) {if(root == NULL){return true;} return abs(help(root->left)-help(root->right))<=1 && isBalanced(root->left)&& isBalanced(root->right);} };56-1.數組中數字出現的次數
思路:hash
python代碼:
class Solution:def singleNumbers(self, nums):dict_ = {}for i in range(len(nums)):dict_[nums[i]] = dict_.get(nums[i],0)+1print(dict_)res = []for key,value in dict_.items():if value==1:res.append(key)print(res)return resnums = [4,1,4,6] sol = Solution() sol.singleNumbers(nums)c++代碼:
#include <map> #include <vector> #include <iostream>using namespace std;class Solution { public:vector<int> singleNumbers(vector<int>& nums) {map<int,int>dict_;for (int k=0;k<nums.size();k++){dict_[nums[k]]++;}vector<int> res;map<int,int>::iterator iter=dict_.begin();for (;iter!=dict_.end();iter++){if(iter->second==1){res.push_back(iter->first);}}return res;} };int main() {vector<int> nums;nums = {4,1,4,6};Solution *sol = new Solution();// vector<int> res;auto res = sol->singleNumbers(nums);for (int k=0;k<res.size();k++){cout<<"res[k]"<<res[k]<<endl;}delete sol;sol = NULL;return 0; }?56-2.數組中數字出現的次數 II
思路:hash
python代碼:
class Solution:def singleNumber(self, nums: List[int]) -> int:dict_={}for num in nums:dict_[num]=dict_.get(num,0)+1# print(dict_)for key,value in dict_.items():if value==1:return keyc++代碼:
#include <iostream> #include <vector> #include <list> #include <map>using namespace std;class Solution { public:int singleNumber(vector<int>& nums) {// cout<<"hhah"<<endl;map<int,int> dict_;for (int k=0;k<nums.size();k++){dict_[nums[k]]++;}map <int,int>::iterator itor = dict_.begin();for(;itor!=dict_.end();itor++){// cout<<itor->first<<" "<<itor->second<<endl;if(itor->second==1){return itor->first;}}return -1;} };int main() { vector<int> nums;// int nums[] = {3,4,3,3};nums.push_back(3);nums.push_back(4);nums.push_back(3);nums.push_back(3);Solution sol;int res = sol.singleNumber(nums);cout<<res<<endl;return 0; }57-1.和為s的兩個數字
思路１：兩層for循環 O(n2)
class Solution:def twoSum(self, nums, target):res = []for i in range(len(nums)):for j in range(i+1, len(nums)):if nums[i]+nums[j]==target:res.extend([i, j])breakprint('==res:', res)return res nums = [2, 7, 6, 15] target = 9 sol = Solution() sol.twoSum(nums, target)思路2：hash python代碼
class Solution:def twoSum(self, nums, target):res_dict = {}for i in range(len(nums)):value = target - nums[i]if value in res_dict:return [res_dict[value], i]res_dict[nums[i]] = iprint('==res_dict:', res_dict)return [-1, -1]nums = [2, 7, 6, 15] target = 9 sol = Solution() res = sol.twoSum(nums, target) print('res:', res)思路2:c++代碼：
#include <string> #include <iostream> #include <vector> #include <list> #include <map> #include <typeinfo>using namespace std;class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {map<int, int> dict_;for(int k=0;k<nums.size();k++){dict_[nums[k]] = k;}map <int,int>::iterator iter = dict_.begin();for (;iter!=dict_.end();iter++){if(dict_[target - iter->first]){// cout<<iter->second<<dict_[target - iter->first]<<endl;return {iter->first,target - iter->first};}}return {-1,-1};} };int main() { vector<int> nums;nums = {2,7,11,15};int target = 9;// nums = [2,7,11,15]Solution sol;vector<int> res;res = sol.twoSum(nums,target);for(int k=0;k<res.size();k++){cout<<"==res[k]:"<<res[k]<<endl;} return 0; }57-2.和為s的連續正數序列
思路:雙指針，和偏大，左指針右移，和偏小，右指針右移，剛好的話就記錄相應的值，左指針在右移停止循環即可。
python代碼:
class Solution:def findContinuousSequence(self, target):list_ = [i for i in range(1, target)]print('==list_:', list_)left,right = 0, 0Sum = 0res = []while right<len(list_):if Sum<target:Sum+=list_[right]right+=1elif Sum == target:res.append(list_[left:right])left += 1Sum -= list_[left-1]else:Sum-=list_[left]left+=1print('==res:', res)return restarget = 9 sol = Solution() sol.findContinuousSequence(target)c++代碼:
#include <map> #include <vector> #include <iostream> #include <queue> #include <algorithm> using namespace std;class Solution { public:vector<vector<int>> findContinuousSequence(int target) {vector<int> nums;for (int i=1;i<target;i++){nums.push_back(i);}int left=0;int right=0;int temp=0;vector<vector<int>> res;while (right<nums.size()){if(temp<target){ temp+=nums[right];right++; }else if(temp>target){temp-=nums[left];left++;}else{ vector<int> res_temp;for (int i=left;i<right;i++){res_temp.push_back(nums[i]);} res.push_back(res_temp);temp-=nums[left];left++;}}return res;} };int main() { Solution *p = new Solution();int target = 9;vector<vector<int>> res;res = p->findContinuousSequence(target);cout<<res.size()<<endl;for(int k=0;k<res.size();k++){ for (int j=0;j<res[k].size();j++){cout<<"res "<<k<<j<<" "<<res[k][j]<<endl;}}delete p;p = NULL;return 0; }58-1.翻轉單詞順序
python代碼:
class Solution:def reverseWords(self, s: str) -> str:s = s.strip()# print(s)s = s.split()# print(s)return ' '.join(s[::-1])c++代碼:
#include <map> #include <vector> #include <iostream> #include <queue> #include <string> #include <algorithm> using namespace std;class Solution { public:string reverseWords(string s) {string res="";int length = s.size();// cout<<"==length:"<<length<<endl;int right = length-1;while (right>=0){if (s[right]==' ')//去除開頭空格{right--;continue;}while (right>=0 && s[right]!= ' ')//減少至空格處{right--;}int index = right;right++;//加回去到非空格處if (res.empty()){while (s[right]!= ' ' && right<length){ res+=s[right];//第一個串 就開始添加right++;}}else{res+=" ";while (s[right]!= ' ' && right<length){ res+=s[right];//第二個串以后 就先添加空格 在繼續添加right++;}}cout<<"res:"<<res<<endl;right = index; }return res;} };int main() { Solution *p = new Solution();// string s = "the sky is blue";string s = " hello world! ";string res;res = p->reverseWords(s);cout<<"res:"<<res<<endl;delete p;p = NULL;return 0; }?58-2.左旋轉字符串
python代碼:
class Solution:def reverseLeftWords(self, s: str, n: int) -> str:return s[n:]+s[:n]c++代碼:
class Solution { public:string reverseLeftWords(string s, int n) {string res;for(int i=n;i<s.size();i++){res+=s[i];}for(int i=0;i<n;i++){res+=s[i];}return res;} };59-1.滑動窗口最大值
思路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思路1:c++可以:
class Solution { public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> res;if (nums.size()==0){return res;}for (int i=0;i<nums.size()-k+1;i++){ int temp = INT_MIN;for (int j=i;j<i+k;j++){temp = max(temp, nums[j]);}res.push_back(temp);}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)思路3:c++代碼
class Solution { public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> res;vector<int> quene;for (int j=0;j<nums.size();j++){ int i = j-k+1;if(i>0 && nums[i-1]==quene.front())//頂部元素正好等于了要左移元素 那么將隊列頂部元素移動開{quene.erase(quene.begin());}while (!quene.empty() && quene.back()<nums[j])//保持單調遞減{quene.erase(quene.end()-1);} quene.push_back(nums[j]);// cout<<"quene.front():"<<quene.front()<<endl;// cout<<"quene.back():"<<quene.back()<<endl;if(i>=0){res.push_back(quene.front());}}return res;} };59-2.隊列的最大值
思路1: 其中去Max操作是o(n)
class MaxQueue:def __init__(self):self.quene = []def max_value(self):if len(self.quene):return max(self.quene)else:return -1def push_back(self, value):self.quene.append(value)def pop_front(self):if len(self.quene):return self.quene.pop(0)else:return -1# Your MaxQueue object will be instantiated and called as such: obj = MaxQueue() param_1 = obj.max_value() value = 10 obj.push_back(value) param_3 = obj.pop_front() print(param_3)思路2:采用雙端隊列,優化取max操作
class MaxQueue:def __init__(self):self.queue = []self.deque = []def max_value(self):return self.deque[0] if self.deque else -1def push_back(self, value):self.queue.append(value)while self.deque and self.deque[-1] < value:self.deque.pop()self.deque.append(value)def pop_front(self):if len(self.queue) == 0:return -1val = self.queue.pop(0)if val == self.deque[0]:self.deque.pop(0)return valobj = MaxQueue() param_1 = obj.max_value()for value in [10, 5, 8]:obj.push_back(value)print('==obj.queue:', obj.queue) print('==obj.deque:', obj.deque) param_3 = obj.pop_front() print('==param_3:', param_3) print('==obj.queue:', obj.queue) print('==obj.deque:', obj.deque)60.n個骰子的點數
思路:一個骰子的概率 first_prob = [1/6, 1/6, 1/6, 1/6, 1/6, 1/6]
兩個骰子的概率 temp_prob = [5*2+1]
temp_prob[i+x] = first_prob[i]*second_prob[x]
第n個骰子的概率 temp_prob = [5*n+1]*0
#一個骰子的概率 first_prob = [1/6, 1/6, 1/6, 1/6, 1/6, 1/6] #兩個骰子的概率 temp_prob = [5*2+1] # temp_prob[i+x] = first_prob[i]*second_prob[x]#第n個骰子的概率 temp_prob = [5*n+1]*0 class Solution:def dicesProbability(self, n):first_prob, second_prob = [1/6]*6, [1/6]*6for index in range(2, n+1):temp_prob = [0]*(5*index+1)for i in range(len(first_prob)): #第一個骰子的概率for j in range(len(second_prob)): #第二個骰子的概率temp_prob[i+j] += first_prob[i]*second_prob[j]print('==temp_prob:', temp_prob)#第一個骰子的概率換成前幾次計算的概率也就是n-1first_prob = temp_probprint('==first_prob:', first_prob)return first_prob n = 2 sol = Solution() sol.dicesProbability(n)c++代碼:
class Solution { public:vector<double> dicesProbability(int n) {vector<double> probs;vector<double> first_prob;for (int i=0;i<6;i++){probs.push_back(1./6);first_prob.push_back(1./6);}for (int i=2;i<n+1;i++){ vector<double> temp_prob;for (int temp_i=0;temp_i<5*i+1;temp_i++){temp_prob.push_back(0);}for (int j=0;j<probs.size();j++){for (int k=0;k<first_prob.size();k++){temp_prob[j+k]+=probs[j]*first_prob[k];} }probs = temp_prob;}return probs;} };61.撲克牌中的順子
思路:1.除去0發現重復的就返回false
2. 如果沒有重復,則再判斷除去的0的最大最小值差值與5的關系
python代碼:
#思路:1.除去0發現重復的就返回false #2. 如果沒有重復,則再判斷除去的0的最大最小值差值與5的關系class Solution:def isStraight(self, nums):nums = sorted(nums)index = 0for i in range(len(nums)-1):if nums[i]==0:index+=1elif nums[i] == nums[i+1]:#先去重return Falseif nums[-1]-nums[index]>4:return Falsereturn True# nums = [0,0,1,2,5] nums = [0,6,1,2,5] sol = Solution() res = sol.isStraight(nums) print(res)c++代碼:
class Solution { public:bool isStraight(vector<int>& nums) {int index = 0;sort(nums.begin(),nums.end());for(int i=0;i<nums.size();i++){if (nums[i]==0){index+=1;}else if(i>0 && nums[i]==nums[i-1]){return false;}}if(nums.back() - nums[index]>4){ return false;}return true;} };62.圓圈中最后剩下的數字
思路:一直迭代
python代碼:
#思路:一直迭代 class Solution:def lastRemaining(self, n, m):index = 0num_list = [i for i in range(n)]while len(num_list) > 1:print('==num_list:', num_list)index = (index + m-1) % len(num_list)print('==index:', index)num_list.pop(index)return num_list[0]n = 4 m = 3 sol = Solution() sol.lastRemaining(n, m)c++代碼:
上述代碼改寫成c++會超時，故換一種思路，從兩個人一直往上遞推到n個人
class Solution { public:int lastRemaining(int n, int m) {int pos=0;for (int i=2;i<=n;i++){pos = (pos+m)%i;}return pos;} };63.股票的最大利潤
思路:一次遍歷更新最小價格和利潤即可 python代碼
class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices)==0:return 0min_price = prices[0]max_profit = 0for i in range(1,len(prices)):max_profit = max(max_profit, prices[i] - min_price)min_price = min(min_price, prices[i])# print(max_profit)return max_profitdp:
class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices)==0:return 0dp =[0]*len(prices)min_price = prices[0]for i in range(1,len(prices)):dp[i] = max(dp[i-1],prices[i]-min_price)min_price = min(min_price,prices[i])# print(dp)return dp[-1]c++代碼:
class Solution { public:int maxProfit(vector<int>& prices) {if(prices.size()==0){return 0;}int min_price = prices[0];int profit = 0;for(int i=1;i<prices.size();i++){profit = max(profit, prices[i]-min_price);min_price = min(min_price, prices[i]);}return profit;} };64.求1+2+…+n
python:
class Solution:def sumNums(self, n: int) -> int:return n if n==0 else n+self.sumNums(n-1)c++:
class Solution { public:int sumNums(int n) {if (n==1){return n;}return n+sumNums(n-1);} };65.不用加減乘除做加法
思路:既然不能用四則運算，那么就用位運算替代
class Solution { public:int add(int a, int b) {if(a==0 || b==0){return a==0?b:a;}int sum_=0;int carry=0;while (b!=0){sum_ = a^b;carry = (unsigned int) (a&b)<<1;a = sum_;b = carry;}return a;} };66.構建乘積數組
思路1:雙指針:
超時
# 雙層for循環 超時 o(n^2) class Solution:def constructArr(self, a):n = len(a)res = [0]*nindex = 0while index<n:temp = 1left = index-1right = index+1while left>=0:temp*=a[left]left-=1while right<n:temp *= a[right]right += 1res[index]= tempindex+=1print(res)return res思路2:dp 用left記錄存儲i的左半部分乘積
? ? ? ? ? ? ?用right記錄存儲i的右半部分乘積
? ? ? ? ?再用left和right對應位置的數相乘就是結果
#B[i] = A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n] #dp left存儲i的左半部分乘積 #dp right存儲i的左半部分乘積 class Solution:def constructArr(self, a):n = len(a)left, right = [1] * n, [1] * nfor i in range(1, n):left[i] = left[i - 1] * a[i - 1]print(left)for i in range(n-2, -1, -1):right[i] = right[i+1]*a[i+1]print(right)res = [0]*len(a)for i in range(n):res[i] = left[i]*right[i]print(res)return res a = [1,2,3,4,5] sol = Solution() sol.constructArr(a)思路3:優化上一個dp
#優化版 class Solution:def constructArr(self, a):n = len(a)left, right = [1] * n, [1] * nfor i in range(1, n):left[i] = left[i - 1] * a[i - 1]print(left)temp = 1for i in range(n-2, -1, -1):temp = temp*a[i+1]left[i] *= tempprint(left)return lefta = [1,2,3,4,5] sol = Solution() sol.constructArr(a)c++:
class Solution { public:vector<int> constructArr(vector<int>& a) {int n = a.size();vector<int>res(n,1);for (int i=1;i<n;i++){res[i] = res[i-1]*a[i-1];}int temp=1;for (int i=n-2;i>-1;i--){temp *= a[i+1];res[i] *= temp;} return res;} };67.把字符串轉換成整數
思路:
?1.去除首尾空格
2.判斷符號索引
3.從符號索引的下一位進行轉換 遇到字母就停止
#思路: # 1.去除首尾空格 # 2.判斷符號索引 # 3.從符號索引的下一位進行轉換 遇到字母就停止 class Solution:def strToInt(self, str):new_str = str.strip()if len(new_str)==0:return 0start = 0sign = 1if new_str[0]=='-':start=1sign = -1if new_str[0]=='+':start=1sign = 1res = 0for i in range(start,len(new_str)):if "0"<=new_str[i]<="9":res = 10*res + int(new_str[i])else:breakprint(res)res = sign*resif res >= 2 ** 31 - 1:return 2**31-1if res<=-2**31:return -2**31return resstr = " -42ddff" sol = Solution() sol.strToInt(str)c++:
class Solution { public:int strToInt(string str) {int index =0;for (int i=0;i<str.size();i++){if (str[i]==' '){index++;}else{break;}}string new_str = "";new_str = str.substr(index);// cout<<new_str<<endl;int start=0;int sign=1;long res=0;if (new_str[0]=='-'){sign=-1;start=1;}if (new_str[0]=='+'){sign=1;start=1;}for(int i=start;i<new_str.size();i++){if('0'<=new_str[i] && new_str[i]<='9'){res=10*res+(new_str[i]-'0');if(sign==1 && res>INT_MAX){return INT_MAX;}if(sign==-1 && res-1>INT_MAX){return INT_MIN;}}else{break;}}res = sign*res;if (res>pow(2,31)-1){return pow(2,31)-1;}if (res<-pow(2,31)){return -pow(2,31);}return res;} };?68-1.二叉搜索樹的最近公共祖先
思路：
1.從根節點開始遍歷樹
2.如果節點 p 和節點 q 都在右子樹上，那么以右孩子為根節點繼續 1 的操作
3.如果節點 p 和節點 q 都在左子樹上，那么以左孩子為根節點繼續 1 的操作
4.如果條件 2 和條件 3 都不成立，這就意味著我們已經找到p 和q 的公共祖先了
解法1:當成普通二叉樹
# 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==p or root==q or root is None:return rootleft_node = self.lowestCommonAncestor(root.left,p,q)right_node = self.lowestCommonAncestor(root.right,p,q)if left_node is None:return right_nodeif right_node is None:return left_nodereturn root解法2利用二叉搜索樹特點根節點值和左右子樹值大小的特點.遞歸法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None #利用二叉搜索樹的特點 class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':print('==root.val:', root.val)if root.val< min(p.val, q.val):#都大于根節點的值 將右孩子作為根節點return self.lowestCommonAncestor(root.right, p, q)elif root.val > max(p.val, q.val):#都小于根節點的值 將左孩子作為根節點return self.lowestCommonAncestor(root.left, p, q)else:#找到公共祖先return root解法3.迭代法
#利用二叉搜索樹的特點 class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':node = rootwhile node:if node.val < min(p.val,q.val):node = node.rightelif node.val > max(p.val,q.val):node = node.leftelse:return nodec++:
/*** 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:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root->val<min(p->val,q->val)){return lowestCommonAncestor(root->right,p,q);}if(root->val>max(p->val,q->val)){return lowestCommonAncestor(root->left,p,q);}return root;} };?68-2:二叉樹的最近公共祖先
python:遞歸
# 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++:
/*** 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:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == NULL){return NULL;}if(root->val == p->val || root->val == q->val){return root;}TreeNode* left_node = lowestCommonAncestor(root->left,p,q);TreeNode* right_node = lowestCommonAncestor(root->right,p,q);if(left_node !=NULL && right_node!=NULL){return root;}if (left_node==NULL){return right_node;}return left_node;} };?
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的python(c++)刷题+剑指offer的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： GIOU loss+DIOU loss+
- 下一篇： python可迭代对象，迭代器，生成器