算法

php解八皇后

回忆 八皇后问题,我心底放了多年的痛。还记得08年在西电上补习班,大神讲师三五句话就说完了八皇后问题,黑板上涂涂画画就讲完了算法原理。然而我,坐在下面一脸懵逼,很尴尬。被嘲讽是必然的。。。。 恰好昨天写动态规划,又想起了这个问题。干脆来实现下 直接上naive方法 逐行扫描,对于第i (0 <= i <= N-1)行,根据历史路径$histories(是一个(x,y)坐标集合,0 < = x <i, 0 <= y <= N-1)来生成当前行可用列$availables。 history中已经使用过的列y,不能再用 history中的(x,y)点,和当前(i,j), 0 <= i < = N-1,存在这样的关系:dist=i-x, (i,j) = (x+dist,y+dist), 或者(i,j) = (x-dist,y+dist),则说明当前j列位置不可用,因为他和之前的点在同一斜线上。 <?php const N = 12; $count = 0; function printHistory($row, $histories){ echo "==========n==========\n"; foreach($histories as $history){ echo "($histo...

袋鼠从起点开始跳,问到终点有多少种不同的跳跃方式

题目 有一只袋鼠,它跳跃一次的方式只有两种:①一次跳1米 ②一次跳3米,现在有一段10米长的路,袋鼠从起点开始跳,问到终点有多少种不同的跳跃方式? 方法1:生成二叉树生成 每一步有两种选择:1米或者3米,所以解集是一棵二叉树,每一个节点代表一种选择。 假设当前运动位置是S,则S = sum(根节点 + ... +当前节点)。(我不知道markdown如何打数学公式,google出来的都没成功,凑合着看吧) 当前运动位置 > 10m,说明路走完了。结束当前路径搜索。 遍历二叉树,找到所有sum <?php const TOTAL_STEP = 10; const OPTION_STEP1 = 1; const OPTION_STEP3 = 3; $table = []; $count = 0; // 生成遍历二叉树 function gene1($path, $dist){ global $table; global $count; $path1 = 0; $path2 = 0; $count += 1; if($dist < TOTAL_STEP){ $path1 = $path . OPTION_STEP1; $set1 = gene1($path1, $dist +...

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前驱节点 退出条...