For example, Given s = “the sky is blue“, return “blue is sky the“. 翻转一个string, 但是里面单词不翻转. 三步: 翻转整个string 用left记录每个单词开始的地方, 然后扫到空格就翻转一下. 最后记得翻转一下最后的string public void reverseWords(char[] s) { reverse(s,0,s.length-1); int left = 0; for(int i = 0 ; i < s.length; i++) { if(s[i] == ‘ ‘){ reverse(s, left, i-1); left = i+1; } } reverse(s, left, […]

给一个2d的grid, 上边有1也有0. 让你找一个点使得所有点到这点的Manhattan Distance 的合为最小. 这题考点很多: 首先,Manhattan Distance 的合为 sum(distance(p1, p2)) = sum(|p2.x – p1.x| + |p2.y – p1.y|)= sum(|p2.x – p1.x|)+sum(|p2.y – p1.y|). 也就是说, 可以分别计算x和y的合, 然后加起来. 其次, 我们需要把2d的grid变成1d, 这里的窍门是, 我们可以证明, 所求的点, 就在其中某点的x或者y的坐标轴上. 所以, 而这点, 必然是1d下的median. http://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations Suppose we have a set S of real numbers that ∑s∈S|s−x|is minimal if x is equal to themedian. 所以, 我们需要count一下x轴上有多少个1的投影, 和y轴上有多少个1的投影. […]

给一个binary tree, 问你怎么找其中最长的连续递增的path. 1 \ 3 / \ 2 4 \ 5 这个返回3. 解法很简单, 和找数组最大连续递增的子序列一样. private int result = Integer.MIN_VALUE; public int longestConsecutive(TreeNode root) { if(root == null) return 0; dfs(root, 0, root); return result; } private void dfs(TreeNode root, int cur, TreeNode pre) { if(root == null) return; if(root.val == pre.val+1) cur++; else cur […]

给一个string, 问你,它的字符随便排序是否能组成一个回文? 能成为回文的话,需要有偶数个字符, 但是其中某个可以是奇数. 偶数比如 ababcc -> abccba 奇数比如 ababccd -> abcdbca 所以就做个count[]数组, 数一下其中的每个字符个数, 然后设置一个counter, 记得是否有奇数个. public boolean canPermutePalindrome(String s) { int[] A = new int[256]; int count=0; for(int i=0; i<s.length(); i++){ if(A[s.charAt(i)]>0) { A[s.charAt(i)]–; count–; } else { A[s.charAt(i)]++; count++; } } return count<=1; }  

尼姆博奕, 给一个堆, 能拿无数个, 玩家先拿, 谁没的拿了就算输. 这个不是普通的尼姆博弈,  因为最大能拿3个, 所以答案就是只需要判断堆中的元素个数是不是能整除4就, 如果能, 就是玩家输, 如果不能, 就有可能赢. public boolean canWinNim(int n) { return n%4 != 0; }  

给一个pattern和一个string, 问string是否满足pattern. 这次string里面的word没有空格. 所以我们要backtracking所有的可能的string的组合, 对于每个组合, 我们都需要添加到hashmap中, 这里, 我们在遍历pattern和string时, 要同时记录pattern中每个char对应在pattern的位置和当前string中substring对应的pattern的位置. 通过string和pattern在pattern中的位置i来判断是否相同. 为了区分pattern和string, 我们可以同两个hashmap, 也可以用一个, 用一个的时候, 注意要用 HashMap<Object,Integer> map 因为pattern存的是<char,integer>,而string存的是<string,integer>, 所以用一个hashmap可以通过比较类型来区别key是pattern或string. 其实是这题和word pattern都是isomorphic问题. public boolean wordPatternMatch(String pattern, String str) { HashMap map = new HashMap(); return dfs(pattern, 0, str, 0, map); } private boolean dfs(String pattern, int i, String str, int j, HashMap map){ if(i == pattern.length() […]

给一个pattern和一个string, 问这个string是否满足这个pattern. 用一个hashmap, 存pattern的每个char和string每个单词, 然后遍历pattern. 如果出现以下两种情况, 则不满足: map中包含这个pattern,但是对应的value不是string的word, 说明已存在其他的mapping. map中不包含这个pattern,但是里面已经有了这个string的word,说明已存在其他的mapping. 其他的返回true. public boolean wordPattern(String pattern, String str) { if (pattern == null || str == null) { return false; } char[] patterns = pattern.toCharArray(); String[] strs = str.split(” “); if (patterns.length != strs.length) { return false; } Map<Character, String> map = new HashMap<Character, String>(); for […]

给一个string s, 包含’+’和’-‘, 给一个操作, 可以翻转++变成–, 两个人比赛, 看谁先不能翻转, 对方就赢了. 问你哪种setting可以保证先手的人必胜. 这个backtracking很好想, 就是假设call这个function的人是先手, 然后尝试所有的翻转, 如果不能翻就说明先手的人不能保证必胜. public boolean canWin(String s) { for (int i = 0; i < s.length() – 1; ++i) if (s.charAt(i) == ‘+’ && s.charAt(i + 1) == ‘+’ && !canWin(s.substring(0, i) + “–” + s.substring(i + 2))) return true; return false; } 这个是O(2^n)的解法 然后看到评论中有一个dp解法. […]

给一个string s, 问翻转其中两个连续的+号, 能有几种翻法? public List<String> generatePossibleNextMoves(String s) { List<String> res = new ArrayList<String>(); for (int i = 0; i < s.length() – 1; i++) { if (s.charAt(i) == ‘+’ && s.charAt(i + 1) == ‘+’) { res.add(s.substring(0, i) + “–” + s.substring(i + 2, s.length())); } } return res; }  

今天刚看到一个好玩的题. 给n个数,其中有两个数字出现过一次, 另外数字都出现过两次. 找出这两个数.要求time: O(n), space: O(1). 思路是这样的: 首先用一个变量diff, 对每个数做xor, 这样得到的diff里面只有这两个数字中bit不同的位代表的数字,diff是一定不为0的, 因为这两个数不同, 不然所有数都出现两次了, 其他的数字因为出现两次, 都被xor删除了, 剩下的两个数字的不同位的代表的数. diff虽然表示了两个数中不同位, 但是它不能用来直接计算, 因为如果用它判断这两个数, 不能确保判断出两个数的位是留下的位. 所以这里我们要取diff中的最右边的为1的位. 这里用的方法是: int rightBit = diff & -diff; 因为java中负数用的是two complement, 所以以上的公式可以返回diff中最右边的为1的位代表的数字. 比如: 这个1的意义是, 我们需要找的两个数可以通过这个1来区别. 所以我们通过这个1,可以把数组分成两组, 每组都包含一个我们要找的数, 因为其他数都是出现两次, 所以留下的就是最后我们要找的答案 Code: public class Solution { public int[] singleNumber(int[] nums) { if (nums.length == 0 || nums == […]