第一题跑过了没啥问题
第二题跑了91% 算了所有可能的分数 太傻了......
可能大家的题不太一样吧 我的第一题是m和n组队编程的问题 第二题是小明做题求最高分的问题
题目1：
let m = 0
let n = 0
rl.on('line',function(line){
let valArr = line.split(' ')
m = parseInt(valArr[0])
n = parseInt(valArr[1])
getResult()
})
function getResult() {
if (m>n) {
if (Math.floor((m+n)/3) > n) {
console.log(n)
} else {
console.log(Math.floor((m+n)/3))
}
} else {
if (Math.floor((m+n)/3) > m) {
console.log(m)
} else {
console.log(Math.floor((m+n)/3))
}
}
}
题目2：
let lineCount = 0
let n = 0
let inputArr = []
rl.on('line',function(line){
if (lineCount === 0) {
n = parseInt(line)
lineCount++
} else {
let valArr = line.split(' ')
valArr = valArr.map(val => parseInt(val))
inputArr.push(valArr)
if (lineCount === n) getResult()
lineCount++
}
})
function getResult() {
let max = 0
let add = function (index,score,time) {
if (index === n) return
add(index+1,score+0,time+0)
let newTime = time+inputArr[index][0]
let newScore = score+inputArr[index][1]
if (newTime <= 120) {
if (newScore > max) max = newScore
if (newTime < 120) add(index+1,newScore,newTime)
}
newTime = time+inputArr[index][2]
newScore = score+inputArr[index][3]
if (newTime <= 120) {
if (newScore > max) max = newScore
if (newTime < 120) add(index+1,newScore,newTime)
}
}
add(0,0,0)
console.log(max)
}
献丑了，第二题只通过了91%，有更好的算法的大神指点一下啊
第二道题，Python解法，通过了82%，超时了，但是我感觉做到最优化了啊，好难呀
n, k, t = map(int, input().split())
nums = list(map(int, input().split()))
nums_map = {}
temp_nums = nums[:k]
for i in range(0, k):
nums_map[nums[i]] = temp_nums.count(nums[i])
res = 1 if max(nums_map.values()) >= t else 0
for i in range(1, n-k+1):
nums_map[nums[i-1]] -= 1
num = nums_map.get(nums[i + k - 1], None)
if num:
nums_map[nums[i + k - 1]] += 1
else:
nums_map[nums[i + k - 1]] = 1
if max(nums_map.values()) >= t:
res += 1
print(res)
第二题：
tmp = input().split() n, k, t = int(tmp[0]), int(tmp[1]), int(tmp[2]) tmp = input().split() a = [int(i) for i in tmp] # print(a) def exist(nums, t): import collections dic = collections.Counter(nums) for key in dic.keys(): if dic[key] >= t: return True return False res = 0 i = 0 while i < len(a)-k+1: tmp = a[i:i+k] # print(tmp) if exist(tmp, t): res += 1 if (i+k < len(a) and ((tmp.count(a[i+k]) >= t-1) or a[i+k] == a[i])): # print(i+k) i += 2 res += 1 continue else: i += 1 print(res)
第二题
tmp = input().split() n, k, t = int(tmp[0]), int(tmp[1]), int(tmp[2]) tmp = input().split() a = [int(i) for i in tmp] # print(a) def exist(nums, t): import collections dic = collections.Counter(nums) for key in dic.keys(): if dic[key] >= t: return True return False res = 0 i = 0 while i < len(a)-k+1: tmp = a[i:i+k] # print(tmp) if exist(tmp, t): res += 1 if (i+k < len(a) and ((tmp.count(a[i+k]) >= t-1) or a[i+k] == a[i])): # print(i+k) i += 2 res += 1 continue else: i += 1 print(res)
第一题 空白 没学过图
第二题 python 过了
def check(nums,n,k,t): record = dict() count = 0 flag = [] for i in range(k): if record.get(nums[i]): record[nums[i]]+=1 else: record[nums[i]]=1 if record[nums[i]] >= t and (nums[i] not in flag): flag.append(nums[i]) if flag: count+=1 index = 1 while index<=n-k: record[nums[index-1]]-=1 if nums[index-1] in flag: if record[nums[index-1]]<t: flag.remove(nums[index-1]) if record.get(nums[index+k-1]): record[nums[index+k-1]]+=1 else: record[nums[index+k-1]]=1 if record[nums[index+k-1]] >= t and (nums[index+k-1] not in flag): flag.append(nums[index+k-1]) if flag: count+=1 index+=1 return count if __name__ == '__main__': n, k, t = map(int,raw_input().split()) nums = raw_input().split() print check(nums,n,k,t)
第一题图的遍历，思路 (n-1)*2-图最大遍历深度
AC代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MAXN 100010
int g[MAXN][100];
int f[MAXN];
int isv[MAXN];
int maxn = 0;
void dfs(int curp,int curs)
{
int i;
// 当前节点走过了
isv[curp] = 1;
// 当前节点是否全部走过，默认为是
bool isallv = true;
for(i=0;i<f[curp];i++){
if( ! isv[g[curp][i]]){
// 当前节点的第 i 个子节点没有被走过，那么可以走
isallv = false;
dfs(g[curp][i],curs+1);
}
}
if(isallv){
//当前节点的所有子节点都被走过，那么不能再走了，计算走到这儿的最大深度
if(curs>maxn)
maxn = curs;
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
if(n==0) break;
memset(g,0,sizeof(g));
memset(f,0,sizeof(f));
memset(isv,0,sizeof(isv));
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
g[a][f[a]++] = b;
g[b][f[b]++] = a;
}
dfs(1,0);
printf("%d\n",(n-1)*2-maxn);
}
return 0;
}
第二题一直是73%，说一下我的思路，大神帮看看有没有问题：
假设数组是 1 2 2 3 3 4 4 5 5
k=2 t=2
初始化一个map表示窗口中数的数量，以及一个count，表示滑动窗口中所有>=t的数目，
然后窗口滑动，进入一个数，出去一个数，进入那个数的数量如果刚好==t的话count++，出去那个数的t如果刚好==t-1的话count--。如果count>0说明当前窗口存在>=t的数，则返回值+1
初始化 (1) [1 2] 2 3 3 4 4 5 5 此时 map[1] = 1 map[2]=1; count = 0;
(2)1 [2 2] 3 3 4 4 5 5 此时 map[1] =0,而map[2] = t,则count++，count大于0则返回值++
(3)1 2 [2 3] 3 4 4 5 5 此时 map[2] = t-1,说明窗口中>=t的数目在此循环处减1，count--,count==0,返回值不变
(4)1 2 2 [3 3] 4 4 5 5 同(2)
...
时间复杂度O(n)
第二个题，java暴力通过82%，之后再优化优化吧
public class Main {
private static int n,k,t;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] arr = sc.nextLine().split(" ");
n=Integer.parseInt(arr[0]);
k=Integer.parseInt(arr[1]);
t=Integer.parseInt(arr[2]);
int[] list = new int[n];
for(int i = 0;i<n;i++){
list[i] = sc.nextInt();
}
int count = 0;
int start = 0;
int end = start + k - 1;
while (end < n) {
if (find(list, start, end)) {
count++;
}
start++;
end = start + k - 1;
}
System.out.println(count);
}
/**
* 计算每个合适的区间
*/
public static boolean find(int[] arr,int left,int right){
for(int i=left;i<=right;i++){
if(count(arr,left,right,arr[i])>=t){
return true;
}
}
return false;
}
/**
* 每个区间暴力统计重复数值的个数（这里优化！！！）
*/
public static int count(int[] arr,int left,int right,int num){
int count=0;
for(int i=left;i<=right;i++){
if(arr[i]==num){
count++;
}
}
return count;
}
}关于 给定N长度的1000010101001 字串 ，允许修改K个0为1，输出最长连续1字串的长度：
我的方法是 给出左右两个指针 left,right，从两端不断向中间移动，直到满足条件：sum[left,right]+K>=right-left+1
N,K = list(map(int, raw_input().split())) arr = list(map(int, raw_input().split())) sum_arr = [sum(arr[:n+1]) for n in range(N)] left = 0 right = N-1 while sum_arr[right] - sum_arr[left] + arr[left] < right-left+1-K: if arr[left] == 0: left += 1 elif arr[right] == 0: right -= 1 else: i = 1 while arr[left+i] == arr[right-i] and i<(right-left)/2: i += 1 if arr[left-i] == 0: left += 1 else: right -= 1 print(right-left+1)
可怜我没有提交。。。。贴出来，大家看看对不对
有大佬看我做到对不
while 1:
x = input().split(' ')
n = int(x[0])
k = int(x[1])
t = int(x[2])
nums = input().split()
for i in range(len(nums)):
nums[i] = int(nums[i])
def max_list(lt):
temp = 0
for i in lt:
if lt.count(i) > temp:
temp = lt.count(i)
return temp
res = 0
for x in range(k):
l, r = x, x + k
if max_list(nums[l:r]) >= t:
res += 1
print(res)
isaimawang
@ 赛码网
533869549