查看: 649|回复: 8
收起左侧

[其他] 求解一道题 单调递增或递减子数组的个数

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   69% (1659)
 
 
30% (718)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
求一个数组中 ,单点递增,或者递减的子数组个数
例子:
[1,2,1,2]的单调递增,或者单调递减的子数组个数为3个:
[1,2], [2,1]. [1,2]
子数组要求:
子数组长度最短为2
子数组只要起始位置不同就算不同,即使内容一样,
贴java code者必加米

评分

参与人数 1大米 +6 收起 理由
14417335 + 6

查看全部评分


上一篇:FB社招该刷哪些题
下一篇:疫情期间刷题成果
lkean9 2021-7-26 03:56:25 来自APP | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   97% (47)
 
 
2% (1)    👎
duao119 发表于 2021-07-25 10:18:16
我有一个问题,“这时候累计单调区间数量为(j - i - 1)的阶乘”
res += math.factorial(j - i - 1)
我觉得这里不是阶乘吧,而是 ((j-i)*(j-i+1)
啊对的对的有道理 不是阶乘 而是等差数列的相加。因为我自己举的例子正好是3+2+1 ,我想当然的想成接乘了。。。

评分

参与人数 1大米 +1 收起 理由
duao119 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

lkean9 2021-7-25 15:43:04 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   97% (47)
 
 
2% (1)    👎
我有两种解法,第一种是简单的1D DP, dp denotes the number of monotonic subarrays starting at nums,这样最终答案就是sum(dp)。这种方法的时间为O(n ^ 2),空间为O(n),不过这肯定不是最优解,不过比较好理解。
所以第二种是Two Pointers,遍历数组的时候,如 [1, 2, 3, 4, 1], 当i = 0时,移动j,直到j = 4, nums[j] 不再与之前的nums ~ nums[j - 1]单调时,这时候累计单调区间数量为(j - i - 1)的阶乘。然后让i 直接等于j - 1,即i = 3,继续循环。这样time is O(n), space is O(1) including factorial computation using built-in package.

我是用python3做的,用java还得换电脑。。。如果代码或者我理解有误的话,还请多多包涵,再讨论讨论。


  1. class Solution: # 1D DP
  2.     # dp[i] denotes the number of monotonic sub-arrays starting from nums[i]
  3.     # for each dp[i]: check the number of monotonic sub-arrays from nums[i + 1] to end of the nums
  4.     # Time O(n ^ 2)
  5.     # Space O(n)
  6.     def mono(self, nums: List[int]) -> int:
  7.         n = len(nums)
  8.         dp = [0 for _ in range(n)]

  9.         for i in range(n - 1):
  10.             if nums[i] == nums[i + 1]:
  11.                 continue
  12.             dp[i] = 1
  13.             for j in range(i + 2, n):
  14.                 if (nums[i] < nums[i + 1] and nums[j - 1] < nums[j]) or (nums[i] > nums[i + 1] and nums[j - 1] > nums[j]):
  15.                     # if monotonic increasing or monotonic descreasing
  16.                     dp[i] += 1
  17.                 else:
  18.                     break
  19.         # print(dp)
  20.         return sum(dp)


  21. class Solution2: # Two Pointers with 1 Pass
  22.     # Time O(n)
  23.     # Space O(1)
  24.     def mono(self, nums: List[int]) -> int:
  25.         n = len(nums)
  26.         res = 0
  27.         i = 0
  28.         while i < n - 1:
  29.             if nums[i] == nums[i + 1]:
  30.                 i += 1
  31.                 continue
  32.             j = i + 2
  33.             while j < n:
  34.                 if (nums[i] < nums[i + 1] and nums[j - 1] < nums[j]) or (nums[i] > nums[i + 1] and nums[j - 1]):
  35.                     j += 1
  36.                 else:
  37.                     break
  38.             res += math.factorial(j - i - 1)
  39.             i = j - 1
  40.         return res


  41. s = Solution2()
  42. print(s.mono([1,2,1,2]))
  43. print(s.mono([1,2,3,4,1]))
  44. print(s.mono([1,1,1,1]))

复制代码


评分

参与人数 2大米 +10 收起 理由
14417335 + 8
美帝马甲 + 2 很有用的信息!

查看全部评分

回复

使用道具 举报

Qzc 2021-7-25 13:42:09 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (12)
 
 
7% (1)    👎
子数组需要连续的对吗?
回复

使用道具 举报

 楼主| 美帝马甲 2021-7-25 14:15:29 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   69% (1659)
 
 
30% (718)    👎
Qzc 发表于 2021-7-24 22:42
子数组需要连续的对吗?

yes  subarray  not subsequence
回复

使用道具 举报

thrillerの空 2021-7-25 19:06:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (60)
 
 
1% (1)    👎
lkean9 发表于 2021-7-25 15:43
我有两种解法,第一种是简单的1D DP, dp denotes the number of monotonic subarrays starting at nums,这 ...

DP也可以达到O(n)的时间复杂度的哦,你把你双指针方法的思路融合到DP里面就可以了。

也就是说DP数组, DP[i ]不是表示原数组第i个数有多少种可能,还是表示第i个单调区间的总个数,所以关系式就是:

DP = DP[i -1] + monotonicCombination(i);

表示第i个单调区间的组合总数 = 上一个单调区间的组合总数 + 当前单调区间的组合总数;

base case:DP[0] = 0;

比如你的例子{1,2,3,4,1}, DP数组:

0 1 2
0 6 7

注意:这里我只算了从左往右的组合,不算从右往左的。第一个单调区间{1,2,3,4}一共6种组合,不算长度为2的,第二个单调区间{4,1},一共1种组合

但这个的space不如双指针,因为需要多开一个DP数组的空间。

评分

参与人数 2大米 +7 收起 理由
14417335 + 5
美帝马甲 + 2 很有用的信息!

查看全部评分

回复

使用道具 举报

tianzhishui 2021-7-25 20:01:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (240)
 
 
1% (4)    👎
数组字符串某个特征的子单元上双指针
回复

使用道具 举报

 楼主| 美帝马甲 2021-7-26 00:02:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   69% (1659)
 
 
30% (718)    👎
lkean9 发表于 2021-7-25 00:43
我有两种解法,第一种是简单的1D DP, dp denotes the number of monotonic subarrays starting at nums,这 ...

其实除了java,我同时也用python刷题
回复

使用道具 举报

duao119 2021-7-26 01:18:16 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (1027)
 
 
1% (14)    👎
本帖最后由 duao119 于 2021-7-25 13:59 编辑
lkean9 发表于 2021-7-25 03:43
我有两种解法,第一种是简单的1D DP, dp denotes the number of monotonic subarrays starting at nums,这 ...

我有一个问题,“这时候累计单调区间数量为(j - i - 1)的阶乘”
  1. res += math.factorial(j - i - 1)
复制代码

我觉得这里不是阶乘吧,而是 ((j-i)*(j-i+1) / 2)  - (j-i)  ,因为这里面也就是求subarray的个数
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表