o******3
发帖数: 91 | 1 听了二爷的话，开始做hackerrank
今天被lego blocks绊住了
测试数据集可以过 但是提交数据集就超时了 虽然我用的确实是DP
下面是题目和我的代码，还望指点
You have 4 types of lego blocks, of sizes 1 * 1 * 1, 1 * 1 * 2, 1 * 1 * 3
and 1 * 1 * 4. Assume you have infinite number of blocks of each type.
You want to make a wall of height N and width M out of these blocks. The
wall should not have any holes in it. The wall you build should be one solid
structure. A solid structure means that it should not be possible to
separate the wall along any vertical line withou... 阅读全帖 |
|
|
g**********y
发帖数: 14569 | 3 Rolling hash code ->
public class FirstPalindrome {
private final static int MOD = 1000000007;
public int first(int[] a) {
int pow3 = 1;
int hash = a[0];
int reverse = a[0];
for (int i=1; i
pow3 = (pow3 * 3) % MOD;
hash = (hash + a[i] * pow3) % MOD;
reverse = (3*reverse + a[i]) % MOD;
if (hash == reverse && test(a, i)) return i;
}
return -1;
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 4 费了老半天劲写了一个恶心的。
int[][] dp = new int[2][];
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
char[] s = in.next().toCharArray();
char[] t = in.next().toCharArray();
int slen = s.length;
int tlen = t.length;
int mod = 1000000007;
dp[0] = new int[tlen];
dp[1] = new int[tlen];
int total = 0;
for (int j = 0; j < tlen; j++)
{
if (s[0] == t[j])
{
total++;
dp[0][j] = 1;
}
}
for (int i = 1; i < slen; i++)
{
if (s[i] == t[0])
{
dp[1][0] = 1;
total++;
}
int sum = 0;
for (... 阅读全帖 |
|
f*****u
发帖数: 308 | 5 网上看到下面的解法，代码看上去非常简洁漂亮。看了半天还是没看明白getWays里面
两个for循环怎么就算出所有的解法种数的。哪个大牛能给解释一下，非常感谢！
问题概述：m是基，对于给定数n，求n == x0*m^0 + x1*m^1 + x2*m^2 + ...的所有解
（x0, x1, x2, ...）的总个数。
#define MOD 1000000007
int getWays(int n, int m) {
vector w = vector(n + 1, 0);
for (long long i = 1; i <= n; i *= m) {
w[i] = (w[i] + 1) % MOD;
for (int j = i + 1; j <= n; j++) {
w[j] = (w[j] + w[j - i]) % MOD;
}
}
return w[n];
} |
|
t**r
发帖数: 3428 | 6 贴个答案
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
|
|
z*********n
发帖数: 1451 | 7 直接上干货, leetcode已经有这题了 (* 代表1~9 而非0~9)，这是我过了的一个解:
class Solution {
int base = 1000000007;
public:
int numDecodings(string s) {
//last1: decode ways of s ending at i-1, last2 decode ways of s
ending at i-2, nlast1 : next last1.
long long last1 = 1, last2 = 1, nlast1 = 0; //there is only 1 way to
decode "", so initialized with 1.
for (int i = 0; i < s.size(); ++ i)
{
//Just look at current character
if (s[i] == '*')
nla... 阅读全帖 |
|
