剑指Offer
T7 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路参考《王道数据结构》P120
思路：
1. 由先序序列第一个pre[0]在中序序列中找到根节点位置gen
2. 以gen为中心遍历
- 0~gen左子树
- 子中序序列：0~gen-1，放入vin_left[]
- 子先序序列：1~gen放入pre_left[]，+1可以看图，因为头部有根节点
- gen+1~vinlen为右子树
- 子中序序列：gen+1 ~ vinlen-1放入vin_right[]
- 子先序序列：gen+1 ~ vinlen-1放入pre_right[]
3. 由先序序列pre[0]创建根节点
4. 连接左子树，按照左子树子序列递归（pre_left[]和vin_left[]）
5. 连接右子树，按照右子树子序列递归（pre_right[]和vin_right[]）
6. 返回根节点
![1566200739629.png][http://img.ariser.cn/blog/1843651184.png] ![1566200965090.png][http://img.ariser.cn/blog/2916335274.png]
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
int vinlen=vin.size();
if(vinlen==0)
return NULL;
vector<int> pre_left, pre_right, vin_left, vin_right;
//创建根节点，根节点肯定是前序遍历的第一个数
TreeNode* head = new TreeNode(pre[0]);
//找到中序遍历根节点所在位置,存放于变量gen中
int gen=0;
for(int i=0;i<vinlen;i++){
if(vin[i]==pre[0]){
gen=i;
break;
}
}
//对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边
// 左子树
for(int i = 0; i < gen; i++){
vin_left.push_back(vin[i]);
pre_left.push_back(pre[i+1]);//先序第一个为根节点
}
// 右子树
for(int i = gen + 1; i < vinlen; i++){
vin_right.push_back(vin[i]);
pre_right.push_back(pre[i]);
}
//递归，执行上述步骤，区分子树的左、右子子树，直到叶节点
head->left = reConstructBinaryTree(pre_left, vin_left);
head->right = reConstructBinaryTree(pre_right, vin_right);
return head;
}leetcode T106 中序和后续构建二叉树
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int len = postorder.size();
if(len == 0)
return NULL;
// 在中序序列中找到根节点位置
int gen = 0;
for(gen = 0; gen < len, inorder[gen] != postorder[len-1]; gen++);
vector<int> in_left, in_right, pos_left, pos_right;
for(int i = 0; i < gen; i++){
in_left.push_back(inorder[i]);
pos_left.push_back(postorder[i]);
}
for(int i = gen+1; i < len; i++){
in_right.push_back(inorder[i]);
pos_right.push_back(postorder[i-1]);
}
TreeNode* head = new TreeNode(postorder[len-1]);
head->left = buildTree(in_left, pos_left);
head->right = buildTree(in_right, pos_right);
return head;
}T9 用栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型
- 出栈：
- 栈2空：（栈一元素到栈二，再栈二出栈）
- 取栈一的顶
- push到栈2
- pop栈一
- 直到栈一空
- 栈二出栈
- 栈2不空：栈二出栈
- 栈2空：（栈一元素到栈二，再栈二出栈）
- 入栈：栈一push
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 temp = stack2.top();
stack2.pop();
return temp;
}
private:
stack<int> stack1;
stack<int> stack2;
};扩展：两个队列实现栈 https://www.jianshu.com/p/285419bfa880
出栈：
//如果 queueA 的大小不为 0 则循环取出元素
while(queueA.size() > 0){
//被取出的元素
int result = queueA.poll();
// 这里注意我们取出元素后再去判断一次，队列是否为空，如果为空代表是最后一个元素
if(queueA.size() != 0){
queueB.add(result)
}else{
return result;
}
}- 任何时候两个队列总有一个是空的。
- 添加元素总是向非空队列中 add 元素。
- 取出元素的时候总是将元素除队尾最后一个元素外，导入另一空队列中，最后一个元素出队。
T10 斐波那契数列
斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39 循环实现：
long long Fibonacci(unsigned int n){
// if(n == 0)
// return 0;
// if(n == 1)
// return 1;
// return Fibonacci(n-1) + Fibonacci(n - 2);
int result[2] = {0, 1};
if(n < 2){
return result[n];
}
long long fbn_1 = 0;
long long fbn_2 = 1;
long long fbn = 0;
for(int i = 2; i <= n; i++){
fbn = fbn_1 + fbn_2;
fbn_1 = fbn_2;
fbn_2 = fbn;
}
return fbn;
}递归实现：
long long Fibonacci(unsigned int n){
if(n == 0)
return 0;
if(n == 1)
return 1;
return Fibonacci(n-1) + Fibonacci(n - 2);
}
青蛙跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 递归实现：
int jumpFloor(int number) {
if(number < 2)
return number;
if(n >= 2){
return FrogJump(n-1) + FrogJump(n-2);
}
}非递归实现：
int jumpFloor(int number) {
if(number < 2)
return number;
int fbn1 = 0;
int fbn2 = 1;
int fbn = 0;
for(int i = 1; i <= number; i++){
fbn = fbn1 + fbn2;
fbn1 =fbn2;
fbn2 = fbn;
}
return fbn;
}
题目10-3 变态青蛙跳台阶—没做
方块填充
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
class Solution {
public:
int rectCover(int number) {
if(number <= 2){
return number;
}
int method1 = 1;
int method2 = 2;
int method = 0;
for(int i = 3; i <= number; i++){
method = method1 + method2;
method1 = method2;
method2 = method;
}
return method;
}
};也是斐波那契数列，这种题如果要用迭代法，从底层开始分析，则需要更改迭代起始位置的，这里是从3开始
T11 旋转最小的数字
题目描述: 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
分析：二分查找变种，没有具体的值用来比较。那么用中间值和高低位进行比较，看处于递增还是递减序列。
- 处于递增：low上移
- 处于递减：high下移（如果是high-1，则可能会错过最小值，因为找的就是最小值）
- 其余情况：low++缩小范围
- 特殊情况：
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.empty())
return 0;
int low = 0;
int high = rotateArray.size() - 1;
int mid = 0;
while(low < high){
// 子数组是非递减的数组，7890112
if (rotateArray[low] < rotateArray[high])
return rotateArray[low];
mid = low + (high - low) / 2;
if(rotateArray[mid] > rotateArray[low])
low = mid + 1;
else if(rotateArray[mid] < rotateArray[high])
high = mid;
else low++;
}
return rotateArray[low];
}边界值搞死人，如果没有书中的分析以及输出的未通过的测试用例，那么将很难想到特殊情况。
T14 剪绳子
长度为n的绳子，请把绳子剪成m段（m、n都为整数，且都大于1），每段绳子长度记为k[0],k1,…,k[m]。请问k[0]x…xk[n]最大乘积是多少？例如，长度为8时，剪为长度为2、3、3三段，最大乘积为18。
思路：f(2)和 f(3)可以先求得，最优为1、1和1、2。再把递归问题化为剩下的迭代
int maxProductAfterCutting_solution(int length){
if(length < 2)
return 0;
if(length == 2)
return 1;
if(length == 3)
return 2;
int *products = new int[length+1]; // 每个长度下对应最大值（最优长度）
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;
int max = 0;
for(int i = 4; i <= length; i++){ // 从长度4开始进行讨论，记录最大值
max = 0;
for(int j = 0; j <= i/2; j++){ // 对当前长度迭代所有情况，记录
int product = products[j] * products[i-j]; // 裁剪长度乘以剩下长度
if(max < product){
max = product;
}
}
products[i] = max;
}
max = products[length];
delete[]products;
return max;
}贪婪算法的思路：
- 长度大于5时，尽可能多剪长度为3的绳子
- 剩下长度为4时，绳子剪为两个长度为2的绳子
int maxProductAfterCutting_solution(int length){
if(length < 2)
return 0;
if(length == 2)
return 1;
if(length == 3)
return 2;
int timesOf3 = length / 3;
if(length - timesOf3*3 == 1){
timesOf3-=1;
}
int timesOf2 = (length - timesOf3*3)/2;
return (int)(pow(3, timesOf3) * (int)(pow(2, timesOf2)));
}
T15 二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。例如，输入9，二进制位1001，输出2 思路1：输入的n不断右移，和00…01做
与运算&
结果为1：最后一位为1
结果为0：最后一位为0
循环停止条件：移位一直到整数变成0。
注：除2运算等同于右移一位，但是位运算效率比较高
缺点：如果输入负数，移位后最高位会变成1。一直右移会变成全1，死循环。
补充：求-3的十六进制：3的十六进制为0003，3求反之后是C，再加1（补码），成D，所以-3的十六进制就是：FFFD
思路2：把右移n变为左移000..001->000...010，再与n做与运算。
int NumberOf1(int n){
int count = 0;
unsigned int flag = 1;
while(flag){
if(n & flag)
count++;
flag = flag<<1;
}
return count;
}循环次数为整数二进制的位数32。（强制循环32次结束，因为unsigned int最大长度为32）
==最优解：==一个整数减1，在和原整数与运算，会把整数最右边的1变成0。那么一个整数的二进制表示有多少个1，就可以进行这样的操作。
例如：
1100 - 1 = 1011，1100 & 1011 = 10001000 - 1 = 0011，1000 & 0011 = 0000
int Number(int n){
int count = 0;
while(n){
count++;
n = (n - 1)&n;
}
return count;
}拓展：
- 一条语句判断整数是不是2的整数次方。
- 如果是2的整数次方，那么二进制表示有且仅有一位是1，其余都为0。所以if(n & (n - 1) == 0){}
- 两个整数m、n，计算改变m的二进制多少位可以得到n。
1. 求两个数的异或
2. 统计结果中1的位数
- 右移替代除二运算、位与替代求余运算判断技术还是偶数
- 4 & 1 -> 0 偶数
- 5 & 1 -> 1 奇数
T16 数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
直接想到的方法：
double Power(double base, int exponent) { double result = 1.0; for(int i = 1; i <= exponent; i++){ result*=base; } return result; }缺陷：没考虑指数正负、底数为0的情况
考虑边界值
double Power(double base, int exponent) { if(equal(base, 0.0)){ return 0.0; } unsigned int unsignedExponent = (unsigned int)(exponent); if(exponent < 0){ unsignedExponent = (unsigned int)(-exponent); } double result = 1.0; for(int i = 1; i <= unsignedExponent; i++){ result*=base; } if(exponent < 0){ return 1.0/result; } return result; }优解：如果求32次方，知道16次方的基础上，可以直接对16次方进行平方，减少计算次数。类似递归中的斐波那契数列，有如下公式： $$ a^n =\begin{cases} a^{n/2} \times a^{n/2}，n为偶数\ a^{(n-1)/2} \times a^{(n-1)/2}，n为奇数 \end{cases} $$
double PowerWithUnsignedExponent(double base, unsigned int exponent); double Power(double base, int exponent) { g_InvalidInput = false; if (equal(base, 0.0) && exponent < 0) { g_InvalidInput = true; return 0.0; } unsigned int absExponent = (unsigned int) (exponent); if (exponent < 0) absExponent = (unsigned int) (-exponent); double result = PowerWithUnsignedExponent(base, absExponent); if (exponent < 0) result = 1.0 / result; return result; } double PowerWithUnsignedExponent(double base, unsigned int exponent) { if (exponent == 0) return 1; if (exponent == 1) return base; double result = PowerWithUnsignedExponent(base, exponent >> 1); result *= result; if ((exponent & 0x1) == 1) result *= base; return result; }
T18 删除链表节点
> 题目一：O(1)时间内删除链表结点 > 给定单链表头指针和一个结点的指针，定义一个函数在O(1)时间内删除该结点。
常规思想：向后p->next，直到找到该结点，然后调整指针删除，复杂度为O(n)。这样做的原因是需要直到该节点的前一个结点。
void DeleteNode(LinkList** L, LinkList *pToBeDelete){
LinkList *pre = L;
while(pre->next != nullptr){
LinkList *q = pre->next;
// 结点在末尾的情况
if(q ->next == nullptr){
pre->next = nullptr;
delete q;
q = nullptr;
return;
}
if(q == pToBeDelete){
pre->next = q->next;
delete q;
q = nullptr;
return;
}
pre = pre->next;
}
}
高级思想，复杂度为1：后继结点赋值到本身，然后删除后继结点
void DeleteNode(LinkList** L, LinkList *pToBeDelete){
LinkList *q = pToBeDelete->next; // 记录以删除结点
pToBeDelete->data = pToBeDelete->next->data;
pToBeDelete->next = pToBeDelete->next->next;
// 也可用q表示
// pToBeDelete->data = q->data;
// pToBeDelete->next = q->next;
delete q;
q = nullptr;
}
加上几种特殊情况：
- 删除结点位于尾部：遍历求解
- 链表中只有一个结点：删除结点，并设置头结点为
nullptr
完整代码：
void DeleteNode(LinkList** L, LinkList *pToBeDelete){
// 结点在末尾的情况
if(pToBeDelete->next == nullptr){
LinkList *pre = *L;
while(pre->next != pToBeDelete){
pre = pre->next;
}
// 此时pre->next == pToBeDelete
pre->next = nullptr;
// 清理
delete pToBeDelete;
pToBeDelete = nullptr;
}
// 只有一个结点
else if(*L == pToBeDelete){
delete pToBeDelete;
pToBeDelete = nullptr;
*L = nullptr;
} else { // 普通情况
LinkList *q = pToBeDelete->next; // 记录以删除结点
pToBeDelete->data = pToBeDelete->next->data;
pToBeDelete->next = pToBeDelete->next->next;
// 也可用q表示
// pToBeDelete->data = q->data;
// pToBeDelete->next = q->next;
delete q;
q = nullptr;
}
}T18-2 删除链表重复结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
我的思路：
ListNode* deleteDuplicates(ListNode* head) {
if(head == NULL)
return head;
ListNode* p = head;
ListNode* pre = NULL; // 记录p前驱
int flag = 0; // 记录是否发生删除操作
while(p->next != NULL){
pre = p;
ListNode* pn = p->next; // p后继
while(pn->next != NULL){ // 向后遍历
if(pn->val == p->val){ // 后继和p相同
pn = pn->next; //后继前进
flag = 1;
// 删除操作
}else // 直到不相等，跳出遍历
break;
}
if(flag == 1){ // 发生删除操作
flag = 0;
p->val = pn->val;
if(pn->next == NULL){ // pn为末尾结点
if(pn->val == p->val){ // [1, 1]，最后两个结点相同的情况
pre->next = NULL;
break;
}
p->next = NULL;
}
else
p->next = pn->next;
}else
p = p->next; // 无操作，前进
}
return head;
}通不过测试用例[1,1]或[0,1,1,2,2]（末尾有相同数字）
ListNode* deleteDuplication(ListNode* head){
ListNode* p = new ListNode(0);
p->next = head;
head = p;
ListNode *left,*right;
while(p->next){
left = p->next;
right = left;
while(right->next && right->next->val==left->val) // 1
right = right->next;
if(left == right) // 2
p = p->next;
else // 3
p->next =right->next;
}
return head->next;
}
T21 调整数组顺序使奇数在前
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路：参考快速排序
- i++往前走碰到偶数停下来，j = i+1
- 若 a[j]为偶数，j++前进，直到碰到奇数
- a[j]对应的奇数插到a[i]位置，j经过的j-i个偶数依次后移
- 如果j==len-1时还没碰到奇数，证明i和j之间都为偶数了，完成整个移动
class Solution {
public:
void reOrderArray(vector<int> &array) {
int len = array.size();
if(len <= 1){ // 数组空或长度为1
return;
}
int i = 0;
while(i < len){
int j = i + 1;
if(array[i]%2 == 0){ // a[i]为偶数，j前进，直到替换
while(array[j]%2 == 0){ // j为偶数，前进
j++;
if(j==len-1 && array[j]%2==0)// i为偶数，j也为偶数，一直后移到了末尾，证明后面都是偶数
return;
}
// 此时j为奇数
int count = j-i;
int temp = array[i];
array[i] = array[j];
while(count>1){
array[i+count] = array[i+count-1];//数组后移
count--;
}
array[i+1] = temp;
}
i++;
}
}
};T30 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路：
- 借助辅助栈实现
stk_main和stk_assist - 入栈、出栈、取顶时，主栈都正常操作。
- 入栈：入主栈，并判断
- 若辅助栈空：元素入辅助栈
- 若元素小于辅助栈顶：入辅助栈
- 出栈：
- 若两栈顶元素相同（证明栈顶为最小值，否则不会插入），辅助栈出栈。
- 主栈出栈
- 取顶：
- 主栈
stk_main.pop()
- 主栈
- 取最小：直接取辅助栈最小
代码：
stack<int> stk_main, stk_assist;
void push(int value) {
stk_main.push(value);
if(stk_assist.empty() || value < stk_assist.top())
stk_assist.push(value);
}
void pop() {
if(stk_assist.top() == stk_assist.top())
stk_assist.pop();
stk_main.pop();
}
int top() {
return stk_main.top();
}
int min() {
return stk_assist.top();
}T31 栈的压入、弹出序列
>给定 pushV和 popV两个序列，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
输入：pushV = [1,2,3,4,5], popV = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
输入：pushV = [1,2,3,4,5], popV = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。思路：
po、pu为popV、pushV的指针外层循环：指针停留在
popV，比较popV[pop]和栈内元素- 栈空：入栈元素，
pu++ 栈顶 ！= popV[pop]：入栈，pu++- 当
pu == len，即pu移动到了范围外，还在本循环内，return false; 栈顶 == popV[pop]：出栈、po++；- 数组走完，出循环，都比较完，
return true;（因为退出条件是在栈状态和popV决定，绝对严格，有不符合就会退出，所以可以保证最后popV循环完，一定都匹配）
- 栈空：入栈元素，
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
int len = pushV.size();
if(len == 0)
return true;
if(len == 1)
return pushV[0] == popV[0] ? true : false;
stack<int> stk;
int pu = 1, po = 0; // pushV 和 popV的游标
while(po <= len-1){
if(stk.empty()){
stk.push(pushV[pu]);
pu++;
}
while(stk.top() != popV[po]){
// 栈顶不等于带比较元素，且指针移动到了最后
if(pu == len)
return false;
// 不匹配时，入栈
stk.push(pushV[pu]);
pu++;
}
// 匹配，出栈，popV前移
stk.pop();
po++;
}
// popV一直比较到了末尾
return true;
}T32 从上往下打印二叉树（层次遍历）
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路：借助队列，入队根节点。打印当前层后出队，如果左右子树存在则入队。一直循环到队空。
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> arr;
if(!root)
return arr;
queue<TreeNode*> Q;
Q.push(root);
while(!Q.empty()){
TreeNode* q = Q.front();
arr.push_back(q->val);
Q.pop();// 访问完后就出队
if(q->left)
Q.push(q->left);
if(q->right)
Q.push(q->right);
}
return arr;
}按层打印 https://ariser.cn/index.php/archives/400/
T33 判断是否是二叉搜索树的后序序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路：
- 例如 5、7、6、9、11、10、8
- 二叉树后序序列，最后一个数字为根节点值
- 前三个小于8，后三个大于8，分别为左子树和右子树。子序列内也满足，6为根，5小于，7大于。
- 再如 7、4、6、5
- 5为根节点
- 7大于5，可能没有左子树
- 但是右子树上却右4小于5，不满足右子树大于根节点，不符合
- 故找到根节点，再往后遍历
- 都小于根的序列定义为左子树序列
- 再判断右边序列是否都大于根节点
- 递归
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int len = sequence.size();
if(len == 0)
return false;
if(len == 1)
return true;
int gen = sequence[len-1]; // 根节点值
vector<int> left;
vector<int> right;
int i; // 左子树序列，都小于根节点
for(i = 0; i < len, sequence[i] < gen; i++){
// 入左子树序列
left.push_back(sequence[i]);
}
if(i < len-1){// 还有右子树序列时
for(int j = i+1; j < len-i; j++){
// 右子树序列有小与根节点的值
if(sequence[j] < gen)
return false;
// 同时入右子树序列
right.push_back(sequence[j]);
}
}
return VerifySquenceOfBST(left) && VerifySquenceOfBST(right);
}
};上述没通过所有测试用例，边界值情况，也就是递归出口十分混乱。
当子序列至少右两个的时候才进入下一轮递归。
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int len = sequence.size();
if(len <= 0)
return false;
int gen = sequence[len-1]; // 根节点值
vector<int> left;
vector<int> right;
int i; // 左子树序列下标，都小于根节点
for(i = 0; i < len-1, sequence[i] < gen; i++){// len-1是因为末尾是根节点
// 入左子树序列
left.push_back(sequence[i]);
}
if(i < len-1){// 还有右子树序列时
for(int j = i; j < len-1; j++){
// 右子树序列有小与根节点的值
if(sequence[j] < gen)
return false;
// 同时入右子树序列
right.push_back(sequence[j]);
}
}
bool bleft = true, bright = true;
// 根节点大于1时才进入下一轮递归，因为通过上面两轮循环，子序列肯定满足条件
if(left.size() > 1)
bleft = VerifySquenceOfBST(left);
if(right.size() > 1)
bright = VerifySquenceOfBST(right);
return bleft && bright;
}
};T34 二叉树中和为某一值的路径
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
思路：利用先序遍历进行探路
- 访问节点，添加到路径内，计算累加值
- 如果是叶节点
- 累加值符合要求：打印
- 不符合要求，删最后的叶节点，访问 父节点的另外一个孩子，不符合的话继续回溯
- 借助栈来实现（题目给的是vector，pop_back是最后一个元素，可以代替栈）
class Solution {
public:
int num;
vector<int> path;
vector<vector<int> > res;
void finder(TreeNode* root, int expectNumber){
// 空，递归出口
if(!root)
return;
num += root->val;
path.push_back(root->val);
// 符合条件，路径存入
if(!root->left && !root->right && num==expectNumber)
res.push_back(path);
//继续探路
finder(root->left, expectNumber);
finder(root->right, expectNumber);
// 探到叶节点，回溯
path.pop_back();
num-=root->val;
}
vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
finder(root, expectNumber);
return res;
}
};T35 复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路：复制，设置指针，分裂。示意图见P187
分裂的那一步出错了，没有Clone = Clone->next;
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
// 克隆
void CloneNodes(RandomListNode* pHead){
RandomListNode* p = pHead;
while(p){
// 没有判断p->next是因为没有对p->next取值，所以可以操作
RandomListNode* clone = new RandomListNode(0);
clone->label = p->label;
clone->next = p->next;
clone->random = nullptr;
p->next = clone;
p = clone->next;
}
}
// 设置Random指针
void SetRandom(RandomListNode* pHead){
RandomListNode* p = pHead;
while(p){
if(p->random != nullptr)
p->next->random = p->random->next;
// else
// p->next->random = nullptr;
// 上两行没必要，因为本来就是指向空
p = p->next->next;
}
}
// 分裂
RandomListNode* Split(RandomListNode* pHead){
RandomListNode* p = pHead;
// 设置头结点的思想，让游标节点去执行连接工作，最后返回头结点
RandomListNode* clone = nullptr;
RandomListNode* cloneHead = nullptr;
if(p){
clone = pHead->next;
cloneHead = clone;
p->next = clone->next;
p = p->next;
}
while(p){
clone->next = p->next;
clone = clone->next;
p->next = clone->next;
p = p->next;
}
return cloneHead;
}
RandomListNode* Clone(RandomListNode* pHead){
CloneNodes(pHead);
SetRandom(pHead);
return Split(pHead);
}
};分裂操作中，设置头结点思想用过很多次。开始设置头结点和游标节点指向“头结点地址”，让游标节点往后走执行连接操作，操作完成后，返回的头结点即整个链表或树。
T36 二叉搜索树和双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：思路借鉴二叉树的中序线索化（二叉排序树中序序列为有序）
- 线索化函数
helper- 左子树线索化
- 进行连接
p->left指向prepre不为空时，指向pp地址到pre以便下一次递归- 右子树线索化
- 主函数调用递归函数
- 返回最左节点（调用线索化函数后直接返回并不是完整的序列）
- 需要注意的是pre必须定义为应用类型，不然下次递归并不会和上次递归有连接
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void Helper(TreeNode* node, TreeNode* &pre){
if(!node)
return nullptr;
// 左子树线索化
Helper(node->left, pre);
// 线索化过程
node->left = pre;
if(pre)
pre->right = node;
pre = node;
Helper(p->right, pre);
}
TreeNode* Convert(TreeNode* pRootOfTree){
if(!pRootOfTree)
return nullptr;
// 第一个pre肯定为空
TreeNode* pre = nullptr;
Helper(pRootOfTree, pre);
// 找到最左节点
TreeNode* list = pRootOfTree;
while(list->left)
list = list->left;
return list;
}
}T39 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路1：评论区看到的一种“投票算法”，即票数过一半者当选。
- 设置票数
ticket和 当选者majority，遍历数组过程进行演变A[i]等于majority，票数加1A[i]不等于majority，票数减1- 当票数为0时，更换当选者
- 如果有到最后票数大于1，那么当选者可能为要求的数字
- 可以手动演变，只要数字大于总数的一半，最后当选者肯定会留下。
- 再遍历一遍，统计数目，大于
len/2即可认为符合要求，否则输出0
代码：其中最后一个 for(int number : numbers){}可以当作foreach用
int MoreThanHalfNum_Solution(vector<int> numbers) {
int len = numbers.size();
if(len == 0)
return 0;
int ticket = 1;
int majority = numbers[0];
for(int i = 1; i < len; i++){
if(numbers[i] == majority)
ticket++;
else
ticket--;
if(ticket == 0){
majority = numbers[i];
ticket = 1;
}
}
ticket = 0;
for(int number : numbers){
if(number == majority)
ticket++;
}
return ticket > len / 2 ? majority : 0;
}思路2：利用Map，空间换时间。注意导入头文件
#include <map>
int MoreThanHalfNum_Solution(vector<int> numbers) {
int n = numbers.size();
map<int, int> m;
int count;
for(int i = 0; i < m; i++){
count = m[number[i]]++;
if(count > n/2)
return number[i];
}
return 0;
}T40 最小的K个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路1：快排思想，对原数组进行调整
- 选取
A[0]作枢纽值index，调整 - 当枢纽
index不为k-1时，继续调整（数组下标0开始）- 若
index大于k-1，高指针下移，调整 - 若
index小于k-1，低指针上移，调整
- 若
- 调整后截取
0到k，即为最后结果
代码：
class Solution {
public:
int Partition(vector<int>& A, int low, int high){
int pivot = A[low];
while(low < high){
while (low < high && A[high] >= pivot)
high--;
A[low] = A[high];
while(low < high && A[low] <= pivot)
low++;
A[high] = A[low];
}
A[low] = pivot;
return low;
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
int len = input.size();
if(len == 0 || k > len || k <= 0)
return vector<int>();
if(len == k)
return input;
int low = 0;
int high = len - 1;
int pivot = Partition(input, low , high);
while(pivot != k-1){
if(pivot > k-1){
high = pivot - 1;
pivot = Partition(input, low, high);
}else{
low = pivot + 1;
pivot = Partition(input, low, high);
}
}
vector<int> res(input.begin(), input.begin() + k);
return res;
}
};快排应该信手拈来
思路2：全排序，直接用sort()，再输出前 k个
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if(input.empty() || k > input.size())
return vector<int>();
sort(input.begin(), input.end());
vector<int> res(input.begin(), input.begin()+k);
return res;
}T41 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
思路：
- 借助两个堆，大根堆max和小根堆min
- 大根堆存放中位数左边的数字
- 小根堆存放中位数右边的数字
- 需要满足：大根堆堆顶（最大） <= 小根堆堆顶（最小）
- 存入的时候维护堆，取出的时候要么是
两堆顶平均数要么是大根堆顶
class Solution {
priority_queue<int, vector<int>, less<int> > max;
priority_queue<int, vector<int>, greater<int> > min;
public:
void Insert(int num){
if(max.empty() || num <= max.top())
max.push(num);
else
min.push(num);
// 控制max.size()大于min.size()且不超过2
// 原因是，max堆内是从 最小值 增长到 中位数，两堆堆相等时取平均值，相差1时取大堆顶
if(max.size() - min.size() == 2){
// max堆顶到min
min.push(max.top());
max.pop();
}
if(min.size() - max.size() == 1){
// min堆顶到max
max.push(min.top());
min.pop();
}
}
double GetMedian(){
// 两堆堆相等时取平均值，相差1时取大堆顶
return max.size() == min.size() ? (max.top() + (min.top() - max.top())/2.0) : max.top();
}
};T42 连续子数组最大和
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
思路1：累加，更新最大值
sum大于max，更新maxsum小于max，max不变- 记得初始化的时候，
max应该设置为A[0]或最小值0x80000000。若按照平常设置0，全负的时候会把0当做最大
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
if(array.size() == 1)
return array[0];
// max必须从第一值取起，不然会导致全负的时候，输出0
int max = array[0];
int sum = 0;
for(int i = 0; i < array.size(); i++){
if(sum < 0)
sum = array[i];
else
sum += array[i];
if(sum > max)
max = sum;
}
return max;
}
};思路2：动态规划，其实代码和上面的一模一样，思维模式的变化：从第一个累加和不为负数开始，进行更新最大值。
T43 1~n整数中1出现的次数
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
aab 、”alouzxilkaxkufsu”（leetcode有栈溢出情况）
思路：快慢指针，慢指针停留，快指针往前，并往map里面记录字符的次数（只要没重复的就往前）。若出现重复则低指针到高指针位置，清空map。整个过程更新最大值。
维护一个
map{a, 1}，数字代表出现次数；max为最大长度，t为每轮的长度快慢指针
h、l,快指针往前，用s[h]的值在map里面查- 没有重复就前进，在map中标记
s[h]，更新max和t - 有重复，慢指针
l移到h处，h前进，更新max和t；清空map
- 没有重复就前进，在map中标记
奈何长度过长时，会出现缓冲区溢出的情况，本地测试通过。
int lengthOfLongestSubstring(string s) {
if(s.length() == 0)
return 0;
map<int, int> _map;
int low = 0;
int high = 0;
int t = 0;
int max = 0;
while(low < s.size() && high < s.size()){
if(_map[s[high]] == 0){
if(s[high] == s[high -1]) // aab的情况
t = 1;
else
t++;
max = t > max ? t : max;
_map[s[high]] = 1;
high++;
} else {
max = t > max ? t : max;
t = (s[high] == s[high -1]) ? 1 : 0; // aab的情况
low = high;
high++;
_map.clear();
}
}
return max;
}最后借鉴了评论区的思路，不用记录每一轮的 t，用高低指针之差算长度。后面调试过程发现应该是由_map.clear();引起的，还是循环的过程中 _map[s[low]]--。
int lengthOfLongestSubstring(string s) {
if(s.length() == 0)
return 0;
map<int, int> _map;
int low = 0;
int high = 0;
int max = 0;
while(high < s.size()){
if(_map[s[high]] == 0){
_map[s[high]]++;
high++;
max = max > (high - low) ? max : (high - low);
} else {
max = max > (high - low) ? max : (high - low);
_map[s[low]]--;
low++;
}
}
return max;
}T56 合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
特殊的用例：
[3,4][1,0] (后面的会插到前面或中间，不是简单的末尾合并)
[1,4][2,3] (后面的会并入前一个里面)
思路：创建res，每次往里面插入一个新的区间，然后和res尾部的合并（最后一点有优化）
[1][4] [4][5]首先就是最简单的并入res[len-2][1] = res[len-1][1];
[1,4][2,3]后面的直接并入前一个res[len-2] = res[len-1];
提交了一次后GG，出错的用例如下：
[3,4][1,0](后面的会插到前面或中间，不是简单的末尾合并)
于是思考了一下如何插入到中间，巴拉巴拉半天想想，觉得太复杂了！看了下评论区，看到了先排序的方法，恍然大悟。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size() < 2)
return intervals;
// 每次往res内添加一组区间，动态维护res，而不在原数组上维护。
vector<vector<int>> res;
// 必须先排序，否则res尾部插入[0,1]这种 “会在中间合并的数组”，会异常麻烦
sort(intervals.begin(), intervals.end());
res.push_back(intervals[0]);
// 每次往res尾部推入一个区间，有合并就改变末尾推出一个
for (int i = 1; i < intervals.size(); i++) { // [][]
res.push_back(intervals[i]);
int len = res.size();
// 合并操作
if(res[len-1][1] <= res[len-2][1]) // [1,4][2,3]，只比较后面因为前面已经排序排好了
res.pop_back();
else
if(res[len-1][0] <= res[len-2][1]){
if(res[len-1][0] <= res[len-2][0]){// [2,3][2,4]
res[len-2] = res[len-1];// 倒数第二替换为倒数第一
res.pop_back();
}
else{ // [1,3][2,4] 正常k合并
res[len-2][1] = res[len-1][1];
res.pop_back();
}
}
}
return res;
}
};数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路1：利用Map存储次数，最后遍历map拿出次数为1的数字
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
map<int, int> _map;
for (int i = 0; i < data.size(); i++) {
_map[data[i]]++;
}
vector<int> nums;
map<int, int>::iterator iter = _map.begin();
while (iter != _map.end()) {
if(iter->second == 1)
nums.push_back(iter->first);
iter++;
}
*num1 = nums[0];
*num2 = nums[1];
}
};思路2：位运算的性质
- 数字和自己本身异或为0（相同为0，不同为1）（
&相同为1不同为0，不进位） - 0和任何数字异或为这个数字
所以先将所有数字异或可以得到最后两个数字异或的结果，再从低往高找差异位，再进行分组。
1， 1，2，2，3，4，5，5
001，001，010，010，011，100，101，101
全部异或得到：111，最低位为第1（即 两个数从此出现差异）。3和4分别最低位为1和0，正好分到了xx1和xx0两个组，分组，组内再异或即可得到3 和 4。
class Solution {
public:
// 为1的最高位
// 右移的过程中判断最低位
int findFirst1(int bitResult){
int index = 0;
while(index < 32 && ((bitResult & 1) == 0)){
bitResult >>= 1;
index++;
}
return index;
}
// 某位是否为1
bool isBit1(int target, int index){
return ((target >> index)&1) == 1;
}
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int bitResult = 0;
for(int i = 0; i < data.size(); i++){
bitResult ^= data[i];
}
// 得到 num1 和 num2 异或的结果，求最高位1的位置1001为4
int index = findFirst1(bitResult);
// 分组，最高位为1和不为1的分组，异或之后的结果
for(int i = 0; i < data.size(); i++){
if(isBit1(data[i], index))
*num1 ^= data[i];
else
*num2 ^= data[i];
}
}
};把二叉树打印成多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路：借助队列，每次打印完当前行，就把他们的子节点入队。队不空的时候一直做判断
由于每一行分开打印，所以每次外层循环时，算作打印一行，要记录队列中结点个数，然后依次存入数组中后再存入总结果。
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > res;
if(!pRoot)
return res;
queue<TreeNode*> que;
que.push(pRoot);
while (!que.empty()) {
int low = 0, high = que.size();
vector<int> row;
while (low++ < high) {
TreeNode* q = que.front();
que.pop();
row.push_back(q->val);
if(q->left)
que.push(q->left);
if(q->right)
que.push(q->right);
}
res.push_back(row);
}
return res;
}
};T50 第一个只出现一次的字符（哈希）
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。
> 如果当前字符流没有存在出现一次的字符，返回#字符。 > ``` 思路：同样是哈希，只是可以直接用数组代替哈希，映射函数即为字符的值 ```c class Solution { public: string s; char hash[256] = {0}; //Insert one char from stringstream void Insert(char ch){ s+=ch; hash[ch]++; } //return the first appearence once char in current stringstream char FirstAppearingOnce(){ int i = 0; while(i < s.size()){ if(hash[s[i]] == 1) return s[i]; i++; } return '#'; } };
T51 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述：
题目保证输入的数组中没有的相同的数字数据范围： 对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5
思路1：归并排序思想，其实就是调整逆序对的过程。可以描述为：分组到最小（两个一组），然后调整逆序对。合并成四个再调整逆序对直到合并成原始数组。所以在这个过程中的调整次数即逆序对的个数。O(nlog2n)
先默写一遍归并排序：
// 归并过程
void merge(int A[], int low, int mid, int high){
int help[high - low + 1]; // 辅助数组(保护现场，以便后面继续，整个做完后再赋给原数组对应的部分)
int i = 0;
int lowIndex = low;
int highIndex = mid + 1;
while(lowIndex <= mid && highIndex <= high){
if(A[lowIndex] < A[highIndex])
help[i++] = A[lowIndex++];
else
help[i++] = A[highIndex++];
}
//左边和右边肯定有一边到头了，不可能同时，因为每次只移动一边
while(lowIndex <= mid)
help[i++] = A[lowIndex++];
while(highIndex <= high)
help[i++] = A[highIndex++];
//将排好序的辅助数组赋值给原始数组，不需要返回值
for(int i = 0; i < high-low+1; i++){
A[low+i] = help[i];
}
}
//递归
void mergeSort(int A[], int low, int high){
if(low == high)
return;
int mid = low + (high-low)/2;
// 左部分归并排序
mergeSort(A, low, mid);
// 右部分归并排序
mergeSort(A, mid+1, high);
// 左右部分归并
merge(A, low, mid, high);
}
//重写, 归并整个数组
void mergeSort(int A[], int n){
if(A == NULL || n < 2)
return;
mergeSort(A, 0, n-1);
}
int main(){
int n;
while(cin >> n){
int arr[n];
for(int i = 0; i < n; i++) cin >> arr[i];
mergeSort(arr, n);
for(int i = 0; i < n; i++){
cout << arr[i] << " ";
}
cout << endl;
}
return 0;
} Vector版：
#include <iostream>
#include <stdio.h>
#include <vector>
#include <map>
#include <stack>
#include <queue>
using namespace std;
void merge(vector<int>& A, int low, int mid, int high){
int i = 0;
int help[high - low + 1];
int lowIndex = low;
int highIndex = mid + 1;
while (lowIndex <= mid && highIndex <= high) {
if(A[lowIndex] <= A[highIndex])
help[i++] = A[lowIndex++];
else
help[i++] = A[highIndex++];
}
while (lowIndex <= mid)
help[i++] = A[lowIndex++];
while (highIndex <= high)
help[i++] = A[highIndex++];
for (int i = 0; i < high-low+1; i++) {
A[low+i] = help[i];
}
}
void mergeSort(vector<int>& A, int low, int high){
if(low == high)
return;
int mid = low + (high-low)/2;
printf("%d\n", A[mid]);
mergeSort(A, low, mid);
mergeSort(A, mid+1, high);
merge(A, low, mid, high);
}
void mergeSort(vector<int>& A){
int n = A.size();
if(A.empty() || n < 2)
return;
mergeSort(A, 0, n-1);
}
void PrintArr(vector<int> arr){
for (int i = 0; i < arr.size(); i++) {
if(i == arr.size()-1)
cout<<arr[i]<<endl;
else
cout<<arr[i]<<", ";
}
}
void PrintArr(int arr[], int n){
for (int i = 0; i < n; i++) {
if(i == n-1)
cout<<arr[i]<<endl;
else
cout<<arr[i]<<", ";
}
}
int main() {
vector<int> A = {6, -3, -2, 7, -15, 1, 2, 2};
mergeSort(A);
PrintArr(A);
return 0;
}// 未完待续
思路2：树状数组
T65 不用加减乘除实现加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
思路：以 87 + 15 = 102 为例
- 正常加法拆分
- 87 = 1010111(2)，15 = 1111(2) 得到 102 = 1100110(2)
- 不进位加法 1011000
- 产生进位后的结果 0011100（作减法或者自己推导）
- 使用二进制实现
- 不进位的加法，显然就是
异或运算 - 关键是求进位后的结果
- 将上述两个结果相加，即可得到最终结果
- 求
进位后结果可以描述为：- 除了1加1都不会产生进位，可以想象成两个数先位与再左移一位（当前位置的1左移到进位的位置）。
- 只有当两个数都为1的时候，位于结果为1，其余为0
- 第一轮
- 1010111 ^ 1111 = 1011000
- (1010111 & 1111) << 1 = 0111 << 1 = 1110
- 第二轮
- 1011000 ^ 1110 = 1010110
- (1011000 & 1110)<<1 = 10000
- 第三轮
- 1010110 ^ 10000 = 1000110
- (1010110 & 10000)<<1 = 100000
- 第四轮
- 1000110 ^ 100000 = 1100110
- (1000110 & 100000)<<1 = 0000
- 跳出循环，结果为 1100110 + 0000 = 1100110
- 不进位的加法，显然就是
代码：
int Add(int num1, num2){
int sum, carry;
do{
sum = num1 ^ num2;
carry = (num1 & num2)<<1;
num1 = sum;
num2 = carry;
}while(num2 != 0);
return num2;
}