编程题记录

柔光的暖阳◎ 2022-02-25 12:42 231阅读 0赞

1.给出一个字符串 *A*, 表示一个 *n* 位正整数, 删除其中 *k* 位数字, 使得剩余的数字仍然按照原来的顺序排列产生一个新的正整数。

找到删除 *k* 个数字之后的最小正整数。*N* <= 240, *k* <= *N*

class Solution {
    public:
        /**
         * @param A: A positive integer which has N digits, A is a string
         * @param k: Remove k digits
         * @return: A string
         * 当某一位比后一位大时删除
         * 最后的结果如果前面是0要去掉
         */
        string DeleteDigits(string &A, int k) {
            // write your code 
            string res;
            if(A.empty())
    			return res;
    		res = A;
    		while(k)
    		{
    			int i = 0;
    			while(i<res.length()-1&&res[i]<=res[i+1])
    				i++;
    			res = res.substr(0,i)+res.substr(i+1);
    			k--;
    		}
    		
    		int i = 0;
    		while(res[i]=='0')
    		    i++;
    		 res = res.substr(i);
    		return res;  
        }
    };

2. 给出一个表达式S，该表达式只包括数字、字母及方括号这三种元素。该表达式具有如下规则：数字只会出现在方括号前，它表示方括号内容的重复次数，方括号中的内容可以是普通的字符串， 也可以另一个表达式。请写一段程序，按照上述规则将输入的表达式展开成目标字符串。

class Solution {
    public:
        /**
         * @param s: an expression includes numbers, letters and brackets
         * @return: a string
         * 用栈，遍历字符串入栈，当遇到']'时出栈，保存的另一个字符串dup中，出栈到'[‘时说明需要重复的都找到了
         * 然后再出栈数字，数字都出来后，将dup重复相应的次数,再入栈
         * 都遍历完之后，逐个出栈
         */
        string expressionExpand(string &s) {
    
            // write your code here
            string res;
            if(s.empty())
                return res;
            stack<char> sk;
            int i = 0;
            while(i<s.size())
            {
                if(s[i]==']')
                {
                    string dup;
                    while(sk.top()!='[')
                    {
                        dup = sk.top()+dup;
                        sk.pop();
                    }
                    sk.pop();
                    string num;
                    while(!sk.empty()&&isdigit(sk.top()))
                    {
                        num = sk.top()+num;
                        sk.pop();
                    }
                    int cnt = stoi(num);
                    string str;
                    while(cnt>0)
                    {
                        str+=dup;
                        cnt--;
                    }
                    for(auto c:str)
                        sk.push(c);
                }else{
                    sk.push(s[i]);
                }
                i++;
            }
            
            while(!sk.empty())
            {
                res = sk.top()+res;
                sk.pop();
            }
            return res;
        }
    };

3.输入一个含有N个数字的数组，问需要几次数组里面的数字就被删完了，删的规则是这样的，每次从一个回文串里删，如果没有回文串，只能一个一个的删，返回需要的最少次数，比如输入\[1,2\],返回2，因为没有回文，只能一个一个的删；输入\[1,4,3,1,5\],返回3，因为第一次删掉3(或4)后，剩下的数组是\[1,4(或3),1,5\]，第二次可以将回文内的数字都删掉，最后把5删掉，一共3次

4.给定一个仅包含0或1的字符串，现在可以对齐进行一种操作：01相邻时可以消除掉这两个字符，这样操作可以一直进行下去直到找不到相邻的0和1为止问这个字符串经历了操作后的最短长度  
4  
1100  
输出 0

#include<iostream>
    #include<string>
    using namespace std;
    class Solution {
    public:
    	int minlen(string &s)
    	{
    		int i = 0;
    		while (s.size()&&i < s.size() - 1)
    		{
    			if ((s[i] == '0'&&s[i + 1] == '1') || s[i] == '1'&&s[i + 1] == '0')
    			{
    				s.erase(i, 2);
    				i = 0;
    			}
    			else
    				i++;
    		}
    		return s.size();
    	}
    };
    int main()
    {
    	Solution s;
    	string str;
    	while (cin >> str)
    	{
    		int len = s.minlen(str);
    		cout << len << endl;
    	}
    	return 0;
    }

5.小Q手上有n种不同面值的硬币，每种硬币都有无限多个希望带尽量少的硬币，并且能组合出1到m之间（包含1和m）的所有面值  
m 20 n 4  
1 2 3 10  
输出 5

class Solution {
    public:
        /**
        *背包问题 填满amount
        *dp[i]:表示填满i所需的数量
        */
        int coinChange(vector<int>& coins, int amount) {
            vector<int> dp(amount+1,amount+1);
            dp[0] = 0;
            for(auto coin:coins)
            {
                for(int i = coin;i<=amount;i++)
                {
                    dp[i] = min(dp[i],dp[i-coin]+1);
                }
            }
            return dp[amount]>amount?-1:dp[amount];
        }
    };

6.打怪兽，依次遇见N只怪兽，每只都有武力值和所需金币数，给金币会护送 ，如果没有贿赂且大于护送的武力值之和会攻击   
问所需最少金币数（只通过了70%，找不到原因）  
3 n只  
8 5 10武力值  
1 1 2金币数  
输出  
2

#include<iostream>
    #include<vector>
    using namespace std;
    int fun(int n,vector<int> d,vector<int> p)
    {
        if(n<=0)
            return 0;
        if(n==1)
            return p[0];
        int d_min = d[0],d_max = d[0];
        int p_min = p[0],p_max = p[0];
        for(int i = 1;i<n;i++)
        {
            if(d_min>d[i])
            {
                d_max += d[i];
                p_max += p[i];
            }else if(d_max>d[i])
            {
                d_min = d_max;
                p_min = p_max ;
            }else{
                d_min +=d[i];
                d_max  = d_min;
                p_min += p[i];
                p_max = p_min;
            }
        }
        return p_min;
    }
    int main()
    {
        int n;
        while(cin>>n)
        {
            vector<int> d(n,0);
            vector<int> p(n,0);
            for(int i = 0;i<n;i++)
            {
                int a;
                cin>>a;
                d[i] = a;
            }
            for(int i = 0;i<n;i++)
            {
                int b;
                cin>>b;
                p[i] = b;
            } 
            int res = fun(n,d,p);
            cout<<res<<endl;
        }
        
        return 0;
    }

7.请设计一个类，该类在同一个进程中只能由一个实例，且该实例允许外部访问。

只能生成一个实例的类是实现了单例模式的类型。

解题思路：

1.必须把构造函数设为私有函数，防止他人创建实例。

2.在类中创建静态私有的实例，在需要时创建该实例，直到程序结束才销毁。

3.提供一个静态的公有的函数用于创建/获取静态私有对象。

class Singleton{
    public:
    	static Singleton* getInstance();
    
    private:
    	Singleton();
    	//把拷贝构造函数和拷贝复制运算符也设为私有,防止被复制
    	Singleton(const Singleton&);
    	Singleton& operator=(const Singleton&);
    
    	static Singleton* instance;
    };