当前位置 博文首页 > DL_fan的博客：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]] = iclass 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 False
w = len(matrix[0])
i, j = h-1, 0
while i >= 0 and j <= w-1:
if matrix[i][j] > target:
i -= 1
elif matrix[i][j] < target:
j += 1
else:
return True
return 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 = None
class 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.next
return 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 = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if len(preorder) == 0 or len(inorder) == 0:
return None
node = 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 -1
if 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, 1
for i in range(2, n + 1):
temp = a
a = b
b = (temp + b) % 1000000007
return 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) - 1
while left < right:
middle = left + (right - left) // 2
if numbers[middle] < numbers[right]:#说明middle是最小值右侧元素
right = middle
elif numbers[middle] > numbers[right]:#说明middle是最小值左侧元素
left = middle + 1
else:
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 False
if index == len(self.word) - 1:
return True
self.board[i][j] = ''#说明board和word找到相同的 因为不能重复 修改一下borad
for direction in self.directions:
new_i, new_j = direction[0] + i, direction[1] + j
if self.help(new_i, new_j, h, w, index + 1):
return True
self.board[i][j] = self.word[index]#回溯出去需要还原
return False
def exist(self, board: List[List[str]], word: str) -> bool:
self.board = board
self.word = word
self.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 True
return 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 = 0
while num:
count += num % 10
num //= 10
return count
def movingCount(self, m: int, n: int, k: int) -> int:
#BFS
queue = [(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 = 0
while num:
count += num % 10
num //=10
return count
def 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 1
if(n == 3):
return 2
res = 1
while(n > 4):
res *= 3
n -= 3
res *= n
return 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 1
if n == 3:
return 2
res = 1;
while n > 4:
res *= 3
res %= 1000000007
n -= 3
res *= n
res %= 1000000007
return 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 = 0
while n:
if n & 1:
res += 1
n >>= 1
return 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 0
if n == 0:
return 1
if n == 1:
return x
temp = self.help(x, n//2)
if n % 2 == 1:
return temp * temp * x
else:
return temp * temp
def 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:#终止条件 位数为length
self.res.append(int(''.join(track)))
return
for i in range(10):
store = track.copy()
track.append(str(i))
self.backtrace(count + 1, track, length)
track = store
def 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 head
new_head = ListNode(0)
new_head.next = head
pre = new_head
cur = head
while cur.val != val:
pre = cur
cur = cur.next
pre.next = cur.next
return 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 False
if p[j - 1] == '.':
return True
return 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] = True
for 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 False
return 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 = 0
right = len(nums) - 1
while left<right:
if nums[left]%2:#奇数左指针就一直右移
left += 1
continue
if nums[right]%2 == 0:#偶数右指针就一直左移
right -= 1
continue
nums[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;
}
};
