华为8_26机试

华为8.26第一题：位转换：没有任何技巧，纯c++代码

* 题目描述：题目中提示，每个数字的二进制为32bit）
* 1.输入n个无符号整数
* 2.给每个数字增加干扰措施。
* 2.1 干扰1：让每个整数的二进制位置上的数字交换，即(2*i）与（2*i+1）交换，i=0：15。以下讨论说的都是二进制数。
* 2.2 干扰2：假设三个数a,b,c，a（XXXXXXXXXXa2a1）的最后两位弹出a1,a2；a1,a2进入b的头,同时b的最后两位b1b2弹出，此时b变为（a2a1XXXXXXXXXXXX），c同理，变为（b2b1XXXXXXXXXXXX），将c的尾巴c1c2弹入a的头，a变为（c2c1XXXXXXXXXXXXX）。
* 最终效果：(干扰2：再把每个数向右移动两位，溢出的部分依次像下一个整数的最高位移动，末尾的右移两位到第一个数的最高两位)
* a（XXXXXXXXXXXXa2a1）->（c2c1XXXXXXXXXXXXX）；
* b（XXXXXXXXXXXXb2b1）->（a2a1XXXXXXXXXXXX）；
* c（XXXXXXXXXXXXc2c1）->（b2b1XXXXXXXXXXXX）；
* 。。。。。。应该叙述清楚了。倘若只有一个数a，这个应该好分析
* 3.输出每个***扰后的数字（十进制的，同空格隔开）

主要思路：

1. 按照题目要求来，本题的思路是用unsigned int转二进制，再转字符串做翻转进行相应操作
   后续这种转换，我感觉要直接用移位来，这是c++的优势

小的tricks:我之前也遇到过字符串输入带空格。。。用getline(cin,s)。。。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 将数转换为32位数的二进制
string zhuanhuan1(unsigned int a)
{
  string temp;
  int t = 0;
  for (int i = 0; i < 32; i++)
  {
    // 转换成二进制，完全按照我们的数学公式来的
    t = a % 2;
    temp.push_back(t + '0'); // 数字转字符
    // 现在比如我们要字符‘1’转换成数字1
    // 字符型常量用''括起来的原因是，它们在计算机中都以各自的ASCII表示。而‘1’的对应编码是49的二进制码，但是我们的数字1，就等于1呀
    // 所以为了由原来的‘1’实际上就是49的二进制变成现在的1对应的二进制1，只好用49-48=1了。但是在ASCII码里‘0’对应的刚好是48的二进制码，
    // 所以我们转换的时候只需要‘1’-‘0’=1；就可以了
    // 而数字的ASCII码是按顺序规定的。所以其它字符要转换成数字都可以用减‘0’来表示
    // 而数字1转字符'1'，就加上’0‘就可以了
    // https://www.cnblogs.com/sprayer/p/3163825.html

    a = a / 2; // 向下取整
  }
  reverse(temp.begin(), temp.end());
  return temp;
}

// 将32为二进制的数转换为十进制数

// 干扰措施1
void ganrao1(string &s)
{
  for (int i = 0; i < 16; i++)
  {
    swap(s[i * 2], s[i * 2 + 1]);
  }
}

// 干扰措施2
void ganrao2(string &s, char l1, char l2)
{
  s.pop_back();
  s.pop_back();
  reverse(s.begin(), s.end());
  s.push_back(l1);
  s.push_back(l2);
  reverse(s.begin(), s.end());
}

int main()
{
  // 输入
  unsigned int temp;
  vector<unsigned int> arr;
  while (cin >> temp)
  {
    arr.push_back(temp);
  }
  vector<string> str(arr.size());

  // 转换为二进制并增加干扰1
  for (int i = 0; i < arr.size(); i++)
  {
    str[i] = zhuanhuan1(arr[i]); // unsigend int arr[i]->string str[i]
    //cout << str[i] << endl;
    ganrao1(str[i]); //干扰1
    //cout << str[i] << endl;
  }

  // 施加干扰2
  char f_l1 = str[0][str[0].size() - 1]; // 第一个数的二进制后两位fl1、fl2
  char f_l2 = str[0][str[0].size() - 2];
  char l_l1 = str[str.size() - 1][str[0].size() - 1]; // 最后一个数的二进制后两位ll1、ll2
  char l_l2 = str[str.size() - 1][str[0].size() - 2];
  if(str.size()>1{
    for (int i = 1; i < str.size(); i++)
    {
      char l = str[i][str[i].size() - 1]; // 记录当前数字的最后两位,在干扰里面会pop_back()出去，先保留
      char r = str[i][str[i].size() - 2];
      ganrao2(str[i], f_l1, f_l2);
      //cout << "干扰2" << str[i] << endl;
      f_l1 = l;
      f_l2 = r;
    }
  }
  ganrao2(str[0], l_l1, l_l2); // 第一个数做干扰2处理
  // 转换回十进制的数
  for(int i=0, i<arr.size(); i++){
    arr[i] = zhuanhuan2(str[i]);
    cout << arr[i] << " ";
  }
  return 0;
}

第二题：输入一组矩形，分别给出宽和高，求这些矩形组成的连续最大面积（最大柱状图面积的变形）。

这题算法上leetcode有变形，算法倒是不难。比较费事的是输入格式，输入的是 “[1,2,3],[1,2,3]" 这样的一行字符串，第一个数组是宽，第二个数组是高，用c++费了好大劲一个个字符串处理的，这时候特别想念Python的split.
这题还考了边界处理，包括非法字符，两个数组长度不对等，宽<=0或高<=0的情况。不处理边界只能拿70%，别问我怎么知道的。 😣

主要思路：双指针方法
c++没有split() 方法：根据匹配给定的正则表达式来拆分字符串
难点在于io处理，我是通过string::find("],[")来把输入分割成两个字符串s1和s2，然后分别处理
如何验证字符串是否合法：处理字符串之后根据数字重构一次正确的字符串，相同则合法，否则不合法

关于输入的一个思路：先去掉所有的[和] 再用,作为分隔符划分

// 假设输入："[1,2,3],[4,5,6]"
while(getline(cin, str)){
	string str2；
	for(auto c:str){
		if(c!='['||c!=']'){
			str2+=c;
		}
	}
	# str2: "1,2,3,4,5,6"
	vector<int> width;
	vector<int> long;
	# 如果str2.size()+1是偶数则长宽不等
	int n = (str2.size()+1)/2;
	int i=0;
	for(auto c:str2){
		if(c!=','){
			if(i<n/2){
				width.push_back(c-'0');
			}
			else{
				length.push_back(c-'0');
			}
		}
	}
	
	// 然后将width，longth输入算法进行处理
} 

恰烂分：

第三题：猜数字

给定一系列字符串，并告诉你每个字符串中有多少个字符是存在的并在最终位置上，有多少个字符存在，但是位置不对。请根据它们猜出正确的字符串。
示例：字符串，存在并位置对的个数，存在但是位置不对的个数
cloxy 3 0
cxmnu 1 1
kcotd 2 1
apqud 2 0
bldwz 1 1
答案：cloud

主要思路：
回溯+dfs

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int p, n;
string w[101];
int a[101], b[101]; // a[i]代表第i个示例，w剩余未分配的正确位置正确字符
string ans = "";

// dfs(j, c) 状态：word:cloud 的第j个字符是c
// 选择： 选择与字符c匹配或者不匹配

bool dfs(int j, char c){
  for(int i=0; i<n; i++){
    // prune  base link
    if(a[i]<0 || b[i]<0 || a[i]+b[i]>(p-j)){
      return false;
    }
  }
  // 选择
  ans+=c; // 全局变量
  vector<int> st(n,0); // visited, if dfs fails, we need to use st to restore a and b

  int cnt = 0;

  // 遍历所有示例
  for(int i=0; i<n; i++){
    // c is at correct position
    if(c==w[i][j]){
      a[i]--;
      s[t]=1;
      cnt+=a[i];
    }
    else if(w[i].find(c)!=-1){ // c is at wrong position而已
      b[i]--;
      st[i]=2;
      cnt+=b[i];
    }
  }
  // cnt = a[i] + b[i] for all i
  if(j==p-1 && cnt ==0) return true; // end of dfs, check correctness

  for(char d ='a'; d<='z'; d++){ // 继续dfs
    if(ans.find(d)!=-1) continue; // d is already used
    if(dfs(j+1, d)) return true;
  }
  // 撤销选择
  ans.pop_back(); // dfs fails, restore a[i], b[i]
  for(int i=0; i<n; i++){
    if(st[i]==1){
      a[i]++；
    }
    else if(st[i]==2){
      b[i]++;
    }
  }
  return false;

}

void main(){
  cin>>p>>n;
  // p是该字符有p个字母
  // n是输入的示例有多少个
  for(int i =0; i<n; i++){
    cin>>w[i];
    cin>>a[i];
    cin>>b[i];
  }
  for(char c='a'; c<='z'; c++){
    if(dfs(0, c)){
      cout << ans << endl;
      return;
    }
  }
}