剑指 Offer 03——10

@Author：Runsen

决定重新刷剑指 Offer，C++和Py版本

03. 数组中重复的数字

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

方法： 排序 遍历、set和map

C++

class Solution {
public:int findRepeatNumber(vector& nums) {// 排序 遍历  	32 ms	22.4 MB// sort(nums.begin(),nums.end());// for(int i = 0; i  set;// for (int num :nums){//     if(set.count(num) == 1 ){//         return num;//     }else{//         set.insert(num);//     }// }// return 0;// map  56 ms	26.8 MB	unordered_map map;for(int num :nums){if (map[num]) {return num;}else{map[num] = true;}}return -1;}
};

python

class Solution:def findRepeatNumber(self, nums: List[int]) -> int:# nums.sort()# for i in range(len(nums)):#     if nums[i] == nums[i+1]:#         return nums[i]# return -1# newset =  set()# for i in nums:#     if i in newset:#         return i#     else:#         newset.add(i)# return -1newmap = {}for i in nums:if i in newmap:return ielse:newmap[i] = 1return -1

04. 二维数组中的查找

现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。

方法：暴力和从右上角到左下角

C++

class Solution {
public:bool findNumberIn2DArray(vector>& matrix, int target) {// 暴力  12 ms	12.7 MB// for(int i = 0; i < matrix.size(); i++ ){//     for (int j = 0; j =0){if( matrix[row][col] == target){return  true;}else if(matrix[row][col] > target){col--;}else{row++;}}return false;}
};

python

class Solution:def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:# 暴力  56 ms 19 MB# for i in range(len(matrix)):#     for j in range(len(matrix[0])):#         if matrix[i][j] == target:#             return True# return False# 32 ms  18.9 MBif not matrix:return Falserows = len(matrix)cols = len(matrix[0])row = 0col = cols  -1 while (row < rows) and (col >=0 ):if matrix[row][col] == target:return Trueelif matrix[row][col] > target:col = col - 1 else:row = row + 1 return False

05. 替换空格

输入：s = “We are happy.”
输出：“We%20are%20happy.”

class Solution {
public:string replaceSpace(string s) {// new string  0 ms 6.1 MB// string st;// for(char c: s){//     if( c == ' '){//         st += "%20";//     }else{//         st += c;//     }// }// return st;// }// C++ 的string可变  0 ms	6 MBint len = s.size();int cout = 0;for(char c: s){if(c ==  ' '){cout++;}}s.resize(len + 2 * cout);for(int i =len-1 , j = s.size() -1 ; i < j ;i--,j--){if (s[i] != ' '){s[j] = s[i];}else{s[j] = '0';s[j-1] = '2';s[j-2] = '%';j -=2; }}return s;}};

Python

class Solution:def replaceSpace(self, s: str) -> str:# 32 ms	15.1 MBst = ""for i in s:if i == ' ':st += "%20"else:st += ireturn st

06. 从尾到头打印链表

输入：head = [1,3,2]
输出：[2,3,1]

Ｃ＋＋

class Solution {
public:// vector reversePrint(ListNode* head) {//     // 4 ms	8.4 MB//     vector vet;//     while (head){//         vet.push_back(head->val);//         head = head->next;//     }//     reverse(vet.begin(),vet.end());//     return vet;// }// 4 ms	10.9 MBvector reversePrint(ListNode* head) {if (head == NULL) return {};vector pre = reversePrint(head->next);pre.push_back(head->val);return pre;}
};

python

class Solution:def reversePrint(self, head: ListNode) -> List[int]:# 递归 120 ms	24.3 MB# return self.reversePrint(head.next) + [head.val] if head else []# 数组反转 	48 ms	16.3 MBif not head : return [] stack = []while head:stack.append(head.val)head = head.next return stack[::-1]

07. 重建二叉树

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:# 遍历 132 ms	87.2 MBif len(preorder) == 0: return Nonenode = TreeNode(preorder[0])index = inorder.index(node.val)node.left = self.buildTree(preorder[1:index + 1],inorder[:index])node.right = self.buildTree(preorder[index + 1 :],inorder[index+1:])return node 

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* buildTree(vector<int>& preorder, vector<int>& inorder) {if (preorder.empty() || inorder.empty()){return NULL;}// 寻找根节点TreeNode *root = new TreeNode(preorder[0]);auto index = find(inorder.begin(),inorder.end(), preorder[0]);vector<int> ileft(inorder.begin(),index);vector<int> lright(index+1,inorder.end());int len = ileft.size();vector<int> pleft(preorder.begin()+1,preorder.begin() +1+ len);vector<int> pright(preorder.begin() + 1+ len, preorder.end());root->left = buildTree(pleft,ileft);root->right = buildTree(pright,lright);return root;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！