IT笔试加分利器

登录 注册

  • 主页/
  • 360春招&实习生招聘3.25在线编程题解
精华 360春招&实习生招聘3.25在线编程题解
发布于 2017-03-25 21:10 8374 次浏览 1 赞 最后一次编辑是 2017-03-28 13:02 来自 笔试面试  

求职360的同学可以加入奇虎360的交流群：436627572 ，供大家在此交流后续面试及职位信息。


以下为原题链接及文字题解


数学期望：

http://exercise.acmcoder.com/online/online_judge_ques?ques_id=3981&konwledgeId=42

偶串：

http://exercise.acmcoder.com/online/online_judge_ques?ques_id=3980&konwledgeId=42


任务列表：

http://exercise.acmcoder.com/online/online_judge_ques?ques_id=3982&konwledgeId=42


数学期望：

简单数学知识，直接实现公式。

示例代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	scanf("%d", &n);
	double ans = 0;
	for(int i = 0; i < n; i++){
		int x, p;
		scanf("%d%d", &x, &p);
		ans += 1.0 * x * p / 100;
	}
	printf("%.3f\n", ans);
	//system("pause");
	return 0;
}


偶串：

用二进制表示每个字母出现的奇偶性，在采用类似前缀和的方法求解。

示例代码：

#include <bits/stdc++.h>
#define maxn 100009
using namespace std;
char s[maxn];
map<int,int>mp;
int n;
int main(){
    scanf("%s",s);
    n = strlen(s);
    mp[0] = 1;
    int cur = 0;
    long long ans = 0;
    for(int i = 0; i < n; i++){
        int x = s[i] - 'a';
        cur ^= (1 << x);
        ans += mp[cur];
        mp[cur]++;
    }
    cout << ans << endl;
    return 0;
}


任务列表：

预处理出机器空闲的时间点，二分答案。

示例代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>

using namespace std;
const int maxn = 111111;
int a[maxn];


int solve(int left, int right) {
	int idx;
	int start = left;
	while (left <= right) {
		int mid = (left + right) >> 1;
		if (a[mid] - a[start] == mid - start) {
			left = mid + 1;
			idx = mid;
		}
		else {
			right = mid - 1;
		}
	}
	return a[idx] + 1;
}

int main() {
	//freopen("task.in", "r", stdin);
	//freopen("task.out", "w", stdout);
	int n, m;
	while (~scanf("%d%d", &n, &m)) {
		for (int i = 0; i < n; i++) {
			scanf("%d", a + i);
		}
		while (m--) {
			int q; scanf("%d", &q);
			int idx = lower_bound(a, a + n, q) - a;
			if (idx == n || a[idx] != q) {
				printf("%d\n", q);
			}
			else {
				printf("%d\n", solve(idx, n - 1));
			}
		}
	}
}


以上思路供同学们参考，也希望同学能分享自己的经验

回帖 赞(1) 收藏 印章
32 条回复 
import java.util.ArrayList;
import java.util.Scanner;
 

public class Main {
    
   
    public static void main(String[] args) {
        // 输入：
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        
        int[] list = new int[M];
        int[] mark = new int[M];
        ArrayList<Integer> taskList = new ArrayList<Integer>();
        ArrayList<Integer> tempTask = new ArrayList<Integer>();
        int count = 0;
        while (in.hasNextInt()) {
            taskList.add(in.nextInt());
            count++;
            if (count == N) {
                break;
            }
        }
        count = 0;
        while (in.hasNextInt()) {
            tempTask.add(in.nextInt());
            count++;
            if (count == M) {
                break;
            }
        }
        
        in.close();
        
        
        if(taskList.get(0) != 1){
            for(int i = 0;i< M;i++)
                if(tempTask.get(i) == 1){
                    list[i] = 1;
                    mark[i] = -1;
                }
        }
        else{
            for(int i = 1; i < N; i++){
                if(taskList.get(i) - taskList.get(i - 1) >= 2){
                    for(int j = 0;j< M;j++){
                        if(mark[j] == -1)
                            continue;
                        if(tempTask.get(j) <= taskList.get(i - 1) + 1){
                            list[j] = taskList.get(i - 1) + 1;
                            mark[j] = -1;
                        }
                        if(tempTask.get(j) > taskList.get(i - 1) + 1 && tempTask.get(j) < taskList.get(i)){
                            list[j] = tempTask.get(j);
                            mark[j] = -1;
                        }
                    }
                }
            }
        }
        for(int i = 0;i< M;i++){
            if(mark[i] == -1)
                continue;
            if(tempTask.get(i) <= taskList.get(N-1) + 1){
                list[i] = taskList.get(N-1)+1;
                mark[i] = -1;
            }
            if(tempTask.get(i) > taskList.get(N-1) + 1 ){
                list[i] = tempTask.get(i);
                mark[i] = -1;
            }
        }
        
        for(int i = 0;i < M;i++)
            System.out.println(list[i]);
        
   
    } 
   
}

