peizhyi
- 浏览: 29571 次
- 性别:
- 来自: 北京
-
最新评论
-
peizhyi：
sydongda 写道有没有考虑重复的数字不好意思，好久没回来 ...
找出数组中和为N的所有配对 -
peizhyi：
zdbill 写道“存储开始的m条记录”，你不觉得前m条记录选 ...
一道算法题——从数据流中随机去m个数 -
zdbill：
“存储开始的m条记录”，你不觉得前m条记录选中的概率比后面的记 ...
一道算法题——从数据流中随机去m个数 -
sydongda：
有没有考虑重复的数字
找出数组中和为N的所有配对 -
peizhyi：
<div class="quote_title ...
最长的滑道
文章列表
问题：
计算一个数的质因数个数，1不是质因数。比如20=2*2*5，2、2、5就是20的三个质因数。
思路：
从小到大，找到N的因数M，递归查找M和N/M的的质因数。
def count_prime(number, expr):
count = 0
for i in range(2, number/2 + 1):
if number%i == 0:
(count_i, epxr) = count_prime(i, expr)
if count_i == 0:
...
把数字拆分成2的幂的和
- 博客分类：
- 算法
问题：
任何数都能分解成2的幂，比如
7=1+1+1+1+1+1+1
=1+1+1+1+1+2
=1+1+1+2+2
=1+2+2+2
=1+1+1+4
=1+2+4
共有6种分解方式，设f(n)为任意正整数可能分解总数，比如f(7)=6
写个算法，输入数，求出其分解的总数。
思路：
先按照树形结构，把一个数可能的2的幂的子数记录下来，比如7拆分成7个1，3个2，1个4。从高到底遍历所有可能的搭配。
import math
import copy
def get_distribute_for ...
问题：
玛雅密码是一串由0、1、2组成的密码，这串数字中如果包含2012，就可以解开末日的大门。给定一串由0、1、2组成的字符串，只有相邻的数字可以交换，求通过最少多少次变换可以得到玛雅密码，并给出这串密码。
思路：
经过很久很久的尝试，放弃了一次性拼凑2012的想法，改用预处理得到所有数字范围中符合玛雅密码的部分，再递归遍历给定的数字串，得到该串所有可能的变换，并比较每个变换的结果需要的步数。
import sys
def find_all_transfers(str):
result={}
if len(str) == 0:
...
问题：
给定一个自然数N，计算1,2,3...N中，出现1和2的数量。比如1,2,3...10，一共出现了3次，1,2,3...12，一共出现了7次。
思路：
比如计算54321，可以先计算50000，再计算50001-54321中1和2的个数，而后者又可以看成计算4321中1和2的个数，于是简化了问题。其中计算50000的时候，可以计算49999中有多少个1和2，也就递归转变成了一个已知的求解方法，再加上50000所代表的1和2的个数（0个）。
def count_from_number(number):
if number < 10 ...
问题描述：
发四堆扑克，一堆是2张，一堆是5张，一堆是8张，一堆是10张。排列如下：
2 5 8 10
两个人，轮流拿牌。每次只能在一堆里面拿，无论拿几张都可以，最多一次可以把任意一堆牌全拿走。经过N轮拿牌过后，拿最后一张牌的人输。
解决思路：
1. 从最简单的情况开始考虑，在简单的情况下可以取胜，才能在更复杂的情况取胜；
2. 我能否取胜，取决于“我本次拿走一些牌以后，对方一定是失败的”；
3. 如果我无法拿走一些牌，使得对方一定失败，那我就输了。
下面是推导：
（其中N表示大于1的数）
只有一堆时：
...
有了网页的骨架，还缺少网页元素的渲染，也就是CSS样式表。一般需要把CSS样式配置独立成文件，然后在网页的头部引用CSS样式文件。引用代码如下：
<head>
<meta content="text/html; charset=utf-8" >
<link rel="stylesheet" type="text/css" href="style.css">
<titile>Test Title</t ...
从位置上划分出网页的区域以后，就需要用到网页的内容标签了，比如<article>、<aside>、<nav>、<p>、<h1>等。网页中，这些内容标签和位置标签交错在一起，比如像下面这样：
<body>
<header>
<h1>Body Title</h1>
<nav>
导航栏
</nav>
</ ...
网页中的body是主体内容，按照html5的标准，可以按照<header>、<footer>、<section>来进行布局上的划分。
一个基本的结构可以是这样：
<body>
<header>
<h1>Body Title</h1>
</header>
<section id="left">
</section>
< ...
一个网页的基础结构
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<titile>Test Title</title>
</head>
<body>
</body>
</html>
其中：
DOCTYPE，指定文档的类型，在html5标准中固定为html；
head，指定页面的基本属性；
m ...
在Spring框架下写了一个东西，用到了org.springframework.core.task.TaskExecutor这个接口，用它来执行一个FutureTask实例，但编写单测的时候遇到个问题。
我按照惯常的套路编写单测：
@Resource
TaskExecutor taskExecutorReal; // 从上下文中得到的实际的TaskExecutor实现
@Mock
TaskExecutor taskExecutor = taskExecutorReal; //mock替身
@InjectMocks
MyClass myCla ...
求一个序列的最长的升序序列，比如数组array[10]。
我的想法：
1. 以变量max_length记录最长的序列长度，以loc记录最长序列的位置，初始化都为0。
2. 设置变量temp_length=0，temp_loc=0，遍历每个元素array[i]{
如果array[i]<=array[i+1]，temp_length++；
否则{
判断temp_length与max_length大小，更新max_length和loc；
temp_length=0，temp_loc=i；
}
}
...
两个人轮流拿10个硬币，每次可以拿1或2或4个，拿到最后的那个人为输，问：怎样才能必胜？
思路是从最简单的情况概况，找到一定的规律。
总结如下，其中A、B代表两个人，数字代表对应人选择前剩下的硬币数，第一行的解释是“有1个硬币留给了A，A拿了一个，剩下0个硬币留给了B，A就输了”：
A B 对A的结果
1 0 lose
2 1 win
3 1 win
4 0/2/3 lose
（这个解释下，A有4个硬币时，可能选4个、2个、1个，对应留给B的数目是0、2、3，结合上面的 ...
问题： Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最 ...
问题：
有大量的字符串格式的URL，如何从中去除重复的，优化时间空间复杂度
我的思路，
1. 将URL存入hash链表，每个URL读入到hash链表中，遇到重复的就舍弃，否则加入到链表里面，最后遍历得到所有不重复的URL。空间复杂度M，时间复杂度为O(N+N/M)，M为不重复的URL，N为总URL数，但是M无法预测，所以存在风险，可能内存不足以存储所有的不重复URL。
2. 为了解决内存可能不足的问题，需要把hash链表变化成普通的hash表，每个hash表元素指向一个文件文件，这个文件记录了所有该hash值对应的无重复的URL，那么在加入URL的时候就遍历对应文件中的URL，没有重复则加 ...