恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】
点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝
第一道：错峰出行
题目描述:
上班了，小程每天晚上都要坐公交车回家
公交车每天晚高峰都很拥挤，但是好在小程不用那么着急回家，可以在公司里坐一会。等高峰期一过，小程再回家。因为要时刻知道当前是否在高峰期，小程需要知道当前公交线路的拥挤段是哪里。
已知小程乘坐的公交车线路有n个站，从起点站到终点站依次为第0站至第n-1站。且己知第i站当前的人流量ai,拥挤段指一段站点个数大于等于K的连续站点区间，这段区间中的站平均人流量最 大。用1 (,为整数)表示从编号为的站点开始，编号为r的站点结束的站点区间，那么平均人 流量就等于编号在、r之间的站点ai的平均值。如果有多 个平均人流是最大的区间，取最长的那个。如果有多个平均人流量最大且最长的区间，取I最小的那个。
请你帮小程找到公交车线路当前的拥挤段[,r]吧!
输入描述
第一行两个正整数n(1<=n<=100)，K(1<=K<=n)接下来行n个整数，第1个数ai表示当前第站的人流量(1<=ai<=1000)
输出描述
输出两个整数(.r，用一个空格隔开，表示拥挤段的开始站和结束站
参考代码：
Java版本
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = sc.nextInt();
}
// 窗口范围[k,n], 平均值最大，次之窗口最宽
int[] preSum = new int[n + 1];
for (int i = 1; i<= n; ++i) {
preSum[i] = preSum[i-1] + arr[i-1]; // preSum[i] = sum(arr[1..i))
}
long sum = 0;
int st = 0, ed = 0; // avg = sum / (ed - st)
for (int i = 0; i <= n - k; ++i) {
for (int j = i + k; j <= n; ++j) {
long tmpSum = preSum[j] - preSum[i];
if (sum * (j - i) < tmpSum * (ed - st) // sum/(ed-st) < tmpSum/(j-i)
|| sum * (j - i) == tmpSum * (ed - st) && (j - i) > (ed - st)) {
sum = tmpSum;
ed = j;
st = i;
}
}
}
System.out.println(st + " " + (ed - 1));
}
}
CPP版本
using namespace std;
long sumvector(vector<int>& record, int left, int right) {
long sum = 0;
while (left <= right) {
sum += record[left];
left++;
}
return sum;
}
int main() {
int n = 0, k = 0;
cin >> n >> k;
vector<int> record;
vector<int> res(2, 0);
double average = -1.0;
while (n--) {
int tmp;
cin >> tmp;
record.push_back(tmp);
}
for (int j = k - 1; j < record.size(); j++) {
int left = 0, right = j;
while (right < record.size()) {
long cursum = sumvector(record, left, right);
double curaverage = cursum / (right - left + 1);
if (curaverage > average) {
res[0] = left;
res[1] = right;
average = curaverage;
}
if (abs(curaverage - average) < 0.0001) {
if (right - left > res[1] - res[0]) {
res[0] = left;
res[1] = right;
}
if (right - left == res[1] - res[0]) {
if (left < res[0]) {
res[0] = left;
res[1] = right;
}
}
}
left++;
right++;
}
}
cout << res[0] << " " << res[1];
return 0;
}
Python版本
from collections import deque
n = int(input())
qa, qb, qc = deque(), deque(), deque()
for _ in range(20):
qa.append(0)
for _ in range(12):
qb.append(0)
for _ in range(6):
qc.append(0)
cnt = 0
que = None
ans = 0
for v in range(n-1, -1, -1):
qa.popleft()
qa.append(ans)
qb.popleft()
qb.append(ans)
qc.popleft()
qc.append(ans)
if v % 3 == 0:
que = qa
cnt = 20
elif v % 3 == 1:
que = qb
cnt = 12
else:
que = qc
cnt = 6
cur = sum(que) / cnt + 1
ans = cur
print("{:.2f}".format(ans))
第二道：数字人生
题目
第1天屏幕上会显示数字串的第社至1+1-1位。由于每天 的内容要变化，每个显示位上的灯管亮灭都会进行调整。 开始第0天时， 所有灯管都是熄 1,从第1天的状态调整到第i+ 1天时(0<mi<n-);: 1,灭掉新数字中没有但目前亮的灯 2、亮起新数字中有但目前没有亮的灯管。我们称一 次灯管的亮/灭操作为“变化”，Q: (为3,数字事为1234567890,天数由0变为1时，亮起了123,发生了12:次变化;天数由1b2时显示的数字串由123变为234,其中1→+2产生了5个变化，2→3产生了2个变化，3→4产生个变化
当屏幕最右边为数字串最后一位时， 屏幕将永远定格不再改变
你能回答出当屏嘉宽度为(1 <=|< =n)时从开始到结束-共产生的变化数吗?
代码
Java版本
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int[][] changeCount = {
{0, 4, 3, 3, 4, 3, 2, 3, 1, 2},
{4, 0, 5, 3, 2, 5, 6, 1, 5, 4},
{3, 5, 0, 2, 5, 4, 3, 4, 2, 3},
{3, 3, 2, 0, 3, 2, 3, 2, 2, 1},
{4, 2, 5, 3, 0, 3, 4, 3, 3, 2},
{3, 5, 4, 2, 3, 0, 1, 4, 2, 1},
{2, 6, 3, 3, 4, 1, 0, 5, 1, 2},
{3, 1, 4, 2, 3, 4, 5, 0, 4, 3},
{1, 5, 2, 2, 3, 2, 1, 4, 0, 1},
{2, 4, 3, 1, 2, 1, 2, 3, 1, 0},
{6, 2, 5, 5, 4, 5, 6, 3, 7, 6},
};
Scanner sc = new Scanner(System.in);
String s = sc.next();
StringBuilder cache = new StringBuilder();
for (int d = 1; d <= s.length(); ++d) { // 宽度
cache.append(work(s, d, changeCount)).append(" ");
}
if (cache.length() > 0) {
cache.deleteCharAt(cache.length() - 1);
}
System.out.println(cache);
}
private static int work(String s, int d, int[][] changeCount) {
int totalCount = 0;
for (int i = 0; i < d; ++i) {
totalCount += changeCount[10][s.charAt(i) - '0'];
}
if (d == s.length()) {
return totalCount;
}
int count = 0;
for (int j = 1; j <= d; ++j) {
count += changeCount[s.charAt(j - 1) - '0'][s.charAt(j) - '0'];
}
totalCount += count;
for (int j = 2; j < s.length() - d; ++j) {
count += - changeCount[s.charAt(j-1) - '0'][s.charAt(j) - '0'] + changeCount[s.charAt(j+d-1) - '0'][s.charAt(j+d) - '0'];
totalCount += count;
}
return totalCount;
}
}
Python版本
m = dict()
m[0] = [1, 1, 1, 0, 1, 1, 1]
m[1] = [0, 0, 1, 0, 0, 1, 0]
m[2] = [1, 0, 1, 0, 1, 0, 1]
m[3] = [1, 0, 1, 1, 0, 1, 1]
m[4] = [0, 1, 1, 1, 0, 1, 0]
m[5] = [1, 1, 0, 1, 0, 1, 1]
m[6] = [1, 1, 0, 1, 1, 1, 1]
m[7] = [1, 0, 1, 0, 0, 1, 0]
m[8] = [1, 1, 1, 1, 1, 1, 1]
m[9] = [1, 1, 1, 1, 0, 1, 1]
tmp = dict()
for i in range(10):
for j in range(i + 1, 10):
str_tmp = str(j) + str(i)
tmp[str_tmp] = sum([abs(m[j][k] - m[i][k]) for k in range(7)])
for i in range(10):
tmp[str(i)] = sum(m[i])
s = input()
n = len(s)
def compare(yes, tod, first):
count = 0
print(yes, tod)
if first:
for s in tod:
count += tmp[s]
else:
n = len(yes)
for i in range(n):
a = int(yes[i])
b = int(tod[i])
if a != b:
max_num = max(a, b)
min_num = min(a, b)
count += tmp[str(max_num) + str(min_num)]
return count
res = []
for i in range(n):
count = 0
for j in range(i, n):
if j == i:
count += compare(None, s[0:i + 1], True)
else:
count += compare(s[j - i - 1:j], s[j - i:j + 1], False)
res.append(count)
print(res)
CPP版本
int num[10]={0x3f,0x06,0x5b,0x4f,0xc6,0x6d,0x7d,0x07,0x7f,0x6f};
int one(int a){
int n=0;
while(a){
n++;
a=a&(a-1);
}
return n;
}
int main(){
string s;
cin>>s;
int n=s.size();
vector<int> presum(n+1,0);
for(int i=0;i<n;i++){
presum[i+1]=presum[i]+one(num[s[i]-'0']^0);
}
vector<vector<int>> c(n,vector<int>(n,0));
for(int i=0;i<n;i++){
int k=0;
for(int j=i+1;j<n;j++){
k+=one(num[s[j-1]-'0']^num[s[j]-'0']);
c[i][j]=k;
}
}
for(int l=1;l<=n;l++){
int cur=presum[l];
for(int i=0;i<l;i++){
cur+=c[i][n-l+i];
}
if(l==n) cout<<cur<<endl;
else cout<<cur<<" ";
}
}
第三道：建树游戏
题目描述：
有n个节点和n.条边，形成一棵树， 我们把其中一条边删除，就形成了两棵树，再在两棵树之间增加一条与之前删除的边不同的边，就形成了一棵新的树。给每个点设置一个权值，并规定每棵新树的权值等于最后增加的那条边的两点权值相乘。
每条边都可以删除，且每条边删除后都有很多可以加的边，因此会形成很多不同的新树。请计算这 | 些新树的数量。同时，对于每条边，删除后可以产生的若干新树的权值之和也不一一定相同，请计算这些权值之和中的最大值。
输入描述
第一行整数n,表示点的数量，3 <=n <= 100000。
第二行n-1个整数，空格隔开，第i个整数a;表示点a;与点i之间有一条边。 第三行n个整数，空格隔开，表示各个点的权值。0 <权值<= 10000。
输出描述
一行， 两个整数，用空格隔开，表示新树的总数量，以及各点删除后可以产生的新树的权值之和中的最大值。
代码
n = int(input())
edges = list(map(int, input().split()))
weights = list(map(int, input().split()))
graph = [[] for _ in range(n)]
for i in range(n - 1):
j = edges[i] - 1
graph[i].append(j)
graph[j].append(i)
root = 0
def search(root, parent, graph, weights, table):
curVal = weights[root]
curCnt = 1
for node in graph[root]:
if node != parent:
val, cnt = search(node, root, graph, weights, table)
curVal += val
curCnt += cnt
table[root] = (curVal, curCnt)
return table[root]
table = {}
search(root, -1, graph, weights, table)
def find(root, parent, graph, weights, table, ttable):
n = len(graph)
total = table[0][0]
resVal = 0
resCnt = 0
for node in graph[root]:
if node != parent:
curVal, curCnt = table[node]
val = curVal * (total - curVal) - weights[node] * weights[root]
cnt = curCnt * (n - curCnt) - 1
resCnt += cnt
resVal = max(resVal, val)
find(node, root, graph, weights, table, ttable)
ttable[root] = (resVal, resCnt)
ttable = {}
find(root, -1, graph, weights, table, ttable)
resVal = 0
resCnt = 0
for node in ttable:
resVal = max(resVal, ttable[node][0])
resCnt += ttable[node][1]
print(str(resCnt) + ' ' + str(resVal))
恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】
点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝
