Menu Sidebar
Menu

Leetcode

Reverse Words in a String II

For example, Given s = “the sky is blue“, return “blue is sky the“. 翻转一个string, 但是里面单词不翻转. 三步: 翻转整个string 用left记录每个单词开始的地方, 然后扫到空格就翻转一下. 最后记得翻转一下最后的string

 

Best Meeting Point

给一个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

所以, 我们需要count一下x轴上有多少个1的投影, 和y轴上有多少个1的投影. 就可以找到这个median. 这里我们不需要sorting, 因为投影本身就是已排序的. 最后, 我们得到一个1d的array, 我们需要计算以上公式,即各点到median的值的合, 这里需要用two pointers, 因为array本身已经是排序过后的了, 所以我们只需要求两头的元素的差值的合, 就是他们到median的合. 6是median,那么 (6-2)+(6-4) + (6-5) + (7-6) […]

Binary Tree Longest Consecutive Sequence

给一个binary tree, 问你怎么找其中最长的连续递增的path.

这个返回3. 解法很简单, 和找数组最大连续递增的子序列一样.

 

Palindrome Permutation

给一个string, 问你,它的字符随便排序是否能组成一个回文? 能成为回文的话,需要有偶数个字符, 但是其中某个可以是奇数. 偶数比如 ababcc -> abccba 奇数比如 ababccd -> abcdbca 所以就做个count[]数组, 数一下其中的每个字符个数, 然后设置一个counter, 记得是否有奇数个.

 

Nim Game

尼姆博奕, 给一个堆, 能拿无数个, 玩家先拿, 谁没的拿了就算输. 这个不是普通的尼姆博弈,  因为最大能拿3个, 所以答案就是只需要判断堆中的元素个数是不是能整除4就, 如果能, 就是玩家输, 如果不能, 就有可能赢.

 

Word Pattern II

给一个pattern和一个string, 问string是否满足pattern. 这次string里面的word没有空格. 所以我们要backtracking所有的可能的string的组合, 对于每个组合, 我们都需要添加到hashmap中, 这里, 我们在遍历pattern和string时, 要同时记录pattern中每个char对应在pattern的位置和当前string中substring对应的pattern的位置. 通过string和pattern在pattern中的位置i来判断是否相同. 为了区分pattern和string, 我们可以同两个hashmap, 也可以用一个, 用一个的时候, 注意要用

因为pattern存的是<char,integer>,而string存的是<string,integer>, 所以用一个hashmap可以通过比较类型来区别key是pattern或string. 其实是这题和word pattern都是isomorphic问题.

 

Word Pattern

给一个pattern和一个string, 问这个string是否满足这个pattern. 用一个hashmap, 存pattern的每个char和string每个单词, 然后遍历pattern. 如果出现以下两种情况, 则不满足: map中包含这个pattern,但是对应的value不是string的word, 说明已存在其他的mapping. map中不包含这个pattern,但是里面已经有了这个string的word,说明已存在其他的mapping. 其他的返回true.

 

Flip Game II

给一个string s, 包含’+’和’-‘, 给一个操作, 可以翻转++变成–, 两个人比赛, 看谁先不能翻转, 对方就赢了. 问你哪种setting可以保证先手的人必胜. 这个backtracking很好想, 就是假设call这个function的人是先手, 然后尝试所有的翻转, 如果不能翻就说明先手的人不能保证必胜.

这个是O(2^n)的解法 然后看到评论中有一个dp解法. 感觉面试不会考这个..既然是面试题….就没看..

Flip Game

给一个string s, 问翻转其中两个连续的+号, 能有几种翻法?

 

Single Number III

今天刚看到一个好玩的题. 给n个数,其中有两个数字出现过一次, 另外数字都出现过两次. 找出这两个数.要求time: O(n), space: O(1). 思路是这样的: 首先用一个变量diff, 对每个数做xor, 这样得到的diff里面只有这两个数字中bit不同的位代表的数字,diff是一定不为0的, 因为这两个数不同, 不然所有数都出现两次了, 其他的数字因为出现两次, 都被xor删除了, 剩下的两个数字的不同位的代表的数. diff虽然表示了两个数中不同位, 但是它不能用来直接计算, 因为如果用它判断这两个数, 不能确保判断出两个数的位是留下的位. 所以这里我们要取diff中的最右边的为1的位. 这里用的方法是:

因为java中负数用的是two complement, 所以以上的公式可以返回diff中最右边的为1的位代表的数字. 比如: 这个1的意义是, 我们需要找的两个数可以通过这个1来区别. 所以我们通过这个1,可以把数组分成两组, 每组都包含一个我们要找的数, 因为其他数都是出现两次, 所以留下的就是最后我们要找的答案 Code:

 

Newer Posts
Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.