国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LeetCode] Palindrome Pairs

DangoSky / 2257人閱讀

摘要:和的區別是,所以對于,效率更高不允許作為鍵值,而允許一個鍵和無限個值有一個,叫,便于查詢可預測的迭代順序。這道題依然選擇的話

Problem

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:

</>復制代碼

  1. Given words = ["bat", "tab", "cat"]
  2. Return [[0, 1], [1, 0]]
  3. The palindromes are ["battab", "tabbat"]

Example 2:

</>復制代碼

  1. Given words = ["abcd", "dcba", "lls", "s", "sssll"]
  2. Return [[0, 1], [1, 0], [3, 2], [2, 4]]
  3. The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
Note

HashMap和HashTable的區別:

HashTable是synchronized,所以對于non-threaded applications,HashMap效率更高;
HashTable不允許null作為鍵值,而HashMap允許一個null鍵和無限個null值;
HashMap有一個subclass,叫LinkedHashMap,便于查詢可預測的迭代順序。

為什么Trie比HashMap效率更高

Trie可以在O(L)(L為word.length)的時間復雜度下進行插入和查詢操作;
HashMap和HashTable只能找到完全匹配的詞組,而Trie可以找到有相同前綴的、有不同字符的、有缺失字符的詞組。

這道題依然選擇HashMap的話

1. map.getOrDefault(str, i)
Method Syntax

</>復制代碼

  1. public V getOrDefault(Object key,V defaultValue)
Method Argument
Data Type Parameter Description
Object Key key the key whose associated value is to be returned
V defaultValue the default mapping of the key
Method Returns

The getOrDefault() method returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.

2. Arrays.asList(i, j)
Method Syntax

</>復制代碼

  1. @SafeVarargs
  2. public static List asList(T… a)
Method Argument
Data Type Parameter Description
T a T – the class of the objects in the array
a – the array by which the list will be backed
Method Returns

The asList() method returns a list view of the specified array.

Solution Using Trie

</>復制代碼

  1. public class Solution {
  2. class TrieNode {
  3. TrieNode[] next;
  4. int index;
  5. List list;
  6. TrieNode() {
  7. next = new TrieNode[26];
  8. index = -1;
  9. list = new ArrayList<>();
  10. }
  11. }
  12. public List> palindromePairs(String[] words) {
  13. List> res = new ArrayList<>();
  14. TrieNode root = new TrieNode();
  15. for (int i = 0; i < words.length; i++) addWord(root, words[i], i);
  16. for (int i = 0; i < words.length; i++) search(words, i, root, res);
  17. return res;
  18. }
  19. private void addWord(TrieNode root, String word, int index) {
  20. for (int i = word.length() - 1; i >= 0; i--) {
  21. if (root.next[word.charAt(i) - "a"] == null) root.next[word.charAt(i) - "a"] = new TrieNode();
  22. if (isPalindrome(word, 0, i)) root.list.add(index);
  23. root = root.next[word.charAt(i) - "a"];
  24. }
  25. root.list.add(index);
  26. root.index = index;
  27. }
  28. private void search(String[] words, int i, TrieNode root, List> list) {
  29. for (int j = 0; j < words[i].length(); j++) {
  30. if (root.index >= 0 && root.index != i && isPalindrome(words[i], j, words[i].length() - 1)) list.add(Arrays.asList(i, root.index));
  31. root = root.next[words[i].charAt(j) - "a"];
  32. if (root == null) return;
  33. }
  34. for (int j : root.list) {
  35. if (i == j) continue;
  36. list.add(Arrays.asList(i, j));
  37. }
  38. }
  39. private boolean isPalindrome(String word, int i, int j) {
  40. while (i < j) {
  41. if (word.charAt(i++) != word.charAt(j--)) return false;
  42. }
  43. return true;
  44. }
  45. }
HashMap method

</>復制代碼

  1. public class Solution {
  2. public List> palindromePairs(String[] words) {
  3. List> ret = new ArrayList<>();
  4. if (words == null || words.length < 2) return ret;
  5. Map map = new HashMap<>();
  6. for (int i=0; i

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/66011.html

相關文章

  • LeetCode 336. Palindrome Pairs

    摘要:描述給定一組唯一的單詞,找出所有不同的索引對,使得列表中的兩個單詞,,可拼接成回文串。遍歷每一個單詞,對每一個單詞進行切片,組成和。 Description Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenatio...

    TigerChain 評論0 收藏0
  • [LeetCode] 336. Palindrome Pairs

    Problem Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome. Example 1: Inpu...

    lentoo 評論0 收藏0
  • Palindrome Pairs & Shortest Palindrome

    摘要:部分是回文的,在里面找是否有的。這里的范圍是,最小是,因為要保證是兩個單詞,最大是,這時候要找出另一個和他相反的串。判斷為回文,可以直接暴力,每個都判斷一次。兩個方向都找一遍就可能出現重復的情況,注意避免重復。例如,結果應該是。 Palindrome Pairs 鏈接:https://leetcode.com/problems... 這道題沒想出來思路,參考了這個博客的內容:http:...

    CNZPH 評論0 收藏0
  • 336. Palindrome Pairs

    摘要:容易出的兩個地方以為例。這兩個互為的在尾部加上也就是在頭部加上所以后部分不能為空,否則就和頭部為空的情況重復了??臻g復雜度因為用了額外的來儲存,需要空間。時間復雜度每個分為兩個部分,調用前后兩部分總長度為所以每次調用為一共次。 Given a list of unique words, find all pairs of distinct indices (i, j) in the g...

    Guakin_Huang 評論0 收藏0
  • leetcode 部分解答索引(持續更新~)

    摘要:前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的??赡艽蠹铱粗卜浅2环奖恪K栽谶@里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫~現在翻起來覺得蠻亂的??赡艽蠹铱粗卜浅2环奖?。所以在這里做個索引嘻嘻。 順序整理 1~50 1...

    leo108 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<