- 浏览: 130636 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
[分析]
在构造函数将各单词出现的所有位置保存在HashMap中,调用shortest()方法时,从HashMap中获取两单词的位置列表,两个列表是已排序的,因此可使用类似MergeSort的思路求解最短距离。
[ref]
https://leetcode.com/discuss/50190/java-solution-using-hashmap
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
[分析]
在构造函数将各单词出现的所有位置保存在HashMap中,调用shortest()方法时,从HashMap中获取两单词的位置列表,两个列表是已排序的,因此可使用类似MergeSort的思路求解最短距离。
[ref]
https://leetcode.com/discuss/50190/java-solution-using-hashmap
public class WordDistance { private HashMap<String, List<Integer>> indexer = new HashMap<String, List<Integer>>(); public WordDistance(String[] words) { if (words == null) return; for (int i = 0; i < words.length; i++) { if (indexer.containsKey(words[i])) { indexer.get(words[i]).add(i); } else { List<Integer> positions = new ArrayList<Integer>(); positions.add(i); indexer.put(words[i], positions); } } } public int shortest(String word1, String word2) { List<Integer> posList1 = indexer.get(word1); List<Integer> posList2 = indexer.get(word2); int i = 0, j = 0; int diff = Integer.MAX_VALUE; while (i < posList1.size() && j < posList2.size()) { int pos1 = posList1.get(i), pos2 = posList2.get(j); if (pos1 < pos2) { diff = Math.min(diff, pos2 - pos1); i++; } else { diff = Math.min(diff, pos1 - pos2); j++; } } return diff; } } // Your WordDistance object will be instantiated and called as such: // WordDistance wordDistance = new WordDistance(words); // wordDistance.shortest("word1", "word2"); // wordDistance.shortest("anotherWord1", "anotherWord2");
发表评论
-
Leetcode - H-Index
2015-09-06 09:08 1085Given an array of citations (ea ... -
Leetcode - LRU Cache
2015-09-03 18:31 504[分析] 自己使用HashMap + LinkedList/A ... -
Leetcode - Max Points on a Line
2015-08-23 15:30 671[分析] 两条直线若包含一个公共点且斜率相同,则为同一条直线。 ... -
Leetcode - Fraction to Recurring Decimal
2015-08-23 10:05 433[分析] 处理int型整数运算时,为避免溢出,省事的做法就是内 ... -
Leetcode - Isomorphic Strings
2015-08-23 09:51 511[分析] 思路1:维护两个哈希表,char[] map, bo ... -
Leetcode - Palindrome Permutation
2015-08-22 16:24 1151[分析] 思路2让我大开眼界,顺便学习下BitSet~ [re ... -
Leetcode - Group Shifted String
2015-08-22 16:20 1685Given a string, we can "sh ... -
Leetcode - Two Sum III - Data Structure Design
2015-08-21 10:30 658[分析] find的version1 版本注意num2Occu ... -
Leetcode - Add Binary
2015-08-21 09:28 434[分析] 从低位往高位逐位相加,就是这么一个简单的题却花了我一 ... -
Leetcode - Longest Consecutive Sequence
2015-08-20 21:20 454[分析] base version说几句: 数组题一定要考虑重 ... -
Leetcode - First Missing Positive
2015-08-20 07:45 607[分析] 将各个正数放入相应下标处,使之满足nums[nums ... -
Leetcode - Set Matrix Zeros
2015-08-19 20:55 515Given a m x n matrix, if an ele ... -
Leetcode - Rotate Image
2015-08-19 19:51 466[分析] 自己的思路:从外到内一圈圈顺时针旋转90度,坐标映射 ... -
Missing Ranges
2015-08-19 09:48 485[分析] 此题若不考虑极大值极小值相关的corner case ... -
Leetcode - 3Sum Smaller
2015-08-18 22:12 1448Given an array of n integers nu ... -
Leetcode - Spiral Matrix II
2015-08-18 19:49 464Given an integer n, generate a ... -
Leetcode - Spiral Matrix
2015-08-18 09:50 392Given a matrix of m x n element ... -
Leetcode - Contains Duplicate II
2015-08-18 07:57 528Given an array of integers and ... -
Leetcode - Shortest Word Distance III
2015-08-17 22:05 1628This is a follow up of Shortest ... -
Leetcode - Shortest Word Distance
2015-08-17 22:01 884Given a list of words and two w ...
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode 答案解析 golang解答
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
leetcode-helper-1.7.1
leetcode-tag-dynamic programming
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode-tag-Tree
leetcode-tag-Stack
leetcode-tag-array
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。