当前位置:网站首页>递增的三元子序列[贪心训练]
递增的三元子序列[贪心训练]
2022-07-04 12:51:00 【REN_林森】
前言
贪心需要认真分析+巧妙的思考,所以需要平时练习时细节思考的积累+见识广度,是考察算法题能力的好类型题,和单调栈/dp一样。
一、递增的三元子序列
二、贪心练习
package everyday.greed;
// 递增的三元子序列
public class IncreasingTriplet {
/* target:前中后,是否存在递增序列。 可记录以每个位置结尾的 */
// 4 5 1 2 3
// 4 5 1 8
// 暴力找找感觉
public boolean increasingTriplet(int[] nums) {
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
if (nums[i] >= nums[j]) continue;
for (int k = j + 1; k < n; k++) {
if (nums[j] >= nums[k]) continue;
return true;
}
}
}
return false;
}
/* 小中右,以中mid为参考点。如果存在左边最小元素minLeft & minLeft < mid。右边最大元素maxRight & maxRight > mid,则存在这样的三元组。 可提前把最小左和最大右记录好,空间换时间。 */
public boolean increasingTriplet2(int[] nums) {
int n = nums.length;
int[] minLeft = new int[n];
int[] maxRight = new int[n];
// 填充左边最小元素。
// bug1:1 << 31是Integer.MIN_VALUE;1 << 30并不是Integer.MAX_VALUE
int min = 0x7FFFFFFF;
// int min = -((1 << 31) + 1);
for (int i = 0; i < n; i++) {
minLeft[i] = min;
min = Math.min(min, nums[i]);
}
int max = 1 << 31;
for (int i = n - 1; i >= 0; i--) {
maxRight[i] = max;
max = Math.max(max, nums[i]);
}
// 遍历nums,使其nums[i]为中心点,判定两边的是否有符合条件的节点。
for (int i = 0; i < n; i++) if (nums[i] > minLeft[i] && maxRight[i] > nums[i]) return true;
// 找不到这样的三元组。
return false;
/* 总结:为什么我想不到这做法? 第一,算法知识量积累少,见识太少。 第二,由于积累量,还是get不到问题的关键点。 第三,这种多元素相对问题,参考点过于死板,比如一上来就算先找左->找大于左的中->找大于中的右。 如果我先确定中,只需找小于中的左 ->联想到这个左应该是左的最小值;再找大于中的右->联想到这个右应该是右的最大值。 从而联想到用空间换时间,记录左->右的最小值;右->左的最大值。 */
}
/* 上面的思路,提供给我们:左边放最小,右边放最大。 以左left 中mid 为参考,寻找右right, 如果right > mid,则找到合法三元组; 如果right > left,则替换mid = right,让小点的值作中。 如果right < left,则让right成为左小,固定好左最小,这样岂不是mid需要换,毕竟mid的小标是小于right的! 不需要,原来的left < mid关系依然存在,right顶替left,只是保证后面的值能慢慢替换mid,进而找到符合条件的真right。 只要left位置在,就保存了曾经存在的left < mid关系,而且left = right,还保持了当前左边的最小值信息,以便后面寻找。 */
public boolean increasingTriplet3(int[] nums) {
int left = nums[0], mid = 0x7FFFFFFF;
for (int i = 1; i < nums.length; i++) {
int right = nums[i];
if (right > mid) return true;
if (right > left) mid = right;
else left = right;
}
// 没有寻找到
return false;
/* 总结:这种贪心,确实需要一定的分析&理解&见识&训练才能想得到。 所以我要学的算法知识&见的算法思路还有很多先500 -> 1000 -> 2000题吧,路还很长,要学的还很多,分析&理解问题的能力还得多训练。 */
}
}
总结
1)为什么我想不到这做法?
第一,算法知识量积累少,见识太少;
第二,由于积累量,还是get不到问题的关键点;
第三,这种多元素相对问题,参考点过于死板,比如一上来就算先找左->找大于左的中->找大于中的右。
如果我先确定中,只需找小于中的左 ->联想到这个左应该是左的最小值;再找大于中的右->联想到这个右应该是右的最大值。
从而联想到用空间换时间,记录左->右的最小值;右->左的最大值。2)这种巧妙的贪心为什么想不到?
确实需要一定的分析&理解&见识&训练才能想得到。
所以我要学的算法知识&见的算法思路还有很多先500 -> 1000 -> 2000题吧,路还很长,要学的还很多,分析&理解问题的能力还得多训练。
参考文献
[1] LeetCode 递增的三元组
边栏推荐
- 吃透Chisel语言.11.Chisel项目构建、运行和测试(三)——Chisel测试之ScalaTest
- Variable promotion and function promotion in JS
- Understand chisel language thoroughly 11. Chisel project construction, operation and test (III) -- scalatest of chisel test
- [antd step pit] antd form cooperates with input Form The height occupied by item is incorrect
- [FAQ] summary of common causes and solutions of Huawei account service error 907135701
- IP 实验室月复盘 · 第 5 期
- C language programming topic reference
- Unity shader learning (3) try to draw a circle
- MySQL8版本免安装步骤教程
- 吃透Chisel语言.08.Chisel基础(五)——Wire、Reg和IO,以及如何理解Chisel生成硬件
猜你喜欢
sharding key type not supported
安装Mysql
华昊中天冲刺科创板:年亏2.8亿拟募资15亿 贝达药业是股东
Unity Shader学习(三)试着绘制一个圆
使用默认路由作为指向Internet的路由
学内核之三:使用GDB跟踪内核调用链
Haobo medical sprint technology innovation board: annual revenue of 260million Yonggang and Shen Zhiqun are the actual controllers
【Antd踩坑】Antd Form 配合Input.Group时出现Form.Item所占据的高度不对
Excel快速合并多行数据
markdown 语法之字体标红
随机推荐
30: Chapter 3: develop Passport Service: 13: develop [change / improve user information, interface]; (use * * * Bo class to accept parameters, and use parameter verification)
China Post technology rushes to the scientific innovation board: the annual revenue is 2.058 billion, and the postal group is the major shareholder
R语言使用dplyr包的mutate函数对指定数据列进行标准化处理(使用mean函数和sd函数)并基于分组变量计算标准化后的目标变量的分组均值
程序员的焦虑
BLOB,TEXT GEOMETRY or JSON column 'xxx' can't have a default value query 问题
205. 同构字符串
2022危险化学品经营单位主要负责人练习题及模拟考试
[antd step pit] antd form cooperates with input Form The height occupied by item is incorrect
安装Mysql
華昊中天沖刺科創板:年虧2.8億擬募資15億 貝達藥業是股東
美国土安全部部长警告移民“不要踏上危险的旅程”
如何在 2022 年为 Web 应用程序选择技术堆栈
sharding key type not supported
[FAQ] Huawei Account Service Error Report 907135701 Common reasons Summary and Solutions
[FAQ] summary of common causes and solutions of Huawei account service error 907135701
Lick the dog until the last one has nothing (state machine)
Dgraph: large scale dynamic graph dataset
Huahao Zhongtian rushes to the scientific and Technological Innovation Board: the annual loss is 280million, and it is proposed to raise 1.5 billion. Beida pharmaceutical is a shareholder
Unity shader learning (3) try to draw a circle
【FAQ】華為帳號服務報錯 907135701的常見原因總結和解决方法