首页 > 华为8.26笔试开发岗思路分享(C++,1+1+0.9)
头像
js8544
编辑于 2020-08-27 08:02
+ 关注

华为8.26笔试开发岗思路分享(C++,1+1+0.9)

1. 按照题目要求实现即可
int n;
unsigned int arr[1001];
unsigned int ans[1001];
void solve() {
  memset(ans, 0, sizeof(ans));
  memset(arr, 0, sizeof(arr));
  int n = 0;
  while (cin >> arr[n++])
    ;
  n--;
  for (int i = 0; i < n; i++) {
    unsigned int x = 0;
    for (int j = 0; j < 32; j += 2) {
      // Swap bits for each pair
      x += (arr[i] & (1 << j)) << 1;
      x += (arr[i] & (1 << (j + 1))) >> 1;
    }
    arr[i] = x;
  }

  unsigned int mask = 3;  // 0...011

  // Shift bits
  for (int i = 0; i < n; i++) {
    int j = (i + 1) % n;
    ans[j] = (arr[i] & mask) << 30;
    ans[j] += arr[j] >> 2;
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
}

2. 题目不难,遍历所有区间找结果即可,用了前缀和来优化。难点在于io处理,我是通过string::find("],[")来把输入分割成两个字符串s1和s2,然后分别处理。如何验证字符串是否合法:处理字符串之后根据数字重构一次正确的字符串,相同则合法,否则不合法。(吐槽:C++不知道什么时候才能加入split方法)
int n;
int w[101]; // width
int h[101]; // height
int pre[101]; // prefix sum
void solve() {
  char c;
  string s;
  cin >> s;
  int b = s.find("],[");
	// Divide into 2 substrings according to b.
  string s1 = s.substr(1, b - 1);
  string s2 = s.substr(b + 3, b - 1);

	// Use stringstream to parse data
  stringstream ss1(s1), ss2(s2);
  int n = 0;

	// read width
  while (!ss1.eof()) {
    ss1 >> w[n++];

    if (w[n - 1] < 1 || w[n - 1] > 100) {
      P1(0);
      return;
    }
    if (ss1.eof()) break;
    ss1 >> c;
  }

	// read height
  n = 0;
  while (!ss2.eof()) {
    ss2 >> h[n++];

    if (h[n - 1] < 1 || h[n - 1] > 100) {
      P1(0);
      return;
    }
    if (ss2.eof()) break;
    ss2 >> c;
  }

	// reconstruct input
  string cs; // correct string
  cs += "[";
  cs += w[0] + '0';
  for (int i = 1; i < n; i++) {
    cs += ',';
    cs += w[i] + '0';
  }
  cs += "],[";
  cs += h[0] + '0';
  for (int i = 1; i < n; i++) {
    cs += ',';
    cs += h[i] + '0';
  }
  cs += "]";
  if (cs != s) {
    P1(0);
    return;
  }
  
	// solve 
  pre[0] = 0;
  for (int i = 0; i < n; i++) {
    pre[i + 1] = pre[i] + w[i];
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      int wi = pre[j + 1] - pre[i];
      int he = INT_MAX;
      for (int k = i; k <= j; k++) {
        he = min(he, h[k]);
      }
      ans = max(wi * he, ans);
    }
  }
  cout<<ans<<endl;
}
3. dfs加剪枝。dfs(j,c)代表第j个字符是c。w是输入单词,a数组代表w剩余未分配的正确位置正确字符,b代表w剩余未分配的错误位置正确字符。如果w[j]==c,则a[i]--,如果c在w的其他位置,则b[i]--,然后继续dfs。剪枝条件是:1. a[i]<0, 2. b[i]<0, 3. a[i]+b[i] > p-j (即后续长度不够分配这么多正确字符)。

int p, n;
string w[101];       // words
int a[101], b[101];  // a: correct position, b: incorrect position
string ans = "";

bool dfs(int j, char c) {
  for (int i = 0; i < n; i++) {  // prune
    if (a[i] < 0 || b[i] < 0 || a[i] + b[i] > (p - j)) {
      return false;
    }
  }

  ans += c;
  vector<int> st(n, 0);  // if dfs fails, we need to use st to restore a and b
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if (c == w[i][j]) {  // c is at correct position
      a[i]--;
      st[i] = 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++) {  // continue 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 solve() {
  cin >> 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;
    }
  }
}
举例:
5
5
cloxy 3 0
cxmnu 1 1
kcotd 2 1
apqud 2 0
bldwz 1 1
开始:a = {3,1,2,2,1}, b = {0,1,1,0,1}
正确路线:
dfs(0,c): a = {2,0,2,2,1}, b = {0,1,0,0,1} (因为i=0,1,c是正确字符,i=2, w包含c但是在错误位置)
-->dfs(1,l) : a = {1,0,2,2,0}, b = {0,1,0,0,1}
---->dfs(2,o): a = {0,0,1,2,0}, b = {0,1,0,0,1}
------>dfs(3,u): a = {0,0,1,1,0}, b = {0,0,0,0,1}
-------->dfs(4,d): a = {0,0,0,0,0}, b = {0,0,0,0,0} 返回正确结果
错误路线举例:
cloxy:
dfs(0,c): a = {2,0,2,2,1}, b = {0,1,0,0,1}
-->dfs(1,l) : a = {1,0,2,2,0}, b = {0,1,0,0,1}
---->dfs(2,o): a = {0,0,1,2,0}, b = {0,1,0,0,1}
------>dfs(3,x): a = {-1,0,1,2,0}, b = {0,-1,0,0,1} 有负数,返回错误

abijk:
dfs(0,a): a = {3,1,2,1,1}, b = {0,1,1,0,1}
-->dfs(1,b): a = {3,1,2,1,1}, b = {0,1,1,0,0}
---->dfs(2,i): a = {3,1,2,1,1}, b = {0,1,1,0,0}
------>dfs(3,j}: a[0]+b[0] = 3 > p-j = 2 后续字符不够分配三个正确字母,返回错误

后续优化思路:这题只过了90%,应该是超时。考虑:因为每个字母只会出现一次,因为可以用bitmap来保存字母是否出现过,用string::find是线性时间,bitmap可以达到O(1)时间。第一次写dfs加剪枝,写的太慢没时间改了。



全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