当前在线人数16264
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
Re: leetcode第829题最优解
[版面:待字闺中][首篇作者:dabaojian] , 2018年05月15日15:10:53 ,次阅读,次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
dabaojian
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: dabaojian (蔡宝健不刷题了,兄弟们再见), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Tue May 15 15:10:53 2018, 美东)

看题目感觉又是狗家的题

--
☆ 发自 iPhone 买买提 1.24.07
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2620:10d:c090:2]

 
zengqinghan
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: zengqinghan (Zzz), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Tue May 15 15:21:53 2018, 美东)

sqrt(n)的解法已经很naive了吧,我以为是贴了更巧妙的解法呢。
给定一个X,如果能被写成连续数字和,那就套下小学的等差数列求和,得出必然存在a
和n使得:
(a + (a + n - 1)) * n / 2 = x
x是给定目标数,已知,任务是求 a 和 n的整数解的个数
那最naive的办法就是用让n取1,2,3,4,... sqrt(2x),然后拿2X挨个除一下,把所有整
数a给找出来就行了。。。
这比你那个思路简单容易理解多了吧
--
※ 修改:·zengqinghan 於 May 15 17:28:26 2018 修改本文·[FROM: 2620:15c:2c1:202]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2620:15c:2c1:20]

 
dabaojian
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: dabaojian (蔡宝健不刷题了,兄弟们再见), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Tue May 15 16:38:52 2018, 美东)

金刚兄让我明白了我为什么没拿到Google的offer

【 在 zengqinghan (Zzz) 的大作中提到: 】
: sqrt(n)的解法已经很naive了吧,我以为是贴了更巧妙的解法呢。
: 给定一个X,如果能被写成连续数字和,那就套下小学的等差数列求和,得出必然存
在a
:  和n使得:
: (a + (a + n - 1)) * n / 2 = x
: x是给定目标数,已知,任务是求 a 和 n的整数解的个数
: 那最naive的办法就是用让n取1,2,3,4,... sqrt(2x),然后拿2X挨个除一下,把所
有整
: 数a给找出来就行了。。。
: 这比你那个思路简单容易理解多了吧




--
☆ 发自 iPhone 买买提 1.24.07
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2620:10d:c090:2]

 
garphy
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: garphy (喜欢猫), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Tue May 15 16:43:34 2018, 美东)

这个题目我比赛错了6次

【 在 zengqinghan (Zzz) 的大作中提到: 】
: sqrt(n)的解法已经很naive了吧,我以为是贴了更巧妙的解法呢。
: 给定一个X,如果能被写成连续数字和,那就套下小学的等差数列求和,得出必然存
在a
:  和n使得:
: (a + (a + n - 1)) * n / 2 = x
: x是给定目标数,已知,任务是求 a 和 n的整数解的个数
: 那最naive的办法就是用让n取1,2,3,4,... sqrt(2x),然后拿2X挨个除一下,把所
有整
: 数a给找出来就行了。。。
: 这比你那个思路简单容易理解多了吧




--
☆ 发自 iPhone 买买提 1.24.07
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2600:1010:b06a:]

 
zengqinghan
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: zengqinghan (Zzz), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Tue May 15 17:31:38 2018, 美东)

看ls这么一说,怕有啥坑没想到,赶快找到这题写了下,没发现有啥坑直接就pass了,
就按那个等差数列实现下就行了。
class Solution {
    public int consecutiveNumbersSum(int target) {
        int count = 0, t = 2 * target;
        for (int n = 1; n < Math.sqrt(t); ++ n)
            if (t % n == 0 && (t / n + 1 - n) % 2 == 0 )
                count ++;
        return count;
    }
}
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2620:15c:2c1:20]

 
zengqinghan
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: zengqinghan (Zzz), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Tue May 15 17:38:25 2018, 美东)


【 在 dabaojian (蔡宝健不刷题了,兄弟们再见) 的大作中提到: 】
: 金刚兄让我明白了我为什么没拿到Google的offer
: 在a
: 有整


大宝建不但题刷的好,还这么谦虚,自叹不如啊。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2620:15c:2c1:20]

 
missingyou
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: missingyou (miss), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Tue May 15 20:31:54 2018, 美东)

现在都800多题了??。。。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 73.]

 
zengqinghan
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: zengqinghan (Zzz), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Tue May 15 21:24:02 2018, 美东)


【 在 missingyou (miss) 的大作中提到: 】
: 现在都800多题了??。。。


你们这行也关注刷题么。。。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2620:15c:2c1:20]

 
missingyou
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: missingyou (miss), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Tue May 15 21:33:18 2018, 美东)

哈哈 有时候问问刷到什么程度了。。。没刷好就先别面试了

【 在 zengqinghan (Zzz) 的大作中提到: 】
: 你们这行也关注刷题么。。。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 73.]

 
liusuyun
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: liusuyun (刘素云), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Wed May 16 13:30:40 2018, 美东)

感谢分享,收藏了,期待更多的新题分享!


