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

資訊專欄INFORMATION COLUMN

Palindrome Pairs & Shortest Palindrome

CNZPH / 1005人閱讀

摘要:部分是回文的,在里面找是否有的。這里的范圍是,最小是,因?yàn)橐WC是兩個(gè)單詞,最大是,這時(shí)候要找出另一個(gè)和他相反的串。判斷為回文,可以直接暴力,每個(gè)都判斷一次。兩個(gè)方向都找一遍就可能出現(xiàn)重復(fù)的情況,注意避免重復(fù)。例如,結(jié)果應(yīng)該是。

Palindrome Pairs

鏈接:https://leetcode.com/problems...

這道題沒(méi)想出來(lái)思路,參考了這個(gè)博客的內(nèi)容:
http://bookshadow.com/weblog/...

把一個(gè)單詞分為兩個(gè)部分:left, right。right部分是回文的,在words里面找是否有reverse的left。這里的left范圍是(0, len(word)),最小是0,因?yàn)橐WC是兩個(gè)單詞,最大是len(word),這時(shí)候要找出另一個(gè)和他相反的串。根據(jù)題目的意思,一個(gè)單詞只能用一次,而且words里面單詞都是unqiue的。
現(xiàn)在的問(wèn)題就在于如果判斷right是否為回文,以及如何找到left的reverse串。判斷right為回文,可以直接暴力,每個(gè)right都判斷一次。找left可以用trie tree或者h(yuǎn)ashmap。可能出現(xiàn)ab, ccba這種第二個(gè)數(shù)比一個(gè)數(shù)長(zhǎng)的情況,所以不光要從左到右看,還要從右往左看。兩個(gè)方向都找一遍就可能出現(xiàn)重復(fù)的情況,注意避免重復(fù)。

兩個(gè)詞形成的string一樣不算重復(fù),只有當(dāng)兩個(gè)詞的組合重復(fù)時(shí)才算重復(fù)。例如: ["", "aa"],結(jié)果應(yīng)該是[(0,1), (1,0)]。那么什么時(shí)候可能出現(xiàn)重復(fù)呢?["ab", "ba"],這種兩個(gè)單詞形成了palindrome,如果在ab和ba的兩邊都查一遍肯定會(huì)重復(fù)。可以看出規(guī)律是當(dāng)map里面有其中一個(gè)詞的reverse時(shí),就少算一邊即可。

</>復(fù)制代碼

  1. public class Solution {
  2. public List> palindromePairs(String[] words) {
  3. Map map = new HashMap();
  4. for(int i = 0; i < words.length; i++) {
  5. map.put(new StringBuilder(words[i]).reverse().toString(), i);
  6. }
  7. List> result = new ArrayList();
  8. for(int i = 0; i < words.length; i++) {
  9. String cur = words[i];
  10. int n = cur.length();
  11. for(int j = 0; j <= n; j++) {
  12. // left: (0, j), right: (j, n)
  13. // right is palindrome and find reversed left
  14. String left = cur.substring(0, j);
  15. String right = cur.substring(j, n);
  16. if(isPalindrome(right) && map.containsKey(left) && map.get(left) != i) {
  17. result.add(Arrays.asList(i, map.get(left)));
  18. }
  19. // left is palindrome and find reversed right
  20. if(isPalindrome(left) && map.containsKey(right) && map.get(right) != i) {
  21. // avoid duplication
  22. if(j == 0 && map.containsKey(cur) && map.get(cur) != i) continue;
  23. result.add(Arrays.asList(map.get(right), i));
  24. }
  25. }
  26. }
  27. return result;
  28. }
  29. private boolean isPalindrome(String s) {
  30. int i = 0, j = s.length() - 1;
  31. while(i < j) {
  32. if(s.charAt(i) != s.charAt(j)) return false;
  33. i++; j--;
  34. }
  35. return true;
  36. }
  37. }

這個(gè)博客還用了一種set的方法:
http://www.cnblogs.com/grandy...

暫時(shí)還沒(méi)看懂,明天再看下。。

Shortest Palindrome

題目鏈接:https://leetcode.com/problems...

這道題和“ Longest Palindromic Substring ” 是一個(gè)意思,不同的是這個(gè)palindrome string必須要從index = 0開(kāi)始。最簡(jiǎn)單的方法就是一個(gè)一個(gè)試。超時(shí)了。。。

Manacher"s Algorithm

這個(gè)算法是用來(lái)找最長(zhǎng)回文字串的,利用的是回文的對(duì)稱信息或者說(shuō)是prefix信息。