第三题贴个Java版本的吧，比较粗糙，可惜输出代码多了一个“ok”

2017-03-25 21:16

问题3：java版

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public void fingEmpty(int[] array, int[] tmpArray) {
        ArrayList<Integer> list = new ArrayList<>(); //保存可以使用的值
        for (int i = 1; i < array[0]; i ++) {
            list.add(i);
        }

        ArrayList<Integer> numberInArray = new ArrayList<>();
        for (int val : array) {
            numberInArray.add(val);
        }

        for (int i = array[0]; i < array[array.length - 1]; i ++) {
            if (!numberInArray.contains(i)) {
                list.add(i);
            }
        }
        list.add(array[array.length - 1] + 1);


        ArrayList<Integer> result = new ArrayList<>();

        for (int j = 0; j < tmpArray.length; j ++) {
            for (int i = 0; i < list.size(); i ++) {
                if (tmpArray[j] <= list.get(i)) {
                    result.add(list.get(i));
                    break;
                }
            }
        }
        for (int val : result) {
            System.out.println(val);
        }
    }


    public static void main(String[] args) {
        Main main = new Main();
//        int[] array = new int[] {1,2,3,5,6};
//        int[] tmpArray = new int[]{3,2,1,4,5,6};
//        main.fingEmpty(array, tmpArray);
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int N = sc.nextInt();
            int M = sc.nextInt();
            int[] array = new int[N];
            int[] tmpArray = new int[M];
            for (int i = 0; i < N; i ++) {
                array[i] = sc.nextInt();
            }
            for (int i  =0; i < M; i ++) {
                tmpArray[i] = sc.nextInt();
            }
            main.fingEmpty(array, tmpArray);
        }


    }
}


2017-03-25 21:21
1 
import java.util.Scanner;

public class Main {
	static int t[];
	static int q[];
	static int q_time[];
	static int n;
	static int m;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		t = new int[n];
		q = new int[m];
		q_time = new int[m];
		int i = 0;
		while(i < n){
			t[i] = scan.nextInt();
			i++;
		}
		i = 0;
		while(i < m){
			q[i] = scan.nextInt();
			i++;
		}
		
		int t_min = t[0];
		search(t_min);	
		
		for(i=1; i<n; i++){
			search(t[i]);
		}
		
		for(i=0; i<m; i++){
			if(q[i] != 0){
				q_time[i] = q[i];
			}
		}
		
		for(i=0; i<m; i++){
			System.out.println(q_time[i]);
		}
		
	}
	
	public static void search(int t){
		for(int i=0; i<m; i++){
			if(q[i] < t && q[i] != 0){
				q_time[i] = q[i];
				q[i] = 0;
			}else if(q[i] == t){
				q[i] = q[i] + 1;
			}
		}
	}

}


第三题，我是这样写的，自己测数据能过，为什么给wrong?

2017-03-25 21:21

第一题期望的那个题中说的是四舍五入，题解没四舍五入啊==

2017-03-25 21:22

var timeArray = [];

var lineCount = 1;

var taskList = [];

var taskLS = [];

var freeTime = [];

while(line = read_line()){

  line = line.trim();

  if (lineCount ==2) {

    taskList = line.split(' ');


  }

  if (lineCount > 2) {

    taskLS.push(parseInt(line));

  }

  lineCount++;

}

var listlength = taskList.length

for(var i = 0; i<listlength;i++){

  taskList[i] = parseInt(taskList[i]);

}

for(var j = taskList.length - 1; j > 0; j++){

  var gap = taskList[j] - taskList[j-1];

  if (gap > 1) {

    var current = taskList[j]-1;

    while(current>taskList[j-1]){

      freeTime.push(current);

      current--;


    }

  }

}

freeTime = freeTime.reverse();

var lslength = taskLS.length;

for(var z=0; z < lslength; z++){

  sss:

  for(var k =0; k<freeTime.length; k++){

    if (taskLS[z]<=freeTime[k]) {

      timeArray[z] = freeTime[k];

      break sss;

    }


    else timeArray[z] = taskList[taskList.length-1];

  }

}

