题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））

解题思路

我们用一个辅助栈来实现最小值的更新工作。

这个辅助栈工作原理：

入栈时：
- 1）当数据栈为空时，进入栈的元素同时也进入辅助栈；
- 2）当它不为空时，就把该入栈元素与辅助栈的栈顶元素进行比较，若入栈元素小，则该元素同时也进入辅助栈；若不是，则对辅助栈不进行操作
出栈时：
- 1）当时辅助栈的栈顶元素等于处理数据的数据栈栈顶元素时，不经数据栈要弹出元素，辅助栈也要弹出栈顶元素，
- 2)当不等时，只对数据栈进行出栈操作。

这样我们思路就很明确了：min函数只需返回辅助栈的栈顶源。

class  {
public:
    void push(int value)
    {
        datastack.push(value);
        
        if(minstack.empty() || value < minstack.top())
            minstack.push(value);
    }

    void pop()
    {
        if(datastack.empty())//数据栈为空
            return ;
        if(datastack.top() == minstack.top()) //数据栈和辅助栈栈顶元素相同
            minstack.pop();
        datastack.pop();
    }

    int top()
    {
        return datastack.top();
    }

    int min()
    {
        return minstack.top();
    }
private:
    stack<int>  datastack;     //  数据栈
    stack<int>  minstack;      //  存储每次栈中最小值的栈信息
};

21-栈的压入弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

解题思路

开辟一个辅助栈，模拟入栈出栈过程(假设pushV为入栈序列，popV为出栈序列)

pushV中的元素依次压入辅助栈s,push++；设置变量push,pop分别代表pushV和popV当前元素的位置；

新压入的元素与弹出序列的pop位元素相同，辅助栈弹出，同时pop++

不相同，pushV中的元素继续入辅助栈s，push++；

如果下一个弹出的数字刚好是栈顶数字，则直接弹出。
若下一个弹出的数字不在栈顶，则把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。

若所有的数字都压入栈了仍没有找到下一个弹出的数字，则表明该序列不可能滴一个弹出序列。

class  {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size() == 0 && popV.size() == 0)
            return false;
        else if(pushV.size() != popV.size())
            return false;
        stack<int> s;
        s.push(pushV[0]);
        for(int push = 0, pop = 0; push < pushV.size() && pop < popV.size();){
            if(s.empty() != true && s.top() == popV[pop]){
                s.pop();
                pop++;
            }
            else{
                s.push(pushV[++push]);
            }
        }
        if(s.empty())
            return true;
        else
            return false;
    }
};

22-从上往下打印二叉树

解题思路

在队列中插入结束标识来标识当前层结束

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/



class  {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        queue<TreeNode* > q;
        q.push(root);
        q.push(NULL);// 在队列中插入结束标识来表示当前层结束
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            if(node){
                res.push_back(node->val);
                if(node->left != NULL)
                    q.push(node->left);
                if(node->right != NULL)
                    q.push(node->right);
            }
            else if(!q.empty())
                q.push(NULL);
        }
        return res;
    }
};

23-二叉搜索树的后序遍历序列

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

解题思路

利用递归，后序遍历中最后一位是根节点，然后将序列前面分成两部分，前面部分比根节点小的为左子树，中间部分比根节点大的为右子树；要考虑最后一层的孩子节点为单孩子还是双孩子节点

class  {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0){
            return false;
        }
        return judge(sequence, 0, sequence.size() - 1);
    }
    bool judge(vector<int> &sequence, int left, int right){
        if(left >= right){ //考虑有左右孩子和单孩子的请况
            return true;
        }
        int mid = right - 1;
        while(sequence[mid] > sequence[right]){
            mid--;
        }
        int i = left;
        while (i < mid && sequence[i] < sequence[right]){
            i++;
        }
        if (i < mid){
            return false;
        }
        ///  这样我们就划分出区间
        ///  [left, mid] 是左子树
        ///  [mid + 1, right - 1] 是右子树
        ///  right 是根节点
        return judge(sequence, left, mid) && judge(sequence, mid + 1, right - 1);
    }
};

