文章目录
- 611. 有效三角形的个数
- 题干：
- 题解：
- 代码：
- LCR 179. 查找总价格为目标值的两个商品
- 题干：
- 题解：
- 代码：
- 1137. 第 N 个泰波那契数
- 题干：
- 原理：
- 1、状态表示（dp表里面的值所表示的含义）
- 2、状态转移方程（dp[i] 等于什么）
- 3、引初始化 （保证填表的时候不越界）
- 4、填文顺表 （为了填写当前状态的时候，所需的状态已经计算过了）
- 5、返回值 （题目要求 + 状态表示）
- 代码：
- 空间优化：
611. 有效三角形的个数
原题链接
题干：
首先看题干，非负整数数组，三元组数
所以，我们可知，这个数组最少有三个元素，这样才能组成三元组
在解题之前，我们补充一点：
给我们三个数，怎么判断是不是能不能构成三角形呢？
我们一般的判断都是任意两边之和大于第三边，但是如果在时间复杂度的位置上考虑，比三次太麻烦
这个时候，我们想，如果让这个数组是有序的，对比的这三个边是有序的，那么两个较短的边相加，大于第三边，是不是就可以说明前面两条边任意一条和后面的相加，都大于其余一条边呢？
很明显，这样是可以的，所以我们的算法就进一步进行了优化
题解：
1、暴力枚举 O(N)
暴力算法就是写三个 for 循环嵌套，在最里面的一层 for 循环判断三个数是否能组成三角形
这个算法虽然可以算出，但是由于时间复杂度太高，会导致超时
2、利用单调性，使用双指针算法解决问题
（0）排序
（1）先固定最大的数
（2）在最大的数的左区间，使用双指正，快速统计出符合要求的三元组个数
我们先看这个数组，我们先把最后一个数字固定，定义 left 和 right，
让left + right，如果大于 最后一个数字，那么left 右边的所有数字和 right 相加都大于，所以中间的统计下来，right –
如果小于，那么left++，再次判断
代码：
class Solution {
public int triangleNumber(int[] nums) {
//1.优化：排序
Arrays.sort(nums);
//2.利用双指针解决问题
int ret = 0;
int n = nums.length;
for (int i = n - 1; i >= 2; i--) {//先固定最大的数
//利用双指针快速统计处符合要求的三元组的个数
int left = 0;
int right = i-1;
while (left < right) {
if (nums[left] + nums[right] > nums[i]) {
ret += right - left;
right--;
}else {
left++;
}
}
}
return ret;
}
}
LCR 179. 查找总价格为目标值的两个商品
原题链接
题干：
先看题干，升序数组，两个数相加等于 target
很好，这道题非常简单
题解：
1、暴力枚举 O(N2)
运用暴力枚举可以直接用两个 for 循环嵌套，然后再循环内部相加判断是不是和 target 相等
这个方法虽然很简单，但是时间复杂度过高，会超出时间
2、利用单调性，使用双指针解决问题
这个时候，我们依然使用我们非常熟悉的单调性和双指针
先判断left 和 right 相加
如果 大于 t ，right–
如果 小于 t ，left++
如果相等，直接返回
代码：
public int[] twoSum(int[] price, int target) {
int left = 0;
int right = price.length-1;
while (left < right) {
int sum = price[left] + price[right];
if (sum > target) {
right--;
}else if (sum < target) {
left++;
}else {
return new int[]{price[left],price[right]};
}
}
return new int[]{0};
}
1137. 第 N 个泰波那契数
原题链接
题干：
由题干可知
T0 = 0
T1 = 1
T2 = 1
Tn+3 = Tn + Tn+1 + Tn+2
可以变形为：Tn = Tn-3 + Tn-2 + Tn-1
原理：
1、状态表示（dp表里面的值所表示的含义）
由于我们在写动态规划问题的时候，需要用到dp表
dp表是怎么来的呢？
- 题目要求：本题 dp[i] 表示 第 i 个泰波那契数的值
- 经验 + 题目要求
- 分析问题的过程中，发现的重复子问题
2、状态转移方程（dp[i] 等于什么）
3、引初始化 （保证填表的时候不越界）
4、填文顺表 （为了填写当前状态的时候，所需的状态已经计算过了）
从左向右
5、返回值 （题目要求 + 状态表示）
dp [n]
代码：
public int tribonacci(int n) {
//1.创建 dp 表
//2.初始化
//3.填表
//4.返回值
//先处理边界
if(n == 0) {
return 0;
}
if(n == 1 || n == 2) {
return 1;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = dp[2] = 1;
for(int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}
空间优化：
这里我们用到的空间优化的方式是滚动数组
在解题的过程中发现，我们求 dp[i] 都是前三个数求和，不需要用到再往前的数
这个时候我们就可以拿三个数来存放，并且用后面的值改变前面的值
这个顺序是无法改变的，因为第二种方法，会把前面的值覆盖掉，导致出错
public int tribonacci(int n) {
//空间优化
//先处理边界
if(n == 0) {
return 0;
}
if(n == 1 || n == 2) {
return 1;
}
int a = 0;
int b = 1;
int c = 1;
int d = 0;
for(int i = 3; i <= n; i++) {
d = a + b + c;
//滚动操作
a = b;
b = c;
c = d;
}
return d;
}
![敌方坦克发射思路[java坦克大战]](https://img-blog.csdnimg.cn/direct/ebdf44a5ccd64070a99ec8c4beaf766b.png)