var timeLength = timeArray.length;

for(var y = 0;y<timeLength; y++){

  print(timeArray[y]);

}


2017-03-25 21:23 


int main() {
    int n = 0;
    int m = 0;
    cin >> n;
    cin >> m;
    if (m == 0) return 0;
    int* temp_task = new int[m];
    int* task = new int[n];
    int* res = new int[m];
    memset(res, 0, m * sizeof(int));
    for (int i = 0; i < n; ++i) {
        cin >> task[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> temp_task[i];
    }
    for (int i = 1, j = 0; i <= task[n-1] + 1; ++i) {
        if (i == task[j]) { //非空闲
            ++j;
            continue;
        }//空闲时间
        for (int k = 0; k < m; ++k) {
            if (res[k] == 0 && temp_task[k] <= i) {
                res[k] = i;
            }
        }
    }
    for (int i = 0; i < m; ++i) {
        cout << res[i] << endl;
    }
    return 0; 
}


2017-03-25 21:25
acmcoderf9AWMSR6 回复 acmcoderyBZnhJgS ：

.3f 就是四舍五入啊 您不写c/cpp吧
2017-03-25 21:25
acmcoderyBZnhJgS 回复 acmcoderf9AWMSR6 ：

我以为.3f是直接截断呢
2017-03-25 21:27 
var T = 'abbb';
function search(str,low){
      var high=[];
      var len = str.length;
      var obj={};
      var x = false;
      for(var i=low;i<len;i++){
            x = true;
            if(!obj.hasOwnProperty(str[i])){
              obj[str[i]]=1;
            }else{
              obj[str[i]]=0;
            }
            for(var key in obj){
                  if(obj[key]==1) x=false;
            }
            if(x==true){
                  high.push(i);
            } 
      }
      return high;
}

var low=0;
var high=0;
var len = T.length;
var result = 0;
while(low<len){
  low = low+1;
  var high = search(T,low);
  result+=high.length;
  
}

console.log(result)


2017-03-25 21:29
小网 回复 acmcoderyBZnhJgS ：

在题目给定的数据范围下， 小数点后从第三位开始一定全是0.
2017-03-25 21:30

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int birany_search(vector<int>&container, int target)

{

for(int i = 0; i < container.size(); ++i)

{

if (target <= container[i])

{

return (i >= 1 ? i - 1 : -1);

}

}

return container.size() - 1;

//int left = 0;

//bool find_that = false;

//int right = container.size();

//int mid = (left + right) / 2;

//while (left < right)

//{

// if (target > container[mid])

// {

// right = mid - 1;

// }

// else if (target < container[mid])

// {

// left = mid + 1;

// }

// else

// {

// find_that = true;

// break;

// }

//}

//if (find_that)

//{

// for(int i = mid; i >= 0; --i)

// {

// if (container[i] != target)

// {

// left = i;

// }

// }

//}

//return left;

}


int main()

{

int n, m;

cin >> n >> m;

vector<int>plan(n);

for(int i = 0; i < n; ++i)

{

int mission;

cin >> mission;

plan[i] = mission;

}

vector<int>temp_list(m);

for(int i = 0; i < m; ++i)

{

int mission;

cin >> mission;

temp_list[i] = mission;

}

sort(plan.begin(), plan.end());

sort(temp_list.begin(), temp_list.end());

int i;

for(i = 1; i < plan.size(); ++i)

{

if (plan[i] != plan[i - 1] + 1)

{

int index = birany_search(temp_list, plan[i]);

if (index >= 0)

{

for (int j = 0; j <= index; ++j)

{

if (temp_list[j] <= plan[i - 1] + 1)

{

cout << plan[i - 1] + 1 << endl;

}

else

{

cout << temp_list[j] << endl;

}

}

temp_list.erase(temp_list.begin(), temp_list.begin() + index + 1);

}

}

}


if (!temp_list.empty())

{

for(int j = 0; j < temp_list.size(); ++j)

{

cout << plan[i - 1] + 1 << endl;

}

}

// system("pause");

    return 0;

}

二分搜索出bug来不及调，最后都不知道自己是否AC

2017-03-25 21:32 
#include  <iostream> 
#include<stdio.h>
using namespace std;
int main()
{
     int i;
	 int count;
	 int x,p;
	 double array1[100],array2[100],array3[100];
	 double sum=0;
	 scanf("%d",&count);
	 for(i=0;i<count;i++)
	 {
		cin>>x;
		cin>>p;
		array1[i]=x;
		array2[i]=p;
		array3[i]=array2[i]/100;
		sum=sum+array1[i]*array3[i];
	 }
	 printf("%.3lf\n",sum);
      return 0;
}


2017-03-25 21:42

//不知道有没有ac，在本地通过了样例数据，也是查找的思想，只是用容器vector的find代替了。另外，有同学把第二题的分析思路分享一下吗，不是很懂。

#include<iostream>

#include<vector>

#include<string>

#include<sstream>

#include<algorithm>

using namespace std;

int main(){

int n,m,a,b;

vector<int> data;

vector<int> res;

cin>>n>>m;

cin.ignore();

string line;

getline(cin,line);

istringstream iss(line);

   while(iss>>a)   

   {

         data.push_back(a);

         iss.clear();

   }

      

    vector<int>::iterator it=data.begin();

    while(cin>>b)

    {

        it=find(data.begin(),data.end(),b);  

      

        if(it==data.end())

        {

          res.push_back(b); 

           }else{

                while(*it++==b++){}

                b--;

                res.push_back(b); 

           }  

         }

         

           for(auto r:res){

         cout<<r<<endl;

          }

    } 


2017-03-25 21:45 
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;
const int maxn=1<<26;
bool vs[30];
long long int total[maxn];
int get_status()
{
    int now=0,d=1;
    for(int i=0;i<26;i++)
    {
        if(vs[i])
            now+=1*d;
        d<<=1;
    }
    return now;
}

inline long long int C(long long int num)
{
    return num*(num-1)/2;
}

int main(void)
{
    ios::sync_with_stdio(false);
    long long int ans=0;
    int status;
    string str;
    cin >> str;
    for(int i=0;i<str.size();i++)
    {
        vs[str[i]-'a']=(vs[str[i]-'a']^1);
        status=get_status();
        total[status]++;
    }
    for(int i=0;i<maxn;i++)
        ans+=C(total[i]);
    cout << ans+total[0] << endl;
    return 0;
}



2017-03-25 21:53

第一题；

#include <stdio.h>

using namespace std;
int main()
{
 int n;
 int data;
 int p;
 scanf("%d",&n);
 int i=0;
 
 double result=0;
 int j=0;
 while(scanf("%d %d",&data,&p))
 {
       
       j++;
	   result += data*p/100.0;
	  
       if(j==n)
             printf("%.3f",result);
 }

 return 0;
}

这是我的程序，本地VS2010测试没有问题，但是在平台上提交就是不对。。。。。。


2017-03-25 22:03
小网 回复 coder_PBVRQRER ：

while(scanf("%d %d",&data,&p) !=EOF) 试试
2017-03-25 22:07

woc 3题赛上改了一年bug一直14%, 刚刚改了个变量就A了. 那么这14%数据到底是有多水啊..

2017-03-25 22:16
acmcoderf9AWMSR6 回复 Holy ：

你这不用仔细看就知道会TLE…
2017-03-25 22:20

第三题Java版 已AC：

import java.util.Arrays;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int m = scanner.nextInt();

int[] taskn = new int[n];

int[] taskm = new int[m];

for (int i = 0; i < n; i++) {

taskn[i] = scanner.nextInt();

}

for (int i = 0; i < m; i++) {

taskm[i] = scanner.nextInt();

}

Arrays.sort(taskn);// 升序排序


int index = 0;

int tt[] = new int[taskn[n - 1] * 2];

boolean flag = false;

for (int i = 1; i <= taskn[n - 1] + 1; i++) {

flag = false;

for (int j = 0; j < n; j++) {

if (taskn[j] == i) {

flag = true;

break;

}

if (taskn[j] > i) {

break;

}

}

if (!flag) {

tt[index] = i;

index++;

}

}

for (int i = 0; i < m; i++) {// 可以执行临时任务的时间列表

int k = 0;

if (taskm[i] <= tt[k]) {

taskm[i] = tt[k++];

} else {

index = k;

while (taskm[i] > tt[index]&&index<=tt.length) {

index++;

}

taskm[i] = tt[index];

}

}

for (int t : taskm) {

System.out.println(t);

}

scanner.close();

}

}


