21、树的子结构
22、树的镜像
23、包含min函数的栈
24、栈的压入、弹出序列
25、字符串的排列
26、数组中出现次数超过一半的数字
27、最小的k个数
28、连续子数组的最大和
29、求1出现的次数
30、把数组排成最小的数
21、树的子结构
题目：输入两棵二叉树A和B，判断B是不是A的子结构。
要查找树A中是否存在和树B结构一样的子树，可以分成两步：
- 第一步在树A中找到和B的根节点的值一样的结点R；
- 第二步再判断树A中以R为根结点的子树是不是包含和树B一样的结构。
第一步在树A中查找与根结点的值一样的结点，这实际上就是树的遍历。递归调用HasSubTree遍历二叉树A。如果发现某一结点的值和树B的头结点的值相同，则调用DoesTreeHavaTree2，做第二步判断。
注意在使用指针的时候一定要注意边界条件，即检查空指针。当树A或树B为空的时候，定义相应的输出。如果没有检查并做相应的处理，程序非常容易崩溃。
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
};
bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
bool result = false;
if(pRoot1 != NULL && pRoot2 != NULL)
{
if(pRoot1->m_nValue == pRoot2->m_nValue)
result = DoesTree1HaveTree2(pRoot1, pRoot2);
if(!result)
result = HasSubtree(pRoot1->m_pLeft, pRoot2);
if(!result)
result = HasSubtree(pRoot1->m_pRight, pRoot2);
}
return result;
}
bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
if(pRoot2 == NULL)
return true;
if(pRoot1 == NULL)
return false;
if(pRoot1->m_nValue != pRoot2->m_nValue)
return false;
return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
}
22、树的镜像
题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。
思路：对于树根，不变，交换左右两个子树，然后在对左右子树作为树根进行递归交换他们的子树。注意处理子树为空的情况。
void Mirror(TreeNode *pRoot) {
if(pRoot==NULL){
return;
}
TreeNode *tmp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = tmp;
Mirror(pRoot->left);
Mirror(pRoot->right);
}
23、包含min函数的栈
题目： 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小素的min 函数。在该栈中，调用min、push 及pop的时间复杂度都是0(1)
思路：在存入栈的时候，计算最小值，将最小值找个地方存一下。要用一个辅助的栈用来保存每次push进来后整个栈的最小值。当pop的时候，也将最小值栈pop一下，这样就行了，而且时间复杂度也能满足题目中的O(1)的要求。就是push新元素的时候，都跟最小值栈的栈顶比较小，如果比栈顶大，则不做任何动作，如果小，则在最小值栈中push新的最小值；pop的时候，将pop的元素跟最小值栈的栈顶比较下，如果等于栈顶，则将最小值栈也pop一下，如果大于的话则无视
class Solution {
public:
stack<int> stack1,stack2;
void push(int value) {
stack1.push(value);
if(stack2.empty())
stack2.push(value);
else if(value<=stack2.top())
{
stack2.push(value);
}
}
void pop() {
if(stack1.top()==stack2.top())
stack2.pop();
stack1.pop();
}
int top() {
return stack1.top();
}
int min() {
return stack2.top();
}
};
24、栈的压入、弹出序列
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路：定义一个vector模拟栈的操作，依次将pushV的元素压入栈中，每次压入都判断这个元素是否和popV相同，如果相同，则将这个元素弹出。直到所有pushV的元素都被压入。 则如果最终vector栈是空的，说明popV是一个弹出序列，否则不是弹出序列。
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
if(pushV.size() == 0) return false;
vector<int> stack;
for(int i = 0,j = 0 ;i < pushV.size();){
stack.push_back(pushV[i++]);
while(j < popV.size() && stack.back() == popV[j]){
stack.pop_back();
j++;
}
}
return stack.empty();
}
};
25、字符串的排列
题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc。则打印出由字符a、b、c 所能排列出来的所有字符串abc、acb、bac 、bca、cab 和cba 。
#include<stdio.h>
#include<string>
//交换两个字符
void Swap(char *a ,char *b)
{
char temp = *a;
*a = *b;
*b = temp;
}
//递归全排列，start 为全排列开始的下标， length 为str数组的长度
void AllRange(char* str,int start,int length)
{
if(start == length-1)
{
printf("%s\n",str);
}
else
{
for(int i=start;i<length;i++)
{ //从下标为start的数开始，分别与它后面的数字交换
Swap(&str[start],&str[i]);
AllRange(str,start+1,length);
Swap(&str[start],&str[i]);
}
}
}
void Permutation(char* str)
{
if(str == NULL)
return;
AllRange(str,0,strlen(str));
}
int main()
{
char str[] = "abc";
Permutation(str);
return 0;
}
26、数组中出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,5,4,2}。由于数字2在数组中出现了5词，超过数组长度的一半，因此输出2.
思路：当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1,；如果下一个数字和我们之前保存的数字不同，则次数减1,。如果次数为0，我们需要保存下一个数字，并把数字设为1,。由于我们要找的数字出现的次数比其他所有数字出现的次数还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。
int HalfData(int arr[],int len)
{
int b,count;
for(int i=0;i<len;i++)
{
if(i==0)
{
b= arr[0];
count = 1;
}
else
{
if(arr[i]==b)
count++;
else if(arr[i] != b && count>0)
count--;
else
{ // 到这一步说明前面i个里面被i/2抵消了
b = arr[i];
count = 1;
}
}
}
return b;
}
27、最小的k个数
题目：例如输入4 、5 、1、6、2、7、3 、8 这8 个数字，则最小的4 个数字是1 、2、3 、4
思路：参见《堆排序》，可以用大小为 k 的大根堆来存储最小的 k 个数。大根堆的堆顶元素就是最小 k 个数中最大的一个。每次新考虑一个数 X：
- 如果 X 比堆顶的元素 Y 大，则不需要改变原来的堆，因为这个元素比最小的 k 个数都大。
- 如果 X 比堆顶元素 Y 小，那么用 X 替换堆顶的元素 Y。在 X 替换堆顶元素 Y 之后，大根堆的结构可能被破坏，需要进行向下调整。调整过程的时间复杂度是 $O(log_2k)$ 。
遍历完成以后，数组的前 k 个数就是最小的 k 个数，但是它们并非有序，而是以堆的形式存在。
void AdjustDown(int A[], int i, int len)
{
int temp = A[i]; // 暂存A[i]
for(int largest=2*i+1; largest<len; largest=2*largest+1)
{
if(largest!=len-1 && A[largest+1]>A[largest])
++largest; // 如果右子结点大
if(temp < A[largest])
{
A[i] = A[largest];
i = largest; // 记录交换后的位置
}
else
break;
}
A[i] = temp; // 被筛选结点的值放入最终位置
}
/* 建堆 */
void BuildMaxHeap(int A[], int len)
{
for(int i=len/2-1; i>=0; --i) // 从i=n/2-1到0，反复调整堆
AdjustDown(A, i, len);
}
/* 维护 A[0...k-1] 这个大根堆 */
void topK(int A[], int n, int k)
{
BuildMaxHeap(A, k); // 先用前面的k个数建大根堆
for(int i=k; i<n; ++i)
{
if(A[i] < A[0]) // 如果小于堆顶元素，替换之
{
int tmp = A[0];
A[0] = A[i];
A[i] = tmp;
AdjustDown(A, 0, k); // 向下调整
}
}
for (int j = 0; j < n; ++j) {
printf("%d",A[j]);
}
}
28、连续子数组的最大和
题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为{1, -2, 3, 10, -4, 7, 2, -5}，和最大的子数组为｛3, 10, -4, 7, 2}。因此输出为该子数组的和18 。
思路：思路：从左往右遍历，将当前相加的结果存入到数字current中，将当前最大的结果记录到result 中，如果current=0，则重新归0计算，从下一个数开始求和，当current>result时，令result=current。当遍历完数组时，最后result中的数就是连续子数组的最大值。
int FindGreatestSumOfSubArray(vector<int> array) {
int result=array[0];
int current=0;
int i=0;
while(i<array.size())
{
current=current+array[i];
if(current>result)
result=current;
if(current<0)
current=0;
i++;
}
return result;
}
29、求1出现的次数
题目：输入一个整数n求从1到n这n个整数的十进制表示中1出现的次数。
思路：我们通过逐位判断的方式，以百位数字为例：
- 如果百位数字是 0 则百位出现 1 的次数，只由更高位决定： 如 12045：百位是 1 的次数 100~199 1100~1199 2100~2199 。。。 11,100~11,199 每一行含有 100 个，共 12 行；故百位出现 1 的次数 更高位数字(12) * 当前位数(100)
- 如果百位数字是 1 则百位出现 1 的次数，不仅由更高位决定，还和当前位的低位有关 如 12145：百位是 1 的次数，除了上述高位*决定的 12100 次 低位部分 12,100 ~ 12,145 百位出现 1 的次数等于低位数字(45) + 1
- 如果百位数字大于 1 (2~9)，则百位出现 1 的次数，只由更高位决定 12345 : 百位是 1 的次数 100~199 1100~1199 2100~2199 。。。 11,100~11,199 12,100~12,199 每一行含有 100 个，共 13 行；故百位出现 1 的次数 更高位数字加一(12+1) * 当前位数(100)
上述算法的时间复杂度：O(logL)O(logL)，L 为 n 的10进制的位数
#include <iostream>
using namespace std;
int Counts1OfN(int n) {
int counts = 0;
int base = 1;
int low = 0; //低位数字
int cur = 0; //当前位
int high = 0; //高位数字
while (n/base > 0) {
//如12345：base = 100, cur = 3, low = 45, hight 12
low = n % base;
cur = (n / base) % 10;
high = n / (base*10);
switch(cur) {
case 0:
counts += high*base;
break;
case 1:
counts += high*base + (low+1);
break;
default:
counts += (high+1)*base;
}
base *= 10;
}
return counts;
}
int main()
{
int nums[] = {4,13,33,103,113,123,9999,33342124};
for (int i = 0; i < sizeof(nums)/sizeof(nums[0]); i++) {
cout << "0 ~ " << nums[i] << " 包含 1 的个数：" << Counts1OfN(nums[i]) << endl;
}
}
30、把数组排成最小的数
题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3， 32, 321}，则扫描输出这3 个数字能排成的最小数字321323。
思路：比较的方法是两个数a、b,若ab>ba,就规定a>b,否则a<b;用这种方法把数组按从小到大的顺序排列并保存到字符串中。
#include <iostream>
#include <vector>
using namespace std;
string PrintMinNumber(vector<int> numbers) {
if (numbers.empty()) return "";
if (numbers.size() == 1) return to_string(numbers.back());
string res = "";
int i = 0;
while (i < numbers.size() - 1){ //只需确定n-1个位置的值；
int j = i + 1,k=i;
while (j < numbers.size()){ //k保存从数组下标i之后的"最小值"下标；
string ab = to_string(numbers[k]) + to_string(numbers[j]);
string ba = to_string(numbers[j]) + to_string(numbers[k]);
if (ab>ba) k = j;
j++;
}
swap(numbers[i], numbers[k]);
res += to_string(numbers[i]);
i++;
}
res += to_string(numbers.back());
return res;
}
int main()
{
int a[3] = {3,23,234};
vector <int> v(a,a+3);
string b = PrintMinNumber(v);
cout << b << endl;
return 0;
}