笔试——Day18

第一题

题目

压缩字符串(一)

思路

模拟

• left和right 指针初始化为0，用于标记当前连续相同字符的起始和结束位置，res 用于存储压缩后的结果字符串;
• 循环用于找到当前连续相同字符的结束位置。即，只要param[right] 与下一个字符相同，right 就向右移动;
• 计算当前连续字符的长度 len = right - left + 1 ;
• 将当前字符 param[left] 添加到结果字符串 res 中;
• 如果长度 len 大于1 ，将长度转换为字符串并追加到 res 中;
• 更新 left和right的新位置；

代码

第二题

题目：

chika和蜜柑

思路

模拟

• 按照题目要求先排序，先吃甜度高的，若一样高，则选酸度低的；
• 取前k个，求和

代码

第三题

题目：

01背包

思路

动态规划

• dp[i][j]表示：从前i个物品中，选总体积不超过j，此时的最大重量；
• 状态转移方程：
  • 不选i：dp[i - 1][j]
  • 选i：dp[i - 1][j - v[i]] + w[i]j（j > v[i]）
  • 取max
• 初始化dp[0][j] = 0

代码