2017-03-25 22:30

我来解释一下第二题好了，，，扫一遍记录下每个前缀子串的状态(每个字母出现的次数为奇/偶)。如果两个前缀状态相同，说明夹在它们中间的子串肯定是个偶串。我是组合数算的，相同状态的前缀两两组合都是一个偶串，像题解里每次相加也行。

因为只有26个字母，所以可以状态压缩，用 32 位 int 的其中 26 位来记录状态，某位为 0 表示 该位对应的字母为偶数。

1<<26的状态数太大了所以用map存。注意有个坑是mp[0] = 1，不然20%会挂掉。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;

map<int, int> mp;

long long solve() {
    char s[100005];
    scanf("%s", s);
    int st = 0;
    mp[0] = 1;
    for(int i = 0; s[i]; i++) {
        st ^= 1 << (s[i] - 'a');
        if(mp.count(st)) mp[st]++;
        else mp[st] = 1;
    }
    map<int, int>::iterator it;
    long long ans = 0;
    for(it = mp.begin(); it != mp.end(); it++) {
        int sc = it -> second;
        //cout << fr << ' ' << sc << endl;
        if(sc > 1) ans += 1LL * (sc - 1) * sc / 2;
    }
    return ans;
}

int main() {
//freopen("in.txt", "r", stdin);
    printf("%lld\n", solve());
    return 0;
}


