f*********m
发帖数: 726 | 1 all from leetcode
1.
Combinations
Given two integers n and k, return all possible combinations of k numbers
out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
2.
Count and Say
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
谢谢。 | p*****2
发帖数: 21240 | 2
第一题
def dfs(n,s,k,l):
if len(l)==k:
print l
if s==n:
return
for i in xrange(s,n):
l.append(i+1)
dfs(n,i+1,k,l);
del l[-1]
def comb(n,k):
l=[]
dfs(n,0,k,l)
【在 f*********m 的大作中提到】
: all from leetcode
: 1.
: Combinations
: Given two integers n and k, return all possible combinations of k numbers
: out of 1 ... n.
: For example,
: If n = 4 and k = 2, a solution is:
: [
: [2,4],
: [3,4],
| p*****2
发帖数: 21240 | 3 第二题
def next(s):
ch=s[0]
c=1
ans=""
for i in xrange(1,len(s)):
if(s[i]==ch):
c+=1
else:
ans+=str(c)+ch
ch=s[i]
c=1
ans+=str(c)+ch
return ans
def get(n):
s="1"
for i in xrange(1,n):
s=next(s)
return s | f*********m
发帖数: 726 | 4 用del l[-1]是要删除l的第一个元素吗？本人愚钝，二哥能否把思路再说详细点？
【在 p*****2 的大作中提到】
: 第二题
: def next(s):
: ch=s[0]
: c=1
: ans=""
: for i in xrange(1,len(s)):
: if(s[i]==ch):
: c+=1
: else:
: ans+=str(c)+ch
| p*****2
发帖数: 21240 | 5
删除最后一个元素。
【在 f*********m 的大作中提到】
: 用del l[-1]是要删除l的第一个元素吗？本人愚钝，二哥能否把思路再说详细点？
| f*********m
发帖数: 726 | | p*****2
发帖数: 21240 | 7
不客气。
【在 f*********m 的大作中提到】
: 谢谢
| r*****e
发帖数: 792 | 8 这个解法什么思想？是用python写的吗？看不懂python的说。
谢谢
【在 p*****2 的大作中提到】
: 第二题
: def next(s):
: ch=s[0]
: c=1
: ans=""
: for i in xrange(1,len(s)):
: if(s[i]==ch):
: c+=1
: else:
: ans+=str(c)+ch
| p*****2
发帖数: 21240 | 9
我也不懂python。这个就是把重复的数字计数吧？
【在 r*****e 的大作中提到】
: 这个解法什么思想？是用python写的吗？看不懂python的说。
: 谢谢
| r*****e
发帖数: 792 | 10 那这是什么语言？我看这个题好像有DP的解法，还有什么lazy evaluation，
所以想知道你的这个是基于什么的。只是不能完全理解这种语言，呵呵。
【在 p*****2 的大作中提到】
:
: 我也不懂python。这个就是把重复的数字计数吧？
| | | p*****2
发帖数: 21240 | 11
就是python，我也是刚学。我这个就是给每一个重复数字计数。我还真不知道那么多解
法。那些解法效率更高吗？
【在 r*****e 的大作中提到】
: 那这是什么语言？我看这个题好像有DP的解法，还有什么lazy evaluation，
: 所以想知道你的这个是基于什么的。只是不能完全理解这种语言，呵呵。
| r*****e
发帖数: 792 | 12 还没有考虑怎么去实现，因为不知道用什么方法更好，我其实也不知道
那个lazy的算法，DP的也还没想明白。你这个给重复数字计数的办法是说
比方有312211，你就数有两个2，两个1吗？这是不是BF的思想？
感觉上应该有什么好的算法利用起前面的结果。
另外，这个输入为n是怎么理解？1, 11, 21, 1211, 111221，这里的1211
是输入为4还是2的结果呢？
【在 p*****2 的大作中提到】
:
: 就是python，我也是刚学。我这个就是给每一个重复数字计数。我还真不知道那么多解
: 法。那些解法效率更高吗？
| p*****2
发帖数: 21240 | 13
1211是输入4的结果
【在 r*****e 的大作中提到】
: 还没有考虑怎么去实现，因为不知道用什么方法更好，我其实也不知道
: 那个lazy的算法，DP的也还没想明白。你这个给重复数字计数的办法是说
: 比方有312211，你就数有两个2，两个1吗？这是不是BF的思想？
: 感觉上应该有什么好的算法利用起前面的结果。
: 另外，这个输入为n是怎么理解？1, 11, 21, 1211, 111221，这里的1211
: 是输入为4还是2的结果呢？
| w********s
发帖数: 1570 | 14 #include
void print(int begin_, int end_, int depth_)
{
static int length = depth_;
static int* array = new int[length];
if (end_ - begin_ + 1 < depth_) return;
if (depth_ == 0)
{
for (int i = 0; i < length - 1; ++i)
{
std::cout << array[i] << ",";
}
std::cout << array[length - 1] << "\n";
return;
}
for (int k = begin_; k <= end_; ++k)
{
array[length - depth_] = k;
print(k + 1, end_, depth_ - 1);
}
if (depth_ == length) delete array;
}
int main()
{
int n = 0, m = 0;
std::cin >> n;
std::cin >> m;
print(1, n, m);
return 0;
} | x*******6
发帖数: 262 | 15 lol第一题
import itertools
def combi(n,k):
i=[]
for j in itertools.combinations(range(1,n+1),k):
i.append(j)
return i | h*****3
发帖数: 1391 | 16 第二题有啥好算法啊？我能想到的就是从1开始好好算，算到n。
第一题也没啥好算法吧？就是不停的求combine（n-1,k-1)? | r*******n
发帖数: 3020 | 17 第二题
written in Python
def count_and_say(nth, r):
""" nth is the nth number in the sequnence,
r is result which starts from '1'
"""
if nth == 1: print r
else:
count = 1
new_r = ''
r += '$'
for idx in range(1, len(r)):
if r[idx-1] == r[idx]:
count += 1
else:
new_r += str(count)+r[idx-1]
count = 1
# recursively go next with new_r
count_and_say(nth-1, new_r)
# test
count_and_say(3, '1')
count_and_say(5, '1')
【在 f*********m 的大作中提到】
: all from leetcode
: 1.
: Combinations
: Given two integers n and k, return all possible combinations of k numbers
: out of 1 ... n.
: For example,
: If n = 4 and k = 2, a solution is:
: [
: [2,4],
: [3,4],
| f******h
发帖数: 45 | 18 第二题，终于弄懂什么意思了.
贴一个Java版的
public class Solution {
public String countAndSay(int n) {
// Start typing your Java solution below
// DO NOT write main() function
if(n<=0)
return null;
else if(n==1)
return "1";
else{
String str = "1";
while(n>1){
str = convert(str);
n--;
}
return str;
}
}
public String convert(String str){
StringBuilder builder = new StringBuilder();
char last = str.charAt(0);
int count = 1;
int index = 1;
while(index
if(last == str.charAt(index))
count++;
else{
builder.append(count);
builder.append(last);
last = str.charAt(index);
count = 1;
}
index++;
}
builder.append(count);
builder.append(last);
return new String(builder);
}
} | n*******w
发帖数: 687 | 19 第一题应该跟subset sum差不多，后者是NP-complete。http://en.wikipedia.org/wiki/Subset_sum_problem
如果有DP解法就不是NP了吧。
【在 r*****e 的大作中提到】
: 那这是什么语言？我看这个题好像有DP的解法，还有什么lazy evaluation，
: 所以想知道你的这个是基于什么的。只是不能完全理解这种语言，呵呵。
|
|
