- [8.30 - medium]☆☆☆ 528. 按权重随机选择
- [8.31 - medium]☆☆☆☆☆ 1109. 航班预订统计
- [9.1 - medium] 165. 比较版本号
- [9.2 - easy] 剑指 Offer 22. 链表中倒数第k个节点
- [9.2 - easy] 1337. 矩阵中战斗力最弱的 K 行
- [9.3 - medium]☆☆☆ 面试题 17.14. 最小K个数
- [9.4 - easy] 剑指 Offer 10- I. 斐波那契数列
- [9.5 - medium]☆☆☆☆☆ 470. 用 Rand7() 实现 Rand10()
- [9.10 - hard]☆☆☆☆☆ 502. IPO
- [9.13 - medium]☆☆ 678. 有效的括号字符串
- [9.19 - medium]☆☆☆☆☆ 650. 只有两个键的键盘
- [9.20 - medium]☆☆☆ 673. 最长递增子序列的个数
- [9.26 - medium]☆☆☆ 371. 两整数之和
- [9.26 - medium] 实现LRU
- [10.1 - medium]☆☆☆ 最长公共子串
- [10.3 - medium]☆☆☆ NC54 数组中相加和为0的三元组
- [10.6 - medium]☆☆☆☆☆ NC91 最长递增子序列
- [10.7 - medium] NC128 接雨水问题
- [10.24 - medium]☆☆☆ 638. 大礼包
[8.30 - medium]☆☆☆ 528. 按权重随机选择
给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。
例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。
也就是说，选取下标 i 的概率为 w[i] / sum(w) 。
示例 1：
输入：
[“Solution”,”pickIndex”]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。
示例 2：
输入：
[“Solution”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”]
[[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。
由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
……
诸若此类。
提示：
1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex 将被调用不超过 10000 次
前缀和 + 二分
直接构造w[i]个i的符合权重的序列，结果超内存了
class Solution {List<Integer> list = new ArrayList<>();public Solution(int[] w) {for (int i = 0; i < w.length; i++) {if (w[i] > 0) {Integer[] temp = new Integer[w[i]];Arrays.fill(temp, i);list.addAll(Arrays.asList(temp));}}Collections.shuffle(list);}public int pickIndex() {int index = (int) (Math.random() * list.size());return list.get(index);}}
前缀和+二分
class Solution { int[] preSum; public Solution(int[] w) { preSum = new int[w.length]; preSum[0] = w[0]; for (int i = 1; i < w.length; i++) { preSum[i] = preSum[i - 1] + w[i]; } } public int pickIndex() { int n = preSum.length; int l = 0; int r = n - 1; int rand = (int) Math.ceil(Math.random() * preSum[n - 1]); while (l < r) { int mid = (l + r) / 2; if (rand <= preSum[mid]) r = mid; else l = mid + 1; } return l; } }
[8.31 - medium]☆☆☆☆☆ 1109. 航班预订统计
这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。
示例 1：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]
示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号 1 2
预订记录 1 ： 10 10
预订记录 2 ： 15
总座位数： 10 25
因此，answer = [10,25]
提示：
1 <= n <= 2 104
1 <= bookings.length <= 2 104
bookings[i].length == 3
1 <= firsti <= lasti <= n
1 <= seatsi <= 104
差分数组
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] diffArr = new int[n]; //差分数组
for (int[] booking : bookings) {
diffArr[booking[0] - 1] += booking[2];
if (booking[1] < n)
diffArr[booking[1]] -= booking[2];
}
for (int i = 1; i < n; i++) {
diffArr[i] += diffArr[i - 1];
}
return diffArr;
}
}
[9.1 - medium] 165. 比较版本号
class Solution {
public int compareVersion(String version1, String version2) {
int len1 = version1.length();
int len2 = version2.length();
int start1 = -1;
int start2 = -1;
int result = 0;
while (start1 < len1 && start2 < len2) {
int end1 = parseString(version1, start1);
int val1 = Integer.parseInt(version1.substring(start1 + 1, end1));
start1 = end1;
int end2 = parseString(version2, start2);
int val2 = Integer.parseInt(version2.substring(start2 + 1, end2));
start2 = end2;
if (val1 != val2) {
result = val1 > val2 ? 1 : -1;
break;
}
}
while (result == 0 && (start1 < len1 || start2 < len2)) {
if (start1 < len1) {
int end = parseString(version1, start1);
int val = Integer.parseInt(version1.substring(start1 + 1, end));
start1 = end;
if (val != 0)
result = 1;
} else {
int end = parseString(version2, start2);
int val = Integer.parseInt(version2.substring(start2 + 1, end));
start2 = end;
if (val != 0)
result = -1;
}
}
return result;
}
int parseString(String str, int now) {
int len = str.length();
//跳过小数点
now++;
while (now < len) {
if (now < len - 1 && str.charAt(now + 1) != '.')
now++;
else
break;
}
return now + 1;
}
}
class Solution {
public int compareVersion(String version1, String version2) {
String[] strs1 = version1.split("\\.");
String[] strs2 = version2.split("\\.");
int len1 = strs1.length;
int len2 = strs2.length;
int start1 = 0;
int start2 = 0;
int result = 0;
while (start1 < len1 && start2 < len2) {
int val1 = Integer.parseInt(strs1[start1++]);
int val2 = Integer.parseInt(strs2[start2++]);
if (val1 != val2) {
result = val1 > val2 ? 1 : -1;
break;
}
}
if (result == 0 && (start1 < len1 || start2 < len2)) {
while (start1 < len1) {
int val = Integer.parseInt(strs1[start1++]);
if (val > 0) {
result = 1;
break;
}
}
while (start2 < len2) {
int val = Integer.parseInt(strs2[start2++]);
if (val > 0) {
result = -1;
break;
}
}
}
return result;
}
}
[9.2 - easy] 剑指 Offer 22. 链表中倒数第k个节点
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
int count = 1;
ListNode last = head;
while (count != k) {
last = last.next;
count++;
}
ListNode aim = head;
while (last.next != null) {
last = last.next;
aim = aim.next;
}
return aim;
}
}
[9.2 - easy] 1337. 矩阵中战斗力最弱的 K 行
class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
int n = mat.length;
Integer[] result = new Integer[n];
for (int i = 0; i < n; i++) {
result[i] = i;
}
Arrays.sort(result, (o1, o2) -> {
int index1 = o1;
int index2 = o2;
int p1 = countPower(mat[index1]);
int p2 = countPower(mat[index2]);
if (p1 != p2)
return p1 - p2;
else return index1 - index2;
});
int[] result1 = new int[k];
for (int i = 0; i < k; i++)
result1[i] = result[i];
return result1;
}
int countPower(int[] m) {
int temp = 0;
for (int num : m) {
if (num == 1)
temp++;
else break;
}
return temp;
}
}
[9.3 - medium]☆☆☆ 面试题 17.14. 最小K个数
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例：
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
提示：
0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))
快速选择
直接排序7ms，快速选择2ms
class Solution { public int[] smallestK(int[] arr, int k) { if (k == 0) return new int[0]; findSmallestK(arr, k - 1, 0, arr.length - 1); int[] result = new int[k]; System.arraycopy(arr, 0, result, 0, k); return result; } void findSmallestK(int[] arr, int k, int l, int r) { int index = sort(arr, l, r); if (index > k) findSmallestK(arr, k, l, index - 1); else if (index < k) findSmallestK(arr, k, index + 1, r); } int sort(int[] arr, int l, int r) { int temp = arr[l]; while (l < r) { // 当队尾的元素大于等于基准数据时,向前挪动high指针 while (l < r && arr[r] >= temp) { r--; } // 如果队尾元素小于tmp了,需要将其赋值给low arr[l] = arr[r]; // 当队首元素小于等于tmp时,向前挪动low指针 while (l < r && arr[l] <= temp) { l++; } // 当队首元素大于tmp时,需要将其赋值给high arr[r] = arr[l]; } arr[l] = temp; return l; } }
[9.4 - easy] 剑指 Offer 10- I. 斐波那契数列
class Solution {
int[] record;
final int MOD = 1000000007;
public int fib(int n) {
if (n == 0 || n == 1)
return n;
record = new int[n + 1];
record[1] = 1;
return count(n);
}
int count(int n) {
if (n <= 1 || record[n] != 0)
return record[n];
record[n] = (count(n - 1) + count(n - 2)) % MOD;
return record[n];
}
}
[9.5 - medium]☆☆☆☆☆ 470. 用 Rand7() 实现 Rand10()
已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random() 方法。
示例 1:
输入: 1
输出: [7]
示例 2:
输入: 2
输出: [8,4]
示例 3:
输入: 3
输出: [8,1,10]
提示:
rand7 已定义。
传入参数: n 表示 rand10 的调用次数。
进阶:
- rand7()调用次数的 期望值 是多少 ?
- 你能否尽量少调用 rand7() ?
拒绝采样
这一类问题的核心是等概率生成10个不同的数即可
- 起初我是这样做的
这种做法是错误的，因为rand7()生成的不是浮点数，而是整数，因此这样只会等概率生成7个不同的数，如3就不可能生成出来，因此本质还是rand7()class Solution extends SolBase { public int rand10() { return rand7() * 10 / 7; } }
方法一：
- 为了等概率生成10个不同的数，可以调用两次rand7()，这样两次调用的组合会有49种可能，满足了10个不同数的需要，同时，我们可以指定生成的前40个结果用来实现rand10()，拒绝剩下的9个数
注意观察该矩阵来体会
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int row, col, idx;
do {
row = rand7();
col = rand7();
idx = col + (row - 1) * 7;
} while (idx > 40);
return 1 + (idx - 1) % 10;
}
☆☆☆方法二：
两次rand7分别构造1/2和1/5的概率即可，这样概率相乘为1/10
第一次rand7限定接收[1, 6]，判断奇偶性，概率是1/2
第二次rand7限定接收[1, 5]，表示基础数
两者结合得到等概率的[1, 10]
class Solution {
public int rand10() {
int first = rand7();
while (first > 6) first = rand7();
int second = rand7();
while (second > 5) second = rand7();
return first % 2 == 0 ? second : second + 5;
}
}
[9.10 - hard]☆☆☆☆☆ 502. IPO
假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。
答案保证在 32 位有符号整数范围内。
示例 1：
输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。
示例 2：
输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6
提示：
1 <= k <= 105
0 <= w <= 109
n == profits.length
n == capital.length
1 <= n <= 105
0 <= profits[i] <= 104
0 <= capital[i] <= 109
利用堆的贪心算法
class Solution {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int n = capital.length;
int[][] map = new int[n][2];
for (int i = 0; i < n; i++) {
map[i][0] = capital[i];
map[i][1] = profits[i];
}
Arrays.sort(map, (o1, o2) -> o1[0] - o2[0]); //将资本从小到大排序
int index = 0;
int count = 0;
int nowCapital = w;
PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1); //大根堆
while (count < k) {
while (index < n && nowCapital >= map[index][0]) {
heap.add(map[index][1]);
index++;
}
if (!heap.isEmpty()) {
count++;
nowCapital += heap.poll();
} else break;
}
return nowCapital;
}
}
[9.13 - medium]☆☆ 678. 有效的括号字符串
给定一个只包含三种字符的字符串：（ ，） 和 ，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。
示例 1:
输入: “()”
输出: True
示例 2:
输入: “()”
输出: True
示例 3:
输入: “())”
输出: True
注意:
字符串大小将在 [1，100] 范围内。
栈
主要的坑就是右括号匹配完后还有可能剩下左括号和号，**而且号一定要在左括号之后才能消掉*，所以新开了一个数组来存左括号和号的前一个下标。
class Solution {
public boolean checkValidString(String s) {
//堆栈，将(和*的索引分别压入堆栈中
Deque<Integer> bracketStack = new LinkedList<>();
Deque<Integer> asteriskStack = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(')
bracketStack.push(i);
else if (c == '*')
asteriskStack.push(i);
else {
if (!bracketStack.isEmpty())
bracketStack.pop();
else if (!asteriskStack.isEmpty())
asteriskStack.pop();
else return false;
}
}
//如果还有左括号，需要判断*是否在左括号之前
while (!bracketStack.isEmpty()) {
if (!asteriskStack.isEmpty()) {
int b = bracketStack.pop();
int a = asteriskStack.pop();
if (a < b)
return false;
} else return false;
}
return true;
}
}
[9.19 - medium]☆☆☆☆☆ 650. 只有两个键的键盘
最初记事本上只有一个字符 ‘A’ 。你每次可以对这个记事本进行两种操作：
Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴 上一次 复制的字符。
给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 ‘A’ 。返回能够打印出 n 个 ‘A’ 的最少操作次数。
示例 1：
输入：3
输出：3
解释：
最初, 只有一个字符 ‘A’。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 ‘AA’。
第 3 步, 使用 Paste 操作来获得 ‘AAA’。
示例 2：
输入：n = 1
输出：0
提示：
1 <= n <= 1000
动态规划
class Solution {
public int minSteps(int n) {
int INF = 0x3f3f3f3f;
int[][] dp = new int[n + 1][n + 1];
for (int[] arr : dp)
Arrays.fill(arr, INF);
dp[1][1] = 1;
dp[1][0] = 0;
for (int i = 2; i <= n; i++) {
int min = INF;
for (int j = 1; j < i / 2 + 1; j++) {
dp[i][j] = dp[i - j][j] + 1;
min = Math.min(min, dp[i][j]);
}
dp[i][i] = min + 1; //全量复制
}
return Arrays.stream(dp[n]).min().getAsInt();
}
}
[9.20 - medium]☆☆☆ 673. 最长递增子序列的个数
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。
动态规划
自己把这道题拿捏了，牛逼
自己的思路：看着像动态规划，思考对于每个数，可以拼接到其前面的哪个数上（即比哪个数大就拼接上去），拼接时还需要考虑被拼接数的前缀长度，此时需要记录一个最长前缀长度，同时记录具有最长前缀长度的数量
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
int[] preLens = new int[n];
int[] counts = new int[n];
Arrays.fill(preLens, 1);
Arrays.fill(counts, 1);
for (int i = 1; i < n; i++) {
int maxPreLen = 0; // 最长的前缀
int count = 0; // 最长前缀的数量
for (int j = 0; j < i; j++) {
// 可以将以nums[j]为首的前缀拼接
if (nums[i] > nums[j]) {
if (preLens[j] > maxPreLen) {
maxPreLen = preLens[j];
count = counts[j];
} else if (preLens[j] == maxPreLen)
count += counts[j];
}
}
preLens[i] += maxPreLen;
if (count > 1)
counts[i] = count;
}
int max = 0;
int result = 0;
for (int i = 0; i < n; i++) {
if (preLens[i] == max)
result += counts[i];
else if (preLens[i] > max) {
max = preLens[i];
result = counts[i];
}
}
return result;
}
}
[9.26 - medium]☆☆☆ 371. 两整数之和
给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
示例 1：
输入：a = 1, b = 2
输出：3
示例 2：
输入：a = 2, b = 3
输出：5
提示：
-1000 <= a, b <= 1000
位运算
class Solution {
public int getSum(int a, int b) {
int result = a ^ b; // a异或b，得到没有进位的结果
int carry = (a & b) << 1; // a与b再向左进一位，得到进位
// 如果存在进位，则将carry与result相加
if (carry != 0)
result = getSum(result, carry);
return result;
}
}
[9.26 - medium] 实现LRU
双向链表+Hash表
public class Main {
public static void main(String[] args) {
Main main = new Main();
int[][] operators = {{1, 1, 1}, {1, 2, 2}, {1, 3, 2}, {2, 1}, {1, 4, 4}, {2, 2}};
System.out.println(Arrays.toString(main.LRU(operators, 3)));
}
static class ListNode {
int val;
int key;
ListNode next = null;
ListNode pre = null;
ListNode(int val, int key) {
this.val = val;
this.key = key;
}
}
int size = 0;
int capacity;
Map<Integer, ListNode> map = new HashMap<>();
ListNode head = null;
ListNode last = null;
public int[] LRU(int[][] operators, int k) {
capacity = k;
List<Integer> result = new ArrayList<>();
for (int[] operator : operators) {
if (operator[0] == 1)
set(operator[1], operator[2]);
else result.add(get(operator[1]));
}
return result.stream().mapToInt(i -> i).toArray();
}
void set(int key, int val) {
ListNode node = new ListNode(val, key);
map.put(key, node);
if (size == 0) {
head = node;
last = node;
size++;
} else {
node.next = head;
head.pre = node;
head = node;
size++;
if (size > capacity) {
ListNode temp = last.pre;
last.pre = null; //help GC
map.remove(last.key);
last = temp;
last.next = null;
size--;
}
}
}
int get(int key) {
ListNode node = map.get(key);
if (node == null)
return -1;
if (size > 1) {
if (last == node)
last = node.pre;
if (head != node) {
node.pre.next = node.next;
if (node.next != null)
node.next.pre = node.pre;
node.pre = null;
node.next = head;
head.pre = node;
head = node;
}
}
return head.val;
}
}
[10.1 - medium]☆☆☆ 最长公共子串
动态规划
注意子串和子序列的区别！！
public class Solution {
public String LCS(String str1, String str2) {
int m = str1.length();
int n = str2.length();
int[][] dp = new int[m + 1][n + 1]; // dp[i][j]表示以str1的第i个字符和str2的第j个字符结尾的最长公共子串长度
int max = 0;
int max_i = 0;
for (int i = 1; i <= m; i++) {
char a = str1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
char b = str2.charAt(j - 1);
if (a == b) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > max) {
max = dp[i][j];
max_i = i;
}
}
}
}
return str1.substring(max_i - max, max_i);
}
}
[10.3 - medium]☆☆☆ NC54 数组中相加和为0的三元组
双指针
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.threeSum(new int[]{-2, 0, 1, 1, 2}));
}
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
Arrays.sort(num);
int n = num.length;
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
for (int i = 0; i < n - 2; i++) {
if (num[i] > 0)
break;
if (i > 0 && num[i] == num[i - 1])
continue;
int target = -num[i];
// 双指针查找符合条件的另外两个数
int l = i + 1;
int r = n - 1;
while (l < r) {
if (num[l] + num[r] == target) {
result.add(new ArrayList<>(Arrays.asList(num[i], num[l], num[r])));
l++;
r--;
while (l < r && num[l] == num[l - 1]) l++;
while (l < r && num[r] == num[r + 1]) r--;
} else if (num[l] + num[r] < target)
l++;
else
r--;
}
}
return result;
}
}
[10.6 - medium]☆☆☆☆☆ NC91 最长递增子序列
动态规划 + 二分
LeetCode 673写过类似的题，但是当时是用朴素的dp算法，时间复杂度O(n2)，在这个题上会超时，这里可以采用二分查找的方式使得时间复杂度降到O(nlogn)
注意关于字典序，有若dp[i] = dp[j], i < j 那么一定有arr[j] < arr[i]，所以倒着查dp
public class Solution {
int maxLen = 0;
public int[] LIS(int[] arr) {
// write code here
int n = arr.length;
int[] dp = new int[n + 1];
// minEnds[i]记录前缀长度为i的最小结尾
int[] minEnds = new int[n + 1];
Arrays.fill(dp, 1);
Arrays.fill(minEnds, Integer.MAX_VALUE);
minEnds[0] = 0;
for (int i = 0; i < n; i++) {
int val = arr[i];
// 找到小于val的最长前缀
int index = binarySearch(val, minEnds);
dp[i] = index + 1;
// 如果val比长度为index+1的前缀最小结尾还小，则用val替换最小结尾
minEnds[index + 1] = Math.min(minEnds[index + 1], val);
maxLen = Math.max(maxLen, index + 1);
}
// 倒着查dp即可保证字典序最小
// 原因：若dp[i] = dp[j], i < j 那么一定有arr[j] < arr[i]，所以倒着查dp
int[] result = new int[maxLen];
int index = maxLen - 1;
int len = maxLen;
for (int i = n-1; i >= 0; i--) {
if (dp[i] == len) {
len--;
result[index--] = arr[i];
}
}
return result;
}
int binarySearch(int val, int[] minEnds) {
int l = 0;
int r = maxLen;
while (l < r) {
int mid = (int) Math.ceil(l + (double) (r - l) / 2);
int minEnd = minEnds[mid];
if (val <= minEnd)
r = mid - 1;
else l = mid;
}
return l;
}
}
[10.7 - medium] NC128 接雨水问题
双指针
个人解法稍显复杂，时间复杂度一样
实际上的解法是
首先比较两个边界，从小边界一侧开始向另一侧移动并累加水量（因为另一侧有比该侧更高的柱子，肯定能接到水），当碰到比小的边界更高的柱子时，重新小的边界，然后继续从小边界一侧向另一侧移动
个人做法
public class Solution { public long maxWater(int[] arr) { int n = arr.length; if (n < 3) return 0; int[] leftMax = new int[n]; int tempMax = 0; for (int i = 0; i < n; i++) { if (arr[i] >= tempMax) { tempMax = arr[i]; } leftMax[i] = tempMax; } int[] rightMax = new int[n]; tempMax = 0; for (int i = n - 1; i >= 0; i--) { if (arr[i] >= tempMax) { tempMax = arr[i]; } rightMax[i] = tempMax; } int l = 0; int r = n - 1; long result = 0; boolean flag = true; while (l < r) { if (flag) { // 右侧没有更高的了，现在从右往左计算 if (rightMax[l + 1] < arr[l]) { flag = false; } else { int temp = l + 1; long sum = 0; int count = 0; while (arr[temp] < arr[l]) { count++; sum += arr[temp]; temp++; } result += ((long) arr[l] * count - sum); l = temp; } } else { // 左侧没有更高的了，现在从左向右计算 if (leftMax[r - 1] < arr[r]) { flag = true; } else { int temp = r - 1; long sum = 0; int count = 0; while (arr[temp] < arr[r]) { count++; sum += arr[temp]; temp--; } result += ((long) arr[r] * count - sum); r = temp; } } } return result; } }
[10.24 - medium]☆☆☆ 638. 大礼包
在 LeetCode 商店中， 有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。
还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1 ，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。
返回 确切 满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。
示例 1：
输入：price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
输出：14
解释：有 A 和 B 两种物品，价格分别为 ¥2 和 ¥5 。
大礼包 1 ，你可以以 ¥5 的价格购买 3A 和 0B 。
大礼包 2 ，你可以以 ¥10 的价格购买 1A 和 2B 。
需要购买 3 个 A 和 2 个 B ， 所以付 ¥10 购买 1A 和 2B（大礼包 2），以及 ¥4 购买 2A 。
示例 2：
输入：price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]
输出：11
解释：A ，B ，C 的价格分别为 ¥2 ，¥3 ，¥4 。
可以用 ¥4 购买 1A 和 1B ，也可以用 ¥9 购买 2A ，2B 和 1C 。
需要买 1A ，2B 和 1C ，所以付 ¥4 买 1A 和 1B（大礼包 1），以及 ¥3 购买 1B ， ¥4 购买 1C 。
不可以购买超出待购清单的物品，尽管购买大礼包 2 更加便宜。
提示：
n == price.length
n == needs.length
1 <= n <= 6
0 <= price[i] <= 10
0 <= needs[i] <= 10
1 <= special.length <= 100
special[i].length == n + 1
0 <= special[i][j] <= 50
回溯法
本题有很明显的完全背包问题特征，但是物品过多，会导致dp的维度过多或索引转换等问题，较为复杂
这里实际上可以采用回溯法来简单解决，因为数据量比较小
// cyc
class Solution {
int n; // needs.length
int m; // special.length
int[] now;
int result = Integer.MAX_VALUE;
int nowPrice = 0;
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
n = needs.size();
m = special.size();
now = new int[n];
dfs(price, special, needs, 0);
return result;
}
void dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int index) {
if (index == m) {
// 尝试过所有礼包后，把没有买的物品以单价购买并计算最小结果
int temp = nowPrice;
for (int i = 0; i < n; i++) {
temp += (needs.get(i) - now[i]) * price.get(i);
}
result = Math.min(result, temp);
} else {
List<Integer> nowSpecial = special.get(index);
int specialPrice = nowSpecial.get(n);
boolean flag = true;
// 判断买下礼包后物品数量是否超限
for (int i = 0; i < n; i++) {
if (nowSpecial.get(i) + now[i] > needs.get(i)) {
flag = false;
break;
}
}
if (flag) {
// 可以买下礼包
for (int i = 0; i < n; i++) {
now[i] += nowSpecial.get(i);
}
nowPrice += specialPrice;
// 礼包可以无限买，因此继续尝试买当前礼包
dfs(price, special, needs, index);
for (int i = 0; i < n; i++) {
now[i] -= nowSpecial.get(i);
}
nowPrice -= specialPrice;
}
// 不买当前礼包
dfs(price, special, needs, index + 1);
}
}
}
若有收获，就点个赞吧
0 人点赞