【 在 Cathy2014 (青云算法) 的大作中提到: 】
: 问题:输入一个整数N,请问有多少种不同的方法把若干个连续的整数相加使得它们的
: 和为N?例如输入N=9,由于9 = 9、9 = 4 + 5、9 = 2 + 3 + 4,因此正确的输出是3。
: 分析:这是LeetCode第829题。
: 解法一:时间复杂度O(n)
: 我们可以想象有一个整数数组,数组里的第一个数字是1,第二个数字是2,以后的数字
: 以此类推。再假设有两个指针,第一个指针初始化指向数组的第一个数字,第二个指针
: 初始化指向数组的第二个数字。这两个指针就定位了一个子数组,该子数组由两个指针
: 之间的所有数字(包括两个指针指向的数字)组成。由于数组里的数字是连续递增的,
: 那么两个指针之间的任意子数组的数字也是连续递增的。
: 如果两个指针之间的子数组的所有数字之和小于输入的整数N,我们希望这个子数组包
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
aaaiii
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: aaaiii (酱爆), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Wed May 16 15:35:55 2018, 美东)

你这个能通过?target本身没有算进去吧?

【 在 zengqinghan (Zzz) 的大作中提到: 】
: 看ls这么一说,怕有啥坑没想到,赶快找到这题写了下,没发现有啥坑直接就pass了,
: 就按那个等差数列实现下就行了。
: class Solution {
:     public int consecutiveNumbersSum(int target) {
:         int count = 0, t = 2 * target;
:         for (int n = 1; n < Math.sqrt(t); ++ n)
:             if (t % n == 0 && (t / n + 1 - n) % 2 == 0 )
:                 count ++;
:         return count;
:     }
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 208.]

 
zengqinghan
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: zengqinghan (Zzz), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Wed May 16 18:40:19 2018, 美东)


【 在 aaaiii (酱爆) 的大作中提到: 】
: 你这个能通过?target本身没有算进去吧?


?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2620:15c:2c1:20]

 
aaaiii
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: aaaiii (酱爆), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Wed May 16 19:25:17 2018, 美东)

N=9,9 = 9这个包括了吗?

【 在 zengqinghan (Zzz) 的大作中提到: 】
: ?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 96.]

 
zengqinghan
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: zengqinghan (Zzz), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Wed May 16 21:43:16 2018, 美东)


【 在 aaaiii (酱爆) 的大作中提到: 】
: N=9,9 = 9这个包括了吗?

我那方法里没有什么特殊情况需要考虑,满足那个公式的自然就是一组解。
9=9不比9=4+5有任何特殊之处。
target = 9, n = 1, a = 9 描述的就是9=9这个解。

从你的问题来看,我推断你是误以为我的n是target的意思,没猜错吧?
我的n是等差数列项数。target是题目中的n。因为我是先在这儿贴的等式,后去写的代
码,所以就把一些变量名改了,以照应我的等式。

而且这个code当然通过了,我连代码都扔这儿了,不过的题目我敢胡说成过了?
--
※ 修改:·zengqinghan 於 May 16 21:51:36 2018 修改本文·[FROM: 2620:15c:2c1:202]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2620:15c:2c1:20]

 
aaaiii
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: aaaiii (酱爆), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Wed May 16 22:05:58 2018, 美东)

明白了,其实 a 并不重要,算的是符合条件n的次数
被N和n搞糊涂了

【 在 zengqinghan (Zzz) 的大作中提到: 】
: 我那方法里没有什么特殊情况需要考虑,满足那个公式的自然就是一组解。
: 9=9不比9=4+5有任何特殊之处。
: target = 9, n = 1, a = 9 描述的就是9=9这个解。
: 从你的问题来看,我推断你是误以为我的n是target的意思,没猜错吧?
: 我的n是等差数列项数。target是题目中的n。因为我是先在这儿贴的等式,后去写的代
: 码,所以就把一些变量名改了,以照应我的等式。
: 而且这个code当然通过了,我连代码都扔这儿了,不过的题目我敢胡说成过了?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 96.]

 
zengqinghan
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 16 ]

发信人: zengqinghan (Zzz), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Wed May 16 22:12:16 2018, 美东)


【 在 aaaiii (酱爆) 的大作中提到: 】
: 明白了,其实 a 并不重要,算的是符合条件n的次数
: 被N和n搞糊涂了


差不多就是这个意思,a也重要,“a为整数”就是n要符合的条件。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2620:15c:2c1:20]

 
susesmth
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 17 ]

发信人: susesmth (susesmth), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Wed May 16 23:23:51 2018, 美东)

原贴给的时间复杂度是square(n), 你给的是 square(2n), 原贴的条件判断也更简洁,
不知为何认为你给的更好。I misunderstand?


【 在 zengqinghan(Zzz) 的大作中提到: 】
<br>: 差不多就是这个意思,a也重要,“a为整数”就是n要符合的条件。
<br>
--
※ 来源:· 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2600:1700:1150:]

 
zengqinghan
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 18 ]

发信人: zengqinghan (Zzz), 信区: JobHunting
标  题: Re: leetcode第829题最优解
发信站: BBS 未名空间站 (Wed May 16 23:48:21 2018, 美东)


【 在 susesmth (susesmth) 的大作中提到: 】
: 原贴给的时间复杂度是square(n), 你给的是 square(2n), 原贴的条件判断也更简洁,
: 不知为何认为你给的更好。I misunderstand?
: <br>: 差不多就是这个意思,a也重要,“a为整数”就是n要符合的条件。
: <br>


Yes.You misunderstood.
原贴解释用了一大堆,我的思路简单清晰。
所以我说的是“思路简单容易理解多”,我没说“更好”
还有,O(sqrt(n) ) == O(sqrt(2n))
还有,那叫sqrt不叫square...

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

[分页:1 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996