字节ES提前批7.22笔试

第一题用备忘录计算一下从1到输入最大的数的1之和，这样不会超时，第二题打家劫舍的修改版，只需要注意dp[0] dp[1]状态可能是0，第三题直接对3取模，如果为0，则分成三份相乘，如果为1，则多出来的1随便加在一份上，如果为2，那么多出来的两个1分别加到两份上

请问字节es笔试不是25号吗

   第一题还可以参考lc233 数字1的个数，按位统计1的个数，然后加起来。或许可以进一步减小时间复杂度。 public static int countByBit(int n) { if (n == 1) return 1; int t = n; int cnt = 0; if ((t & 1) == 1) {//number of 1 in the lowest digit     t = t >> 1;     cnt += (t + 1); } else {     t = t >> 1;             cnt +=t; } int mask = 1; while (t > 1) {     int prev = t >> 1;     int after = n & mask;     if ((t & 1) == 1) { cnt += (prev + 1) * (after + 1);     } else { cnt += prev * (after + 1);     }     t = prev;     mask |= (mask << 1); } cnt += (n & mask) + 1;//number of 1 in the highest digit return cnt;     }

老哥a了多少

能把第二个题仔细描述一下吗？

第一题LeetCode中的比特位计数吧？第三题是剑指offer的剪绳子吧？

第一题 找规律嘛 0   0000 1    0001 2   0010 3   0011 4   0100 5   0101 6   0110 7   0111 8   1000 9   1001 10  1010 11   1011 12  1100 13  1101 14  1110 32位整数： 第一位 0101010101010101 第二位 001100110011001100. 第三位 00001111000011110000 看出规律了嘛~

挖矿问题：打家劫舍变形题，修改一下状态转移方程

第三题 拆成两个数的知道嘛，就是把数字分解成2和3 目测拆成三个数的就是把数字分解成2 3 5 连乘

```java  public int  dig (int [] arr){         int len = arr.length;         if(len ==0 ) return 0;         if(len ==1 ) return arr[0]<0?0:arr[0];         int [] dp0 = new int[len] , dp1= new int[len] ;         dp1[0] = arr[0];         for(int i =1 ; i< len; i++){             dp1[i] = dp0[i-1] + arr[i];             dp0[i] = Math.max(dp0[i-1],dp1[i-1]);         }         return Math.max(dp0[len-1],dp1[len-1]);     } ```

第三题是拆的三个数和是n么

第一题这样不知道会不会超时额： int get_bin_num(int n ){     if(n<=1)         return n;     int sum = 0;     vector<int> buffer(n+1, 0);     buffer[1] = 1;     for(int i = 0; i<=n; ++i){         int buffer_value = 0;         if(i % 2 == 0){             buffer_value = buffer[ i / 2 ];         }         else{             buffer_value = buffer[i/2] + 1;         }         buffer[i] = buffer_value;         sum += buffer[i];     }     return sum; }