网易算法岗2018秋招两道笔试题

1./*小易立方体：每次操作从某塔上取下一块立方体放到lingyige塔上；其中最高的塔减去最低的塔为不稳定值
输入：n，k分别为塔数和最大操作次数；
输出：不稳定值，操作次数
每次操作的塔位置
分析：对每次操作暴力遍历最大值和最小值；最大值+1，最小值-1；
边界条件：直至操作次数num=k或者不稳定值为0或1；*/

#include "stdafx.h"
#include <iostream>
#include <string>
#include <algorithm>
#include<vector>
using namespace std;
int main(){
    int n, k, max=0, min=0;//记录最大值最小值
    int num = 0;//计数
    cin >> n >> k;
    vector<int> a;
    vector<int> countk;
    int tmp;
    //输入n个int值push_back至数组
    for (int i = 0; i < n; i++){
        cin >> tmp;
        a.push_back(tmp);
    }
    for (int i = 0; i < k; i++){
        num++;
        //寻找最大值最小值挪动
        for (int j = 0; j < a.size(); j++){
            if (a[j] > a[max]) max = j;
            if (a[j] < a[min]) min = j;
            }
        //不稳定值已最小
        if ((a[max] - a[min] == 0) || (a[max] - a[min] == 1)){
            cout << a[max] - a[min] << ' ' << num << endl;
            for (int x = 0; x < num; x++){
                cout << countk[2 * x] << ' ' << countk[2 * x + 1] << endl;
            }
            break;
        }
        a[max]--;
        a[min]++;
        countk.push_back(max);
        countk.push_back(min);
    }
    cout << a[max] - a[min] << ' ' << num << endl;
    for (int x = 0; x < num; x++){
        cout << countk[2 * x] << ' ' << countk[2 * x + 1] << endl;
    }
}

2./题目描述：对n个a，m个z组成的字符串全排列，输出第k个字符串/
分析：主要考察字符串全排列（小点：字符与串的转换，字符串排序等）

#include "stdafx.h"
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include<vector>
using namespace std;
/*1.n个元素的全排列 = （n-1）个元素的全排列 + 另一个元素作为前缀
2.如果只有一个元素，那么这个元素本身就是它的全排列
3.不断将每个元素放作第一个元素，然后将这个元素作为前缀，
并将其余元素继续全排列，等到出口，出口出去后还需要还原数组*/
void pailie(set<string>& ss, int num, vector<char> chars){
    if (num == 1){
        return;
    }
    else
    {
        char tmpc;
        string tmpss;

        for (int i = num - 2; i >= 0; i--){
            tmpc = chars[i];
            chars[i] = chars[num-1];
            chars[num-1] = tmpc;
            for (auto it = chars.begin(); it != chars.end(); ++it){
                tmpss += *it;
            }
            ss.insert(tmpss);
            tmpss.clear();
            pailie(ss, num - 1, chars);
        }

    }

}
int main(){
    int n, m, k;
    int count=0;
    cin >> n >> m >> k;
    string tmpss;
    vector<char> chars;
    set<string> ss;//set容器，对字符串默认升序排序，并去除重复
    for (int i = 0; i < n; i++){
        chars.push_back('a');
    }
    for (int j = 0; j < m; j++){
        chars.push_back('z');
    }
    //插入初始字符串，char-》string
    for (auto it = chars.begin(); it != chars.end(); ++it){
        tmpss += *it;
    }
    ss.insert(tmpss);
    pailie(ss, n+m, chars);
    for (auto it = ss.begin(); it != ss.end(); it++){
        count++;
        if (count = k - 1){ cout << *it << endl; }
    }

}

比较函数的定义：
https://blog.csdn.net/diyinqian/article/details/72904404