好未来笔试[整理了下大佬们的答案和自己的想法]

一个数分成几份,可以被 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;
}
#好未来##笔试题目##题解#
全部评论
好帖啊老哥 第三题暴力递归也能过
点赞 回复
分享
发布于 2018-08-28 23:02
// 三整除那道题 #include <iostream> #include <vector> #include <string> using namespace std; bool judge(string &str) { int res = 0; for(auto c : str) res += (c - '0'); return (res % 3 == 0); } int fun(const string &str) { if(str.empty()) return 0; int len = str.size(); vector<vector<int>> dp(len + 1, vector<int>(len + 1, 0)); for(int i = 1; i <= len; ++i) { for(int j = 1; j <= len - i + 1; ++j) { for(int k = 1; k < i; ++k) { dp[j][j + i - 1] = max(dp[j][j + i - 1], dp[j][j + k - 1] + dp[j + k][j + i - 1]); } string tmp = str.substr(j - 1, i); if(judge(tmp)) dp[j][j + i - 1] = max(1, dp[j][j + i - 1]); } } return dp[1][len]; } int main() { string str; cin >> str; cout << fun(str) << endl; return 0; }
点赞 回复
分享
发布于 2018-08-28 23:05
百信银行
校招火热招聘中
官网直投
第四题,我的解法类似于树的广度优先遍历,用到了队列
点赞 回复
分享
发布于 2018-08-28 23:28
这些全部是ac的?
点赞 回复
分享
发布于 2018-08-28 23:40
第三题: #include <iostream> #include <string> #include <vector> using namespace std; void dfs(vector<int> & flags,int start,vector<string> & ans,string tmp) {     if (start == flags.size()) {         ans.push_back(tmp);         return;     }     dfs(flags,start+1,ans,tmp+to_string(start));     if(flags[start] == 0)         dfs(flags, start + 1, ans, tmp);          } int main(void) {     int tmp;     while(cin>>tmp) {         vector<int> flags;         vector<string> ans;         flags.push_back(tmp);         for (int i = 1; i < 10;++i) {             cin >> tmp;             flags.push_back(tmp);         }         dfs(flags, 0, ans, ""); sort(ans.begin(),ans.end());       for (auto x : ans)             cout << x << endl;     } } 使用了backtrace,注意解空间是类似于二叉树,当然也可以使用数组的解空间,但是比较繁琐。
点赞 回复
分享
发布于 2018-08-29 15:44
马克一下,很强
点赞 回复
分享
发布于 2018-08-29 16:10
char* ReplaceSubStr(const char* str, const char* srcSubStr, const char* dstSubStr,char * out) {     /* 基本思路:迭代,然后使用双指针跟踪目标地址,和原地址,有点归并排序中合的味道。 注意:python、C++、Java中都有相应比较方便的库,但是本题就是想考察造轮子的过程,但是 可以使用C语言的库。 */ int i;     const char * ptr_str;     char * ptr_out=out;     for (i=0; i<strlen(str);) {         if ((ptr_str = strstr(str + i, srcSubStr)) == NULL) {             memcpy(ptr_out, str+i,strlen(str + i)+1);             break;         }         else {             memcpy(ptr_out, str + i, ptr_str - (str + i));             ptr_out += ptr_str - (str + i);             memcpy(ptr_out, dstSubStr, strlen(dstSubStr));             ptr_out += strlen(dstSubStr);             i = ptr_str - str + strlen(srcSubStr);         }     }     return out; }
点赞 回复
分享
发布于 2018-08-29 16:52

相关推荐

点赞 85 评论
分享
牛客网
牛客企业服务