A****L
发帖数: 138 | 1 贴一个 O(n) 解法， java code 用了KMP 里的prefix function. 思路是前面有人提到
的 topcoder连接里讲解的。
public boolean checkRepetition(String s) {
int m = s.length();
if(m<4) return false;
for(int i=1;i
if(s.charAt(i)!=s.charAt(i-1)) break;
if(i==m-1) return false;
}
int[] pattern = prefixFunction(s);
int p = pattern[m];
while(p>1) {
if(p%(m-p)==0) return true;
p=pattern[p];
}
return f... 阅读全帖 |
|
S******1
发帖数: 216 | 2 //11:55 第3题不是图，是disjoint set
boolean isRight(String[] ss1, String[] ss2) {
if (ss1 == null || ss2 == null)
return false;
Map indexMap = new HashMap();
for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
if (!indexMap.containsKey(c1))
indexMap.put(c1, indexMap.size());
if (!indexMap.containsKey(c2))
indexMap.put(c2, indexMap.size());
}
int[] set = ne... 阅读全帖 |
|
S******1
发帖数: 216 | 3 //11:55 第3题不是图，是disjoint set
boolean isRight(String[] ss1, String[] ss2) {
if (ss1 == null || ss2 == null)
return false;
Map indexMap = new HashMap();
for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
if (!indexMap.containsKey(c1))
indexMap.put(c1, indexMap.size());
if (!indexMap.containsKey(c2))
indexMap.put(c2, indexMap.size());
}
int[] set = ne... 阅读全帖 |
|
y**********a
发帖数: 824 | 4 int longestTwoCharWindow(String s) {
if (s.length()==0) return 0;
char c1=s.charAt(0),c2=c1;
int ct=1,ml=1,rec=1;
for (int l=0,r=1;r
if (ct==1)
if (s.charAt(r)==c1)++rec;
else {++ct;rec=1;c2=s.charAt(r);}
else if (ct==2)
if (s.charAt(r)==c1){rec=1;}
else if (s.charAt(r)==c2){++rec;}
else {l=r-rec;rec=1;c1=c2;c2=s.charAt(r);}
ml=... 阅读全帖 |
|
y**********a
发帖数: 824 | 5 int longestTwoCharWindow(String s) {
if (s.length()==0) return 0;
char c1=s.charAt(0),c2=c1;
int ct=1,ml=1,rec=1;
for (int l=0,r=1;r
if (ct==1)
if (s.charAt(r)==c1)++rec;
else {++ct;rec=1;c2=s.charAt(r);}
else if (ct==2)
if (s.charAt(r)==c1){rec=1;}
else if (s.charAt(r)==c2){++rec;}
else {l=r-rec;rec=1;c1=c2;c2=s.charAt(r);}
ml=... 阅读全帖 |
|
y**********a
发帖数: 824 | 6 遍历所有的可能性，计算。
public int maxResult(int[]A) {
int[]rel=new int[1];rel[0]=Integer.MIN_VALUE;
dfs(A, new int[A.length-1], 0, rel);
return rel[0];
}
void dfs(int[]A, int[]op, int i, int[] max) {
if (i==op.length) {
StringBuilder s=new StringBuilder();
s.append(Integer.toString(A[0]));
char[] opc=new char[4];
opc[0]='+';opc[1]='-';opc[2]='*';opc[3]='/';
for (int j=0;j
... 阅读全帖 |
|
w****e
发帖数: 3827 | 7 如果是压缩的话，压完了长度要比原长度小，所以出现一两次的就不数个数了。
抛个砖，求轻拍
public static String encode(String s) {
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < s.length()) {
int count = 1;
while (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
i++;
count++;
}
if (count == 2) {
sb.append(s.charAt(i));
sb.append(s.charAt(i));
i++;
} else if (count > 2) {
sb.append(count);
... 阅读全帖 |
|
S***w
发帖数: 1014 | 8 题目好难
dfs暴力试吧
boolean dfs(String s, String p, Map s_to_p, Map
, String> p_to_s) {
if (s.isEmpty() && p.isEmpty()) return true;
if (s.isEmpty() || p.isEmpty()) return false;
for(int i = 2; i <= s.length(); ++i) {
String pre = s.substring(0, i);
if (s_to_p.containsKey(pre)) {
if (s_to_p.get(pre) == p.charAt(0) &&
dfs(s.substring(i), p.substring(1), s_to_p, p_to_s))
return true;
}
else if (p_to_s.containsK... 阅读全帖 |
|
S***w
发帖数: 1014 | 9 题目好难
dfs暴力试吧
boolean dfs(String s, String p, Map s_to_p, Map
, String> p_to_s) {
if (s.isEmpty() && p.isEmpty()) return true;
if (s.isEmpty() || p.isEmpty()) return false;
for(int i = 2; i <= s.length(); ++i) {
String pre = s.substring(0, i);
if (s_to_p.containsKey(pre)) {
if (s_to_p.get(pre) == p.charAt(0) &&
dfs(s.substring(i), p.substring(1), s_to_p, p_to_s))
return true;
}
else if (p_to_s.containsK... 阅读全帖 |
|
t******d
发帖数: 1383 | 10 做了个望上的测试，结果昨天晚上做了，今天被据了。请刷了poj的看看。 这哪里还有
bug？
跑出来的结果是
the number 007 is a number: false
the number 0.5 is a number: true
the number .01 is a number: true
the number 9. is a number: true
the number 1.000 is a number: true
the number 00.5 is a number: false
the number -.005000 is a number: true
我看着没问题
public class IsNumber {
/**
* The IsNumber function takes a String and returns true if that string
is a number, and false otherwise.
* This implementation, however, has several bugs in ... 阅读全帖 |
|
z****e
发帖数: 54598 | 11 今天做leetcode突然遇到的一个问题
在数据量比较小的时候，不会有问题
但是数据量一旦变大，马上就出问题了
不多说废话，上代码，代码很简单
Map m1 = new HashMap();
Map m2 = new HashMap();
然后
m1.put('a',1);
m2.put('a',new Integer(1));
然后
m1.get('a') == m2.get('a')，这个autoboxing理论上是可以的
但是实际上，在数据量陡然变大了之后，这个会出现false的结果
不是很明白为什么
不过让我想起一个往事就是
enum类型的判断，同样可以用==来替换equals
但是，这个情况在rmi的时候会出问题
所以说到底，还是尽量避免使用＝＝
否则会出现很多很subtle的问题
以下是代码正文
test case什么都写好了
可以直接debug和运行main函数
package test;
import java.... 阅读全帖 |
|
S****h
发帖数: 115 | 12 贴下自己的代码供参考，大家有兴趣的话给挑挑ug,thanks！
import java.util.List;
class Solution {
List groups;
int score;
public Solution() {
groups = new ArrayList();
}
}
public class StringNumberGroup {
public Solution getOptimalGroup(String phone) {
if (phone.length() <= 3) {
Solution s = new Solution();
s.groups.add(phone);
s.score = getScore(phone);
... 阅读全帖 |
|
A*H
发帖数: 127 | 13 是一定code有问题么，还是有可能程序跑得不够快?
wildcard matching 那题，small test 过了，large test 一直timeout, 大家帮忙看
看这个java code有什么问题么? 除了暴力法，还有更快得解法么？
public boolean isMatch(String s, String p) {
return match(s, p, 0, 0);
}
public boolean match(String s1, String s2, int i1, int i2) {
int l1 = s1.length();
int l2 = s2.length();
if (i2 == l2) return i1 == l1;
if (s2.charAt(i2) == '*') {
while (i2
i2++; // find next n... 阅读全帖 |
|
p*****2
发帖数: 21240 | 14 我写了一个DP的怎么还是超时呢？
哪里可以改善？
public boolean isMatch(String s, String p)
{
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[2][n + 1];
dp[0][0] = true;
for (int j = 1; j <= n; j++)
{
if (p.charAt(j - 1) == '*')
dp[0][j] = dp[0][j - 1];
}
for (int i = 1; i <= m; i++)
{
int curr=i%2;
int prev=(i+1)%2;
Arrays.fill(dp[curr],false);
... 阅读全帖 |
|
r*****a
发帖数: 421 | 15 用recursive brutal force的算法leetcode通过了small data test，
但是在large data test的时候超时了。
尤其是以下这个例子，自己电脑上都算不出来。
s="bbbababbbbabbbbababbaaabbaababbbaabbbaaaabbbaaaabb"
p="*b********bb*b*bbbbb*ba"
有没有更优化的算法？
贴个java的
public boolean wildcardMatch(String s, String p, int sPos, int pPos) {
if (sPos == s.length()) {
if (pPos == p.length()) // p also used up
return true;
} else if (pPos < p.length() && p.charAt(pPos) == '*') { // current p
is *, rest should all be *
return wild... 阅读全帖 |
|
p*****2
发帖数: 21240 | 16
你再仔细看看。不过我可以换一种写法就更清楚了。
public boolean isMatch(String s, String p)
{
int n=s.length();
int m=p.length();
boolean[][] dp=new boolean[2][n+1];
dp[m%2][n]=true;
for(int i=m-1;i>=0;i--)
{
Arrays.fill(dp[i%2], false);
dp[i%2][n]=p.charAt(i)=='*' && dp[(i+1)%2][n];
for(int j=n-1;j>=0;j--)
if(p.charAt(i)=='*')
dp[i%2][j]=dp[(i+1)%2][j] || dp[i%2][j+1];
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 17 我用Java写了一个，真是没有C＋＋简洁呀。
public boolean isMatch(String s, String p)
{
int n=s.length();
int m=p.length();
int i=0;
int j=0;
int star=-1;
int sp=0;
while(i
{
//one * and multiple *, same effect
while(j
{
star=j++; //* match 0 character
sp=i;
}
if(j==m || (p.charAt(j)!=s.charAt(i) && p.ch... 阅读全帖 |
|
r****m
发帖数: 70 | 18 boolean validate(String expression){
String expr = expression.trim();
boolean expectNum = true;
int numOfParentheses = 0;
int i = 0;
while(i < expr.length()){
if(expr.charAt(i) == '('){
if(!expectNum) return false;
numOfParentheses++;
i++;
} else if (expr.charAt(i) == ')'){
if(expectNum || numOfParentheses < 1) return false;
numOfParentheses--;
... 阅读全帖 |
|
r****m
发帖数: 70 | 19 boolean validate(String expression){
String expr = expression.trim();
boolean expectNum = true;
int numOfParentheses = 0;
int i = 0;
while(i < expr.length()){
if(expr.charAt(i) == '('){
if(!expectNum) return false;
numOfParentheses++;
i++;
} else if (expr.charAt(i) == ')'){
if(expectNum || numOfParentheses < 1) return false;
numOfParentheses--;
... 阅读全帖 |
|
a**c
发帖数: 52 | 20 来自主题: JobHunting版 - G家电面题 Boolean checkBasicVowel(char c) {
if (c == ‘a’ || c ==’e’ || c == ‘i’ || c ==’o’ ||
c == ‘u’ || c == ‘A’ || c ==’E’ || c == ‘I’ ||
c ==’O’ ||c == ‘U’)
return True;
}
// check whether it is vowel
Boolean checkVowel(String s, int index){
char c = s.charAt(index);
if (checkBasicVowel(c))
return True;
if (index == 0)
return False;
if (c == ‘y’ || c == ‘Y’) {
if(!checkVowel(s, index - 1))
return True;
return False;
}
return False;
}
... 阅读全帖 |
|
h******3
发帖数: 351 | 21 was asked this question onsite interview. Think through and come up with
this version.
public String int2roman(int n){
String[] values = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","
I"};
int[] table = {100,900,500,400,100,90,50,40,10,9,5,4,1};
StringBuilder res = new StringBuilder();
for(int i = 0; i< table.length(); i++){
if ( n >= table[i]){
res.append(values[i]);
n -= table[i];
}
}
return res.toString();
}
public int roman2int(String roman){
Map阅读全帖 |
|
c******a
发帖数: 789 | 22 大小测试都过了
public boolean exist(char[][] board, String word) {
if (board==null || board.length==0 || board[0].length==0) return
false;
for (int i=0; i
for (int j=0; j
if (board[i][j]==word.charAt(0)) {
boolean[][] used = new boolean[board.length][board[0].
length];
used[i][j] = true;
if (walk(board, i, j, word, 1, used)) return true;
... 阅读全帖 |
|
c********p
发帖数: 1969 | 23 上代码，大家批斗！
public class Solution {
public boolean isMatch(String s, String p) {
// Start typing your Java solution below
// DO NOT write main() function
if(s == null || p == null){
return false;
}
int slen = s.length();
int plen = p.length();
boolean[][] dp = new boolean[slen + 1][plen + 1];
dp[0][0] = true;
for(int i = 1; i <= plen; i++){
if(p.charAt(i - 1) == '*'){
if( dp[... 阅读全帖 |
|
f*******b
发帖数: 520 | 24 这题是要上DP的，LZ用的方法和我开始一样，但通过不了大数据，不是DP的问题，是所
用算法本身的问题，我改了后就能过大数据了：
public boolean isMatch(String s, String p) {
int count=0;
for(int i=0;i
if(p.charAt(i)!='*') count++;
if(count>s.length()) return false;
if(s.length()==0) return true;
if(p.length()==0) return s.length()==0;
boolean[][] blc=new boolean[s.length()+1][p.length()+1];
blc[0][0]=true;
for(int j=1;j
for(int i=... 阅读全帖 |
|
s******7
发帖数: 1758 | 25 我给你写个java的
这种前后双指针夹逼得淫荡招数一定要用熟练
public static String findLongest(String s)
{
int max=0;
int maxRight=0;
int maxLeft=0;
char c1=s.charAt(0);
int last1=0; //record last c1 position
char c2=' ';
int n=s.length();
int j=0; //后指针
for (int i=1; i
{
if(s.charAt(i)==c1||s.charAt(i)==c2)
{
if(s.charAt(i)==c1) last1=i;
if(i-j>max)
{
... 阅读全帖 |
|
d********i
发帖数: 582 | 26 解法： Fraction To Decimal结合Longest Substring Without Repeating Characters
变种
测试：
System.out.println(fractionToDecimal(2, 4)); // 0.5
System.out.println(fractionToDecimal(1, 3)); // 0.(3)
System.out.println(fractionToDecimal(1, 7)); // 0.(142857)
代码：
public static String fractionToDecimal(int numerator, int denominator) {
String res = "0.";
while (numerator != 0) {
int tmp = (numerator * 10) / denominator;
res = res + Integer.toString(tmp);
numerator = (numerator * 10) % denominator;
if (res.length... 阅读全帖 |
|
S******1
发帖数: 216 | 27 来自主题: JobHunting版 - FB 面筋
Minimum
写一个考虑顺序的inverted indexing做法
//7:10
//给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB
int findMinWindow(String s, String p) {
if (s == null || p == null || s.length() < p.length())
return -1;
if (p.isEmpty())
return 0;
Map> indexMap = new HashMap
Integer>>();
for (int i = 0; i < s.length(); i++) {
if (!indexMap.containsKey(s.charAt(i)))
indexMap.put(s.charAt(i), new Arra... 阅读全帖 |
|
发帖数: 1 | 28 仅此而已，no trick ，
public String lc301(String input) {
char[]inputt = input.toCharArray();
StringBuilder s = new StringBuilder();
StringBuilder res = new StringBuilder();
int open = 0;
for (char i : inputt) {
if (i =='(') {
open++;
s.append(i);
}else if (i ==')') {
if(open >0) {
s.append(i);
open--;
}
}el... 阅读全帖 |
|
g**e
发帖数: 6127 | 29 Here is my java version
public static void KMP(String target, String pattern) {
boolean found = false;
int[] overlap = getOverlap(pattern);
int j = 0;
for (int i=0; i
while (true) {
if (target.charAt(i) == pattern.charAt(j)) {
j++;
if (j =... 阅读全帖 |
|
S*******0
发帖数: 198 | 30 正数和负数的overflow判断不一样，
public static int atoi(String str) throws Exception{
String expression = str.trim();
if(expression==null||expression.equals("")){
throw new Exception("expression is empty");
}
int sign = 1;
int index = 0;
if(expression.charAt(0) == '-'){
sign = -1;
}
if(expression.charAt(0) == '-' || expression.charAt(0) == '+'){
index++;
if(expression.length()==1){
... 阅读全帖 |
|
S*******0
发帖数: 198 | 31 这个版上讨论过多次了，这是我的code
//atoi
public static int atoi(String str) throws Exception{
String expression = str.trim();
if(expression==null||expression.equals("")){
throw new Exception("expression is empty");
}
int sign = 1;
int index = 0;
if(expression.charAt(0) == '-'){
sign = -1;
}
if(expression.charAt(0) == '-' || expression.charAt(0) == '+'){
index++;
if(expression.length()==1){
... 阅读全帖 |
|
d********w
发帖数: 363 | 32 需要逻辑缜密阿，
我实现的好像有bug，大家能想到比较好的办法么
static int encode(String str) {
int num = 0;
int sum = 0;
int cur = 0;
boolean vowelBefore = false;
boolean vowel;
str = str.toLowerCase();
for ( int i=0; i< str.length(); i++) {
if (map.get(str.charAt(i)) != null) {
cur = map.get(str.charAt(i));
vowel = true;
} else {
vowel = false;
}
if (str.char... 阅读全帖 |
|
n**0
发帖数: 136 | 33 简单四则运算
public static double cal(String s) {
int lastpos = -1;
char lastOps = ' ';
int rightBracket = 0;
for (int i = s.length() - 1; i >= 0; i--) {
switch (s.charAt(i)) {
case ')':
rightBracket++;
break;
case '(':
rightBracket--;
break;
}
if (rightBracket > 0)
continue;
switch (s.charAt(i)) {
case '+':
return cal(s.substring(0, i).trim())
+ cal(s.substring(i + 1, s.length()).trim());
case '-':
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 34 店面写的话还有有些麻烦。onsite更合适。随便写了一个练练手。不调试不能一次搞定
呀。
public class test4
{
public static void main(String[] args)
{
test4 t = new test4();
System.out.println(t.Multiple("1234", "23"));
}
String add(String s1, String s2)
{
StringBuffer sb = new StringBuffer();
int carrier = 0;
int p1 = s1.length() - 1;
int p2 = s2.length() - 1;
while (p1 >= 0 || p2 >= 0)
{
int a = 0;
int b = 0;
if (p1 >=... 阅读全帖 |
|
p*****2
发帖数: 21240 | 35 店面写的话还有有些麻烦。onsite更合适。随便写了一个练练手。不调试不能一次搞定
呀。
public class test4
{
public static void main(String[] args)
{
test4 t = new test4();
System.out.println(t.Multiple("1234", "23"));
}
String add(String s1, String s2)
{
StringBuffer sb = new StringBuffer();
int carrier = 0;
int p1 = s1.length() - 1;
int p2 = s2.length() - 1;
while (p1 >= 0 || p2 >= 0)
{
int a = 0;
int b = 0;
if (p1 >=... 阅读全帖 |
|
p*g
发帖数: 141 | 36 private static String strMultiple(String s1, String s2) {
int len2 = s2.length();
String rv = "";
for (int i = 0; i < len2; i++) {
String part = strMultipleChar(s1, s2.charAt(i));
rv = rv + "0";
rv = strSum(part, rv);
}
return rv;
}
private static String strSum(String s1, String s2) {
StringBuilder sb = new StringBuilder();
int carryin = 0;
int len1 = s1.length();
int len2 = s2.len... 阅读全帖 |
|
a*******8
发帖数: 110 | 37 面试时的String match题，如果要求比brute force更好的解的话，都可以考虑这个。
看了半天Wiki，才弄明白。。。
//KMP algorithm
//Reference WIKI: //http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
String getCommon(String s1, String s2) {
int maxLength = Math.min(s1.length(), s2.length());
int[] table = buildFailureTable(s2, maxLength);
int m = s1.length() - maxLength;
int i = 0;
while (m + i < s1.length()) {
if (s1.charAt... 阅读全帖 |
|
f*****n
发帖数: 15 | 38 one way to solve it is to use DP. runtime is O(n^2) and it requires O(n)
extra space.
import java.util.ArrayList;
import java.util.List;
public class StringOperation {
public static void main(String[] args) {
StringOperation strOp = new StringOperation();
System.out.println(strOp.findLongRepeatedString("banana"));
System.out.println(strOp.findLongRepeatedString("aaaaa"));
}
public String findLongRepeatedString(String src) {
Result longestResult = n... 阅读全帖 |
|
p*****2
发帖数: 21240 | 39
的确。
boolean dfs(String a, String b, String c, int i, int j)
{
if(i+j==c.length())
return true;
if(i
{
if(dfs(a,b,c,i+1,j))
return true;
}
if(j
{
if(dfs(a,b,c,i,j+1))
return true;
}
return false;
}
boolean isInterleave(String a, String b, String c)
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 40 写了一个dp的。
public boolean isInterleave(String s1, String s2, String s3)
{
if(s1==null || s2==null || s3==null)
return false;
int l1=s1.length();
int l2=s2.length();
int l3=s3.length();
if(l1+l2!=l3)
return false;
boolean[][] dp=new boolean[l1+1][l2+1];
dp[l1][l2]=true;
for(int i=l1;i>=0;i--)
for(int j=l2;j>=0;j--)
{
if(i阅读全帖 |
|
p*****2
发帖数: 21240 | 41
代码要麻烦一些。
public boolean isInterleave(String s1, String s2, String s3)
{
if(s1==null || s2==null || s3==null)
return false;
int l1=s1.length();
int l2=s2.length();
int l3=s3.length();
if(l1+l2!=l3)
return false;
boolean[][] dp=new boolean[2][l2+1];
for(int i=l1;i>=0;i--)
{
int id=i%2;
Arrays.fill(dp[id],false);
for(int j=l... 阅读全帖 |
|
p*****2
发帖数: 21240 | 42
看我的例子。
int[][] dp=null;
boolean dfs(String a, String b, String c, int i, int j)
{
if(dp[i][j]!=-1)
return dp[i][j]==1;
dp[i][j]=0;
if(i+j==c.length())
{
dp[i][j]=1;
}
else
{
if(i
dp[i][j]=1;
if(dp[i][j]==0 && j
,b,c,i,j+1))
dp[i][j]=1;
}
return d... 阅读全帖 |
|
z****e
发帖数: 54598 | 43 public class Solution {
public boolean exist(char[][] board, String word) {
// Start typing your Java solution below
// DO NOT write main() function
if(word.length()<1) return false;
for(int i=0;i
for(int j=0;j
if(board[i][j]==word.charAt(0)){
board[i][j] = ' ';
if(this.existed(board,word.substring(1),i,j)
) return tr... 阅读全帖 |
|
s******c
发帖数: 99 | 44 import java.io.*;
public class Solution {
public static void main(String args[] ) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.
in));
String line = br.readLine();
int N = Integer.parseInt(line);
String []strs=new String[N];
for (int i = 0; i < N; i++) {
strs[i]=br.readLine();
}
for(int i=0;i
{
char start=strs[i].charAt(0);
int sumtotal=0... 阅读全帖 |
|
c******t
发帖数: 391 | 45 判断回文那题，照着思路写了一个，不知道对不对，请指点：
public static boolean checkPalindrome(String str){
str = str.toLowerCase();
int i = 0;
int j = str.length()-1;
while(i
while(!isValid(str.charAt(i)))
i++;
while(!isValid(str.charAt(j)))
j--;
if(str.charAt(i)!=str.charAt(j))
return false;
i++;
j--;
}
return true;
}
public static boolean isValid(char ch){
if((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z'))
retu... 阅读全帖 |
|
p*****2
发帖数: 21240 | 46 我觉得这题面试最好还是用DP来解。
public boolean isMatch(String s, String p)
{
int n=s.length();
int m=p.length();
boolean[][] dp=new boolean[2][n+1];
dp[m%2][n]=true;
for(int i=m-1;i>=0;i--)
{
Arrays.fill(dp[i%2], false);
if(p.charAt(i)=='*')
for(int j=n;j>=0;j--)
{
if(dp[(i+1)%2][j])
for(int k=0;k<=j;k++)
dp[i%2][k... 阅读全帖 |
|
l**b
发帖数: 457 | 47 二爷不用DP，奇怪啊！第3题用Trie的话memory吃不消吧？用DP是不是好点？
贴个简单的代码，helper是recursive的，helper2是DP的，2爷帮忙看看，是不是又出
错了：
public boolean isSubSequence(String s, String t) {
assert(s != null && t != null);
if (t.length() == 0) return true;
//return helper(s, t, 0, 0);
return helper2(s, t);
}
private boolean helper(String s, String t, int si, int ti) {
if (ti == t.length()) return true;
if (si >= s.length()) return false;
if (s.charAt(si) == t... 阅读全帖 |
|
l**b
发帖数: 457 | 48 二爷不用DP，奇怪啊！第3题用Trie的话memory吃不消吧？用DP是不是好点？
贴个简单的代码，helper是recursive的，helper2是DP的，2爷帮忙看看，是不是又出
错了：
public boolean isSubSequence(String s, String t) {
assert(s != null && t != null);
if (t.length() == 0) return true;
//return helper(s, t, 0, 0);
return helper2(s, t);
}
private boolean helper(String s, String t, int si, int ti) {
if (ti == t.length()) return true;
if (si >= s.length()) return false;
if (s.charAt(si) == t... 阅读全帖 |
|
s*********s
发帖数: 140 | 49 贴个java recursive的吧。
float compute(String exp) {
if(exp == null || exp.length() == 0) return 0;
int plusPos = exp.indexOf('+');
int minusPos = exp.indexOf('-');
if(plusPos < 0 && minusPos < 0) return convert(exp);
if(plusPos < 0 || (minusPos > 0 && minusPos < plusPos))
return convert(exp.substring(0, minusPos)) - compute(exp.
substring(minusPos+1));
if(minusPos < 0 || (plusPos > 0 && plusPos < minusPos... 阅读全帖 |
|
s*********s
发帖数: 140 | 50 贴个java recursive的吧。
float compute(String exp) {
if(exp == null || exp.length() == 0) return 0;
int plusPos = exp.indexOf('+');
int minusPos = exp.indexOf('-');
if(plusPos < 0 && minusPos < 0) return convert(exp);
if(plusPos < 0 || (minusPos > 0 && minusPos < plusPos))
return convert(exp.substring(0, minusPos)) - compute(exp.
substring(minusPos+1));
if(minusPos < 0 || (plusPos > 0 && plusPos < minusPos... 阅读全帖 |
|
