t******i
发帖数: 483 | 1 public static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i < n; i++) {
permutation(prefix + str.charAt(i), str.substring(0, i)
+ str.substring(i + 1, n));
}
}
} |
|
n******r
发帖数: 869 | 2
思路好像跟开始不大一样，不过试了abc例子好像work的
str.length最小为1吧？
该了2行
if (n == 0) 改成 if (n == 1)
permutation(prefix + str.charAt(i), str.substring(0, i)
+ str.substring(i + 1, n)); 中的str.substring(0, i)改成str.substring(0, i
-1)
不知对不对
以abc为例
permutation(null, abc)
--> P(a,bc),P(b,ac),P(c,ab)
-->P(a,P(b,c)),P(a,P(c,b)),P(b,P(a,c)),P(a,P(c,a)),P(c,P(a,b)),P(c,P(b,a)) |
|
e******i
发帖数: 106 | 3 昨天做了storm8 的online code，挂了。
题目变了，不再是以前说的find max sum path in one grid。
题目如下：
给定一个string,如 “codility”,每次向左循环一个char.
codility 0th;
odilityc 1st;
dilityco 2nd;
ilitycod 3rd;
....
codility 8th;
要求返回Unique 的string. 如上所示，应当返回 7.
然后又举例，“byebye”，应当返回二
任何string，包括空数组，应当最少返回1.
要求time complexity 和 space complexity 都为O(N).
我的code：
import java.util.HashMap;
public class Cyclic {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
... 阅读全帖 |
|
e******i
发帖数: 106 | 4 昨天做了storm8 的online code，挂了。
题目变了，不再是以前说的find max sum path in one grid。
题目如下：
给定一个string,如 “codility”,每次向左循环一个char.
codility 0th;
odilityc 1st;
dilityco 2nd;
ilitycod 3rd;
....
codility 8th;
要求返回Unique 的string. 如上所示，应当返回 7.
然后又举例，“byebye”，应当返回二
任何string，包括空数组，应当最少返回1.
要求time complexity 和 space complexity 都为O(N).
我的code：
import java.util.HashMap;
public class Cyclic {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
... 阅读全帖 |
|
e******i
发帖数: 106 | 5 这是在career cup 上看到的题：
Given a hashmap M which is a mapping of characters to arrays of substitute
characters, and an input string S, return an array of all possible mutations
of S (where any character in S can be substituted with one of its
substitutes in M, if it exists).
What is the time complexity? What is the space complexity? Can you optimize
either?
Example input:
M = { f: [F, 4], b: [B, 8] }
S = fab
Expected output:
[fab, Fab, 4ab, faB, FaB, 4aB, fa8, Fa8, 4a8]
这是我的解法，用backtrack... 阅读全帖 |
|
a*****a
发帖数: 46 | 6 题目是说用递归取代循环，如果是多种括号的话，即使递归也得用stack吧。虽然递归
自己就有stack，但是这里左右括号的处理不同，右括号的话需要pop，所以我觉得还是
得用stack。
用java写了一下，欢迎指正
private boolean isValidHelper(String s, int cur, Stack stack) {
if (cur == s.length()) return stack.isEmpty();
char c = s.charAt(cur);
switch (c) {
case '(':
case '[':
case '{':
stack.push(c);
break;
case ')':
if (stack.isEmpty() || stack.pop() != '(') return false;
break;
case ']':
if (stack.isEmpty() || stack.pop() ... 阅读全帖 |
|
u*l
发帖数: 1943 | 7 和走台阶那个题差不多吧。 DP
// Java
public static int count(String str) {
if(str == null || str.isEmpty())
return 0;
if(str.charAt(0) =='0') // 0 ?
return count(str.substring(1));
if(str.length() == 1)
return 1;
int firstStep = Integer.parseInt(str.substring(0,2));
if(firstStep > 26 ) {
return count(str.substring(2)); // cannot move 2 steps
} else {
return count(str.subst... 阅读全帖 |
|
z*******3
发帖数: 13709 | 8 五个步骤
0）预处理，把输入的string给trim一下，这个适用于任何string作为输入的问题
1）写出is unsigned integer的方法
2）写出is integer的方法，借用步骤1写好的方法，加一个判断是不是＋－号开头
3）写出is unsigned double的方法，借用步骤1写好的方法
这里有一个很特殊的corner case，就是.单独出现的情况，其实整个流程就这一个
corner case
4）写出is double的方法，借用步骤3写好的方法
5）然后valid number根据e做切割
e后面必需是integer，用步骤2的方法
e前面必需是double，用步骤4的方法
搞定
看起来很长，其实没啥东西，甚至没有脑筋急转弯的地方，就一个corner case记住就
好了
如果可以自由选择java类库的话，double.parseDouble(String)和integer.parseInt(
String)
加上try catch exception block，简简单单搞定一大串内容
废话说完咯，以下是代码
public class Solution ... 阅读全帖 |
|
|
g***s
发帖数: 30 | 10 The Python is super, but if you do not know it, try to refer java below:
public List BinaryOutput(String input) {
if (input == null || input.empty())
return null;
List output = new ArrayList();
List temp = new ArrayList("");
for (int i = 0; i < input.length(); i++) {
output.clear();
for (String s : temp) {
if (input.charAt(i) == '?') {
output.add(s + '0');
output.add(s + '1');
}
else {
outpu... 阅读全帖 |
|
x****8
发帖数: 127 | 11 private static void printCombinations(String string) {
List positions = new ArrayList();
List values = new ArrayList();
for(int i = 0; i < string.length(); ++i){
if(string.charAt(i) == '?'){
positions.add(i);
values.add(-1);
}
}
int pos = 0;
while(pos >= 0){
int val = values.get(pos) + 1;
if(val == 2){
values.set(p... 阅读全帖 |
|
z****e
发帖数: 54598 | 12 public class Solution {
public String countAndSay(int n) {
// Start typing your Java solution below
// DO NOT write main() function
String input = "1";
while(n>1){
input = this.cs(input);
n--;
}
return input;
}
private String cs(String cs){
String result = "";
int count = 0;
int current = -1;
for(int i=0;i
int c = Integer.parseInt(cs.charAt(i)+"");
... 阅读全帖 |
|
t*******2
发帖数: 182 | 13 也写了一个，思路和ls的大同小异吧
public class Solution {
public String countAndSay(int n) {
if(n < 1) {
return "";
}
String result = "1";
for(int i=1; i
result = translate(result);
}
return result;
}
public String translate (String n) {
StringBuilder sb = new StringBuilder("");
String temp = n;
int[] digits = new int[temp.length()];
... 阅读全帖 |
|
d*****d
发帖数: 180 | 14 第一个我得初步想法是先扫一遍T，把每个字母的位置记录下来，存到一个List array,
List [] x=List[26];
x[i]是个List, i是字母-'a'得到的0-25，List里是i代表的字母出现在T中的
所有坐标，扫描完应该是排好序的，从小到大。
然后依次在X查询Sj中每个字母，如果x[Sj-'a']存在，选最小的，但要大于前一次选的
位置，依次类推。。
for(s:S)
{
int start=-1;
boolean valid=true;
for(int j=0;j
{
int idx=s.charAt(i)-'a';
List list=x.get[idx];
if (list==null) {valid=false;break;}
int idx=getMin(list, start);
if (idx<0) {valid=false;break;}
start=idx;
}
}
---
int g... 阅读全帖 |
|
s*****b
发帖数: 8 | 15 我来贴一个。
Rocket fule (Software Engineer - Machine Learning Scientist ) 技术电面后code
test. code通过了所有test cases. 人家看过code 后就拒了。问题在哪里呢？请各位
牛人不吝赐教。题目本版以前贴过
You are standing in a rectangular room and are about to fire a laser toward
the east wall. Inside the room a certain number of prisms have been placed.
They will alter the direction of the laser beam if it hits them. There
are north-facing, east-facing, west-facing, and south-facing prisms. If the
laser beam strikes an east-facing prism, its cours... 阅读全帖 |
|
L*******r
发帖数: 119 | 16 how about the following?
int index = m-1-i;
int p = index>=0 ? a.charAt(index)-'0' : 0; |
|
l*********d
发帖数: 78 | 17 尝试过许多解法，但老是 TLE. 有高人能帮忙看一下这一段代码吗？
基本上就是 double queue + backtracking，跟这里的http://blog.csdn.net/niaokedaoren/article/details/8884938
很相似。但是问题出在哪里呢？
提前谢谢了！
------------------------------------------------------------------------
import java.util.Map;
public class Solution {
public void fillPaths(String start, String cur, Map>
map,
ArrayList> result, LinkedList post
) {
post.addFirst(cur);
if (start.equals(cur)) {
... 阅读全帖 |
|
g**********y
发帖数: 14569 | 18 以前写的代码：permute() 和 getRank()就是要求的function
public class PermuteK {
private int[] P;
public String permute(String input, int k) {
calculatePermuteNumber(input.length());
return find(input, k);
}
private void calculatePermuteNumber(int N) {
P = new int[N];
P[0] = 1;
for (int i=1; i
P[i] = P[i-1]*i;
}
}
private String find(String input, int k) {
int N = input.length();
if (N == 1) re... 阅读全帖 |
|
t*******7
发帖数: 63 | 19 感谢楼主分享，下礼拜电面，紧张ING。。。本人去年12月PHD毕业，专业方向DATA
MINING AND MACHINE LEARNING，搬到湾区找工作，OPT快开始了，目前还没着落，希望
能和一起在湾区找工作的同学多多交流互通信息。毕业前没时间准备现在着急了。。。
平常MATLAB写得多，JAVA最近才开始练习。。。
把电面的两个题写了一下，请拍
第一题
public boolean judgeCapital(String inputString) {
//
if ((inputString==null) || (inputString.length() == 0)) {
return false;
}
// get the first character
char firstChar = inputString.charAt(0);
//
i... 阅读全帖 |
|
c********6
发帖数: 33 | 20 static String reverseWords(String s)
{
if(s.length() == 0) return s;
s += " ";
StringBuilder temp = new StringBuilder();
Stack stack = new Stack();
for(int i = 0; i < s.length(); i++)
{
char c = s.charAt(i);
if(c == ' ')
{
if(temp.length() > 0) stack.push(temp.toString());
temp = new StringBuilder();
}
else temp.append(c);
}
... 阅读全帖 |
|
c********6
发帖数: 33 | 21 static String reverseWords(String s)
{
if(s.length() == 0) return s;
s += " ";
StringBuilder temp = new StringBuilder();
Stack stack = new Stack();
for(int i = 0; i < s.length(); i++)
{
char c = s.charAt(i);
if(c == ' ')
{
if(temp.length() > 0) stack.push(temp.toString());
temp = new StringBuilder();
}
else temp.append(c);
}
... 阅读全帖 |
|
g****s
发帖数: 1755 | 22 我来一个不用统计学的Draft吧，只需要知道所有可能组合就可以推出原String：
比如google的所有可能组合一共是13种：{gge,gle,ole,ogl,goe,oge,gog,ool,ggl,oog
, gol,ooe,goo}，把这些组合都放到一个ArrayList里，然后call dfsDecode()就可以
逆推了。
private static void dfsDecode(String head, ArrayList setList,
ArrayList prosStrList) {
// TODO Auto-generated method stub
if(head.length()==6){
prosStrList.add(head);
return;
}
for(int i=0; i
if(head==""){
... 阅读全帖 |
|
s******7
发帖数: 1758 | 23 brute force solution to compare each pair, complexity should be O(n^2*26)= O
(n^2), assumption all word are lower case.
public static int largestProduct(String[] s)
{
int[][] c=new int[s.length][26];
int max=1;
for (int i=0; i
{
for (int j=0; j
a']=1;
}
for (int i=0; i
{
j: for (int j=i+1; j
{
... 阅读全帖 |
|
l*****a
发帖数: 14598 | 24 我想这么做,你看咋样
List list=new ArrayList();
List result=new ArrayList();
for(int i=0;i
if(input.charAt(i)=='?') list.add(0);
}
while(true) {
String cur=genString(input,list);
result.add(cur);
// if all 1 in list, break;
for(int i=list.size()-1;i>=0;i--) {
if(list.get(i)==0) {
list.set(i)=1;
break;
} else {
list.set(i)=0;
}
}
}
return result; |
|
d**e
发帖数: 6098 | 25 你的code似乎有个bug: while(true)没有条件退出,进入死循环.
我觉得你flip bit的那段code有些问题,它并没有正确地flip, list.get(i)是?的index
,用它来跟0/1比较应该是不正确的.
我把它改成这样,用shift bit来做,不知有没有更好的方法.
public static List genMatchers(String str) {
List results = new ArrayList();
if (str != null && str.length() != 0) {
List questionMarkPositions = new ArrayList();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c... 阅读全帖 |
|
c**********y
发帖数: 38 | 26 小弟也是刚毕业在找工作刷题，学识浅薄，说的不对的请斧正。
1.不建议转换成chararray，因为你到后面还要转换回String，用stringbuilder可能会
更方便
2.这道题dfs里面不应该用for loop，虽然一样能出结果，但是compare非*字符的操作
在for里面会重复，会浪费很多时间，用for loop的时间复杂度是2^n,不用的是2^k,k
refers to number of * in string.
3.dfs在把字符分别设为0和1之后，要把字符还原成*，这是为什么大哥的结果里面没有
001100，因为在第二层设为1之后返回上一层，上一层在第二层原本是*的地方现在是1
了，于是结果只有00,01,11，若在第二层分别置0和1之后将该位置还原成*再返回上一
层，上一层再跑到这个位置的时候就会分出两个结果。
原代码里面只需要在dfs函数的for loop里面第二个dfs(sc, res, starCount);下面加
一句sc[i]='*'，代码应该就能出正确结果，这是小弟的代码，仅供参考：
public static ArrayList co... 阅读全帖 |
|
m*****n
发帖数: 204 | 27
The following is an O(nlgn) solution for string of size n.
It maintains a heap for eligible chars, preferring longer streams.
Ineligible chars are maintained in a candidate queue, and added back
to the working queue when their position constraint is removed.
public class MinDistance {
public String rearrange(String source, int distance) {
// TODO Check params.
// WorkingQueue of eligible streams. Longest stream at head,
// but BackupStream at tail.
PriorityQueue阅读全帖 |
|
S******2
发帖数: 248 | 28 和rtscts说的一样.
public static String removeDup(String str)
{
if(str == null || str.length() <= 1)
return str;
Stack stack = new Stack();
for(int i = 0; i < str.length(); i++)
{
char ch = str.charAt(i);
if(stack.isEmpty() || ch != stack.peek())
{
stack.push(ch);
}
else if(ch == stack.peek())
{
stack.pop();
}
... 阅读全帖 |
|
r****s
发帖数: 1025 | 29 稍微改一下，stack也可以做出来。
public static String removeDup(String str)
{
if(str == null || str.length() <= 1)
return str;
Stack stack = new Stack();
Character last = ' ';
for(int i = 0; i < str.length(); i++)
{
char ch = str.charAt(i);
if(ch!=last && (stack.isEmpty() || ch != stack.peek()))
{
stack.push(ch);
... 阅读全帖 |
|
y*******o
发帖数: 6632 | 30 这个不对，我搞定java了
class GetString{
static int seedIdx=0;
String getResult() {
String seedStr=Integer.toBinaryString(seedIdx++);
int dotCount=0;
for(int i=0;i
if(seedStr.charAt(i)=='1'){
result=result.substring(0, i+dotCount+1) + "." +
result.substring(i+dotCount+1, result.length());
++dotCount;
}
}
return result；
}
public static void main（String[] args){
while(seedIdx++<1000000){
getResult();
}
}
}
多谢大家 |
|
m*****k
发帖数: 731 | 31 public static void addDot(String input){
char[] dots = new char[input.length() - 1];
getDottedString(dots, 0, input);
}
private static void getDottedString(char[] dots, int i, String input) {
if(i==dots.length){
//merge dots with input and output
StringBuilder result = new StringBuilder();
for(int j=0; j
result.append(input.charAt(j));
if(j阅读全帖 |
|
P*******L
发帖数: 2637 | 32 MSDN 里 C# 的样例多得是
C# 最不幸的就是被贴上了 MS 的标签，结果这么一门好语言被埋没了
每次写 Java 写到 str.charAt() 这种我都想吐，C# 的语法多么优美多么高效啊…… |
|
b****z
发帖数: 176 | 33 代码如下：
基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
recover path。感觉没有任何冗余计算啊！！！为什么过不了？
谢谢各位！！
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> res = new ArrayList>();
Set visited = new HashSet();
... 阅读全帖 |
|
b****z
发帖数: 176 | 34 代码如下：
基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
recover path。感觉没有任何冗余计算啊！！！为什么过不了？
谢谢各位！！
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> res = new ArrayList>();
Set visited = new HashSet();
... 阅读全帖 |
|
m***2
发帖数: 595 | 35 贴块砖，感觉是我见到的最容易理解好记的版本了
而且能够过最新的test （好多解法之前能过，最新的容易Memory超，感觉leetcode的
判断更严格了）
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> result = new ArrayList>();
if (start == null || end == null || start.length() != end.length() |
| dict.size() == 0) {
return result;
}
HashMap> visited = new HashMap
HashSet>();
... 阅读全帖 |
|
T******g
发帖数: 790 | 36 实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据
结构。 (即只使用基本的数据结构)
public boolean isUniqueChars2(String str) {
int checker = 0;
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i) - 'a';
if ((checker & (1 << val)) > 0) {
return false;
} else {
checker |= (1 << val);
}
}
return true;
}
看不懂啊
|
|
x******0
发帖数: 1025 | 37 不行吧！
最多用charAt(), length(),其它都不能用啊 |
|
p*****p
发帖数: 379 | 38 public class Solution {
int[][] stateTrans = {
{1, 2, 3, -1, -1},
{1, -1, 4, 5, -1},
{1, -1, 3, -1, -1},
{4, -1, -1, -1, -1},
{4, -1, -1, 5, -1},
{7, 6, -1, -1, -1},
{7, -1, -1, -1, -1},
{7, -1, -1, -1, -1}
};
public... 阅读全帖 |
|
p*********j
发帖数: 47 | 39 输入一个字符串，返回所有字串，即"abc" -> {"a", "b", "c", "ab", "bc", "abc"}
。觉得写的好烂，大神们给提提意见，多谢！
public static ArrayList combinationsString(String s) {
ArrayList res = new ArrayList();
for (int i = 1; i <= s.length(); i++) {
dfs(s, 0, i, res);
}
return res;
}
private static void dfs(String s, int start, int resLength, ArrayList<
Character> res) {
if (resLength == 0) {
System.out.println(res.toString());
... 阅读全帖 |
|
z*********e
发帖数: 10149 | 40 现在会超时，哪个地方应该优化一下？用的BFS
本机上一秒之内就出结果了，应该没有严重的算法问题吧
public List> findLadders(String start, String end, Set
dict) {
List> lastPaths = new ArrayList<>();
if(start == null || end == null) return lastPaths;
dict.add(end);
List top = new ArrayList<>();
top.add(start);
lastPaths.add(top);
if(start.equals(end)) return lastPaths;
int wordLen = start.length();
while(!dict.isEmpty()){ // same as ... 阅读全帖 |
|
S*******C
发帖数: 822 | 41 第一种更简洁，但s.toCharArray()要占用O(N)的空间吧？
public int titleToNumber(String s) {
int res = 0;
for (char c: s.toCharArray())
res = res * 26 + (c - 'A' + 1);
return res;
}
第二种有点啰嗦，但不需要额外占用O(N)的空间，不过s本来就要占O(N)的空间啊
public int titleToNumber1(String s) {
int res = 0;
for (int i = 0; i < s.length(); i++)
res = res * 26 + (s.charAt(i) - 'A' + 1);
return res;
}
哪种更好？ |
|
c*****e
发帖数: 3226 | 42 public class Solution {
class Record {
Record prev;
String cur;
public Record(Record prev, String cur) {
this.prev = prev;
this.cur = cur;
}
}
public List> findLadders(String start, String end, Set<
String> dict) {
List> r = new LinkedList>();
if (start == null || end == null || dict == null || start.length() =
= 0 || start.length() != end.len... 阅读全帖 |
|
d******v
发帖数: 801 | 43 没看懂，不能改string，那Character.toLowerCase(s.charAt(i))也不行？ |
|
j**7
发帖数: 143 | 44 int smallestTime(String tasks, int coolDownTime) {
int time = 0;
// assume uppercase English letters
int[] lastSeen = new int[26];
for (int i = 0; i < 26; i++) {
lastSeen[i] = -1;
}
int index = 0;
for (int i = 0; i < tasks.length(); i++) {
int last = tasks.charAt(i) - 'A';
if (lastSeen[last] != -1) {
time += Math.max(0, coolDownTime - (index - lastSeen[last] +
1 - 2));
in... 阅读全帖 |
|
h***k
发帖数: 161 | 45 把二楼的c++版翻译了一下，能过但应该还能优化
public class Solution {
/**
*@param A: A positive integer which has N digits, A is a string.
*@param k: Remove k digits.
*@return: A string
*/
public String DeleteDigits(String A, int k) {
// write your code here
int len = A.length();
if (len == k) {
return "";
}
int idx = 0;
int[] num = new int[len];
for (int i = 0; i < len; i++) {
num[i] = A.charAt(i) - '0';
... 阅读全帖 |
|
h***k
发帖数: 161 | 46 把二楼的c++版翻译了一下，能过但应该还能优化
public class Solution {
/**
*@param A: A positive integer which has N digits, A is a string.
*@param k: Remove k digits.
*@return: A string
*/
public String DeleteDigits(String A, int k) {
// write your code here
int len = A.length();
if (len == k) {
return "";
}
int idx = 0;
int[] num = new int[len];
for (int i = 0; i < len; i++) {
num[i] = A.charAt(i) - '0';
... 阅读全帖 |
|
a*****2
发帖数: 96 | 47 这不是leetcode的原题吗？
public class Solution {
public List findRepeatedDnaSequences(String s) {
List result=new ArrayList();
HashMap computed=new HashMap();
for(int i=0;i<=s.length()-10;i++)
{
String sub=s.substring(i,i+10);
int key=getKey(sub);
if(computed.containsKey(key))
{
computed.put(key,computed.get(key)+1);
if(computed.get(key)==2)
result.add(sub... 阅读全帖 |
|
a*****2
发帖数: 96 | 48 这不是leetcode的原题吗？
public class Solution {
public List findRepeatedDnaSequences(String s) {
List result=new ArrayList();
HashMap computed=new HashMap();
for(int i=0;i<=s.length()-10;i++)
{
String sub=s.substring(i,i+10);
int key=getKey(sub);
if(computed.containsKey(key))
{
computed.put(key,computed.get(key)+1);
if(computed.get(key)==2)
result.add(sub... 阅读全帖 |
|
S***w
发帖数: 1014 | 49 String balance(String s) {
int start = 0, i = 0;
Stack stack = new Stack();
String cur = "", ret = "";
while (i < s.length()) {
if (s.charAt(i) == '(') {
stack.push(i);
i = i + 1;
}
else {
if (stack.isEmpty()) {
ret += cur;
i = i + 1;
start = i;
cur = "";
}
... 阅读全帖 |
|
h****3
发帖数: 89 | 50 public static String bestTime(String tasks, int cooldown){
if(tasks==null || tasks.length()==0 || cooldown<0){
throw new IllegalArgumentException("input not valid");
}
int waitTime = cooldown;
int curRep =0;
StringBuilder res = new StringBuilder();
Stack stack = new Stack();
HashMap map = new HashMap();
PriorityQueue pq = new PriorityQueue(11, new Comparator<... 阅读全帖 |
|
