刷题记录

Analysis : Leetcode上面90个赞，785个踩，和String to integer是难兄难弟。考到的几率很小。 Solution: class Solution { public boolean isNumber(String s) { int i = 0, n = s.length(); boolean isNumber = false; // start space while (i

无聊的题目，leetcode上177赞，1808踩。代码如吓： 反正记住result一开始用double就好了。 public class Solution { public int myAtoi(String str) { if( str.length() < 1|| str==null) return 0; str=str.trim(); char flag='+'; int i=0; double result=0; if(str.charAt(0)=='-') { flag='-'; i++; }else if(str.charAt(0)=='+') { i++; } while(str.length()>i&&str.charAt(i)>='0'&&str.charAt(i)<='9') { result=result*10+(str.charAt(i)-'0'); i++; } if(flag=='-') result=-result; // handle max and min if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE; if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE; return (int) result; } }

Problem: Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing spaces and the words are always separated by a single space. For example, Given s = " the sky is blue ", return " blue is sky the ". Could you do it  in-place  without allocating extra space? Analysis: Similar to rotate array, if a word is detected, reverse the word. Then reverse the whole string.  Solution: class Solution { public void reverseWords(char[] str) { if (str == null || str.length == 0) { return; } int start = 0; for (int end = 0; end < str.length; end++) { if (end == str.length - 1 || str[end+1] == ' ') { reverse(start, end, str); start = end + 2; } } reverse(0, str.length - 1, str); } private void reverse(int start, int end, char[] str) { ...

Analysis: A straight forward approach is to do with two-pass, first pass extract all the words, store in either array or stack. Second pass output. The one pass solution uses two pointers to keep track of the start of the word and end of the word by reserve scanning.   Since substring will be used, need to check s.charAt(start - 1), then we can use s.substring(start, end) to extract word. Solution: public class Solution { public String reverseWords(String s) { StringBuilder sb = new StringBuilder(); int end = s.length(); for (int start = s.length() - 1; start >= 0; start--) { if (s.charAt(start) == ' ') { end = start; } else if ( start == 0 || s.charAt(start - 1) == ' ') { if (sb.length() != 0) { sb.append(' '); } sb.append(s.substring(start, end)); } } return sb.toString(); } }

11/30/2017 update 这道题看似简单，但是能写出bug free还有有难度的。 My implementation: ------------------------- class Solution { public int strStr(String haystack, String needle) { if (needle.isEmpty()) return 0; for (int i = 0; i <= haystack.length() - needle.length(); i++) { if (haystack.charAt(i) == needle.charAt(0)) { int temp = i; int j = 1; for (j = 1; j < needle.length(); j++) { if (haystack.charAt(++temp) != needle.charAt(j)) { break; } } if (j == needle.length() ) return i; } } return -1; } } Leetcode clean code hand book has a very genius implementation, I won't be able to reach that level. So skip it. 思路： 太简单了没啥好说的。 实现： corner case不太容易想到，如果对string不熟的话。比如s=“ewffwe”, target=""。这个情况就要返回0。一开始检查corner case代码为： if(source==null||target==null) return -1; if(target.length()==0) return 0;