字节跳动19.03.16研发笔试高效率题解(含复杂度分析)
1.签到题,用位操作会比较高效,简单耍一下,[时间复杂度O(1),空间复杂度O(1)]
#include <cstdio> int main(int n) { scanf("%d", &n) ; n = 1024-n ; for (int i = 3, cnt = 0; i-- || !printf("%d\n", cnt+n); n >>= 2) cnt += n&0x03 ; return 0 ; }
2.字符串操作,循环就好了,新开一个字符串应该可以以空间换时间(不用移动后面的字符)[时间复杂度O(n),空间复杂度O(n)]
因为题目没有给出字符串长度,不知道开多大数组于是用了string
#include <iostream> #include <string> using namespace std ; int main(void) { int n ; cin >> n ; while (n--) // case数 { string str ; cin >> str ; // 如果字符串长度小于等于2就不需要调整,直接输出 if (str.size() < 3) { cout << str << endl ; continue ; } string res(str, 0, 2) ; char pre3 = -1 ; char pre2 = str[0] ; char pre1 = str[1] ; for (auto ch = str.cbegin()+2; ch != str.cend(); ++ch) { if (pre1 == *ch) { if (pre2 == pre1 || pre2 == pre3) continue ; } res += *ch ; pre3 = pre2 ; pre2 = pre1 ; pre1 = *ch ; } cout << res << endl ; } return 0 ; }
3.dfs,分四种情况,比左右低给1个奖品,比左右高给max(左、右奖品数)+1,剩下的,比左高给左奖品+1,比右高给右奖品+1,[时间复杂度O(n),空间复杂度O(n)]
#include <cstdio> #include <cstring> #include <iostream> #define MAX 101000 using namespace std ; int arr[MAX] ; int score[MAX] ; int num ; inline int index(int i) { if (i < 0) return i+num ; else if (i >= num) return i-num ; else return i ; } int fun(int i) { i = index(i) ; if (score[i] > 0) return score[i] ; const int l = arr[index(i-1)] ; const int r = arr[index(i+1)] ; if (arr[i] <= l && arr[i] <= r) return score[i] = 1 ; else if (arr[i] > l && arr[i] > r) return score[i] = 1 + max(fun(i-1), fun(i+1)) ; else if (arr[i] > l) return score[i] = 1 + fun(i-1) ; else if (arr[i] > r) return score[i] = 1 + fun(i+1) ; else fprintf(stderr, "error") ; return 0 ; } int main(void) { int N ; scanf("%d", &N) ; // case数 while (N--) { scanf("%d", &num) ; // 人数 for (int i = 0; i < num; ++i) scanf("%d", &arr[i]) ; memset(score, -1, sizeof(score)) ; for (int i = 0; i < num; ++i) { if (score[i] < 0) fun(i) ; } int total = 0 ; for (int i = 0; i < num; ++i) total += score[i] ; cout << total << endl ; } return 0; }
4.先对绳子长度排序,以便试探是否可行的时候剪枝。再折半查找,我只过了90%,后来觉得是精度问题,换成整型也过不了。看另一个帖子精确到0.00001能过,没想明白为什么保留两位小数要精确到0.00001,求大佬指导, 同时贴上错误代码[时间复杂度O(nlogn),空间复杂度O(1)]
// 注意这是错误的示例 // 注意这是错误的示例 // 注意这是错误的示例 #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <iostream> typedef long long ll ; using namespace std ; int N, M ; ll arr[100100] ; ll maxLength = -1 ; inline bool fun(ll len) { int cnt = 0 ; for (int i = 0; i < N; ++i) { if (len > arr[i]) return false ; cnt += arr[i]/len ; if (cnt >= M) return true ; } return false ; } bool cmp(ll a, ll b) { return a > b ; } int main(void) { maxLength = -1 ; scanf("%d%d", &N, &M) ; for (int i = 0; i < N; ++i) { scanf("%d", &arr[i]) ; arr[i] *= 100 ; maxLength = max(maxLength, arr[i]); } sort(arr, arr+N, cmp) ; ll low = maxLength / N ; ll high = maxLength + 10 ; while ( high > low ) { ll mid = low + ((high-low)>>1) ; if (mid == 0) break ; if ( fun(mid) ) low = mid + 1 ; else high = mid ; } if (low <= 0) printf("0.00\n") ; else printf("%.2lf\n", (low-1)/100.0) ; return 0; }
#字节跳动##题解##笔试题目##春招##内推##实习#