</>復(fù)制代碼

  1. public class Solution {
  2. public String longestPalindrome(String s) {
  3. // base case
  4. if(s == null || s.length() <= 1) return s;
  5. // Manacher Algorithm
  6. /* new index: 0 1 2 3 4 5 6
  7. old index: # 0 # 1 # 2 #
  8. m c i r
  9. */
  10. // An array to store the max length at each center
  11. int n = s.length() * 2 + 1;
  12. int[] pivot = new int[n];
  13. pivotInitial(pivot, s);
  14. // find the maximum length
  15. int maxLen = 0;
  16. int center = 0;
  17. for(int i = 0; i < n; i++) {
  18. if(pivot[i] > maxLen) {
  19. maxLen = pivot[i];
  20. center = i;
  21. }
  22. }
  23. int lo = (center - maxLen) / 2;
  24. int hi = lo + maxLen;
  25. return s.substring(lo, hi);
  26. }
  27. // Manacher
  28. /* new index: 0 1 2 3 4 5 6
  29. old index: # 0 # 1 # 2 #
  30. m c i r
  31. */
  32. private void pivotInitial(int[] arr, String s) {
  33. // center and maximum reachable index
  34. int c = 0, r = 0;
  35. for(int i = 0; i < arr.length; i++) {
  36. int diff = r - i;
  37. // mirror to i with pivot c
  38. int m = c - (i - c);
  39. // the maximum palindrome is in the reachable
  40. if(diff >= 0 && arr[m] < diff) {
  41. arr[i] = arr[m];
  42. }
  43. else {
  44. // if i > r, then just start from i
  45. int left = i / 2 - 1;
  46. int right = i / 2 + i % 2;
  47. // start from the index that exceed the reachable index
  48. if(diff >= 0) {
  49. left -= diff / 2;
  50. right += diff / 2;
  51. }
  52. // update center and maximum reachable
  53. arr[i] = len(s, left, right);
  54. c = i;
  55. r = i + arr[i];
  56. }
  57. }
  58. }
  59. private int len(String s, int left, int right) {
  60. while(left >= 0 && right <= s.length() - 1) {
  61. if(s.charAt(left) == s.charAt(right)) {
  62. left--; right++;
  63. }
  64. else break;
  65. }
  66. return right - left - 1;
  67. }
  68. }
KMP

這個(gè)算法是用來(lái)找substring的,利用的是substring自身的prefix信息。

</>復(fù)制代碼

  1. // KMP algorithm
  2. public class KMPSubstringSearch {
  3. /* compute the prefix array for the pattern string */
  4. private int[] prefixArray(String pattern) {
  5. int[] pre = new int[pattern.length()];
  6. // pre[0] = 0, pre[i] means the index of prefix
  7. // index used to store the position of matched prefix
  8. int index = 0;
  9. int i = 1;
  10. while(i < pattern.length()) {
  11. if(pattern.charAt(i) == pattern.charAt(index)) {
  12. pre[i] = index + 1;
  13. i++; index++;
  14. }
  15. else {
  16. if(index == 0) {
  17. pre[i] = 0;
  18. i++;
  19. }
  20. else {
  21. index = pre[index-1];
  22. }
  23. }
  24. }
  25. return pre;
  26. }
  27. // kmp, pattern match, return the position
  28. // if no match, return -1
  29. private int kmp(String text, String pattern) {
  30. int[] pre = prefixArray(pattern);
  31. int i = 0; int j = 0;
  32. char[] ctext = text.toCharArray();
  33. char[] cpattern = pattern.toCharArray();
  34. while(i < ctext.length && j < cpattern.length) {
  35. // match
  36. if(ctext[i] == cpattern[j]) {
  37. i++; j++;
  38. }
  39. // not match
  40. else {
  41. // first char of the pattern string
  42. if(j == 0) {
  43. i++;
  44. }
  45. else {
  46. j = pre[j-1];
  47. }
  48. }
  49. }
  50. if(j == cpattern.length) {
  51. return i-j;
  52. }
  53. else return -1;
  54. }
  55. public static void main(String args[]) {
  56. String text = "abdacabc";
  57. String pattern = "abc";
  58. KMPSubstringSearch test = new KMPSubstringSearch();
  59. int result = test.kmp(text, pattern);
  60. System.out.println(result);
  61. }
  62. }

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/66572.html

相關(guān)文章

  • 214. Shortest Palindrome

    摘要:題目鏈接找到從頭開(kāi)始最長(zhǎng)的那么只要把的加到前面就是結(jié)果了。找的過(guò)程可以用來(lái)做優(yōu)化,由于,那么就照著里面見(jiàn)數(shù)組的方法來(lái)查,最后就是的長(zhǎng)度,注意兩個(gè)并在一起的要加分隔符,防止算的出問(wèn)題。 214. Shortest Palindrome 題目鏈接:https://leetcode.com/problems... 找到string從頭開(kāi)始最長(zhǎng)的palindrome substring:s[0...

    beita 評(píng)論0 收藏0
  • [LeetCode] 214. Shortest Palindrome

    Problem Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation. Exa...

    liangdas 評(píng)論0 收藏0
  • [Leetcode] Shortest Palindrome 最短回文拼接法

    摘要:第二個(gè)是,因?yàn)樵诘趥€(gè)位置,可以有最長(zhǎng)為的相同前后綴,依次類推。匹配時(shí)分為幾種情況字母相同,則和都加,且,因?yàn)楹缶Y匹配的長(zhǎng)度是前綴的長(zhǎng)度加。注意為了方便處理空字符串,我們?cè)诜崔D(zhuǎn)拼接的時(shí)候中間加了,這個(gè)字符要保證不會(huì)出現(xiàn)在字符串中。 Shortest Palindrome Given a string S, you are allowed to convert it to a palin...

    Chiclaim 評(píng)論0 收藏0
  • 336. Palindrome Pairs

    摘要:容易出的兩個(gè)地方以為例。這兩個(gè)互為的在尾部加上也就是在頭部加上所以后部分不能為空,否則就和頭部為空的情況重復(fù)了。空間復(fù)雜度因?yàn)橛昧祟~外的來(lái)儲(chǔ)存,需要空間。時(shí)間復(fù)雜度每個(gè)分為兩個(gè)部分,調(diào)用前后兩部分總長(zhǎng)度為所以每次調(diào)用為一共次。 Given a list of unique words, find all pairs of distinct indices (i, j) in the g...

    Guakin_Huang 評(píng)論0 收藏0
  • LeetCode 336. Palindrome Pairs

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

    TigerChain 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<