字节跳动2019春招研发部分编程题解析

万万没想到之聪明的编辑

这一题有点绕，写了好久。利用状态机来写，可以分出三种状态来。

#include <iostream>
using namespace std;
int n;
void solve(string& a) {
    int sz = a.size();
    int cnt1 = 1, cnt2 = 0;
    string ans;
    ans = a[0];
    // cnt1 [1, 2]   cnt2 : [0, 1]
    for(int i = 1; i < sz; ++i) {
        if(a[i] == a[i-1]) {
            if(cnt1 != 2 && cnt2 != 1) ans += a[i]; 
        }else ans += a[i];
        int ssz = ans.size();
        cnt1 = 1, cnt2 = 0;
        if(ssz >= 2 && ans[ssz - 1] == ans[ssz - 2]) cnt1 = 2, cnt2 = 1;
        else if(ssz >= 3 && ans[ssz - 2] == ans[ssz - 3]) cnt2 = 1;
    }
    cout << ans << endl;
}
int main() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        string a;
        cin >> a;
        solve(a);
    }
}

万万没想到之抓捕孔连顺

枚举起始点 + 滑动窗口 + 组合数

#include <iostream>
using namespace std;
int n, d;
int A[1000008];
const int mod = 99997867;
void solve() {
    int i = 0, j = 1;
    long long ans = 0;
    for(; i < n - 2; ++i) {
        while(j < n && A[i] + d >= A[j]) ++j;
        int cnt = j - i;
        if(cnt >=3) {
            ans = (ans + (long long)(cnt - 1) * (cnt - 2) / 2) % mod;
        }
    }
    cout << ans << endl;
}
int main () {
    cin >> n >> d;
    for(int i = 0; i < n; ++i)
       cin >> A[i];
    solve();
}

雀魂启动！

第一次写的时候，觉的逻辑上挺对的，但是就过不了，非常纳闷。直到看了别人的解答，才发现自己读错题了，四张顺子或刻子，我理解成了四张顺子或四张刻子

• 枚举可能添加的牌
  • 枚举可能的雀头
    • 利用dfs来检查剩余的牌是否可以构成四张顺子或刻子 （其实就是枚举刻子，检验剩下的牌是否构成顺子，每个大于3张的牌型可以选择作为刻子或不作为刻子）

这题写起来有些复杂。

#include <iostream>
#include <cstring>
using namespace std;
int A[14];
bool check_shunzi(int *cnt_) {
     int cnt[10];
     for(int i = 0; i < 10; ++i) cnt[i] = cnt_[i];
     for(int i = 1; i < 10; ++i) {
          while(cnt[i] > 0) {
              --cnt[i];
              if(i + 1 < 10 && cnt[i + 1] > 0) cnt[i+1]--;
              else return false;
              if(i + 2 < 10 && cnt[i + 2] > 0) cnt[i+2]--;
              else return false;
          }
     }
     return true;
}
bool dfs(int *cnt, int i) {
    if( i == 10 ) {
          return check_shunzi(cnt);
    }
    bool state = false;
    if(cnt[i] >= 3) {
        cnt[i] -= 3;
        state = dfs(cnt, i+1);
        cnt[i] += 3;
    }
    state = state || dfs(cnt, i+1);
    return state;
} 
bool check(int i) {
    A[13] = i;
    int cnt[10];
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < 14; ++i) {
        cnt[A[i]]++;
        if(cnt[A[i]] > 4) return false;
    }
    
    // enum 雀头
    for(int i = 1; i < 10; ++i) {
        if(cnt[i] >= 2) {
            cnt[i] -= 2;
            bool state = dfs(cnt,1);
            cnt[i] += 2;
            if(state) return true;
        }
    }
    return false;
}
void solve() {
    int flag = 0;
    for(int i = 1; i < 10; ++i) {
        if(check(i)) {
            cout << i << " ";
            flag = 1;
        } 
    }
    if(flag == 0) cout << 0 ;
}
int main() {
    for(int i = 0; i < 13; ++i)
      cin >> A[i];
    solve();
}

