数字排列 

输入一组数字（可能包含重复数字），输出其所有的排列方式。

数据范围

输入数组长度 [0,6]。

样例

输入：[1,2,3]
 
输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

源代码 

c++类的简单设计以及二维vector数组的使用 

class Solution
{
    public:
        vectorint>> permutation(vector<int>& nums)
        {
            sort(nums.begin(),nums.end());
            vectorint>> S;
            S.push_back(nums);
            while(next_permutation(nums.begin(),nums.end()))S.push_back(nums);
            return S;
        }
};

笨拙的手指

奶牛贝茜正在学习如何在不同进制之间转换数字。

但是她总是犯错误，因为她无法轻易的用两个前蹄握住笔。

每当贝茜将数字转换为一个新的进制并写下结果时，她总是将其中的某一位数字写错。

例如，如果她将数字 1414 转换为二进制数，那么正确的结果应为 1110，但她可能会写下 0110 或 1111。

贝茜不会额外添加或删除数字，但是可能会由于写错数字的原因，写下包含前导 0 的数字。

给定贝茜将数字 N 转换为二进制数字以及三进制数字的结果，请确定 N 的正确初始值（十进制表示）。

输入格式

第一行包含 N 的二进制表示，其中一位是错误的。

第二行包含 N 的三进制表示，其中一位是错误的。

输出格式

输出正确的 N 的值。

数据范围

0≤N≤10^9，且存在唯一解。

输入样例：

1010
212

输出样例：

14

样例解释

14 在二进制下的正确表示为 1110，在三进制下的正确表示为 112。

源代码

本题很简单只用三个函数即可解决

第一个二进制转化为十进制的函数

第二个二进制转化位三进制的函数(嵌套二进制转十进制)

第三个判断情况的布尔函数

观察题目我们若是使用暴力枚举的方法的话会超时，从暴力当中减少调整枚举方法从而减少枚举个数，避免TLE，若是对于三进制的字符串每位进行枚举的话则有除本位之外的两种情况，若是对于二进制的字符串进行每位枚举的话则只有除本位之外的一种情况，所以二进制字符串枚举处理较为容易，1010对于每位的情况取反的话只有四种情况：1110、1000、0010、1011(题目所给仅有一位出错)，因此这四个字符串当中必定有一个正确，正确的字符串转化为三进制之后必定仅仅与只有一位错误的三进制字符串有一位不同

因此我们对于二进制字符串的每位取情况相反的状况然后枚举，而后在枚举的二进制字符串转化为三进制的字符串当中找出与所给的三进制字符串有着仅一位不同的字符串ans即可，将ans串转化为十进制输出即可，时间复杂度控制在了O(n)

#include 
#include 
using namespace std;
int getans(string s)
{
    int ans = 0;
    int w = 1;
    for(int i = s.size() - 1;i >= 0;i -- )
    {
        ans = ans + (s[i] - '0') * w;
        w = w * 2;
    }
    return ans;
}
string trans(string s)
{
    int ans = getans(s);
    string t;
    while(ans > 0)
    {
        int num = ans % 3;
        t = t + char(num + '0');
        ans /= 3;
    }
    reverse(t.begin(),t.end());
    return t;
}
bool check(string a,string b)
{
    int nums = 0;
    for(int i = 0;i < a.size() || i < b.size();i ++ )
    {
        if(a[i] != b[i])nums ++ ;
        if(nums > 1)break;
    }
    if(nums == 1)return true;
    else return false;
}
int main()
{
    string a,b;
    cin >> a >> b;
    for(int i = 0;i < a.size();i ++ )
    {
        string t = a;
        if(t[i] == '0')t[i] = '1';
        else if(t[i] == '1')t[i] = '0';
        if(check(trans(t),b))
        {
            cout << getans(t) << endl;
            return 0;
        }
    }
    return 0;
}

查找

题目描述

输入 n(n≤10^6) 个不超过 10^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1​,a2​,…,an​，然后进行 m(m≤10^5) 次询问。对于每次询问，给出一个整数 q(q≤10^9)，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。

输入格式

第一行 2 个整数 n 和 m，表示数字个数和询问次数。

第二行 n 个整数，表示这些待查询的数字。

第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。

输出格式

m 个整数表示答案。

输入输出样例

输入 

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

输出 

1 2 -1 

说明/提示

10^6 规模的数据读入，请用 scanf。用 cin 会超时。

源代码 

标准的二分查找题目，不过我还是加了优化使用的cin和cout，也没有TLE

#include 
using namespace std;
const int N = 1000000 + 10;
int a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i = 0;i < n;i ++ )cin >> a[i];
	while(m -- )
	{
		int num;
		cin >> num;
		int l = 0,r = n - 1;
		while(l < r)
		{
			int mid = l + r >> 1;
			if(a[mid] >= num)r = mid;
			else l = mid + 1;
		}
		if(a[l] == num)cout << l + 1 << ' ';
		else cout << "-1" << ' ';
	}
} 

砍树

题目描述

伐木工人 Mirko 需要砍 M 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。

Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 H，并锯掉所有树比 H 高的部分（当然，树木不高于 H 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 20,15,10 和 17，Mirko 把锯片升到 15 米的高度，切割后树木剩下的高度将是 15,15,10 和 15，而 Mirko 将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。

Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 H，使得他能得到的木材至少为 M 米。换句话说，如果再升高 1 米，他将得不到 M 米木材。

输入格式

第 1 行 2 个整数 N 和 M，N 表示树木的数量，M 表示需要的木材总长度。

第 2 行 N 个整数表示每棵树的高度。

输出格式

1 个整数，表示锯片的最高高度。

输入输出样例

输入

4 7
20 15 10 17

输出 

15

输入 

5 20
4 42 40 26 46

输出 

36

说明/提示

对于 100% 的测试数据，1≤N≤10^6，1≤M≤2×10^9，树的高度 <10^9，所有树的高度总和 M。

源代码

二分是简单但是注意数据范围，要开long long防止超出

#include 
using namespace std;
const int N = 1000000 + 10;
typedef long long ll;
ll a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n,m;
	cin >> n >> m;
	ll maxtree = 0;
	for(int i = 1;i <= n;i ++ )
	{
		cin >> a[i];
		maxtree = max(maxtree,a[i]);
	}
	ll l = 0,r = maxtree;
	while(l < r)
	{
		ll mid = l + r + 1 >> 1;
		ll sum = 0;
		for(int i = 1;i <= n;i ++ )
		{
			if(a[i] > mid)sum = sum + (a[i] - mid);
		}
		if(sum >= m)l = mid;
		else r = mid - 1;
	}
	cout << l;
	return 0;
}