Re: [閒聊] 每日LeetCode已回收
2389. Longest Subsequence With Limited Sum
給你一個陣列nums表示一個數列，並給你一個陣列表示每次查詢和的上限，從數列中找
出一個序列（不必連續）滿足小於等於查詢之和並且盡可能的大。
Input: nums = [4,5,2,1], queries = [3,10,21]
Output: [2,3,4]
Explanation:
第一次查詢 queries[0] = 3，序列[2,1]為最長序列所以結果為2
第二次查詢 queries[1] = 10，序列[4,2,1]為最長序列所以結果為3
第三次查詢 queries[2] = 21，序列[4,5,2,1]為最長序列所以結果為4
思路：
1.因為序列不需要是連續的，所以我們可以每次都從整個序列中取出任意位置最小的數
字並加到sum，若sum小於等於target則長度加一，否則返回當前長度。
2.因為要每次都取出最小數字所以我們可以將原陣列先做排序，並查詢n次即可。
Java Code：
------------------------
class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
int n = queries.length;
Arrays.sort(nums);
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = helper(nums, queries[i]);
}
return res;
}
private int helper(int[] nums, int target) {
int len = 0;
int sum = 0;
for (int num : nums) {
sum += num;
if (sum > target) {
break;
}
len++;
}
return len;
}
}
------------------------
同樣的概念用binary search加上prifix sum也可以
Java Code：
------------------------
class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
Arrays.sort(nums);
int n = nums.length;
int m = queries.length;
int[] res = new int[m];
for (int i = 1; i < n; i++) {
nums[i] += nums[i - 1];
}
for (int i = 0; i < m; i++) {
int j = Arrays.binarySearch(nums, queries[i]);
res[i] = Math.abs(j + 1);
}
return res;
}
}
------------------------
--
https://i.imgur.com/fHpKflu.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671950998.A.4F9.html
※ 編輯: Rushia (122.100.75.86 臺灣), 12/25/2022 14:57:38
推
12/25 15:03,
3年前
, 1F
12/25 15:03, 1F
→
12/25 15:21,
3年前
, 2F
12/25 15:21, 2F
推
12/25 20:12,
3年前
, 3F
12/25 20:12, 3F
討論串 (同標題文章)
完整討論串 (本文為第 152 之 719 篇)：