24-二叉树和为某一值的路径

题目描述

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

解题思路

用个递归来实现，先序遍历;

每次访问一个节点，那么就将当前权值求和
如果当前权值和与期待的和一致，那么说明我们找到了一个路径，保存或者输出
否则的话就递归其左右孩子节点

这里需要注意一个问题，就是递归退出的时候，权值和的信息是保存在递归栈中的会恢复，但是我们保存的路径是无法恢复的，那么我们就需要在递归返回时将数据弹出。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class  {
public:
    vector<vector<int> > ans;
    vector<vector<int> > FindPath(TreeNode* root,int target){
        if(root == NULL)
            return ans;
        vector<int> path;
        FindToPath(root, target, path, 0);
        return ans;
    }
    void FindToPath(TreeNode* root, int target, vector<int> path, int currentsum){
        currentsum += root->val;
        path.push_back(root->val);
        if(target == currentsum && root->left == NULL && root->right == NULL)
            ans.push_back(path);
        if(root->left != NULL)
            FindToPath(root->left, target, path, currentsum);
        if(root->right != NULL)
            FindToPath(root->right, target, path, currentsum);
        //  此处不需要恢复currentSum和path的值:                                  
        //  因为currentSum作为参数在函数递归调用返回时会自动恢复                 
        //  而如果作为静态局部变量存储则需要进行恢复                             
        //  currentSum -= root->val;                                               
        //  path.pop_back( );
    }
};

28-数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路

充分利用出现次数超过一半这个条件

数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现的次数之和还要多

我们考虑阵地攻守（镇守阵地），遇见一个友军就抱成团，遇见一个敌军就同归于尽，那么最后战场上剩余的肯定就是人数（出现次数）最多的那个队伍（数字）

采用阵地攻守的思想：

第一个数字作为第一个士兵，守阵地；count = 1；
遇到相同元素，count++; 遇到不相同元素，即为敌人，同归于尽,count–；
当遇到count为0的情况，又以新的i值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，有可能是主元素。
再加一次循环，记录这个士兵的个数看是否大于数组一般即可。

由于我们要找的数字出现的次数比他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字，因为少的元素都已经阵亡了，战场上仅剩下的一定是人数数目要多的那个队伍

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size() == 0)
            return 0;
        else if(numbers.size() == 1)
            return numbers[0];
        int len = numbers.size(), key = numbers[0], count = 1;
        for(int i = 1; i < len; i++){
            if(key == numbers[i]){
                count++;
            }
            else{
                count--;
                if(count < 1){
                    key = numbers[i];
                }
            }
        }
        count = 0;
        for(int j = 0; j < len; j++){
            if(key == numbers[j])
                count++;
        }
        if(count > (len / 2))
            return key;
        return 0;
    }
};

29-最小的K个数

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

解题思路

采用冒泡排序法, K趟找出前K个数字

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    vector<int> res;
    int len = input.size();
    if(len < k)
        return res;
    
    for(int i = 0; i < k; i++){ //冒泡排序前K个元素
        for(int j = len - 1; j > 0; j--){
            if(input[j] < input[j - 1])
                swap(input[j], input[j - 1]);
        }
        res.push_back(input[i]);
    }
    return res;
}

30-连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

解题思路

利用贪心思想
如果希望达到O(n)时间复杂度，我们就应该能够想到我们只能对整个数组进行一次扫描，在扫描过程中求出最大连续子序列和以及子序列的起点和终点位置。

这个方法其实就是动态规划算法的改进

如果当前和为负数，那么就放弃前面的累加和，从数组中的下一个数再开始计数
否则我们就继续累计，并且保存当前的累计和

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size() == 0)
            return 0;
        int sum = 0, maxsum = INT_MIN;
        for(int i = 0; i < array.size(); i++){
            sum += array[i];
            sum = max(sum, array[i]);
            maxsum = max(sum, maxsum);
        }
        return maxsum;
    }
};

