【码农的自我修养】华为算法岗机试题整理

我不是女神ヾ 2023-05-21 07:13 2阅读 0赞

在这里复盘本人4月29号晚做的机试题，由于记在纸上了，断断续续的，大体意思是这样。

1、小明有一串字符弄乱了顺序，问这些字符可以组成的不重复的字符串的最多可能有几种，输出所有可能的字符串的个数。

输入：输入的字符串中没有空格，字符个数不超过8个
    
    输出：
    
    （1）样例1：                        （2）样例2
    
    输入：abc                            输入：aab
    
    输出：6                              输出：3

解答思路：递归实现。以abc为例。

*  固定a，求后面bc的排列
 *  固定b，求后面ac的排列
 *  固定c，求后面ab的排列

s = input()
    def dfs( nums, perm):
        size = len(nums)
        if size>8:
            return;
        if size == 0:
            res.append(perm)
        else:
            for i in range(size):
                if (i>0) and (nums[i] == nums[i-1]):
                    continue
                dfs(nums[:i]+nums[i+1:], perm+[nums[i]])
    
    if s=='':
        print(0)
    else:
        res = []
        dfs(s,[])
        print(len(res))

2、A先发给B一个字符串M，B再发给A一个数字k，从M中移除k个字母后，得到的字典序最小的字符串即为两者后续通信的密钥。试根据给定的M和k，返回最终合法的密钥。字符串M中仅包括小写英文字母。100000>=M.len>k。

输入描述：
    第一行：字符串
    第二行：数字，表示从字符串中移除几位
    输出描述：
    移除若干个字母后，字典序最小的字符串
    
    输入：
    bacaa
    1
    输出：
    acaa

解答思路： 这里如果使用暴力解法，对每个元素后面都进行扫描，找到第一个更大的元素，时间复杂度为O(n^2)。这里的问题是一个Next Greater Number 问题，可以使用“单调栈”的思路。

首先入栈一个元素，那么再往栈中输入元素时，应该与栈顶元素对比，如果大于栈顶元素那么就入栈，如果小于栈顶元素，则让栈顶元素出栈。我们只要确保出栈的元素个数不超过输入的k即可。

#include<bits/stdc++.h>
    #define M(a,b) memset(a,b,sizeof a)   //在一段内存块中填充某个给定的值
    #define LL long long
    using namespace std;
    const int maxn=100001;
    char a[maxn];
    stack<char>q;
    int n,m,k;
    int main()
    {
        //清空栈
        while(!q.empty())
            q.pop();
        scanf("%s",a);//获取字符串
        scanf("%d",&k);//获取数字
        n=strlen(a);
        m=n-k;
        int cnt=0; //用来统计删掉的字符数
        int flag=n;
        //遍历字符串，将字符串存在栈里
        for(int i=0; i<n; i++)
        {
            //入栈
            if(q.empty())
                q.push(a[i]);
            else
            {
                if(a[i]>q.top())
                    q.push(a[i]);
                else
                {
                    //栈顶元素比当前字符串大的就出栈
                    while(!q.empty()&&q.top()>a[i])
                    {
                        q.pop();//出栈
                        cnt++;
                        //最多删除k个字符
                        if(cnt>=n-m)
                        {
                            flag=i;
                            break;
                        }
                    }
                    q.push(a[i]);
                }
            }
            if(cnt>=n-m)
                break;
        }
        //现在栈中只剩下小的了
        string ans="";
        for(int i=n-1;i>flag;i--)
            ans+=a[i];
        while(!q.empty())
            ans+=q.top(),q.pop();
        cout<<ans<<endl;
        //逆转（栈是先进后出）
        reverse(ans.begin(),ans.end());
        //复制子字符串
        ans=ans.substr(0,m);
        cout<<ans<<"\n";
    }