高网站排名吗,多网合一网站,免备案空间是什么,长沙中小企业有哪些公司文章目录 611. 有效三角形的个数题干#xff1a;题解#xff1a;代码#xff1a; LCR 179. 查找总价格为目标值的两个商品题干#xff1a;题解#xff1a;代码#xff1a; 1137. 第 N 个泰波那契数题干#xff1a;原理#xff1a;1、状态表示#xff08;dp表里面的值所… 文章目录 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 Tn3 Tn Tn1 Tn2 可以变形为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[n1];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;}
