剑指Offer 算法练习
03.数组中重复的数字
IMG_AF84035C576B-1.jpeg
class Solution {
public:
int findRepeatNumber(vector<int> nums) {
unorder_map<int,bool> map;
for (int num: nums) {
if (map[num]) {
return num;
} else {
map[num] = true;
}
return -1;
}
}
};
04.二维数组的查找
IMG_CF4977BFE491-1.jpeg
class Solution {
public:
bool find(int target,vector<vector<int>> array) {
if(array.empty() || array[0].empty())
return false;
int i = 0;
int j = array[0].size() - 1;
while(i <= array.size() - 1 && j >=0) {
if (array[i][j] == target) {
return true;
}
if (array[i][j] > target) {
j--;
} else {
I++;
}
}
return false;
}
};
05.替换空格
IMG_478AA4EAC0CC-1.jpeg
class Solution {
public:
void replaceSpace(char *str, int length) {
int count = 0;
for (int i = 0; i < length; i ++) {
if (str[i] == ' ') {
count++;
}
}
for(int i = length - 1; i >= 0; i--) {
if (str[i] != ' ') {
str[i + count*2] = str[I];
}
if (str[i] == ' ') {
count--;
str[i + count*2] = '%';
str[i + count*2 + 1] = '2';
str[i + count*2 + 2] = '0';
}
}
}
}
06.从尾到头打印链表
IMG_221848074178-1.jpeg
class Solution {
public:
vector<int> reversePrint(ListNode *head) {
ListNode *p = head;
stack<int> stk;
vector<int> result;
while(p != NULL) {
stk.push(p->val);
p = p->next;
}
int len = stk.size();
for(int i = 0; i < len; i++) {
result.push_back(stk.top());
stk.pop();
}
return result;
}
}
07.重建二叉树
image.png
class Solution {
public:
unordered_map<int,int> pos ; // 记录中序结点的位置
TreeNode* buildTree(vector<int> pre, vector<int> in) {
int n = pre.size();
for(int i = 0; i < n; i++) {
pos[v[i]] = I;
}
return dfs(pre,v,0,n-1,0,n-1);
}
TreeNode* dfs(vector<int> pre, vector<int> in, int pl, int pr, int vl, int vr) {
if (pl > pr) return NULL;
//找根节点，pre[pl]
TreeNode* root = new TreeNode(pre[pl]);
//左子树的长度k
int k = pos[pre[pl]] - rl;
root-> left = dfs(pre,in,pl+1,pl+k,vl,vl+k-1);
root-> right = dfs(pre,in,pl+k+1,pr,vl+k+1,vr);
return root;
}
}
08.二叉树的下一个节点
image.png
分析：
A->C->B->D->F->H->E->M->G
若给定H,则下一个节点是E
若给定E,则下一个节点是M
若给定D,则下一个节点是F
class Solution {
public:
TreeNode* GetNext(TreeNode* p) {
//若右子树存在，返回右子树最左边的结点
if(p->right) {
p = p->right;
while(p->left) {
p = p->left;
}
return p;
}
// 若右子树不存在，只有左子树，则需要找到父节点的根节点
while(p->next) {
if(p->next->left == p) {
return p->next;
}
p = p->next;
}
return NULL;
}
}
09.用两个栈实现队列
image.png
class Solution {
public:
void push(int node) {
stk1.push(node);
}
int pop() {
if(!stk2.size()) {
while(stk1.size()) {
stk2.push(stk1.pop());
}
if(stk2.size()) {
return stk2.pop();
} else {
return -1;
}
}
}
private:
stack<int> stk1,stk2;
}
10.斐波那契数列
image.png
class Solution {
public:
int fibonacci(int n) {
if(n < 2) {
return n;
}
int f1 = 0;
int f2 = 1;
for(i = 2;i <= n; i++) {
int temp = f1 + f2;
f1 = f2;
f2 = temp;
}
return f2;
}
}
11. 旋转数组的最小数字
image.png
class Solution {
public:
int rotateArray(vector<int> nums) {
int l = 0;
int r = nums.size() - 1;
while(l < r) {
int mid = (l + r) / 2; //[0,mid],[mid+1,r]
if(nums[mid] > nums[r]) {
l = mid + 1;
} else if(nums[mid] < nums[r]) {
r = mid;
} else {
r--;
}
}
return l;
}
}
12. 矩阵中的路径
image.png
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int rows = board.size();
int cols = board[0].size();
for(int i = 0; i < rows ; i++) {
for(int j = 0; j < cols; j++) {
if(dfs(board,word,i,j,0)) {
return true;
}
}
}
return false;
}
private:
bool dfs(vector<vector<char>> &board, string word, int i, int j, int k) {
int rows = board.size();
int cols = board[0].size();
if(i < 0 || i >= rows || j < 0 || j >= cols || word[k] != board[i][j]) {
return false;
}
if(k == word.size() - 1)
return true;
board[i][j] = '\0';
bool res = dfs(board,word,i+1,j,k+1) || dfs(board,word,i-1,j,k+1) || dfs(board,word,i,j+1,k+1) || dfs(board,word,i,j-1,k+1);
board[i][j] = word[k];
return res;
}
}
13.机器人的运动范围
image.png
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>> visited(m,vector<bool>(n));
return dfs(0,0,m,n,k,visited);
}
private:
int dfs(int i,int j,int m,int n,int k,vector<vector<bool>>& visited) {
if(i < 0 || i >= m|| j < 0 || j >= n || digitalSum(i) + digitalSum(j) > k || visited[i][j]) {
return false;
}
visited[i][j] = true;
return 1 + dfs(i+1,j,m,n,k,visited) + dfs(i-1,j,m,n,k,visited) + dfs(i,j+1,m,n,k,visited) +dfs(i,j-1,m,n,k,visited);
}
int digitalSum(int i) {
int sum = 0;
while(i) {
sum += i % 10;
i = i / 10;
}
return sum;
}
}
14. 剪绳子
image.png
class Solution {
int cuttingRope(int n) {
if(n == 1) {
return 0;
}
if(n == 2) {
return 1;
}
if(n == 3) {
return 2;
}
int dp[n + 1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
int sum = 1;
for(int i = 4; i <= n; i++) {
for(int j = 1; j <= i / 2; j++) {
int tmp = dp[j] * dp[i - j];
sum = sum <= tmp ? tmp : sum;
dp[i] = sum;
}
}
return dp[n];
}
}
15.二进制中1 的个数
image.png
class Solution {
public:
int numberOf1(int n) {
int res = 0;
while(n) {
n = n&(n-1);
res++;
}
return res;
}
}
数值的整数次方
image.png
class Solution {
public:
double exp(double base, int e) {
double res = 1;
for(int i = 0; i < abs(e); i++) {
res *= base;
}
if(e < 0) {
res = 1 / res;
return res;
}
}
17. 打印从1到最大的n位数
image.png
class Solution {
vector<int> printNum(int n) {
int res = 1;
vector<int> resV;
for(int i = 0; i < n;i++) {
res *= 10;
}
for(int i = 0; i < res;i++)
resV.push_back(i);
return resV;
}
}
18.删除链表的节点
image.png
class Solution{
public:
ListNode* deleteNode(ListNode* head,int val) {
ListNode* dummy = new ListNode(-1);
dummy.next = head;
ListNode *cur = dummy;
while(cur->next) {
if(cur->next->val = val) {
cur->next = cur->next->next;
break;
}
cur = cur->next;
}
return dummy->next;
}
}
