好未来笔试[整理了下大佬们的答案和自己的想法]
一个数分成几份，可以被 3 整除的最大份数。比如 12345 分成12 3 45 结果为3.
思路： 从前向后扫描，贪心： 遇到符合要求的继续下去。
- m 记录前后几个数相加之和，最大不超过3 （111 222）, c1 c2 记录单位被 3 除余1 余2 的情况， m>0 && m%3==0 || c1 >1 && c2 >2 归位
- 某个数可以被 3 整除 continue
作者：泫
链接：https://www.nowcoder.com/discuss/100031?type=2&order=0&pos=7&page=1
来源：牛客网
#include <bits/stdc++.h>
using namespace std;
int main() {
//freopen("../in.txt", "r", stdin);
string str;
cin >> str;
int i, len = str.length(), m, number, ans = 0, c1, c2;
for (i = 0, m = 0, c1 = 0, c2 = 0; i < len; i++) {
number = str[i] - '0';
//遇到3的情况直接加1
if (number % 3 == 0) {
ans++;
m = 0, c1 = 0, c2 = 0;
continue;
}
m += number;
if (number % 3 == 1)
c1++;
else
c2++;
//判断能不能有一个组合
if ((m > 0 && m % 3 == 0) || (c1 > 0 && c2 > 0)) {
ans++;
m = 0, c1 = 0, c2 = 0;
}
}
cout << ans << endl;
}
x + y = x|y 给定x, 求满足要求的第 k 个 y
思路: 位运算。把 k 的所有位从低到高填充到 x 对应为0的位上。
比如 x = 2 =0b10
k = 1 = 0b1 , y = 0b01
k = 2 = 0b10 , y = 0b100(加粗的1是因为要跳过x对应的1)
仔细想一下就知道为什么了。
作者：泫
链接：https://www.nowcoder.com/discuss/100031?type=2&order=0&pos=7&page=1
来源：牛客网
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
//freopen("../in.txt", "r", stdin);
ll t,x,k,ans,i,j,a,lenX,lenK,lenA;
int posX[160],posK[160],posA[160];
cin>>t;
while (t--){
memset(posX,0, sizeof(posX));
cin>>x>>k;
i=0,ans=0;
while (x>0){
posX[i++]=x&1;
x=x>>1;
}
lenX=i;
i=0;
while (k>0){
posK[i++]=k&1;
k=k>>1;
}
lenK=i;
for(i=0,j=0,a=0;j<lenK;i++){
if(posX[i]==0)
posA[a++]=posK[j++];
else
posA[a++]=0;
}
lenA=a;
for(i=lenA-1;i>=0;i--){
ans=ans<<1;
ans=ans|posA[i];
}
cout<<ans<<endl;
}
}
自己的代码（丑）
# coding=utf-8
import sys
if __name__ == "__main__":
n = sys.stdin.readline().strip()
for i in range(int(n)):
x, k = list(map(int, sys.stdin.readline().strip().split()))
x_bin = bin(x)[2:]
x_bin_len = len(x_bin)
x_bin_reverse = [i for i in x_bin][::-1]
k_bin = bin(k)[2:]
res = []
x_index = 0
for k_i in k_bin[::-1]:
while x_index <= x_bin_len-1 and x_bin_reverse[x_index]== "1":
res.append(0)
x_index += 1
res.append(k_i)
x_index += 1
num = "".join(list(map(str, res[::-1])))
print(int(num, 2))
给定数组[1-9] 和 boll_array[01111110], 0表示可以不输出， 1必须输出对应位，输出所有可能情况（字符串升序）
这道题不是很会，暴力递归 ac 了50多的用例。后来想了想感觉可以求多个数组的笛卡尔集。
下面是别人的ac代码。
作者：whlprogram
链接：https://www.nowcoder.com/discuss/100047?type=2&order=0&pos=7&page=1
来源：牛客网
#include<cstdio>
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<string> arr;
int main()
{
int a[11];
for(int i=0; i<10; i++)
scanf("%d",&a[i]);
for(int i=0; i<(1<<10); i++)
{
int f=0;
for(int j=0; j<10; j++)
if(!((i&(1<<j)))&&a[j])
{
f=1;
break;
}
if(f)
continue;
string str="";
for(int j=0; j<10; j++)
if(i&(1<<j))
str.push_back('0' + j);
arr.push_back(str);
}
sort(arr.begin(),arr.end());
for(int i=0; i<arr.size(); i++)
cout<<arr[i]<<endl;
return 0;
}
作者：泫
链接：https://www.nowcoder.com/discuss/100031?type=2&order=0&pos=7&page=1
来源：牛客网
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[10]={0,1,2,3,4,5,6,7,8,9};
int pos[10],i,p[10];
set<string> v;
void Print(){
string s="";
for(i=0;i<10;i++){
if(p[i]==1)
s+=a[i]+'0';
// cout<<a[i];
}
v.insert(s);
// cout<<s<<endl;
}
int main() {
// freopen("../in.txt", "r", stdin);
for(i=0;i<10;i++)
cin>>pos[i];
int add = 0,tmp;
while (1){
int flag=0;
for(i=9;i>=0;i--){
if(p[i]==0){
flag=1;
}
}
if(flag==0){
break;
}
//打印
tmp=add++;
for(i=9;i>=0;i--){
p[i]=pos[i];
if(pos[i]==0){
p[i]=tmp&1;
tmp=tmp/2;
}
}
Print();
}
set<string>::iterator it;
for(it=v.begin();it!=v.end();it++){
cout<<*it<<endl;
}
}
求期望。
n 面筛子，m面有奖，有奖继续掷筛子，没奖结束。
输入给定 score 数组 s_array, len(s_array) == n， 求期望。
数学题, e =
- ave_score = sum(s_array)/n
- (n-m)/n * avg_score (第一次就没奖)+
- m/n * (score + e) (第一次有奖，相当于从头开始)
化简得到 e = sum(s_array)/n-m
最大上升子序列和， 动态规划
题目和思路见 https://blog.csdn.net/sjf0115/article/details/8715586， 贴下大佬的代码
作者：whlprogram
链接：https://www.nowcoder.com/discuss/100047?type=2&order=0&pos=7&page=1
来源：牛客网
#include<stdio.h>
using namespace std;
int arr[100];
int maxSumIS( int arr[], int n )
{
int i, j, max = 0;
int dp[n];
for ( i = 0; i < n; i++ )
dp[i] = arr[i];
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i] > arr[j] && dp[i] < dp[j] + arr[i])
dp[i] = dp[j] + arr[i];
for ( i = 0; i < n; i++ )
if ( max < dp[i] )
max = dp[i];
return max;
}
int main()
{
int temp=0, i=0;
while(~scanf("%d", &temp)){
arr[i] = temp;
i++;
}
printf("%d\n", maxSumIS(arr, 100));
return 0;
}#好未来##笔试题目##题解#
投递小米集团等公司10个岗位