c*****a
发帖数: 808 | 1 char[256] set + 2个指针
检查isAnagram用constant time 256，就是O(1)
总共就是O(n) time, O(1) space， 256space是constant...
public boolean isAnagram(char[]s1,char[]s2){
int i=0;
for(char c:s1)
if(c!=s2[i++]) return false;
return true;
}
public boolean checkAna(String s1,String s2){
if(s1==null || s2==null)return false;
if(s2.length()==0) return true;
if(s1.length()
char[] set1 = new char[256];
char[] set2 = new char[256];
for(int i=0;i阅读全帖 |
|
J*****a
发帖数: 4262 | 2 练一个
public static ArrayList maxConsecutiveRep(String s){
if(s == null || s.length() == 0) return null;
int max = 1;
int count = 1;
ArrayList rl = new ArrayList();
if(s.charAt(0) != ' ') rl.add(s.charAt(0));
for(int i = 1; i < s.length(); i++){
char cr = s.charAt(i);
if(cr == ' ') continue;
if(cr == s.charAt(i-1)) count++;
else count = 1;
if(max == c... 阅读全帖 |
|
l*********8
发帖数: 4642 | 3 谢谢。 这样啊。 那就不用追求行数少了。
你的程序，我的格式是这样的： 不算空行，加上括号的话27行。
public static ArrayList maxConsecutiveRep(String s){
if(s == null || s.length() == 0)
return null;
int max = 1;
int count = 1;
ArrayList rl = new ArrayList();
if(s.charAt(0) != ' ')
rl.add(s.charAt(0));
for(int i = 1; i < s.length(); i++){
char cr = s.charAt(i);
if(cr == ' ')
continue;
... 阅读全帖 |
|
z*******3
发帖数: 13709 | 4 public static List getMaxSequentChars(String string){
List l = new ArrayList();
int cn = 0, max=0;
char pre = 0;
for(int i=0;i
if(string.charAt(i)==pre){
cn++;
if(cn>max){
l.clear();
max = cn;
}
}else{
cn =0;
}
if(cn>=max){
if(string.charAt(i)!=' ') l.add(string.charAt(i));... 阅读全帖 |
|
b*******3
发帖数: 109 | 5 贴个java solution O(n m) :
public String minWindow (String originalString, String patternString)
{
List valuePairs = new ArrayList();
int shortestWindowLength = originalString.length();
int shortestHolderIndex = 0;
for (int i=0; i< originalString.length(); i++)
{
if (patternString.indexOf(originalString.charAt(i))>=0)
{
ValuePair valuePair = new ValuePair(originalSt... 阅读全帖 |
|
h******3
发帖数: 351 | 6 complain runtime error
Last executed input
"a"
public int minCut(String s){
int count = 0;
ArrayList> res = partition(s);
for(ArrayList subpa : res)
count += subpa.size();
return count;
}
public ArrayList> partition(String s) {
if(s == null || s.length() == 0)
return new ArrayList>();
boolean[][] isPa = new boolean[s.length()][s.length()];
for(int i = 0; i < s.length(); i++){
isPa[i][i] = true;
... 阅读全帖 |
|
d****n
发帖数: 233 | 7 Another one for Wildcard match:
public class Solution {
public boolean isMatch(String s, String p) {
int m = s.length() + 1;
int n = p.length() + 1;
boolean[][] result = new boolean[n][m];
result[0][0] = true;
for( int i = 1; i < n; i++){
result[i][0] = p.charAt(i-1) == '*' ? result[i-1][0] : false;
}
for( int j = 1; j < m; j++){
result[0][j] = false;
}
for( int i = 1; i ... 阅读全帖 |
|
f*******b
发帖数: 520 | 8 可是在我自己的IDE,没有问题，可以通过！
测试内容一样。。。
怎么回事阿。。。
原因会不会是我在method外申明的HashMap对OJ测试有影响? 也不知道怎么改。
Longest palindromic substring
代码如下：
public class Solution {
HashMap map= new HashMap();
public String longestPalindrome(String s) {
if(map.containsKey(s))
return map.get(s);
StringBuilder sb= new StringBuilder();
int i=0,j=s.length()-1;
while(i<=j)
{
if(i==j)
{
String middle=Characte... 阅读全帖 |
|
f*******b
发帖数: 520 | 9 可是在我自己的IDE,没有问题，可以通过！
测试内容一样。。。
怎么回事阿。。。
原因会不会是我在method外申明的HashMap对OJ测试有影响? 也不知道怎么改。
Longest palindromic substring：
代码：
public class Solution {
HashMap map= new HashMap();
public String longestPalindrome(String s) {
if(map.containsKey(s))
return map.get(s);
StringBuilder sb= new StringBuilder();
int i=0,j=s.length()-1;
while(i<=j)
{
if(i==j)
{
String middle=Character... 阅读全帖 |
|
s********x
发帖数: 914 | 10 // check if string a can be the anagram of substring of b
public static boolean isAnagramSubstring(String a, String b) {
if (a == null || a.length() == 0 || b == null) {
throw new IllegalArgumentException();
}
if (a.length() > b.length()) {
return false;
}
int size = a.length();
Map needToFind = new HashMap
(size);
for (int i = 0; i < size; i++) {
... 阅读全帖 |
|
r*****e
发帖数: 30 | 11 public boolean isMultiple(String s){
if(s==null || s.length()<3) return false;
ArrayList pattern = new ArrayList();
pattern.add(s.charAt(0));
pattern.add(s.charAt(1));
int times = 1;
int pos = 0;
for(int i=2; i
if(s.charAt(i)==pattern.get(pos)){
if(pos==pattern.size()-1){
times++;
pos = 0;
}
else{
... 阅读全帖 |
|
l*****4
发帖数: 267 | 12 贡献一下我的，试过大家提到的所有case， 都可以
public boolean isMultiple(String s) {
if (s == null || s.length() == 0) {
return false;
}
int len = s.length();
if (len == 1) {
return true;
}
if (len == 2) {
return s.charAt(0) == s.charAt(1);
}
int left = 0;
for (int i = 1; i < len; i++) {
char c = s.charAt(i);
if (c == s.charAt(left)) {
left++;
} else {
... 阅读全帖 |
|
r*****e
发帖数: 30 | 13 public boolean isMultiple(String s){
if(s==null || s.length()<3) return false;
ArrayList pattern = new ArrayList();
pattern.add(s.charAt(0));
pattern.add(s.charAt(1));
int times = 1;
int pos = 0;
for(int i=2; i
if(s.charAt(i)==pattern.get(pos)){
if(pos==pattern.size()-1){
times++;
pos = 0;
}
else{
... 阅读全帖 |
|
l*****4
发帖数: 267 | 14 贡献一下我的，试过大家提到的所有case， 都可以
利用string本身作为pattern
如果前半部分都match的话，指针要过中点
只判断是否过中点的话，“aaaaabaaaa”这种就判断错误
是因为后一段短，从指针到pattern结束的位置没有被扫到
如果把指针到string 末尾的再和string前一部分相同长度的段对比，如果是重复，那
就真的是true
如果没办法重复，就说明漏扫了不同的部分，false
解释的可能不清楚，还是看代码吧，java
public boolean isMultiple(String s) {
if (s == null || s.length() == 0) {
return false;
}
int len = s.length();
if (len == 1) {
return true;
}
if (len == 2) {
return s.charAt(0) == s.charAt(1);
}
int left = 0;
for (int i = 1; i < len; i++) {
char c = s.charAt(i);
if (c ... 阅读全帖 |
|
p**p
发帖数: 742 | 15 这题用KMP吧。检查preprocess部分生产的array l 就可以了。如果是valid case.
preprocessing array 必然满足下面的几个条件：
1. l[n-1] 必须是最大值 (这个没必要专门检查,只要3满足就成);
2. s[0,...,n-l[n-1])就是repeating pattern;
3. l[n-1]/(length of the repeating pattern) >= 1;
4. l[n-1] % (length of the repeating pattern) == 0.
比如：
"abcabcabc" -> [0, 0, 0, 1, 2, 3, 4, 5, 6]
"abcdabcd"-> [0, 0, 0, 0, 1, 2, 3, 4]
几个false cases:
"bcdbcdbcdebcdbcdbcd" -> [0, 0, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7,
8, 9]
"ababeabab"-> [0, 0, 1, 2, 0, 1, 2, 3, 4]
code 如下：... 阅读全帖 |
|
p**p
发帖数: 742 | 16 这题用KMP吧。检查preprocess部分生产的array l 就可以了。如果是valid case.
preprocessing array 必然满足下面的几个条件：
1. l[n-1] 必须是最大值 (这个没必要专门检查,只要3满足就成);
2. s[0,...,n-l[n-1])就是repeating pattern;
3. l[n-1]/(length of the repeating pattern) >= 1;
4. l[n-1] % (length of the repeating pattern) == 0.
比如：
"abcabcabc" -> [0, 0, 0, 1, 2, 3, 4, 5, 6]
"abcdabcd"-> [0, 0, 0, 0, 1, 2, 3, 4]
几个false cases:
"bcdbcdbcdebcdbcdbcd" -> [0, 0, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7,
8, 9]
"ababeabab"-> [0, 0, 1, 2, 0, 1, 2, 3, 4]
code 如下：... 阅读全帖 |
|
S*******C
发帖数: 822 | 17 谢谢指正，这题难度很大，上面这么多解法只有3种是对的
贴一种比较简洁的写法，不知道怎么证明是O(N)的解法？
public boolean isMultipleDuplicate(String s) {
if (s == null || s.length() < 4)
return false;
int len = s.length();
int[] a = new int[len];
int j = 0;
for (int i = 1; i < len; i++) {
while (j > 0 && s.charAt(i) != s.charAt(j))
j = a[j - 1];
if (s.charAt(i) == s.charAt(j))
j++;
a[i] = j;
}
int patternLen ... 阅读全帖 |
|
h******6
发帖数: 2697 | 18 public static String getNext(String s) {
int len = s.length();
int i = len - 1;
char[] a = s.toCharArray();
for (; i > 0; --i) {
if (s.charAt(i) > s.charAt(i-1)) {
break;
}
}
for (int j = len - 1; j >= i; --j) {
if (s.charAt(j) > s.charAt(i-1)) {
swap(a, i-1, j);
}
}
Arrays.sort(a, i, len);
return new String(a);
} |
|
f***s
发帖数: 112 | 19 这题45分钟弄不出来
import java.util.HashMap;
import java.util.Map;
public class KDistance {
static class Node{
char c;
boolean isLeaf;
Node p;
Map children;
String word;
int no;
int depth;
static int counter = 0;
static Map nodemap = new HashMap();
public Node(Node parent, char c){
children = new HashMap();
p = parent;
if(... 阅读全帖 |
|
f***s
发帖数: 112 | 20 这题45分钟弄不出来
import java.util.HashMap;
import java.util.Map;
public class KDistance {
static class Node{
char c;
boolean isLeaf;
Node p;
Map children;
String word;
int no;
int depth;
static int counter = 0;
static Map nodemap = new HashMap();
public Node(Node parent, char c){
children = new HashMap();
p = parent;
if(... 阅读全帖 |
|
D***0
发帖数: 138 | 21 网上申请的，回复的挺快，安排了code challenge，一道题，不限时，半个小时写完了
，发过去，第二天收到了thank you but 88.不知道哪里的问题。
* Write a function that takes two parameters:
* (1) a String representing a text document and
* (2) an integer providing the number of items to return.
* Implement the function such that it returns a list of Strings ordered by
word frequency,
* the most frequently occurring word first.
* Use your best judgement to decide how words are separated.
* Your solution should run in O(n) time where n is the number of cha... 阅读全帖 |
|
p****6
发帖数: 724 | 22 public static boolean oneEditApart(String a, String b) {
String small = a.length() > b.length() ? b : a;
String large = a.length() > b.length() ? a : b;
int operation = 0;
//case 1, two word's length differ by more than one
if(large.length() - small.length() > 1) return false;
//case 2, length is equal, check every char one by one
else if(large.length() == small.length()){
int i = 0;
while(i < sma... 阅读全帖 |
|
i******d
发帖数: 7 | 23 Space O(1), Time O(n)
public int maxLength(String s){
if (s.isEmpty()) return 0;
int diffCharIndex = -1, currentLength = 1, maxLength = 1;
for (int i = 1; i < s.length(); i++)
{
if (s.charAt(i) != s.charAt(i-1))
{
if (diffCharIndex == -1 || s.charAt(i) == s.charAt(
diffCharIndex)) {
currentLength++; diffCharIndex = i - 1; }
else { currentLength = i - diffCharIndex; diffCharIndex = i-
1; ... 阅读全帖 |
|
i******d
发帖数: 7 | 24 Space O(1), Time O(n)
public int maxLength(String s){
if (s.isEmpty()) return 0;
int diffCharIndex = -1, currentLength = 1, maxLength = 1;
for (int i = 1; i < s.length(); i++)
{
if (s.charAt(i) != s.charAt(i-1))
{
if (diffCharIndex == -1 || s.charAt(i) == s.charAt(
diffCharIndex)) {
currentLength++; diffCharIndex = i - 1; }
else { currentLength = i - diffCharIndex; diffCharIndex = i-
1; ... 阅读全帖 |
|
r****m
发帖数: 70 | 25 有朋友提到不知道怎么做DP的题目，分享一下自己的总结，希望对大家有帮助。
1. Distinct Subsequence (String S, String T)
F(i, j) = F(i-1, j) , S[i] != T[j]
F(i-1, j) + F(i-1, j-1) , S[i] ==T[j]
2. Longest Common Subsequence (String S1, String S2)
F(i, j) = F(i-1, j-1) + 1, S[i] == T[j]
Max{ F(i-1, j), F(i, j-1) }, S[i] !=T[j]
LCS可以把空间复杂度O(n^2)减少到O(n),因为第n步的DP只 和前一步(第n-1步)的
最优子结果有关 F(n) = F(n-1)
3. Edit Distance (String S1, String S2)
F(i, j) = Min { F... 阅读全帖 |
|
r****m
发帖数: 70 | 26 有朋友提到不知道怎么做DP的题目，分享一下自己的总结，希望对大家有帮助。
1. Distinct Subsequence (String S, String T)
F(i, j) = F(i-1, j) , S[i] != T[j]
F(i-1, j) + F(i-1, j-1) , S[i] ==T[j]
2. Longest Common Subsequence (String S1, String S2)
F(i, j) = F(i-1, j-1) + 1, S[i] == T[j]
Max{ F(i-1, j), F(i, j-1) }, S[i] !=T[j]
LCS可以把空间复杂度O(n^2)减少到O(n),因为第n步的DP只 和前一步(第n-1步)的
最优子结果有关 F(n) = F(n-1)
3. Edit Distance (String S1, String S2)
F(i, j) = Min { F... 阅读全帖 |
|
I*******g
发帖数: 7600 | 27 第一题：
public static String shortestString(String s, String p){
String result = null;
if (s== null || p == null || p.length() >s.length()) return null;
if (s.length() ==0 || p.length() ==0) return "";
Map indexMap = new HashMap();
List indexList = new ArrayList();
int min = s.length() +1;
for(int i =0 ;i < s.length(); i++){
for(Integer x: indexList){
... 阅读全帖 |
|
I*******g
发帖数: 7600 | 28 第一题：
public static String shortestString(String s, String p){
String result = null;
if (s== null || p == null || p.length() >s.length()) return null;
if (s.length() ==0 || p.length() ==0) return "";
Map indexMap = new HashMap();
List indexList = new ArrayList();
int min = s.length() +1;
for(int i =0 ;i < s.length(); i++){
for(Integer x: indexList){
... 阅读全帖 |
|
p*********g
发帖数: 911 | 29 不错。看明白了。
我也贴一下，求各位大牛给给意见。如果没问题, credits归IFloating和bunnih。
public static String shortestString(String s, String p){
String result = null;
if (s== null || p == null || p.length() >s.length()) return null;
if (s.length() ==0 || p.length() ==0) return "";
Map indexMap = new HashMap();
int min = s.length() +1;
for(int i =0 ;i < s.length(); i++){
for(Entry ent: indexMap.entrySet()){
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 30
这个行吗？
Node dfs(String str, int s, int e){
int i = s;
while(i
i++;
if(i==e){
return new Node(str.substring(s, e+1));
}
int j=i+1;
int count=0;
while(j
if(str.charAt(j) == '?')
count++;
if(str.charAt(j) == ':')
count--;
j++;
}
Node node = new Node(str.subs... 阅读全帖 |
|
p*****2
发帖数: 21240 | 31
这个行吗？
Node dfs(String str, int s, int e){
int i = s;
while(i
i++;
if(i==e){
return new Node(str.substring(s, e+1));
}
int j=i+1;
int count=0;
while(j
if(str.charAt(j) == '?')
count++;
if(str.charAt(j) == ':')
count--;
j++;
}
Node node = new Node(str.subs... 阅读全帖 |
|
t**r
发帖数: 3428 | 32 public class T10 {
static boolean matchFirst(String s, String p){
System.out.println("in matchFirst: s is "+s+",p is: "+p+";");
System.out.println("s is empty "+ s.isEmpty());
System.out.println("p is empty "+ p.isEmpty());
if(s.isEmpty() ^ p.isEmpty()) return false;
if(s.isEmpty() && p.isEmpty()) return true;
return ( s.charAt(0)==p.charAt(0) || p.charAt(0)=='.' );
}
public static boolean isMatch(String s, String p) {
if (p.i... 阅读全帖 |
|
q*****1
发帖数: 160 | 33 用java写的DP版本的解法，总是超时。改了很多天还是不行，有谁能帮我看下啊？或者
给我一个能通过的DP的O(N2)版本学习一下，（我知道有O(n)的算法）谢谢大家了！
public class Solution {
public String longestPalindrome(String s) {
int n = s.length();
int longestBegin = 0;
int maxLen = 1;
int table[][] = new int[1000][1000];
for (int i = 0; i < n; i++) {
table[i][i] = 1;
}
for (int i = 0; i < n-1; i++) {
if (s.charAt(i) == s.charAt(i+1)) {
table[i][i+1] = 1;
longestBegin = i;
maxLen = 2;
}
}
for (int len = 3; len ... 阅读全帖 |
|
b**********5
发帖数: 7881 | 34 是不是这个？
public boolean isPalindrome(String s) {
int n = s.length();
int i=0; int j = n-1;
while (i <= j) {
while (i < j && !Character.isLetterOrDigit(s.charAt(i)))
i++;
while (i < j && !Character.isLetterOrDigit(s.charAt(j)))
j--;
if (i <= j && Character.toLowerCase(s.charAt(i)) == Character.
toLowerCase(s.charAt(j)))
i++; j--;
else
return false;
}
return true;
} |
|
S*******C
发帖数: 822 | 35 这题用递归即使只传下标也不能通过长String的oj
有没有什么改进方法
我这种写法应该是O(N) time, O(N) space的吧
Runtime Error Message: Line 12: java.lang.StackOverflowError
public boolean isPalindrome(String s) {
if (s == null || s.length() < 2)
return true;
if(!rec(s, 0, s.length() - 1))
return false;
return true;
}
private boolean rec(String s, int start, int end){
if(start >= end)
return true;
if (!Character.isLetterOrDigit(s.charAt(start)))
... 阅读全帖 |
|
S*******C
发帖数: 822 | 36 你的答案质量稍稍有待提高，FB对答案质量要求很高的。
我给你看个最优解
public boolean isPalindrome2(String s) {
if (s == null || s.length() < 2)
return true;
int start = 0, end = s.length() - 1;
while (start < end) {
while (start < end && !Character.isLetterOrDigit(s.charAt(start)
))
start++;
while (start < end && !Character.isLetterOrDigit(s.charAt(end)))
end--;
if (Character.toLowerCase(s.charAt(start++)) != Character.
to... 阅读全帖 |
|
S*******C
发帖数: 822 | 37 这个答案是对的，也能通过OJ
但改成JAVA版就是不能过大的test case
public boolean isPalindrome(String s) {
if (s == null || s.length() < 2)
return true;
return rec(s, 0, s.length() - 1);
}
private boolean rec(String s, int start, int end){
if(start >= end)
return true;
while (start < end && !Character.isLetterOrDigit(s.charAt(start)))
start++;
while (start < end && !Character.isLetterOrDigit(s.charAt(end)))
end--;
r... 阅读全帖 |
|
b**********5
发帖数: 7881 | 38 kmp 没几行字吧。。。
int strstr(String haystack, String needle) {
int hLen = hayStack.length();
int nLen = needle.length();
int i = 0; int j = 0;
int[] next = new int[nLen];
preProcess(needle, next);
while (i < hLen && j < nLen) {
if (haystack.charAt(i) == needle.charAt(j)) { i++; j++;}
else {
j = next[j];
}
}
if (j == nLen) return i-j;
else return -1;
}
void preProcess(String needle, int[] next) {
next[0] = -1;
int k = -1... 阅读全帖 |
|
f**********e
发帖数: 288 | 39 题目现场做，会很有压力。 楼主拍拍。
public static String getStep(String movieName){
int curCol = 0, curRow = 0;
StringBuffer buffer = new StringBuffer();
for(int i = 0; i < movieName.length(); i++){
if(i > 0 && movieName.charAt(i-1) == movieName.charAt(i)){
buffer.append("!");
} else {
int nextRow = (movieName.charAt(i) - 'a') / 5, nextCol = (
movieName.charAt(i) - 'a') % 5;
// moving col
String moving... 阅读全帖 |
|
f*********l
发帖数: 46 | 40 写了一个用list的版本
public static String reverse(String s) {
List list = new ArrayList();
boolean word = Character.isLetter(s.charAt(0));
int i = 0, n = s.length(), start = 0;
while(i < n) {
char cur = s.charAt(i);
while(i < n && ((word&&Character.isLetter(cur)) || (!word&&
Character.isLetter(cur)))) {
++i;
}
list.add(s.substring(start, i));
start = i;
word = !word... 阅读全帖 |
|
J*********a
发帖数: 50 | 41 来献上本侠在此版第一道题：
public static int start = 0;
public static TreeNode deTree2(String s) {
//(A(B(C)(D))(E)(F))
while (s.charAt(start) == '(') start++;
TreeNode res = new TreeNode(s.charAt(start));
start++;
if (s.charAt(start) == ')') {
start++;
return res;
}
List list = new ArrayList<>();
while (s.charAt(start) == '(') {
list.add(deTree2(s));
}
res.children = list;
st... 阅读全帖 |
|
j********r
发帖数: 127 | 42 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
Map> allSubSet = new HashMap();
Set getAllPalidrome(String s, int x, int y){
int ind = x * s.length() + y;
if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
Set ret = new HashSet();
if (s == null || s.size() == 0) { ret.add(""); return ret;}
if (s.size() == 1) { ret.add(s); return ret;}
for(int i = x; i <= y; i++){
for (int j = y; j >= i; j--){
... 阅读全帖 |
|
j********r
发帖数: 127 | 43 给一个string, 可以删除任意字符，求所有可以得到的palidrome字串集
我就想了个递归, 还是没有区分掉一些重复的情况，worst case O(2^n)基本同暴力解
Map> allSubSet = new HashMap();
Set getAllPalidrome(String s, int x, int y){
int ind = x * s.length() + y;
if(allSubSet.constainsKey(ind)) return allSubSet.get(ind);
Set ret = new HashSet();
if (s == null || s.size() == 0) { ret.add(""); return ret;}
if (s.size() == 1) { ret.add(s); return ret;}
for(int i = x; i <= y; i++){
for (int j = y; j >= i; j--){
... 阅读全帖 |
|
发帖数: 1 | 44 题目如下：
String s1 = "
waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";
s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也
就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺
序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有
四个。
----------------------------------------------------------------------
这里有解答，但是测试后发现不对（http://www.1point3acres.com/bbs/thread-145290-1-1.html）
结果测试sln.findMatches("aaaaaa", "a+a-") ，出来结果为0，不对
另外System.out.println(sln.fin... 阅读全帖 |
|
h**********I
发帖数: 51 | 45 这是我的DP解法，测试过的:
private String getToken(char c, char op) {
String s = c + "" + c;
if (op == '+')
return s;
return s + s;
}
private boolean match(String s1, int s1EndIndex, String token) {
for (int i = token.length() - 1; i >= 0; i--, s1EndIndex--) {
if (s1EndIndex < 0)
return false;
if (s1.charAt(s1EndIndex) != token.charAt(i))
return false;
}
return true;
}
public int findMatches(String s1, String s2) {
int s1Len = s1.lengt... 阅读全帖 |
|
s******7
发帖数: 1758 | 46 是很简单， 不过你这个还漏了检查相邻字符相等的情况 charAt(i-1)==charAt(i) ||
charAt(i-1)==charAt(i+1) 一个循环即可 |
|
a**********0
发帖数: 422 | 47 第22题不知道是不是有个小bug
//calculate KMP array
public int[] getNext(String needle) {
int[] next = new int[needle.length()];
next[0] = 0;
for (int i = 1; i < needle.length(); i++) {
int index = next[i - 1];
while (index > 0 && needle.charAt(index) != needle.charAt(i)) {
index = next[index - 1];
}
if (needle.charAt(index) == needle.charAt(i)) {
next[i] = next[i - 1] + 1;
} else {
next[i] = 0;
}
}
return next;
}
其中
next[i] = next[i - 1] + 1;
应该改为
next[i] = next[index - 1] + 1;
谢谢 |
|
g**e
发帖数: 6127 | 48 O(n) time, O(1) space based on KMP. Here I used an utility ArrayList but it
can be removed to do in-place.
public static void recursiveDelete(String target, String pattern) {
if (target == null || pattern == null || pattern.length() ==
0
|| target.length() == 0)
return;
// convert target string into a ArrayList of char
ArrayList charset = new ArrayList();
... 阅读全帖 |
|
i*******n
发帖数: 114 | 49 你能否把这段code做成可编译的C++或java代码，运行一下就知道对不对了。
我做了一个Java的。
结果是
“pylhtesy aatsfoe psaatn ifsyo”
和要求的
“pylhssrtnaatareyeopsfefasmeietawodny”
从第五位字符开始就不对。
但是按照题目的第一行pattern的话，第五位应该是t啊。
1 3 6 10 15 21 ....
public static String parseEncodedString(String inputString){
int numOfRows = 4;
String trimmedInputString = inputString.trim();
trimmedInputString = trimmedInputString.replace(" ", "");
trimmedInputString = trimmedInputString.replace(".", "");
tri... 阅读全帖 |
|
w**z
发帖数: 8232 | 50 我再贴一下Java的sourcecode。不懂为什么要把正数转成负数再查溢出呢？有什么好处？
code里有Author的comments
// Accumulating negatively avoids surprises near MAX_VALUE
/**
* Parses the string argument as a signed integer in the radix
* specified by the second argument. The characters in the string
* must all be digits of the specified radix (as determined by
* whether {@link java.lang.Character#digit(char, int)} returns a
* nonnegative value), except that the first character may be an
* ASCII minus sig... 阅读全帖 |
|