31-整数中1出现的次数

题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

解题思路

暴力破解法

最简单直接的方法就是我们循环所有的1~n中的每个number，计算每个number出现的次数
此方法简单，容易理解，但它的问题是效率，时间复杂度为$O(N * logN)$，N比较大的时候，需要耗费很长的时间。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count = 0;

        for(int i = 1;
            i <= n;
            i++)
        {
            count += NumberOf1(i);
        }

        return count;
    }
    int NumberOf1(int number)
    {
        int count = 0;
        while(number != 0)
        {
            if(number % 10 == 1)
            {
                count++;
            }
            number /= 10;
        }

        return count;
    }
};

分治法

我们重新分析下这个问题，

对于任意一个个位数n，只要n>=1,它就包含一个”1”；

n<1，即n=0时，则包含的”1”的个数为0。

于是我们考虑用分治的思想将任意一个n位数不断缩小规模分解成许多个个位数，这样求解就很方便。

但是，我们该如何降低规模？

仔细分析，我们会发现，

任意一个n位数中”1”的个位可以分解为两个n-1位数中”1”的个数的和，最后再加上一个与最高位数相关的常数C
例如，

对于n=12，可以拆分为01-09,10-12，即 f(12) = f(10 - 1) + f(12 - 10) + 3,其中3是表示最高位为1的数字个数，这里就是10,11,12；

对于n=132，可以拆分为0-99，100-132，即f(132)=f(100 -1) + f(132 - 100) + 33，33代表最高位为1的数字的个数，这里就是100~132百位数字的1出新了33次

对于232，可以拆分为0-99，100-232，即f(232) = 2*f(100 - 1) + f(32) + 100，因为232大于199，所以它包括了所有最高位为1的数字即100~199，共100个。

综上，我们分析得出，最后加的常数C只跟最高位n1是否为1有关

当最高位为1时，常数C为原数字N去掉最高位后剩下的数字+1，如N=12时，$C = 2 + 1 = 3$，N=132时，$C = 32 + 1 = 33$
当最高位大于1时，常数C为$10^(bit-1)$，其中bit为N的位数，如N=232时，bit=3，$C = 10^(bit-1) = 10^2 = 100$。于是，我们可以列出递归方程如下：
1
2
3
4

if(n1 == 1)
f(n) = f(10bit-1) + f(n - 10bit) + n - 10bit+ 1;
else
f(n) = n1*f(10bit-1) + f(n – n1*10bit) + 10bit;

进一步可以归结为

f(n) = n1*f(10bit-1) + f(n – n1*10bit) + LEFT;
其中
if(n1 == 1)
    LEFT = n - 10bit+ 1;
else
    LEFT = 10bit;

此算法的优点是不用遍历1~N就可以得到f(N)。经过我测试，此算法的运算速度比解法一快了许多许多，数字在1010内时，算法都可以在毫秒级内结束。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        return CountOne(n);
    }
    int CountOne(int n){
        long count = 0;
        if(n < 1)
            count = 0;
        else if(n > 1 && n < 10)
            count = 1;
        else{// 计算n的位数
            long highest = n;//表示最高位的数字
            int bit = 0;
            while(highest >= 10){
                highest /= 10;
                bit++;
            }//  循环结束时, bit表示n的位数, 而highest是其最高位的数字
            int weight = pow(10, bit);//代表最高位的权重，即最高位一个1代表的大小
            if(highest == 1){
                count = CountOne(weight - 1)
                + CountOne(n - weight)
                + n - weight + 1;
            }
            else{
                count = highest * CountOne(weight - 1)
                + CountOne(n - highest * weight)
                + weight;
            }
        }
        return count;
    }
};

32-把数组排成最小的数

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解题思路

对vector容器内的数据进行排序，按照将a和b转为string后.若 a＋b<b+a a排在在前的规则排序,如 2 21 因为 212 < 221 所以排序后为 21 2 ,to_string() 可以将int 转化为string

Tips:

