记录网易雷火笔试
1、交换完全二叉树某子树
第一眼看上去需要建立二叉树，但是因为是完全二叉树，可以直接用数组代替，对于每个节点n，其子树为2n和2n+1，因此直接根据这个规律操作数组即可。
因为对于节点n，其子树也需要交换，因此这里采用递归，对节点n的子树及其子树节点也进行交换。
对于节点n，首先判断其左右子树是否存在，如果不存在，直接返回；如果存在，则对左右子树进行递归，最后左右子树全部交换完后，再对当前节点的左右子树进行交换。
因为对于节点n，其子树也需要交换，因此这里采用递归，对节点n的子树及其子树节点也进行交换。
对于节点n，首先判断其左右子树是否存在，如果不存在，直接返回；如果存在，则对左右子树进行递归，最后左右子树全部交换完后，再对当前节点的左右子树进行交换。
#include<iostream>
#include<vector>
using namespace std;
void dfs(vector<int> &arr, int left, int right)
{
if (left > arr.size() - 1 || right > arr.size() - 1)
return;
else
{
dfs(arr, 2 * left+1, 2 * right+1);
dfs(arr, 2 * (left + 1), 2 * (right + 1));
swap(arr[left], arr[right]);
return;
}
}
int main()
{
vector<int> arr = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
int n = 3;
dfs(arr, 2 * n-1, 2 * n);
for (int i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << endl;
system("pause");
return 0;
}
2、有N种商品，每种商品有N_i个，现在需要将K个不同的商品放入福袋中，问最多可以做多少个福袋
我的思路是，尽可能先拿个数多的那种商品。
首先将个数最多的K个商品，每种中拿出1个，然后对剩余的个数进行排序，再从个数最多的K个中每种拿出一个...每次拿之前先判断剩余商品种类是否大于K个。
首先将个数最多的K个商品，每种中拿出1个，然后对剩余的个数进行排序，再从个数最多的K个中每种拿出一个...每次拿之前先判断剩余商品种类是否大于K个。
int main()
{
int N, K;
cin >> N >> K;
vectorarr(N, 0);
for(int i = 0; i< N; i++)
cin >> arr[i];
int flag = 0;
int res = 0;
while(1)
{
flag = 0;
for(int i = 0; i< N; i++)
if(arr[i] > 0)
flag++;
if(flag < K)
break;
sort(arr.begin(), arr.end());
for(int i = arr.size()-1; i >= arr.size()-K; i--)
arr[i]--;
res++;
}
cout << res << endl;
return 0 ;
}
3、老王打字：①输入一个字母，步数加1；选定全部已输入字符，步数加2；复制全部选定字符，步数加2；粘贴全部复制字符，步数加2；按ESC取消选择，步数加1；
问：输入N个字最少需要多少步。
动态规划：
假设F(n)表示输入n个字需要的步数。
F(0) = 0；
F(1) = 1;
F(2) ：分情况讨论：①在输入了1个字的基础上，再输入1个字，即F(2) = F(2-1) + 1；②第二、三种情况，这里不明显，后面讨论
F(3) ：分情况讨论：①在输入1个的基础上输入2个，在输入2个的基础上输入1个，即F(3) = min( F(3-2) + 2, F(3 - 1) + 1)，两种情况中取最小值；②第二、三种情况，这里还是不明显，下一步讨论
........
F(10) ：分情况讨论：
①即为上面，在输入了i个字符的基础上，再输入10-i个，(i为从1到9)；
②第二种情况：输入了i个字符后，我复制这i个字符，取消选择，然后在后面进行多次粘贴，这里的i可以从1到10/2；循环取i，求最小值，需要注意的是，当10%i不为0时，需要再加上F(10%i)；
③第三种情况：输入了i个字符后，我还是复制粘贴这i个字符，但是上面②是复制之后，取消选择，在原来的后面继续粘贴；这里我复制之后，输入一个字符，将原来输入的都覆盖掉，然后再粘贴；
假设F(n)表示输入n个字需要的步数。
F(0) = 0；
F(1) = 1;
F(2) ：分情况讨论：①在输入了1个字的基础上，再输入1个字，即F(2) = F(2-1) + 1；②第二、三种情况，这里不明显，后面讨论
F(3) ：分情况讨论：①在输入1个的基础上输入2个，在输入2个的基础上输入1个，即F(3) = min( F(3-2) + 2, F(3 - 1) + 1)，两种情况中取最小值；②第二、三种情况，这里还是不明显，下一步讨论
........
F(10) ：分情况讨论：
①即为上面，在输入了i个字符的基础上，再输入10-i个，(i为从1到9)；
②第二种情况：输入了i个字符后，我复制这i个字符，取消选择，然后在后面进行多次粘贴，这里的i可以从1到10/2；循环取i，求最小值，需要注意的是，当10%i不为0时，需要再加上F(10%i)；
③第三种情况：输入了i个字符后，我还是复制粘贴这i个字符，但是上面②是复制之后，取消选择，在原来的后面继续粘贴；这里我复制之后，输入一个字符，将原来输入的都覆盖掉，然后再粘贴；
int main()
{
int N;
cin >> N;
vectordp(N+1, 99999);
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= N; i++)
{
for(int j = 1; j <= i; j++)
dp[i] = min(dp[i], dp[i-j] + j); //情况①
for(int j = 1; j <= i/2; j++)
{
dp[i] = min(dp[i], dp[j] + i/j*2 + 3 + dp[i%j]); //情况②
dp[i] = min(dp[i], dp[j] + i/j*2 + 5); //情况③
}
}
cout << dp[N] << endl;
return 0;
}