特征提取

暴力 + 哈希查找 （没想到这样可以过）
原本想用unordered_set的，可以降低一些时间复杂度，但是不能存pair，也不能存vector。

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int n, m;
void solve(vector<set<pair<int,int>>>& A, set<pair<int,int>>& All) {
    int ans = 0, seq = 0, sz = A.size();
    for(auto &p:All) {
        seq = 0;
        for(int i = 0; i < sz; ++i) {
            if(A[i].count(p)) ++seq;
            else {
                if(seq > ans) ans=seq;
                seq = 0;
            }
        }
        ans = max(ans, seq);
    }
    
    cout << ans << endl;
}
int main() {
   cin >> n;
   while(n--) {
       cin >> m;
       vector<set<pair<int,int>>> A(m);
       set<pair<int,int>> All;
       for(int i = 0; i < m; ++i) {
           int k;
           cin >> k;
           for(int j = 0; j < k; ++j) {
               int x, y;
               cin >> x >> y;
               A[i].insert({x, y});
               All.insert({x, y});    
           }
           
       }
       solve(A, All);
   }
}

毕业旅行问题

经典问题 哈密顿回路
使用dp来解，第一次做应该很难做出来。

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
int G[20][20];
int n;
void solve() {
    int mask_limit = pow(2, n);
    int dp[mask_limit][n];
    
    for(int mask = 0; mask < mask_limit; ++mask) {
        for(int i = 0; i < n; ++i) {
            if(mask & (1<<i)) continue;
            dp[mask][i] = INT_MAX;
            if(mask == 0) dp[mask][i] = G[0][i];
            else {
                for(int j = 0; j < n; ++j) {
                if(mask & (1<<j)) {
                        dp[mask][i] = min(dp[(mask ^ (1<<j))][j] + G[j][i], dp[mask][i]);
                    }
                }    
            } 
        }
    }
    cout << dp[((mask_limit - 1) ^ 1)][0] << endl;
}
int main() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j)
           cin >> G[i][j];
    }
    solve();
}

找零

一个"简单"的贪心问题 （贪心的证明往往都不容易）

证明:
当找回钱为$yy$时的最优解 = 一个最大的硬币x($max(x\le y,x\in \{1,4,16,64\}max(x\; \backslash le\; y,\; x\; \backslash in\; \backslash \{1,\; 4,\; 16,\; 64\backslash \}$) + 当找回钱为$(y-x)(y-x)$时的最优解

假设存在一个最优解不包含x，那么就该解的总钱数是小于y的， 与该解为可行解矛盾。
为什么小于y？
因为是最优解，所以一定不存在1、4、16的个数一定不超过3。
当x为4时，只能由1构成，而个数不超过3，故无法构成可行解。
当x为16时， 只能由1和4构成，而个数也都不能超过3， 故无法构成可行解。
当x为64时，类似。

#include <iostream>
using namespace std;
int n;
const int money[] = {1,  4, 16, 64};
void solve() {
    int ans = 0;
    for(int i = 3; i >= 0; --i) {
        ans += n/money[i];
        n = n % money[i];
    }
    cout << ans  << endl;
}
int main() {
    cin >> n;
    n = 1024 - n;
    solve();
}

机器人跳跃问题

二分 + 注意溢出

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int A[100005];
bool check(int t, int max_value) {
    for(int i = 0; i < n; ++i) {
        t += (t - A[i]);
        if(t >= max_value) return true;
        if(t < 0) return false;
    }
    return true;
}
void solve() {
    int left = 0, max_value = *max_element(A, A + n), right = max_value;
    while(left <= right) {
        int middle = (left + right) / 2;
        if(check(middle, max_value))
            right = middle - 1;
        else left = middle + 1;
    }
    cout << left << endl;
}
int main() {
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> A[i];
    solve();
}