b**********i
发帖数: 51 | 1 写一个function，对于参数n，输出从0到n之间所有含5的数字。
func(30) 应该输出5，15，25
这道题除了一个个数字的检查以外，还有什么更efficient的解法吗？ | l*****a
发帖数: 14598 | 2 *****5
****5*
***5**
**5***
*5****
5*****
make sense? need to remove dup
【在 b**********i 的大作中提到】
: 写一个function，对于参数n，输出从0到n之间所有含5的数字。
: func(30) 应该输出5，15，25
: 这道题除了一个个数字的检查以外，还有什么更efficient的解法吗？
| w****3
发帖数: 110 | 3 我瞎说一下，可以一位一位的试。固定一位为5，求所有其他位为不同数的组合。注意
去重，比如func（200），从最高位开始，百位不能是5，所以skep， 然后10为固定为5
，百位可以是0~2， 个位可以是0~9。然后个位固定为5，百位可以是0~2，10位可以是0
~9但是不能为5。 | c**********y
发帖数: 38 | 4 奇数乘以5才会含5，直接输出n/5以内所有的奇数和5的乘积 | m******e
发帖数: 1293 | 5 50呢
【在 c**********y 的大作中提到】
: 奇数乘以5才会含5，直接输出n/5以内所有的奇数和5的乘积
| s********e
发帖数: 23 | 6 这题很简单啊。一个快速的方法就是看给的数是5的多少倍数。
i.e.如果给的数是16， 16/5-->取整是3， 那在小于16的区域里，就有3个数是5的倍数
。 | p*****1
发帖数: 103 | | P**********k
发帖数: 1629 | 8 51, 52, 53, 54, 56, 57, 58, 59哭了。。。
【在 s********e 的大作中提到】
: 这题很简单啊。一个快速的方法就是看给的数是5的多少倍数。
: i.e.如果给的数是16， 16/5-->取整是3， 那在小于16的区域里，就有3个数是5的倍数
: 。
| s********e
发帖数: 23 | | s******r
发帖数: 21 | 10 用递归，基本思路是，
考虑第i位的数字，取得值可以是0-9；唯一要注意的是最后一位数字，如果5没有出现
过，只能取5.
public class Solution {
public void str5(String number, String prefix, int length, int pos,
boolean has5) {
if (pos >= length) {
System.out.println(prefix);
} else if (pos < length - 1 || has5) {
for (int i = 0; i <= 9; i++) {
String tmp = prefix + i;
if (Integer.parseInt(tmp) > Integer.parseInt(number.
substring(0, pos + 1))) {
continue;
}
if (i == 5) {
str5(number, tmp, length, pos + 1, true);
} else {
str5(number, tmp, length, pos + 1, has5);
}
}
} else {
String tmp = prefix + 5;
if (Integer.parseInt(tmp) < Integer.parseInt(number.substring(0,
pos + 1))) {
str5(number, tmp, length, pos + 1, true);
}
}
}
public static void main(String...argv) {
Solution s = new Solution();
s.str5(argv[0], "", argv[0].length(), 0, false);
}
} | | | p**o
发帖数: 3409 | 11 只要意识到递归关系：后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5
实现就异常elegant（Python3.3+）
def gen5 (n):
""" Generate all k-digit (1<=k<=n) decimals with digit 5 in ascending
order. """
if n>=1:
POW = 10**(n-1)
yield from (x * POW + y for x in range(5) for y in gen5(n-1))
yield from (5 * POW + y for y in range(POW))
yield from (x * POW + y for x in range(6,10) for y in gen5(n-1))
如果你只是要顺序输出打印“所有含5的N位十进制数”，简单地
>>> list(gen5(0))
[]
>>> list(gen5(1))
[5]
>>> list(gen5(2))
[5, 15, 25, 35, 45, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 65, 75, 85, 95]
如果是设一个上限，再判断一下即可
def gen5_upto (maxnum):
import math
N = math.ceil(math.log10(n))
for n5 in gen5(N):
if n5 > maxnum: break
yield n5
>>> list(gen5_upto(3))
[]
>>> list(gen5_upto(53))
[5, 15, 25, 35, 45, 50, 51, 52, 53]
>>> len(list(gen5_upto(8888)))
3148 | b**********i
发帖数: 51 | 12 谢谢你的解法。学习了！
这个解法的复杂度应该是所有的含5的数字吧。唯一的concern就是parseInt，对于每一
个数字，包括中间结果都调用这个函数判断，这个复杂度不容忽视。
【在 s******r 的大作中提到】
: 用递归，基本思路是，
: 考虑第i位的数字，取得值可以是0-9；唯一要注意的是最后一位数字，如果5没有出现
: 过，只能取5.
: public class Solution {
: public void str5(String number, String prefix, int length, int pos,
: boolean has5) {
: if (pos >= length) {
: System.out.println(prefix);
: } else if (pos < length - 1 || has5) {
: for (int i = 0; i <= 9; i++) {
| b**********i
发帖数: 51 | 13 我一开始是这样想的，计算如果给定参数是k位数，有多少个含5的数字
对于1位数字 gen5(1)=1
2位数字 gen5(2)=8*gen5(1)+10=18
3位数字 gen5(3)=8*gen5(2)+10^2
...
但是我困扰在，如果给的参数不是位数，而是一个最大值，就不知道怎样计算了。
现在看来，你的思路跟我的有点像，但是你直接按这种思路输出含5的数字，这样就可
以判断是否超出最大值了，code真的很elegant，多谢！
【在 p**o 的大作中提到】
: 只要意识到递归关系：后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5
: 实现就异常elegant（Python3.3+）
: def gen5 (n):
: """ Generate all k-digit (1<=k<=n) decimals with digit 5 in ascending
: order. """
: if n>=1:
: POW = 10**(n-1)
: yield from (x * POW + y for x in range(5) for y in gen5(n-1))
: yield from (5 * POW + y for y in range(POW))
: yield from (x * POW + y for x in range(6,10) for y in gen5(n-1))
| p**o
发帖数: 3409 | 14 开个数组每次递归传引用就行了，不一定要字符串累加
var digits : array[1..N] of integer;
【在 b**********i 的大作中提到】
: 谢谢你的解法。学习了！
: 这个解法的复杂度应该是所有的含5的数字吧。唯一的concern就是parseInt，对于每一
: 个数字，包括中间结果都调用这个函数判断，这个复杂度不容忽视。
| p**o
发帖数: 3409 | 15 我11楼那个方法，“后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5”，
从most significant digit开始递归，保证输出有序，
所以容易根据给定的最大值终止生成器。
此前我的思路是从个位数往高位开始左移递归：
“前n位含5 当且仅当 第n位是5 或 前n-1位含5”。
这种方法的缺陷是：结果无序，所以不方便根据给出的最大值跳出生成器。
DIGIDS_NO5 = (0,1,2,3,4,6,7,8,9)
# Generate all k-digit (1<=k<=n) numbers without digit 5
def genno5 (n):
if n == 1: yield from DIGIDS_NO5
else:
for x in genno5(n-1):
for y in DIGIDS_NO5:
yield 10 * y + x
# Generate all k-digit (1<=k<=n) numbers with digit 5
def gen5 (n):
if n == 1: yield 5
else:
yield from (10 * x + 5 for x in genno5(n-1))
for x in gen5(n-1):
for y in range(10):
yield 10 * x + y
>>> list(gen5(2))
[5, 15, 25, 35, 45, 65, 75, 85, 95, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59]
其实我最早的思路是：对于N-digit的数，考虑k=1,2,...,N个digits含'5'，对每个k，
'5'的分布有C(N,k)种情况，对于每一种情况，对剩下的N-k digits每个digit遍历
(0,1,2,3,4,6,7,8,9)，直接输出。这种思路也不用判重，但缺点也是无法保证有序。
也想过更啰嗦的思路：从给定的最大值开始递减，从低位到高位逐位模拟十进制数减法，
比如给定的最大值里第k位是4，那么该位先递减到0，再跳到9（前k-1位要递归退位）。
定义 `var has5 : array[1..N] of boolean`，其中has5[k]表示前k位含'5'，
has5[k] :=true if has5[k-1]=true or digit[k]=5, :=false if otherwise。
但退位时更新一次has5要O(N)复杂度，写起来又麻烦。想想就作罢了。
【在 b**********i 的大作中提到】
: 我一开始是这样想的，计算如果给定参数是k位数，有多少个含5的数字
: 对于1位数字 gen5(1)=1
: 2位数字 gen5(2)=8*gen5(1)+10=18
: 3位数字 gen5(3)=8*gen5(2)+10^2
: ...
: 但是我困扰在，如果给的参数不是位数，而是一个最大值，就不知道怎样计算了。
: 现在看来，你的思路跟我的有点像，但是你直接按这种思路输出含5的数字，这样就可
: 以判断是否超出最大值了，code真的很elegant，多谢！
| x*****0
发帖数: 452 | | h*****e
发帖数: 14 | 17 这是cc150的原题吧，cc150上问的是2的个数，这里求5的个数而已。 | b********r
发帖数: 620 | 18 my 2 bricks:
1) find out floor of n/5, let it be m. for all odd numbers smaller or equal
to m, output the product with 5
2) find out the i, such that 6 x pow(10, i) <= n < 6 x pow(10, i+1), then
output everything 5* (such as 50, 51, 59, 500, 501, 599, 5000, 5001, 5999),
which is less than 6 x pow(10, i)
3) substract 6 x pow(10, i) from n, then recursion with base of 6 x pow(10,
i)
will code and see
【在 h*****e 的大作中提到】
: 这是cc150的原题吧，cc150上问的是2的个数，这里求5的个数而已。
| m**********e
发帖数: 22 | 19 同楼下一大侠的算法。C#写的：
public List GetContainsFive(int num)
{
int m = num;
int i = 0;
while (m > 0)
{
i++;
m = m / 10;
}
string solution = string.Empty;
List result = new List();
GetContainsFiveHelper(num, i, solution, result);
return result;
}
private void GetContainsFiveHelper(int num, int n, string solution,
List result)
{
if (solution.Length == n)
{
int curr = int.Parse(solution);
if (curr <= num)
result.Add(curr);
return;
}
if (solution.Length < n - 1 || HasFive(solution))
{
for (char i = '0'; i <= '9'; ++i)
{
GetContainsFiveHelper(num, n, solution + i, result);
}
}
else
{
GetContainsFiveHelper(num, n, solution + 5, result);
}
}
private bool HasFive(string num)
{
if (num == null || num.Length == 0) return false;
foreach (var c in num)
{
if (c == '5')
return true;
}
return false;
}
【在 b**********i 的大作中提到】
: 写一个function，对于参数n，输出从0到n之间所有含5的数字。
: func(30) 应该输出5，15，25
: 这道题除了一个个数字的检查以外，还有什么更efficient的解法吗？
| w********8
发帖数: 55 | 20 借鉴楼上各位大牛的做法，我也写了一份Java的代码。。。。
public void mySolution(int num) {
if (num >= 5) {
String str = String.valueOf(num);
helper(num, "", 0, str.length(), false);
}
}
private void helper(int max, String prefix, int pos, int len, boolean
have5) {
if (pos == len) {
int cur = Integer.parseInt(prefix);
if (cur <= max) {
System.out.print(cur + ", ");
}
return;
}
for (int i = 0; i < 10; i++) {
if (pos == len - 1 && !have5 && i != 5) {
continue;
}
helper(max, prefix + i, pos + 1, len, have5 || i == 5);
}
}
望指教！ | | | s*********s
发帖数: 5 | 21 O(logN)算法，递归深度logN，但是每次递归的复杂度O(1)
思路是将f(XXX) 递归转化为 多个f(XX)，需要处理一些特殊情况
因为有重叠子结构，用memory记录一下，避免重复DFS，引入了DP的一些东西
int num5Impl(int num, unordered_map &memory)
{
if(num < 5)
return 0;
if(num <= 10)
return 1;
if(memory.find(num) != memory.end())
return memory[num];
int unit = 10;
while(num/unit >= 10)
{
unit *= 10;
}
int primeVal = num/unit;
int ret = 0;
if(primeVal > 5)
{
ret = (primeVal-1)*num5Impl(unit-1, memory) + unit;
}
else
ret = primeVal*num5Impl(unit-1, memory);
if(primeVal == 5)
ret += num-primeVal*unit + 1;
else
ret += num5Impl(num-primeVal*unit, memory);
memory[num] = ret;
return ret;
}
int num5(int num)
{
unordered_map memory;
return num5Impl(num, memory);
} | b*******n
发帖数: 8 | 22 用讨论里的方法写了java 代码，不用字符串操作。
public class NumsWith5 {
public static void numsWith5(int maxvalue, int partial, int pos, boolean
hasFive) {
if (pos == 0) {
if (partial <= maxvalue && hasFive)
System.out.printf(partial + " ");
return;
}
int num = (int)Math.pow(10, pos - 1);
for (int i = 0; i < 10; i++) {
numsWith5(maxvalue, partial + num * i,
pos - 1, hasFive || i == 5);
}
}
public static void main(String[] args) {
int maxvalue = 200;
int pos = 0;
int n = maxvalue;
while (n > 0) {
pos++;
n /= 10;
}
numsWith5(maxvalue, 0, pos, false);
System.out.printf("\n");
}
} | k*******q
发帖数: 5493 | 23 直接除以5，如果结果是偶数就再除2；如果结果是奇数就再除2然后+1
【在 b**********i 的大作中提到】
: 写一个function，对于参数n，输出从0到n之间所有含5的数字。
: func(30) 应该输出5，15，25
: 这道题除了一个个数字的检查以外，还有什么更efficient的解法吗？
| m*******n
发帖数: 12 | 24 用'>>'移位岂不是更容易?
【在 s*********s 的大作中提到】
: O(logN)算法，递归深度logN，但是每次递归的复杂度O(1)
: 思路是将f(XXX) 递归转化为 多个f(XX)，需要处理一些特殊情况
: 因为有重叠子结构，用memory记录一下，避免重复DFS，引入了DP的一些东西
: int num5Impl(int num, unordered_map &memory)
: {
: if(num < 5)
: return 0;
: if(num <= 10)
: return 1;
: if(memory.find(num) != memory.end())
| b**********i
发帖数: 51 | 25 写一个function，对于参数n，输出从0到n之间所有含5的数字。
func(30) 应该输出5，15，25
这道题除了一个个数字的检查以外，还有什么更efficient的解法吗？ | l*****a
发帖数: 14598 | 26 *****5
****5*
***5**
**5***
*5****
5*****
make sense? need to remove dup
【在 b**********i 的大作中提到】
: 写一个function，对于参数n，输出从0到n之间所有含5的数字。
: func(30) 应该输出5，15，25
: 这道题除了一个个数字的检查以外，还有什么更efficient的解法吗？
| w****3
发帖数: 110 | 27 我瞎说一下，可以一位一位的试。固定一位为5，求所有其他位为不同数的组合。注意
去重，比如func（200），从最高位开始，百位不能是5，所以skep， 然后10为固定为5
，百位可以是0~2， 个位可以是0~9。然后个位固定为5，百位可以是0~2，10位可以是0
~9但是不能为5。 | c**********y
发帖数: 38 | 28 奇数乘以5才会含5，直接输出n/5以内所有的奇数和5的乘积 | m******e
发帖数: 1293 | 29 50呢
【在 c**********y 的大作中提到】
: 奇数乘以5才会含5，直接输出n/5以内所有的奇数和5的乘积
| s********e
发帖数: 23 | 30 这题很简单啊。一个快速的方法就是看给的数是5的多少倍数。
i.e.如果给的数是16， 16/5-->取整是3， 那在小于16的区域里，就有3个数是5的倍数
。 | | | p*****1
发帖数: 103 | | P**********k
发帖数: 1629 | 32 51, 52, 53, 54, 56, 57, 58, 59哭了。。。
【在 s********e 的大作中提到】
: 这题很简单啊。一个快速的方法就是看给的数是5的多少倍数。
: i.e.如果给的数是16， 16/5-->取整是3， 那在小于16的区域里，就有3个数是5的倍数
: 。
| s********e
发帖数: 23 | | s******r
发帖数: 21 | 34 用递归，基本思路是，
考虑第i位的数字，取得值可以是0-9；唯一要注意的是最后一位数字，如果5没有出现
过，只能取5.
public class Solution {
public void str5(String number, String prefix, int length, int pos,
boolean has5) {
if (pos >= length) {
System.out.println(prefix);
} else if (pos < length - 1 || has5) {
for (int i = 0; i <= 9; i++) {
String tmp = prefix + i;
if (Integer.parseInt(tmp) > Integer.parseInt(number.
substring(0, pos + 1))) {
continue;
}
if (i == 5) {
str5(number, tmp, length, pos + 1, true);
} else {
str5(number, tmp, length, pos + 1, has5);
}
}
} else {
String tmp = prefix + 5;
if (Integer.parseInt(tmp) < Integer.parseInt(number.substring(0,
pos + 1))) {
str5(number, tmp, length, pos + 1, true);
}
}
}
public static void main(String...argv) {
Solution s = new Solution();
s.str5(argv[0], "", argv[0].length(), 0, false);
}
} | p**o
发帖数: 3409 | 35 只要意识到递归关系：后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5
实现就异常elegant（Python3.3+）
def gen5 (n):
""" Generate all k-digit (1<=k<=n) decimals with digit 5 in ascending
order. """
if n>=1:
POW = 10**(n-1)
yield from (x * POW + y for x in range(5) for y in gen5(n-1))
yield from (5 * POW + y for y in range(POW))
yield from (x * POW + y for x in range(6,10) for y in gen5(n-1))
如果你只是要顺序输出打印“所有含5的N位十进制数”，简单地
>>> list(gen5(0))
[]
>>> list(gen5(1))
[5]
>>> list(gen5(2))
[5, 15, 25, 35, 45, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 65, 75, 85, 95]
如果是设一个上限，再判断一下即可
def gen5_upto (maxnum):
import math
N = math.ceil(math.log10(n))
for n5 in gen5(N):
if n5 > maxnum: break
yield n5
>>> list(gen5_upto(3))
[]
>>> list(gen5_upto(53))
[5, 15, 25, 35, 45, 50, 51, 52, 53]
>>> len(list(gen5_upto(8888)))
3148 | b**********i
发帖数: 51 | 36 谢谢你的解法。学习了！
这个解法的复杂度应该是所有的含5的数字吧。唯一的concern就是parseInt，对于每一
个数字，包括中间结果都调用这个函数判断，这个复杂度不容忽视。
【在 s******r 的大作中提到】
: 用递归，基本思路是，
: 考虑第i位的数字，取得值可以是0-9；唯一要注意的是最后一位数字，如果5没有出现
: 过，只能取5.
: public class Solution {
: public void str5(String number, String prefix, int length, int pos,
: boolean has5) {
: if (pos >= length) {
: System.out.println(prefix);
: } else if (pos < length - 1 || has5) {
: for (int i = 0; i <= 9; i++) {
| b**********i
发帖数: 51 | 37 我一开始是这样想的，计算如果给定参数是k位数，有多少个含5的数字
对于1位数字 gen5(1)=1
2位数字 gen5(2)=8*gen5(1)+10=18
3位数字 gen5(3)=8*gen5(2)+10^2
...
但是我困扰在，如果给的参数不是位数，而是一个最大值，就不知道怎样计算了。
现在看来，你的思路跟我的有点像，但是你直接按这种思路输出含5的数字，这样就可
以判断是否超出最大值了，code真的很elegant，多谢！
【在 p**o 的大作中提到】
: 只要意识到递归关系：后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5
: 实现就异常elegant（Python3.3+）
: def gen5 (n):
: """ Generate all k-digit (1<=k<=n) decimals with digit 5 in ascending
: order. """
: if n>=1:
: POW = 10**(n-1)
: yield from (x * POW + y for x in range(5) for y in gen5(n-1))
: yield from (5 * POW + y for y in range(POW))
: yield from (x * POW + y for x in range(6,10) for y in gen5(n-1))
| p**o
发帖数: 3409 | 38 开个数组每次递归传引用就行了，不一定要字符串累加
var digits : array[1..N] of integer;
【在 b**********i 的大作中提到】
: 谢谢你的解法。学习了！
: 这个解法的复杂度应该是所有的含5的数字吧。唯一的concern就是parseInt，对于每一
: 个数字，包括中间结果都调用这个函数判断，这个复杂度不容忽视。
| p**o
发帖数: 3409 | 39 我11楼那个方法，“后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5”，
从most significant digit开始递归，保证输出有序，
所以容易根据给定的最大值终止生成器。
此前我的思路是从个位数往高位开始左移递归：
“前n位含5 当且仅当 第n位是5 或 前n-1位含5”。
这种方法的缺陷是：结果无序，所以不方便根据给出的最大值跳出生成器。
DIGIDS_NO5 = (0,1,2,3,4,6,7,8,9)
# Generate all k-digit (1<=k<=n) numbers without digit 5
def genno5 (n):
if n == 1: yield from DIGIDS_NO5
else:
for x in genno5(n-1):
for y in DIGIDS_NO5:
yield 10 * y + x
# Generate all k-digit (1<=k<=n) numbers with digit 5
def gen5 (n):
if n == 1: yield 5
else:
yield from (10 * x + 5 for x in genno5(n-1))
for x in gen5(n-1):
for y in range(10):
yield 10 * x + y
>>> list(gen5(2))
[5, 15, 25, 35, 45, 65, 75, 85, 95, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59]
其实我最早的思路是：对于N-digit的数，考虑k=1,2,...,N个digits含'5'，对每个k，
'5'的分布有C(N,k)种情况，对于每一种情况，对剩下的N-k digits每个digit遍历
(0,1,2,3,4,6,7,8,9)，直接输出。这种思路也不用判重，但缺点也是无法保证有序。
也想过更啰嗦的思路：从给定的最大值开始递减，从低位到高位逐位模拟十进制数减法，
比如给定的最大值里第k位是4，那么该位先递减到0，再跳到9（前k-1位要递归退位）。
定义 `var has5 : array[1..N] of boolean`，其中has5[k]表示前k位含'5'，
has5[k] :=true if has5[k-1]=true or digit[k]=5, :=false if otherwise。
但退位时更新一次has5要O(N)复杂度，写起来又麻烦。想想就作罢了。
【在 b**********i 的大作中提到】
: 我一开始是这样想的，计算如果给定参数是k位数，有多少个含5的数字
: 对于1位数字 gen5(1)=1
: 2位数字 gen5(2)=8*gen5(1)+10=18
: 3位数字 gen5(3)=8*gen5(2)+10^2
: ...
: 但是我困扰在，如果给的参数不是位数，而是一个最大值，就不知道怎样计算了。
: 现在看来，你的思路跟我的有点像，但是你直接按这种思路输出含5的数字，这样就可
: 以判断是否超出最大值了，code真的很elegant，多谢！
| x*****0
发帖数: 452 | | | | h*****e
发帖数: 14 | 41 这是cc150的原题吧，cc150上问的是2的个数，这里求5的个数而已。 | m**********e
发帖数: 22 | 42 同楼下一大侠的算法。C#写的：
public List GetContainsFive(int num)
{
int m = num;
int i = 0;
while (m > 0)
{
i++;
m = m / 10;
}
string solution = string.Empty;
List result = new List();
GetContainsFiveHelper(num, i, solution, result);
return result;
}
private void GetContainsFiveHelper(int num, int n, string solution,
List result)
{
if (solution.Length == n)
{
int curr = int.Parse(solution);
if (curr <= num)
result.Add(curr);
return;
}
if (solution.Length < n - 1 || HasFive(solution))
{
for (char i = '0'; i <= '9'; ++i)
{
GetContainsFiveHelper(num, n, solution + i, result);
}
}
else
{
GetContainsFiveHelper(num, n, solution + 5, result);
}
}
private bool HasFive(string num)
{
if (num == null || num.Length == 0) return false;
foreach (var c in num)
{
if (c == '5')
return true;
}
return false;
}
【在 b**********i 的大作中提到】
: 写一个function，对于参数n，输出从0到n之间所有含5的数字。
: func(30) 应该输出5，15，25
: 这道题除了一个个数字的检查以外，还有什么更efficient的解法吗？
| w********8
发帖数: 55 | 43 借鉴楼上各位大牛的做法，我也写了一份Java的代码。。。。
public void mySolution(int num) {
if (num >= 5) {
String str = String.valueOf(num);
helper(num, "", 0, str.length(), false);
}
}
private void helper(int max, String prefix, int pos, int len, boolean
have5) {
if (pos == len) {
int cur = Integer.parseInt(prefix);
if (cur <= max) {
System.out.print(cur + ", ");
}
return;
}
for (int i = 0; i < 10; i++) {
if (pos == len - 1 && !have5 && i != 5) {
continue;
}
helper(max, prefix + i, pos + 1, len, have5 || i == 5);
}
}
望指教！ | s*********s
发帖数: 5 | 44 O(logN)算法，递归深度logN，但是每次递归的复杂度O(1)
思路是将f(XXX) 递归转化为 多个f(XX)，需要处理一些特殊情况
因为有重叠子结构，用memory记录一下，避免重复DFS，引入了DP的一些东西
int num5Impl(int num, unordered_map &memory)
{
if(num < 5)
return 0;
if(num <= 10)
return 1;
if(memory.find(num) != memory.end())
return memory[num];
int unit = 10;
while(num/unit >= 10)
{
unit *= 10;
}
int primeVal = num/unit;
int ret = 0;
if(primeVal > 5)
{
ret = (primeVal-1)*num5Impl(unit-1, memory) + unit;
}
else
ret = primeVal*num5Impl(unit-1, memory);
if(primeVal == 5)
ret += num-primeVal*unit + 1;
else
ret += num5Impl(num-primeVal*unit, memory);
memory[num] = ret;
return ret;
}
int num5(int num)
{
unordered_map memory;
return num5Impl(num, memory);
} | b*******n
发帖数: 8 | 45 用讨论里的方法写了java 代码，不用字符串操作。
public class NumsWith5 {
public static void numsWith5(int maxvalue, int partial, int pos, boolean
hasFive) {
if (pos == 0) {
if (partial <= maxvalue && hasFive)
System.out.printf(partial + " ");
return;
}
int num = (int)Math.pow(10, pos - 1);
for (int i = 0; i < 10; i++) {
numsWith5(maxvalue, partial + num * i,
pos - 1, hasFive || i == 5);
}
}
public static void main(String[] args) {
int maxvalue = 200;
int pos = 0;
int n = maxvalue;
while (n > 0) {
pos++;
n /= 10;
}
numsWith5(maxvalue, 0, pos, false);
System.out.printf("\n");
}
} | k*******q
发帖数: 5493 | 46 直接除以5，如果结果是偶数就再除2；如果结果是奇数就再除2然后+1
【在 b**********i 的大作中提到】
: 写一个function，对于参数n，输出从0到n之间所有含5的数字。
: func(30) 应该输出5，15，25
: 这道题除了一个个数字的检查以外，还有什么更efficient的解法吗？
| m*******n
发帖数: 12 | 47 用'>>'移位岂不是更容易?
【在 s*********s 的大作中提到】
: O(logN)算法，递归深度logN，但是每次递归的复杂度O(1)
: 思路是将f(XXX) 递归转化为 多个f(XX)，需要处理一些特殊情况
: 因为有重叠子结构，用memory记录一下，避免重复DFS，引入了DP的一些东西
: int num5Impl(int num, unordered_map &memory)
: {
: if(num < 5)
: return 0;
: if(num <= 10)
: return 1;
: if(memory.find(num) != memory.end())
| f**********t
发帖数: 1001 | 48 // 对于参数n，输出从0到n之间所有含5的数字。
void print5_(unsigned up, unsigned prefix, unsigned numLen, bool has5) {
if (numLen == 1) {
if (has5) {
for (unsigned i = 0; i < 10; ++i) {
if (prefix * 10 + i > up) {
return;
}
cout << prefix * 10 + i << ' ';
}
} else if (prefix * 10 + 5 <= up) {
cout << prefix * 10 + 5 << ' ';
}
return;
}
for (unsigned i = 0; i < 10; ++i) {
if (prefix * 10 + i > up) {
return;
} else {
print5_(up, prefix * 10 + i, numLen - 1, has5 || i == 5);
}
}
}
void print5(unsigned num) {
unsigned numLen = 0;
for (unsigned i = num; i != 0; i /= 10) {
++numLen;
}
print5_(num, 0, numLen, false);
cout << endl;
}
【在 b**********i 的大作中提到】
: 写一个function，对于参数n，输出从0到n之间所有含5的数字。
: func(30) 应该输出5，15，25
: 这道题除了一个个数字的检查以外，还有什么更efficient的解法吗？
| y*******n
发帖数: 99 | 49 这个行么？
BFS
[X]5->[XX](15,25,...,95, 50, 51, ..., 59) -> [XXX](105, .....)
Hash Table 去重
【在 b**********i 的大作中提到】
: 写一个function，对于参数n，输出从0到n之间所有含5的数字。
: func(30) 应该输出5，15，25
: 这道题除了一个个数字的检查以外，还有什么更efficient的解法吗？
|
|
