LintCode

lintcode-4 丑数算法

题目 设计一个算法求出第n个只包含因子2,3,5的数。认为1也是丑数 比如输入9,则返回10;输入1,返回1 分析 只包含因子2,3,5,则这个数的形式就是F = (2^x) (3^y) (5^z), 限制条件x,y,z>=0 求出对应x,y,z即可 1th:x=y=z=0, F1 = (2^0) (3^0) (5^0) = 1 2th:x=1,y=z=0, F2 = 2 F1 = 2 3th:x=0,y=1,z=0, F3 = 3 F1 = 3 4th:x=2,y=0,z=0, F4 = 2 F2 = 4 5TH: x=0,y-0,z-1, F5 = 5 F1 = 5 对于第N个丑数,它的x+y+z < N-1 因子2,3,5的数量。 两个2相乘会大于3,因此增加一个2,就要对应增加一个3 一个2,一个3相乘,会大于5,。因此,增加一个2,3就需要替换成5 F1 = 1 迭代1:基底F1=1 F2 = F1 2 = 2(乘以2最小) F3 = F1 3 = 3(乘以3最小) F4 = F1 2 2 = 4(乘以2^2最小) F5 = F1 5 = 5(乘以5最小) F6 = F1 2 3 = 6(乘以23最小) F7 = F1 3 3 = 9(乘以3*3最小) 迭代2:基底 = F5=5 F8 = F5 2 = 10(乘以...

41. 最大子数组

动态规划大法。 第一步,建模,得出递推公式 有一个数组A[n], 对于A[i] (0<i<n)位置向前(0位置方向)最大和为C[i], 那么 C[i] = Max(C[i-1] + A[i], A[i]) 终止条件 C[0] = A[0] 这样子我们就得到了对于任意一个位置 0 <= i < n,数组中从0到i的最大子串和。 但是我们的目标并不是求i位置,最大子串和。我们的目标是求整个数组上,最大子串和,也就是 Opt(A) = Max(C[i]), 0 <= i < n 第二步,试着实现算法 class Solution: def maxSubArray(self, nums): # write your code here length = len(nums) c = [0] * length c[0] = nums[0] maxSum = c[0] i = 1 while i < length: if c[i-1] + nums[i] > nums[i]: c[i] = c[i-1] + nums[i] el...

lintcode 103. 带环链表 II

首先,判断是否有环;接着计算环中有多少个节点;再第一步得到的节点倒推,直到有一个不相同,他的后继节点就是环的起始节点。 第一步,很简单,设置两个指针A和B,指向头结点。A和B分别以速度1和2前进,如果A和B相遇,则说明有环(B追上A) 退出条件: A == B, B追上A,设置当前节点为SomeWhereInRing, 跳去第二步 B == None or B.next == None, 到达链表结尾。 此时算法可以结束了,返回None 第二步,计算环中有几个节点 设置counter = 1, A = SomeWhereInRing, 循环绕环一圈即可知道环中有多少节点 while A != SomeWhereInRing: counter += 1 A = A.next 第三步,以SomeWhereInRing为基准向前倒推,直到能推出两个节点A != B。 单链表无法得到前驱节点,所以我们要想得到SomeWhereInRing的前驱节点,只能通过两种方式: 我们直到SomeWhereInRing节点相对于head头结点的距离,M 我们直到环中有N个节点 那么我们设置指针A和B,A指向head,B指向SomeWhereInRing A向前挪动到M-1位置,即是SomeWhereInRing的前驱节点 B向前挪动N-1节点,则到达SomeWhereInRing前驱节点 退出条...
执行时间: 33.534049987793 毫秒