剑指 Offer 题解
ctrl+f页面查找题目
持续更新
反转链表
头插法
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead == NULL) return NULL;
ListNode* newHead = new ListNode(-1);
while(pHead != NULL) {
ListNode *tmp = pHead->next;
pHead->next = newHead->next;
newHead->next = pHead;
pHead = tmp;
}
return newHead->next;
}
};用两个栈实现队列
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.empty()) {
while(!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
int v = stack2.top();
stack2.pop();
return v;
}
private:
stack<int> stack1;
stack<int> stack2;
};从尾到头打印链表
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> vc;
while(head != NULL) {
vc.push_back(head->val);
head = head->next;
}
reverse(vc.begin(), vc.end());
return vc;
}
};求1+2+3+...+n
class Solution {
public:
int Sum_Solution(int n) {
int sum = n;
bool f = (n>0)&&((sum += Sum_Solution(n-1)));
return sum;
}
};重建二叉树
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
int len = vin.size(), p;
if(len == 0) return NULL;
for (int i = 0; i < len; ++i) {
if(vin[i] == pre[0]) {
p = i;
break;
}
}
vector<int> preL, preR, vinL, vinR;
for (int i = 0; i < p; ++i) {
preL.push_back(pre[i+1]);
vinL.push_back(vin[i]);
}
for (int i = p+1; i < len; ++i) {
preR.push_back(pre[i]);
vinR.push_back(vin[i]);
}
TreeNode* rt = new TreeNode(pre[0]);
rt->left = reConstructBinaryTree(preL, vinL);
rt->right = reConstructBinaryTree(preR, vinR);
return rt;
}
};二叉树的下一个节点
两种情况：1有右子树找右子树的最左子孙；2没有右子树，往上找第一个右父亲。
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode) {
if(pNode->right == NULL) {
TreeLinkNode* tmp = pNode;
while(tmp->next != NULL) {
TreeLinkNode* par = tmp->next;
if(par->left == tmp) return par;
tmp = par;
}
return NULL;
}
else {
TreeLinkNode* tmp = pNode->right;
while(tmp->left != NULL) {
tmp = tmp->left;
}
return tmp;
}
}
};斐波那契数列
class Solution {
public:
int Fibonacci(int n) {
int a = 0, b = 1;
if(n == 0) return 0;
for (int i = 1; i < n; ++i) {
int c = a+b;
a = b;
b = c;
}
return b;
}
};矩形覆盖
class Solution {
public:
int rectCover(int number) {
if(number <= 2) return number;
int a = 1, b = 2;
for (int i = 3; i <= number; ++i) {
int c = a+b;
a = b;
b = c;
}
return b;
}
};变态跳台阶
class Solution {
public:
int jumpFloorII(int number) {
//0--1
//1--1
//2--1+1=2
//3--1+1+2=4
//4--1+1+2+4=8
return 1<<(number-1);
}
};旋转数组的最小数字
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size() == 0) return 0;
int l = 0, r = rotateArray.size()-1, m = l+r >> 1;
while(l < r) {
if(rotateArray[l] < rotateArray[r]) return rotateArray[l];
if(rotateArray[m] < rotateArray[l]) r = m;
else if(rotateArray[m] > rotateArray[l]) l = m+1;
else l++;
m = l+r >> 1;
}
return rotateArray[m];
}
};矩阵中的路径
class Solution {
public:
bool dfs(char *matrix, bool* f, int x, int y, int rows, int cols, char *str, int p) {
if(str[p] == '\0') return true;
if(x < 0 || x >= rows || y < 0 || y >= cols) return false;
if(matrix[x*cols+y] == str[p] && !f[x*cols+y]) {
f[x*cols+y] = true;
if(dfs(matrix, f, x+1, y, rows, cols, str, p+1)
||dfs(matrix, f, x, y+1, rows, cols, str, p+1)
||dfs(matrix, f, x-1, y, rows, cols, str, p+1)
||dfs(matrix, f, x, y-1, rows, cols, str, p+1)
) return true;
f[x*cols+y] = false;
}
return false;
}
bool hasPath(char* matrix, int rows, int cols, char* str)
{
bool* f = new bool[rows*cols];
for (int i = 0; i < rows*cols; ++i) f[i] = false;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if(dfs(matrix, f, i, j, rows, cols, str, 0)) return true;
}
}
return false;
}
};机器人的运动范围
class Solution {
public:
inline int Sum(int x, int y) {
int res = 0;
while(x) res += x%10, x /= 10;
while(y) res += y%10, y /= 10;
return res;
}
void dfs(int x, int y, int rows, int cols, int k, bool* f) {
if(x < 0 || x >= rows || y < 0 || y >= cols) return ;
if(Sum(x, y) > k) return ;
if(f[x*cols+y]) return ;
f[x*cols+y] = true;
dfs(x+1, y, rows, cols, k, f);
dfs(x, y+1, rows, cols, k, f);
dfs(x-1, y, rows, cols, k, f);
dfs(x, y-1, rows, cols, k, f);
}
int movingCount(int threshold, int rows, int cols) {
bool* f = new bool[rows*cols];
for (int i = 0; i < rows*cols; ++i) f[i] = false;
dfs(0, 0, rows, cols, threshold, f);
int cnt = 0;
for (int i = 0; i < rows*cols; ++i) if(f[i]) ++cnt;
return cnt;
}
};二进制中1的个数
class Solution {
public:
int NumberOf1(int n) {
return __builtin_popcount(n);
}
};链表中倒数第k个结点
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
ListNode* p = pListHead;
int n = 0;
while(p!=NULL) {
++n;
p = p->next;
}
if(k > n) return NULL;
k = n-k;
while(pListHead!=NULL && k) {
--k;
pListHead = pListHead->next;
}
return pListHead;
}
};