2017-03-25 22:58
3
acmcoderf9AWMSR6 回复 Holy ：

第二题的思路我放在下面了
2017-03-25 23:01

问题3，java

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n,m;
		n=scanner.nextInt();
		m=scanner.nextInt();
		int t[]=new int[n];
		int q[]=new int[m];
		int now1=0,now2=0;
		for (int i = 0; i < t.length; i++) {
			t[i]=scanner.nextInt();
		}
		for (int i = 0; i < q.length; i++) {
			q[i]=scanner.nextInt();
		}
		scanner.close();
		int result[]=new int[m];
		boolean flag;
		for (int i = 0; i < q.length; i++) {
			flag=true;
			for (int j = 0; j < t.length; j++) {
				if (t[j]==q[i]) {
					flag = false;
					q[i]++;
					j=0;
				}
				if (t[j]!=q[i]&&j==t.length-1) {
					flag=true;
				}
			}
			if (flag) {
				result[i] = q[i];
			}else{
				result[i] = t[n-1]+1;
			}
		}
		for (int i = 0; i < result.length; i++) {
			System.out.println(result[i]);
		}
	}
}


2017-03-25 23:48
1
Holy 回复 acmcoderf9AWMSR6 ：

是的，find是无序遍历查找
2017-03-26 10:39
acmcoderQdM6q4Uj 回复 花语飘天 ：

通过率只有20%啊
2017-03-26 11:46
acmcoderQdM6q4Uj 回复 花语飘天 ：

而且这种方法不能找出子串的个数吧，只能找到奇偶
2017-03-26 11:47
coder_767DHEHX 回复 acmcoderf9AWMSR6 ：

请教一下，这道题中两个状态一样的前缀子串之间一定是偶串想到了，可是1<<(s[i]-‘a’),楼主是怎么想到的要进行这样的转换呢，我因为没想到这样的转换，挂了~
2017-03-27 09:06

第二题偶串，Javascript,本地运行没问题。。。有人要帮忙看看么

var str = read_line();
var count = 0;
var sLength = str.length;
function isO(strSon){
  var d = [];
  for(var n = 0;n<=i ;n++){
    var a = strSon.slice(n,n+1);
    if(d.includes(a)){
      var c = d.indexOf(a);
      d.splice(c,1);
    }else{
      d.push(a);     
    } 
  } 
  if(d.length == 0){
      count++;
    }
}
for(var i = 1;i < sLength;i++){
  for(var j = 0;j < sLength-i;j++){
    var strSon = str.slice(j,j+(i+1));
    isO(strSon);
  }  
}
print(count);


2017-03-31 21:47
1
coder_F9YUTSVD 回复 coder_NEA5GNTV ：

请问下本地怎么运行
2017-04-11 16:18
coder_F9YUTSVD 回复 coder_NEA5GNTV ：

同学能给个qq吗？哈哈
2017-04-11 17:09
acmcoderf9AWMSR6 回复 coder_767DHEHX ：

见过一次以后就会记得了……
2017-04-18 21:35
acmcoderf9AWMSR6 回复 coder_767DHEHX ：

啊，再多说一句，不知道你对Linux内核有没有过了解，读过源码没有，内核里很多用到这种置位表示状态的 flags
2017-04-22 09:46
添加回复
注册
回到顶部