Group Anagrams
Given an array of strings, group anagrams together.
For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:
[
[“ate”, “eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
Note:
For the return value, each inner list’s elements must follow the lexicographic order.
All inputs will be in lower-case.
思路:先将各个单词排序,排序后的字符串相同的单词即是anagrams。
具体实现需要用到容器HashMap
e.g. (“abc”, [“abc”, “acb”, “bac”])
- 遍历string数组,得到当前单词的顺序字符串,然后在HashMap中查找。
- 若HashMap中已存在该key,则将该单词插入到对应的list中。
- 若不存在,则新插入键值对。
最后将Map中的list放入需要返回的表中。
注意,因为题中要求list中的元素是有序的,所以要在最开始的时候将单词数组排序,以保证插入的顺序。 对容器的使用还不是很熟练啊~而且没有IDE,库函数好难记啊~
1 | public List<List<String>> groupAnagrams(String[] strs) { |
Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = “aabcc”,
s2 = “dbbca”,
When s3 = “aadbbcbcac”, return true.
When s3 = “aadbbbaccc”, return false.
要用到’dynamic programing’的思想。
若s1的前i个与s2的前j个对于s3的前(i+j)个来说是合法的(即这部分的s1和s2可以插入得到s3),则可继续对s3的(i+j+1)个进行判断。
- 最开始初始化i=0和j=0的情况为合法。
- i=0即s1为空,只判断s2。
- j=0即s2为空,只判断s1。
- 都不为空,则s1或s2有一个合法即可。
- 最后返回s1s2都插入后的结果。
1 | public boolean isInterleave(String s1, String s2, String s3) { |
Integer to English Words
Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
For example,
123 -> “One Hundred Twenty Three”
12345 -> “Twelve Thousand Three Hundred Forty Five”
1234567 -> “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”
大致分为(以前没注意,现在才发现歪果仁写数字总三个数隔一个逗号的用意。):
"123" -> "One Hundred Twenty Three"
"123,000" -> "One Hundred Twenty Three Thousand"
"123,000,000" -> "One Hundred Twenty Three Million"
"123,000,000,000" -> "One Hundred Twenty Three Billion"
可以每三个数字转换,然后相应加上Thousand, Million, Billion。
注意要考虑一些特殊情况,比如’0’和’1000中的0’,’11’和’21’等。
考虑空格真是太麻烦了!
1 | public final String[] digit = new String[] {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"}; |
吐槽:感觉关于字符串处理,很多是考的归纳能力,然后就着wrong answer打补丁。
这两天刷的有点乱,希望明天能有条理一点。