首页 > 0821京东笔试
头像
关山口的冬天
编辑于 2021-08-22 12:58
+ 关注

0821京东笔试

笔试编程题

1:相邻邻居的数量

两个点在对角线上就是相邻的,看到这个题目想了两分钟,决定用最暴利的解法试一下,用类似于八皇后的方法表示对角线:
对角线的直线表示是y = x + bi 或者 y = -x + bi; 变换一下是y - x = bi;  y + x = bi;
因此判断两个点在不在对角线,只需要判断两者的y - x; y + x是不是相等的;
笔试的时候暴力做的,过了73,n平方复杂度了,后面自己想了下用一个map存下来每个点的y + x和y - x就可以额O(n)做了;
#include <iostream>
#include <unordered_map>
using namespace std;

const int N = 1e5 + 1;
int a[N][2];
int n, res = 0;

int main()
{
    cin >> n;
    for(int i = 0; i < n ;i++) cin >> a[i][0] >> a[i][1];
    /*
    //暴力
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            if(a[i][0] + a[i][1] == a[j][0] + a[j][1] || a[i][1] - a[i][0] == a[j][1] - a[j][0])
                res++;
    */
    //用map优化
    unordered_map<int, int> dict;
    for(int i = 0; i < n; i++)
    {
        dict[a[i][1] + a[i][0]]++;
        dict[a[i][1] - a[i][0]]++;
    }
    for(unordered_map<int, int>::iterator it = dict.begin(); it != dict.end(); it++)
        if(it->second > 1) res += it->second;
    cout << res << endl;
    return 0;
}

2.分个字符串01的比例相等

笔试的时候用暴力的方法做的,做完后看到网上gcd的方法感觉更妙

后面参照gcd方法实现的:

#include <iostream>
#include <unordered_map>
using namespace std;

int n;
string s;
typedef pair<int, int> PII;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int main()
{
    cin >> n >> s;
    int zeros = 0, ones = 0;
    PII p;
    unordered_map<PII, int> dict;
    for(int i = 0; i < n; i++)
    {
        if(s[i] == '0') zeros++;
        else ones++;
        if(zeros == 0)
        {
            p = make_pair(1, 0);
            dict[p] += 1;
        }
        else if(ones == 0)
        {
            p = make_pair(0, 1);
            dict[p] += 1;
        }
        else
        {
            int gcd_ = gcd(zeros, ones);
            p = make_pair(zeros / gcd_, ones / gcd_);
            dict[p] += 1;
        }
        cout << dict[p] << " ";
    }
    puts("");
    return 0;
}


自己笔试的时候做的:

#include <iostream>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
int n;
string s;
int splitString(string s, int len)
{
	if(len == 1) return 1;
	int cnt = 1;
	vector<PII> vec(len, make_pair(0, 0));
	if(s[0] == '0') vec[0].first++;
	else vec[0].second++;

	for(int i = 1; i < len; i++)
	{
		if(s[i] == '0')
		{
			vec[i].first = vec[i - 1].first + 1;
			vec[i].second = vec[i - 1].second;
		}
		else{
			vec[i].first = vec[i - 1].first;
			vec[i].second = vec[i - 1].second + 1;
		}
	}
	//for(int i = 0; i < len; i++) cout << vec[i].first << ": " << vec[i].second << endl;

	for(int i = 0; i < len; i++)
	{
		int n1 = vec[i].first * (vec[len - 1].second - vec[i].second);
		int n2 = vec[i].second * (vec[len - 1].first - vec[i].first);
		if(n1 != n2) continue;
		else
		{
			for(int j = i; j < len - 1; j = j + i + 1)
			{
				int tmp1 = vec[j].first * (vec[len - 1].second - vec[j].second);
				int tmp2 = vec[j].second * (vec[len - 1].first - vec[j].first);
				if(tmp1 != tmp2) break;
				else cnt++;
			}
			break;
		}	
	}
	return cnt;
}
int main()
{
	cin >> n >> s;
	//string s = "010100001";
	for(int i = 0; i < n; i++)
	{
		string tmp = s.substr(0, i + 1);
		cout << splitString(tmp, i + 1) << " ";
	}
	puts("");
	return 0;
}




全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