sort中的比较函数compare要声明为静态成员函数或全局函数，不能作为普通成员函数，否则会报错。
因为：非静态成员函数是依赖于具体对象的，而std::sort这类函数是全局的，因此无法再sort中调用非静态成员函数。
静态成员函数或者全局函数是不依赖于具体对象的, 可以独立访问，无须创建任何对象实例就可以访问。
同时静态/全局函数不可以调用类的非静态成员。
sort 是将数组里所有的数都按照这个规则排序了, 排序完成以后, 数组里面数的排列就已经是最小的数了,

再用一个循环拼接成字符串就好了

using namespace std;
class Solution {
public:
    static bool com(int a, int b){//定义一个比较函数，作为参数传入sort函数中
        string str1 = to_string(a);
        string str2 = to_string(b);
        return (str1+str2) < (str2+str1);
    }
    string PrintMinNumber(vector<int> numbers){
        string res = "";
        if(numbers.empty()) return res;
        sort(numbers.begin(), numbers.end(), com);
        for(int i = 0; i < numbers.size(); i++){
            res += to_string(numbers[i]);
        }
        return res;
    }
};

33-丑数

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解题思路

暴力破解法

最简单直接的方法，就是逐个判断每个整数是不是丑数，循环所有数字，判断它是不是丑数首先我们需要判断某个整数number是不是丑数

#include<iostream>
#include<vector>
using namespace std;
#define __tmain main
bool IsUglyNum(int num) {
	while (num % 5 == 0)
		num /= 5;
	while (num % 3 == 0)
		num /= 3;
	while (num % 2 == 0)
		num /= 2;
	return (num == 1);
}
int GetUglyNumber_Solution(int index) {
	if (index < 1)
		return 0;
	int num = 0, count = 0;
	while (count < index) {
		num++;
		if (IsUglyNum(num))
			count++;
	}
	return num;
}
int __tmain() {
	int n,result;
	cin >> n;
	result = GetUglyNumber_Solution(n);
	cout << result << endl;
}

空间换时间法：时间效率较高

根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（1除外）。因此我们可以创建一个数组，里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以2、3或者5得到的。那关键就是确保数组里的丑数是有序的了。
我们假设数组中已经有若干个丑数，排好序后存在数组中。我们把现有的最大丑数记做M。现在我们来生成下一个丑数，该丑数肯定是前面某一个丑数乘以2、3或者5的结果。
我们首先考虑把已有的每个丑数乘以2。在乘以2的时候，能得到若干个结果小于或等于M的。由于我们是按照顺序生成的，小于或者等于M肯定已经在数组中了，我们不需再次考虑；我们还会得到若干个大于M的结果，但我们只需要第一个大于M的结果，因为我们希望丑数是按从小到大顺序生成的，其他更大的结果我们以后再说。
我们把得到的第一个乘以2后大于M的结果，记为M2。同样我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么下一个丑数应该是M2、M3和M5三个数的最小者。

class Solution {
public:
    int ugly[10000];
    int min(int a, int b, int c){
        int tmp = (a < b ? a : b);
        return (tmp < c ? tmp: c);
    }
    int GetUglyNumber_Solution(int N){
        ugly[0] = 1;
        int index2 = 0, index3 = 0,index5 = 0;
        int index = 0;
        while(index < N){
            int val = min(ugly[index2] * 2,
                         ugly[index3] * 3,
                         ugly[index5] * 5);
            if(val == ugly[index2] * 2)
                index2++;
            if(val == ugly[index3] * 3)
                index3++;
            if(val == ugly[index5] * 5)
                index5++;
            ugly[++index] = val;
        }
        int res = ugly[N-1];
        return res;
    }
};

34-第一次只出现一次的字符

题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

解题思路

使用辅助数组进行计数，统计每个字符串的出现的次数，然后查找第一个只出现一次的字符位置

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.length() == 0)
            return -1;
        int count[256];
        //  将计数器数组清0
        memset(count, '

近期文章

近期评论

标签

热门

文章归档

分类目录

功能