读数
把一个数字用中文表示出来。数字范围为 [0, 99999]。为了方便输出，使用字母替换相应的中文：
万W 千Q 百B 十S 零L。
注意：对于 11 应该表示为 一十一（1S1），而不是十一（S1）
输入描述：
数字 0（包含）到 99999（包含）。
输出描述：
用字母替换相应的中文，万W 千Q 百B 十S 零L
示例：
// 输入12001// 输出1W2QL1
代码实现：
import java.util.Arrays;
import java.util.List;
public class ChineseExpression {
static String getNumChiExp(int num) {
if (num < 0 || num > 99999) return null;
if (num < 10) return String.valueOf(num);
List<String> list = Arrays.asList(new String[]{"S", "B", "Q", "W"});
StringBuilder sb = new StringBuilder();
String str = String.valueOf(num);
for (int i = str.length() - 1; i >= 0; i--) {
char cur = str.charAt(i);
if (cur == '0' && sb.length() > 0 && i > 0 && i != str.length() - 1 && str.charAt(i + 1) != '0') {
sb.insert(0, "L");
continue;
}
if (cur != '0') {
if (i != str.length() - 1) {
int temp = str.length() - i - 1;
while (temp > 0) {
sb.insert(0, list.get(temp % 4 == 0 ? 3 : temp % 4 - 1));
temp -= 4;
}
}
sb.insert(0, cur);
}
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(getNumChiExp(11001));
for (int i = 0; i < 100000; i++) {
System.out.println(getNumChiExp(i));
}
}
}
未出现的数
给定一个整数数组 A，长度为 n，有 1 <= A[i] <= n，且对于 [1,n] 的整数，其中部分整数会重复出现而部分不会出现。实现算法找到 [1,n] 中所有未出现在 A 中的整数。
提示：尝试实现 O(n) 的时间复杂度和 O(1) 的空间复杂度（返回值不计入空间复杂度）。
输入描述：
一行数字，全部为整数，空格分隔
A0 A1 A2 A3…
输出描述：
一行数字，全部为整数，空格分隔R0 R1 R2 R3…
示例1:
// 输入
1 3 4 3
// 输出
2
思路：
首先想到的：直接创建一个长度为 n 的数组 B，然后遍历 A，将 A 中每个元素 A[i] 放入对应的下标中 B[A[i]] = 1，然后遍历 B，将 B 中为 0 的下标打印出来就是 A 中为出现的数。但是该思路中需要用到辅助数组 B，做不到 O(1) 的空间复杂度。
那么，怎么才能做到空间复杂度为 O(1) 呢？
可以在遍历时，将当前遍历到的 A[i] 和 A[A[i]] 交换，这样就能使 A[i] 放到了自己相等的下标上，然后继续将新的 A[i] 和 A[A[i]] 交换直到 A[i] 和 A[A[i]] 不能再交换（A[A[i]] == A[i] 就不能再交换）停止，然后继续遍历。当遍历完成时，再一次遍历数组，如果 A[i] 上的数不等于 i+1，那么就说明该数不存在。
import com.example.test.base.sort.ArrayGenerator;
import java.util.Arrays;
public class PrintNumberNoInArray {
static void printNumberNoInArray(int[] A) {
if (A == null || A.length == 0) return;
int[] B = new int[A.length];
for (int i : A) {
B[i - 1] = 1;
}
for (int i = 0; i < B.length; i++) {
if (B[i] == 0) System.out.print(i + 1 + " ");
}
System.out.println();
}
static void printNumberNoInArray1(int[] A) {
if (A == null || A.length == 0) return;
for (int i = 0; i < A.length; i++) {
modify(A[i], A);
}
for (int i = 0; i < A.length; i++) {
if (A[i] != i + 1) System.out.print(i + 1 + " ");
}
System.out.println();
}
static void modify(int value, int[] arr) {
while (arr[value - 1] != value) {
int tmp = arr[value - 1];
arr[value - 1] = value;
value = tmp;
}
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
int[] arr = ArrayGenerator.getArr(10, 10);
for (int j = 0; j < arr.length; j++) {
arr[j] += 1;
}
System.out.println(Arrays.toString(arr));
printNumberNoInArray(arr);
printNumberNoInArray1(arr);
System.out.println("##########################");
}
}
}
被 3 整除
小Q 得到一个神奇的数列：1, 12, 123,...12345678910,1234567891011...。并且小Q对于能否被 3 整除这个性质很感兴趣。小Q 现在希望你能帮他计算一下从数列的第 l 个到第 r 个（包含端点）有多少个数可以被 3 整除。
输入描述：
输入包括两个整数 l 和 r （1 <= l <= r <= 1e9），表示要求解的区间两端。
输出描述：
输出一个整数，表示区间内能被3整除的数字个数。
示例1:
// 输入
2 5
// 输出
3
思路：
能被 3 整除是很好计算的，直接模 3 判断就可以；或者将这个数的所有位置上的数相加后再模 3。
那么就在于这个数列或者这个数列中每一项的和是如何实现了，每一项的和正好是一个等差数列，等差数列的和为：。
代码实现：
public class ThreeTimes {
public static int getNum(int l, int r) {
int sum = 0;
for (int i = l; i <= r; i++) {
long tmp = (long) (i + 1) * (long) i / 2L;
if (tmp % 3 == 0) {
sum++;
}
}
return sum;
}
}
花费最少
CC 直播里面有一个土豪很喜欢一位女直播 Kiki 唱歌，平时就经常给她点赞、送礼、私聊。最近 CC 直播平台在举行中秋之星主播唱歌比赛，假设一开始该女主播的初始人气值为 start， 能够晋升下一轮人气需要刚好达到 end，土豪给主播增加人气的可以采取的方法有：
- 点赞 花费 x C币，人气 + 2
- 送礼 花费 y C币，人气 * 2
- 私聊 花费 z C币，人气 - 2
其中 end 远大于 start 且 end 为偶数， 请写一个程序帮助土豪计算一下，最少花费多少C币就能帮助该主播 Kiki 将人气刚好达到 end，从而能够晋级下一轮？
输入描述：
第一行输入5个数据，分别为：x y z start end，每项数据以空格分开。其中：0＜x, y, z＜＝10000，0＜start，end＜＝1000000
输出描述：
需要花费的最少C币。
示例1:
// 输入
3 100 1 2 6
// 输出
6
思路：
首先肯定是递归所有操作，但是在写出来之后就会发现这个递归式个死循环。因为存在 -2 的操作，总会将现在的人气回归到之前的某时间的人气，然后让有执行 +2 或者 *2 再将人气涨回来……然后就会发现递归死住了。为什么会出现这样的情况呢？因为递归的 basecase 设置的不够好，我们需要设置更多的现在条件。
根据题干，可以知道：
- start、end 都是偶数，且 start < end，那么 start 一定可以通过 +2 来得到 end，也就是说花费 C 币一定不会比
(end - start)/2 * x多 - 人气如果需要执行 -2 操作来到达 end，那么人气一定不会大于等于 2end，因为要到达 2end 只有可能是：
- 使用 +2 操作大于等于 2*end，那为什么不直接到达 end 就停止呢？
- 使用 2 操作大于等于 2end，那说明是在 end 或者 大于 end 时使用的 *2，那为什么不使用 -2 操作呢？
所以说，一定不会到达 2*end
增加限制条件后写递归。然后可以修改为动态规划
代码实现：
public class Kiki {
static int minCoins(int add, int times, int del, int start, int end) {
return process(add, times, del, start, end, ((end - start) / 2) * add, start, 0);
}
/**
* @param add
* @param times
* @param del
* @param start
* @param end
* @param limit 限制：不会超过使用 +2 达到 end 的钱
* @param cur 当前的人气
* @param coin 花费
* @return
*/
static int process(int add, int times, int del, int start, int end, int limit, int cur, int coin) {
if (cur == end) {
return coin;
}
if (coin > limit || cur < 0 || cur > 2 * end) {
return Integer.MAX_VALUE;
}
int c1 = process(add, times, del, start, end, limit, cur + 2, coin + add);
int c2 = process(add, times, del, start, end, limit, cur * 2, coin + times);
int c3 = process(add, times, del, start, end, limit, cur - 2, coin + del);
return Math.min(c1, Math.min(c2, c3));
}
// 动态规划
static int minCoins1(int add, int times, int del, int start, int end) {
int x = ((end - start) / 2) * add;
int y = 2 * end;
int[][] dp = new int[x + 1][y + 1];
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
if (j == end) {
dp[i][j] = i;
} else {
dp[i][j] = Integer.MAX_VALUE;
}
}
}
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
if (i + add <= x && j + 2 <= y) {
dp[i][j] = Math.min(dp[i][j], dp[i + add][j + 2]);
}
if (i + times <= x && j * 2 <= y) {
dp[i][j] = Math.min(dp[i][j], dp[i + times][j * 2]);
}
if (i + del <= x && j - 2 >= 0) {
dp[i][j] = Math.min(dp[i][j], dp[i + del][j - 2]);
}
}
}
return dp[x][end];
}
public static void main(String[] args) {
System.out.println(minCoins(3, 100, 1, 2, 6));
System.out.println(minCoins1(3, 100, 1, 2, 20));
}
}
最大奖励
CC 直播的运营部门组织了很多运营活动，每个活动需要花费一定的时间参与，主播每参加完一个活动即可得到一定的奖励，参与活动可以从任意活动开始，但一旦开始，就需要将后续活动参加完毕（注意：最后一个活动必须参与），活动之间存在一定的依赖关系（不存在环的情况），现在给出所有的活动时间与依赖关系，以及给出有限的时间，请帮主播计算在有限的时候内，能获得的最大奖励，以及需要的最少时长。
如上图数据所示，给定有限时间为 10 天。可以获取得最大奖励为：11700，需要的时长为：9 天。参加的活动为 BDFH 四个。
输入描述：
第一行输入数据 N 与 D，表示有 N 项活动，D 表示给予的时长。0＜N＜＝1000，0＜D＜＝10000。
从第二行开始到 N+1 行，每行描述一个活动的信息，其中第一项表示当前活动需要花费的时间 t，第二项表示可以获得的奖励 a，之后有 N 项数据，表示当前活动与其他活动的依赖关系，1 表示有依赖，0 表示无依赖。每项数据用空格分开。
输出描述：
输出两项数据 A 与 T，用空格分割。A 表示所获得的最大奖励，T 表示所需要的时长。
// 输入
8 10
3 2000 0 1 1 0 0 0 0 0
3 4000 0 0 0 1 1 0 0 0
2 2500 0 0 0 1 0 0 0 0
1 1600 0 0 0 0 1 1 1 0
4 3800 0 0 0 0 0 0 0 1
2 2600 0 0 0 0 0 0 0 1
4 4000 0 0 0 0 0 0 0 1
3 3500 0 0 0 0 0 0 0 0
// 输出
11700 9
思路：让每个活动都得到该活动在每种消耗时间情况下的最大收益，如在 A 活动最大收益为 3 天 2000，在 B 活动为 [3 天 4000、6 天 6000]，在 C 活动为 [2 天 2500、5 天 4500]，D 活动为 [1 天 1600、3 天 4100、4 天 5600、6 天 6100、 7 天 7600 ]……每个活动收益都可以通过本活动收益 + 之前的活动收益得到。这样就可以得到最大的收益：
代码实现，这段是自己写的：
import java.util.*;
public class MaxRevenue {
private static int[] maxRevenue(int allTime, int[] revenue, int[] times, int[][] dependents) {
int num = dependents.length;
// 每个活动 和 后续活动 的依赖关系
TreeMap<Integer, List<Integer>> actMap = new TreeMap<>();
// 每个活动 和 之前活动 的依赖关系
HashMap<Integer, List<Integer>> actDepMap = new HashMap<>();
for (int i = 0; i < num; i++) {
if (!actMap.containsKey(i)) actMap.put(i, new ArrayList<>());
for (int j = 0; j < dependents[0].length; j++) {
if (!actDepMap.containsKey(j)) actDepMap.put(j, new ArrayList<>());
if (dependents[i][j] == 0) continue;
actMap.get(i).add(j);
actDepMap.get(j).add(i);
}
}
return getMax(revenue, times, allTime, actMap, actDepMap);
}
private static int[] getMax(int[] revenue, int[] times, int allTime, TreeMap<Integer, List<Integer>> actMap, HashMap<Integer, List<Integer>> actDepMap) {
// <活动, <天数, 最大收益>>
Map<Integer, Map<Integer, Integer>> maxMap = new HashMap<>();
// 天数
int time = 0;
// 最大收益
int max = 0;
for (Map.Entry<Integer, List<Integer>> entry : actMap.entrySet()) {
Integer key = entry.getKey();
if (!maxMap.containsKey(key)) maxMap.put(key, new HashMap<>());
// 上一节点
List<Integer> preKeyList = actDepMap.get(key);
maxMap.put(key, new HashMap<>());
maxMap.get(key).put(times[key], revenue[key]);
if (preKeyList == null || preKeyList.isEmpty()) continue;
for (Integer preKey : preKeyList) {
if (maxMap.get(preKey) != null) {
// 当前收益 = 上一个节点的最大收益 + 本次活动收益
// 记录不同时间的最大收益
for (Map.Entry<Integer, Integer> preEntry : maxMap.get(preKey).entrySet()) {
int curTime = preEntry.getKey() + times[key];
if (curTime <= allTime) {
int newRevenue = preEntry.getValue() + revenue[key];
if (!maxMap.containsKey(key)) maxMap.put(key, new HashMap<>());
if (!maxMap.get(key).containsKey(curTime)) {
maxMap.get(key).put(curTime, newRevenue);
} else {
Integer oldRevenue = maxMap.get(key).get(curTime);
if (newRevenue > oldRevenue) {
maxMap.get(key).put(curTime, newRevenue);
} else {
newRevenue = oldRevenue;
}
}
if (max < newRevenue) {
max = newRevenue;
time = curTime;
} else if (max == newRevenue) {
time = Math.min(time, curTime);
}
}
}
} else {
maxMap.put(key, new HashMap<>());
maxMap.get(key).put(times[key], revenue[key]);
}
}
}
return new int[]{time, max};
}
public static void main(String[] args) {
int allTime = 10;
int[] revenue = {2000, 4000, 2500, 1600, 3800, 2600, 4000, 3500};
int[] times = {3, 3, 2, 1, 4, 2, 4, 3};
int[][] dependents = {
{0, 1, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0}};
int[] res = maxRevenue(allTime, revenue, times, dependents);
System.out.println(res[0] + " , " + res[1]);
}
}
下面这段是答案，直接复制粘贴上来的：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.TreeMap;
public class Problem06_MaxRevenue {
// 请保证只有唯一的最后节点
public static int[] maxRevenue(int allTime, int[] revenue, int[] times, int[][] dependents) {
int size = revenue.length;
HashMap<Integer, ArrayList<Integer>> parents = new HashMap<>();
for (int i = 0; i < size; i++) {
parents.put(i, new ArrayList<>());
}
int end = -1;
for (int i = 0; i < dependents.length; i++) {
boolean allZero = true;
for (int j = 0; j < dependents[0].length; j++) {
if (dependents[i][j] != 0) {
parents.get(j).add(i);
allZero = false;
}
}
if (allZero) {
end = i;
}
}
HashMap<Integer, TreeMap<Integer, Integer>> nodeCostRevenueMap = new HashMap<>();
for (int i = 0; i < size; i++) {
nodeCostRevenueMap.put(i, new TreeMap<>());
}
nodeCostRevenueMap.get(end).put(times[end], revenue[end]);
LinkedList<Integer> queue = new LinkedList<>();
queue.add(end);
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int last : parents.get(cur)) {
for (Entry<Integer, Integer> entry : nodeCostRevenueMap.get(cur).entrySet()) {
int lastCost = entry.getKey() + times[last];
int lastRevenue = entry.getValue() + revenue[last];
TreeMap<Integer, Integer> lastMap = nodeCostRevenueMap.get(last);
if (lastMap.floorKey(lastCost) == null || lastMap.get(lastMap.floorKey(lastCost)) < lastRevenue) {
lastMap.put(lastCost, lastRevenue);
}
}
queue.add(last);
}
}
TreeMap<Integer, Integer> allMap = new TreeMap<>();
for (TreeMap<Integer, Integer> curMap : nodeCostRevenueMap.values()) {
for (Entry<Integer, Integer> entry : curMap.entrySet()) {
int cost = entry.getKey();
int reven = entry.getValue();
if (allMap.floorKey(cost) == null || allMap.get(allMap.floorKey(cost)) < reven) {
allMap.put(cost, reven);
}
}
}
return new int[] { allMap.floorKey(allTime), allMap.get(allMap.floorKey(allTime)) };
}
public static void main(String[] args) {
int allTime = 10;
int[] revenue = { 2000, 4000, 2500, 1600, 3800, 2600, 4000, 3500 };
int[] times = { 3, 3, 2, 1, 4, 2, 4, 3 };
int[][] dependents = {
{ 0, 1, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 1, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 1, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0 } };
int[] res = maxRevenue(allTime, revenue, times, dependents);
System.out.println(res[0] + " , " + res[1]);
}
}
求完全二叉树节点的个数
思路：
首先遍历该树并统计肯定是可以的，那有没有更快的呢？
根据完全二叉树的特性：除了最下层的节点外其他层都是满的，而最下层的节点都集中到左侧。
那么就可以先求出该树左子树最左侧的节点并统计树的深度为 h，然后遍历右子树的最左侧节点，如果：
- 右子树的最左侧节点深度为 h，说明左子树是满二叉树，总的节点个数为：
2^h - 1 + 1 + ? (左子树节点个数 + 头结点 + 右子树节点个数) - 右子树的最左侧节点深度为 h-1，说明右子树是满二叉树，总的节点个数为：
2^(h-1) - 1 + 1 + ?(左子树节点个数 + 头结点 + 右子树节点个数)
然后去递归计算未知的子树个数
代码实现：
public class CompleteTreeNodeNumber {
static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
private static int nodeNum(Node head) {
if (head == null) return 0;
return process(head, 1, getMostLeftLevel(head, 1));
}
/**
* @param node 当前节点
* @param level 当前节点的深度
* @param height 树的高度
* @return
*/
static int process(Node node, int level, int height) {
if (level == height) return 1;
if (getMostLeftLevel(node.right, level + 1) == height) {
// 左子树是满二叉树
return (1 << height - level) + process(node.right, level + 1, height);
} else {
// 右子树是满二叉树
return (1 << height - level - 1) + process(node.left, level + 1, height);
}
}
// 获取最左侧节点深度
private static int getMostLeftLevel(Node node, int level) {
while (node != null) {
level++;
node = node.left;
}
return level - 1;
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
System.out.println(nodeNum(head));
}
}
最长递增子序列问题
例子：
// 输入
[3, 1, 2, 6, 3, 4]
// 输出
[1, 2, 3, 4]
思路一：
递归，第 i 个数可以取或者不取，强行拼出一个最长的有序子序列
思路二：
动态规划：遍历数组，使用数组 dp 保存每个位置上以该数结尾的最小有序子序列的长度，如数组：[3, 1, 2, 6, 3, 4] 遍历：
- 3 是第一个数，能组成最小的有序子序列长度为 1
- 1 < 3，能组成最小的有序子序列长度为 1
- 2 之前比 2 小的长度最大的是 1，能组成最小的有序子序列长度为 2
- 6 之前比 6 小的长度最大的是 2，能组成最小的有序子序列长度为 3
- 3 之前比 3 小的长度最大的是 2，能组成最小的有序子序列长度为 3
- 4 之前比 4 小的长度最大的是 3，能组成最小的有序子序列长度为 4
这样，在 dp 数组中最大值就是最大长度
思路三：
对动态规划的优化，使用一个额外的数组 ends 来记录每个子序列长度的最小结尾：
arr[0] = 3，是第一个数，能组成最小的有序子序列长度为 1，长度为 1 的最小结尾就是 3，此时，dp = [1, 0, 0, 0, 0, 0]、ends = [3, 0, 0, 0, 0, 0]arr[1] = 1，二分查找ends，找到大于 1 的数第一个数，如果找到就更新，没有找到就扩展ends，此时找到了 3 > 1，更新。dp[i] 的值为 ends 的下标 + 1，此时dp = [1, 1, 0, 0, 0, 0]、ends = [1, 0, 0, 0, 0, 0]arr[2] = 2，二分查找ends，找到大于 2 的数第一个数，没有找到扩展ends。dp[i] 的值为 ends 的下标 + 1，此时dp = [1, 1, 2, 0, 0, 0]、ends = [1, 2, 0, 0, 0, 0]arr[3] = 6，二分查找ends，找到大于 6 的数第一个数，没有找到扩展ends。dp[i] 的值为 ends 的下标 + 1，此时dp = [1, 1, 2, 3, 0, 0]、ends = [1, 2, 6, 0, 0, 0]arr[4] = 3，二分查找ends，找到大于 3 的数第一个数为 6，更新。dp[i] 的值为 ends 的下标 + 1，此时dp = [1, 1, 2, 3, 3, 0]、ends = [1, 2, 3, 0, 0, 0]arr[5] = 4，二分查找ends，找到大于 4 的数第一个数，没有找到扩展ends。dp[i] 的值为 ends 的下标 + 1，此时dp = [1, 1, 2, 3, 4, 0]、ends = [1, 2, 3, 4, 0, 0]
返回 dp 的最大值。
代码实现：
import java.util.Arrays;
public class LongestIncrementSubArr {
// 思路一：递归
static int[] getLongest(int[] arr) {
if (arr == null || arr.length == 0) return null;
ReturnType data = process(arr, 0, new int[arr.length], 0);
int[] res = Arrays.copyOf(data.arr, data.size);
return res;
}
static class ReturnType {
int[] arr;
int size;
public ReturnType(int[] arr, int size) {
this.arr = arr;
this.size = size;
}
}
static ReturnType process(int[] arr, int i, int[] orderArr, int j) {
if (i == arr.length) return new ReturnType(orderArr, j);
int[] temp = Arrays.copyOf(orderArr, orderArr.length);
if (j == 0 || j > 0 && arr[i] > orderArr[j - 1]) {
temp[j] = arr[i];
ReturnType data1 = process(arr, i + 1, temp, j + 1);
ReturnType data2 = process(arr, i + 1, orderArr, j);
return data1.size > data2.size ? data1 : data2;
}
return new ReturnType(orderArr, j);
}
// 思路二：动态规划
static int getLongest1(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int[] dp = new int[arr.length];
dp[0] = 1;
int max = 1;
for (int i = 1; i < arr.length; i++) {
int preMax = 0;
for (int j = 0; j < i; j++) {
// 找到之前比arr[i]小的最大长度
if (arr[j] < arr[i] && dp[j] > preMax) {
preMax = dp[j];
}
}
dp[i] = preMax + 1;
max = Math.max(max, dp[i]);
}
return max;
}
// 思路三：ends 数组优化
static int getLongest2(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int[] dp = new int[arr.length];
dp[0] = 1;
int[] ends = new int[arr.length];
ends[0] = arr[0];
int endsLength = 1;
int max = 1;
for (int i = 1; i < arr.length; i++) {
int j = 0;
boolean flag = false;
// 因为 ends 有单调性，这里可以使用二分查找，但是我懒得写了
for (; j < endsLength; j++) {
if (ends[j] > arr[i]) {
ends[j] = arr[i];
flag = true;
break;
}
}
if (!flag) ends[endsLength++] = arr[i];
dp[i] = endsLength;
max = Math.max(max, dp[i]);
}
return max;
}
public static void main(String[] args) {
int[] arr = {3, 1, 2, 6, 3, 4};
int[] arr1 = {3, 1, 5, -1, 2, 6, 4, 5, 3, 4, 8};
System.out.println(Arrays.toString(getLongest(arr)));
System.out.println(Arrays.toString(getLongest(arr1)));
System.out.println(getLongest1(arr));
System.out.println(getLongest1(arr1));
System.out.println(getLongest2(arr));
System.out.println(getLongest2(arr1));
}
}
若有收获，就点个赞吧
0 人点赞
