我要招人

去企业版

首页 > 试题广场 >

笔记精选

[编程题]笔记精选

热度指数：5509 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

薯队长写了n篇笔记，编号从1~n,每篇笔记都获得了不少点赞数。

薯队长想从中选出一些笔记，作一个精选集合。挑选的时候有两个规则：

1.不能出现连续编号的笔记。

2.总点赞总数最多

如果满足1，2条件有多种方案，挑选笔记总数最少的那种

输入描述:

输入包含两行。第一行整数n表示多少篇笔记。 第二行n个整数分别表示n篇笔记的获得的点赞数。   
 （0<n<=1000,    0<=点赞数<=1000)

输出描述:

输出两个整数x,y。空格分割。
 x表示总点赞数，y表示挑选的笔记总数。

示例1

输入

4
1 2 3 1

输出

4 2

算法知识视频讲解

JavaScript

喜欢溜溜球的小蜗牛要发财

看结果好像是对的

function dpNote(num: number, nums: number[]) {

if (nums.length === 0) return 0

if (nums.length === 1) return nums[0]

const dp = new Array(num).fill(0)//点赞数

const dpNum = new Array(num).fill(0)//笔记数

dp[0] = nums[0]

dpNum[0] = 1

dp[1] = Math.max(nums[0], nums[1])

dpNum[1] = 1

for (let i = 2; i < nums.length; i++) {

if (dp[i - 1] < dp[i - 2] + nums[i]) {

dpNum[i] = dpNum[i - 1]

}else{

dpNum[i] = dpNum[i - 1] + 1

}

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])

}

console.log(dp[nums.length - 1])//点赞数

console.log(dpNum[nums.length - 1])//笔记数

}

发表于 2024-02-23 17:39:49 回复(0)

JavaScript

愿offer多多的里根很能干

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        let arr=line.split(' ')
        let dp=[]
        let g=[]
       
        if(arr.length<2) continue
        arr=arr.map((item)=>{
            return Number(item)
        })
        dp[0]=arr[0]
        dp[1]=arr[1]
        g[0]=1
        g[1]=1
        for(let i=2;i<arr.length;i++){
           dp[i]=Math.max(dp[i-1],dp[i-2]+arr[i])
           if(dp[i]==dp[i-2]+arr[i]){
              g[i]=g[i-2]+1
           }else{
              g[i]=g[i-1]
           }
        }
        console.log(dp[arr.length-1]+" "+g[arr.length-1])
    }
}()

为啥只通过了八组有没有大佬解读一下

发表于 2023-09-19 14:10:28 回复(0)

JavaScript

妖妖灵丶

let pick = (nums, stars)=>{
    let sums = [];
    let pickeds = [];
    sums[0] = stars[0];
    sums[1] = Math.max(stars[0], stars[1]);
    pickeds[0] = pickeds[1] = 1;
    for(let i = 2; i < nums; i++) {
        if(sums[i - 2] + stars[i] > sums[i - 1]) {
            sums[i] = sums[i - 2] + stars[i];
            pickeds[i] = pickeds[i - 2] + 1;
        }else {
            sums[i] = sums[i - 1];
            pickeds[i] = pickeds[i - 1];
        }
    }
    return [sums[nums - 1], pickeds[nums - 1]];
}

let nums = Number(readline());
let stars = readline().split(' ');
stars = stars.map(v=>Number(v));
let [sum, picked] = pick(nums, stars);
console.log(sum, picked);

发表于 2021-03-19 02:56:01 回复(0)

JavaScript

-just

打家劫舍算法：进最少的房子拿最多的钱。这里同理，收最少的文章有最多的点赞数。

文章篇数由3中情况：

（1）只有1篇文章，则直接返回其点赞数

（2）有两篇文章，返回最大值，文章篇数仍是1

（3）有三篇文章，则有两种选择：第1篇文章的点赞数+第3篇文章的点赞数与仅第2篇文章的点赞数

同理，有 i ( i>2 ) 篇文章时,其对应的点赞数是：

max( 有i-1篇文章的点赞总数，有i-2篇文章的点赞总数+当前文章的点赞数 )

设：

dzArr数组：all文章对应的点赞数 //由用户输入

dzNum数组：为不同文章篇数下的最多点赞数

articleNum数组：辅助dzNum，记录对应的点赞数是由几篇文章组成的。

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
let lines = [];
rl.on('line', (line) => {
    lines.push(line);
    if (lines.length == 2) {
        let dzArr = lines[1].split('/n')[0].split(' ').map(Number);
        let len=dzArr.length;
        if(len==1){
            console.log(`${dzArr[0]} 1`);
        }else if(len==2){
            console.log(`${Math.max(dzArr[0],dzArr[1])} 1`);
        }else{
            let articleNum= [1,1];
            let dzNum = [dzArr[0]];
            dzNum[1]=Math.max(dzArr[0],dzArr[1]);
            for(let i=2;i<len;i++){
                if(dzArr[i]+dzNum[i-2] >dzNum[i-1]){   //选择1+3
                    dzNum.push( dzArr[i]+dzNum[i-2] );
                    articleNum.push( articleNum[i-2]+1  );
                }else{  //仅第2篇文章
                    dzNum.push( dzNum[i-1] );
                    articleNum.push( articleNum[i-1]  );
                }
            } 
            console.log(dzNum[len-1],articleNum[len-1]);
        }
    }
})

发表于 2020-11-05 09:47:23 回复(0)