咖啡网站设计模板,黄南北京网站建设,网址导航页面,wordpress国内开发题目#xff1a; https://leetcode.cn/problems/find-the-count-of-monotonic-pairs-i/description/ 不为别的#xff0c;只是记录下这个超过100%#xff0c;而且比原先最快的快了一个量级
不知道咋分析#xff0c;反正得出结论就是#xff0c;变大不变#xff0c;变小…题目 https://leetcode.cn/problems/find-the-count-of-monotonic-pairs-i/description/ 不为别的只是记录下这个超过100%而且比原先最快的快了一个量级
不知道咋分析反正得出结论就是变大不变变小跟着变最后一个数如果是负数直接为0如果为正数就是C(lenn取n) 两个解题时间如图 1、使用加法计算C
class Solution {public int countOfPairs(int[] nums) {int jj 0;int len nums.length;for (int i 1; i len; i) {if (nums[i] - jj nums[i - 1]) {jj nums[i] - nums[i - 1];nums[i] nums[i - 1];} else {nums[i] - jj;if (nums[i] 0) {return 0;}}}return getAns(nums.length, nums[len - 1]);}//使用加法计算private int getAns(int length, int num) {long[] anss new long[num 1];for (int i 0; i anss.length; i) {anss[i] 1;}for (int i 0; i length; i) {for (int j 1; j num; j) {anss[j] anss[j - 1];anss[j]%1_000_000_007;}}return (int) anss[num];}
}2、使用计算式计算C因为存在1000_000_007,所以先约分
class Solution {public int countOfPairs(int[] nums) {int jj 0;int len nums.length;for (int i 1; i len; i) {if (nums[i] - jj nums[i - 1]) {jj nums[i] - nums[i - 1];nums[i] nums[i - 1];} else {nums[i] - jj;if (nums[i] 0) {return 0;}}}return getAns(nums.length, nums[len - 1]);}private int getAns(int length, int num) {if (length num) {return getAA(length, length num);} else {return getAA(num, length num);}}//以下计算C(length取n)private int getAA(int n, int length) {if (n 0) {return 1;}int[] fenzi new int[n];for (int i 0; i n; i) {fenzi[i] length - i;}for (int i 1; i n; i) {int temp i;int j 0;while (temp 1) {int yue getYue(temp, fenzi[j]);temp / yue;fenzi[j] / yue;j;}}long ans 1;for (int i : fenzi) {ans * i;ans % 1000_000_007;}return (int) ans;}private int getYue(int t1, int t2) {if (t1 t2) {return t1;}if (t1 t2) {return getYYY(t1, t2);} else {return getYYY(t2, t1);}}private int getYYY(int t1, int t2) {int t3 t1 % t2;if (t3 0) {return t2;}return getYYY(t2, t3);}
}
