- 浏览: 142092 次
-
文章分类
- 全部博客 (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
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.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
[balabala] 以当前字符或者当前相邻两个字符为中心向两边扩展,如果左边能一直扩展到边界,则将右边剩余子串翻转后拼接在原字符串前面即构成一个回文。实现中两个要点:
1)中心字符串从原字符串的中间位置向左遍历,组成的首个回文即是最短回文。 因为回文中心越靠近中间则前面额外添加的字符数越少。
2)先判断以当前两字符为中心能否构成回文再判断以当前一个字符为中心的情况。这同样是为了得到最短回文,考虑aaaa, aab 就很容易理解。
这题自己做了两天,因为一开始没有注意到题目中的限定条件,在字符串前面添加额外字符来得到最短回文串。我忽略了这个限定还在想leetcode给的test case也会不周到啊,ba对应的最短回文可以是aba,也可以还是bab,为了被Accept,花了很长时间改代码使类似的case通过,但最终自己的版本仍然没有一个被通过,没意识到限定条件估计还得调很久,后来看别人的解答时才恍然意识到自己忽略了重要限定条件。另外,做这题还遇到个奇葩现象,我的方法三在Eclipse中运行ba 得到的是aba,但在leetcode中一直wrong answer,说是我的函数运行结果是bab,想不通。 最终被Accept的代码就29行,对比起来自己先前的代码真像懒婆娘的裹脚布,自己都懒得去看了,╮(╯▽╰)╭ , 效率上Method3 > Method1 > Method2 以后类似情况要及时参考下别人的解法。
[ref]
http://blog.csdn.net/xudli/article/details/45931667
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
[balabala] 以当前字符或者当前相邻两个字符为中心向两边扩展,如果左边能一直扩展到边界,则将右边剩余子串翻转后拼接在原字符串前面即构成一个回文。实现中两个要点:
1)中心字符串从原字符串的中间位置向左遍历,组成的首个回文即是最短回文。 因为回文中心越靠近中间则前面额外添加的字符数越少。
2)先判断以当前两字符为中心能否构成回文再判断以当前一个字符为中心的情况。这同样是为了得到最短回文,考虑aaaa, aab 就很容易理解。
这题自己做了两天,因为一开始没有注意到题目中的限定条件,在字符串前面添加额外字符来得到最短回文串。我忽略了这个限定还在想leetcode给的test case也会不周到啊,ba对应的最短回文可以是aba,也可以还是bab,为了被Accept,花了很长时间改代码使类似的case通过,但最终自己的版本仍然没有一个被通过,没意识到限定条件估计还得调很久,后来看别人的解答时才恍然意识到自己忽略了重要限定条件。另外,做这题还遇到个奇葩现象,我的方法三在Eclipse中运行ba 得到的是aba,但在leetcode中一直wrong answer,说是我的函数运行结果是bab,想不通。 最终被Accept的代码就29行,对比起来自己先前的代码真像懒婆娘的裹脚布,自己都懒得去看了,╮(╯▽╰)╭ , 效率上Method3 > Method1 > Method2 以后类似情况要及时参考下别人的解法。
[ref]
http://blog.csdn.net/xudli/article/details/45931667
public class Solution { public String shortestPalindrome(String s) { if (s == null || s.length() < 2) return s; int center = (s.length() - 1) / 2; String result = null; for (int i = center; i >= 0; i--) { if (s.charAt(i) == s.charAt(i + 1)) { if ((result = buildPalin(s, i, i + 1)) != null) return result; } if ((result = buildPalin(s, i, i)) != null) return result; } return null; } private String buildPalin(String s, int left, int right) { int n = s.length(); while (left >= 0 && right < n) { if (s.charAt(left) != s.charAt(right)) break; left--; right++; } if (left >= 0) return null; StringBuilder extra = new StringBuilder(s.substring(right)); return extra.reverse().append(s).toString(); } }
// Method 3 public String shortestPalindrome3(String s) { if (s == null || s.length() < 2) return s; int n = s.length(); int minLen = Integer.MAX_VALUE; String bestAns = ""; int right = n / 2; int left = right - 1; String ans; while (true) { // round 1: 从中心开始,左右开弓,找到的首个以当前字符为中心且边界之前左右都相等即是这种找法下最短回文串中心点 if (left >= 0) { ans = wrap(s, left, left, n, minLen); if (ans != null && ans.length() < minLen) { minLen = ans.length(); bestAns = ans; if (minLen == n) return bestAns; } if (left + 1 < n) { ans = wrap(s, left, left + 1, n, minLen); if (ans != null && ans.length() < minLen) { minLen = ans.length(); bestAns = ans; if (minLen == n) return bestAns; } } left--; } if (right < n) { ans = wrap(s, right, right, n, minLen); if (ans != null && ans.length() < minLen) { minLen = ans.length(); bestAns = ans; if (minLen == n) return bestAns; } if (right + 1 < n) { ans = wrap(s, right, right + 1, n, minLen); if (ans != null && ans.length() < minLen) { minLen = ans.length(); bestAns = ans; if (minLen == n) return bestAns; } } right++; } if (left < 0 && right >= n) break; } return bestAns; } // Method 2 public String shortestPalindrome2(String s) { if (s == null || s.length() < 2) return s; int n = s.length(); int minLen = Integer.MAX_VALUE; String bestAns = ""; for (int i = 0; i < n - 1; i++) { // round 1: 从中心开始,左右开弓,找到的首个以当前字符为中心且边界之前左右都相等即是这种找法下最短回文串中心点 String ans = wrap(s, i, i, n, minLen); if (ans != null && ans.length() < minLen) { minLen = ans.length(); bestAns = ans; } // round 2: 以相邻两个字符为中心向外辐射查找最短回文串 ans = wrap(s, i, i + 1, n, minLen); if (ans != null && ans.length() < minLen) { minLen = ans.length(); bestAns = ans; } } return bestAns; } public String wrap (String s, int left, int right, int n, int minLen) { int len = getPalin(s, left, right, n); if (len == n) { return s; } else if (len > 0 && len < minLen) { int leftLen = left != right ? (left + 1) : left; int rightLen = left != right ? (n - left - 1) : (n - right - 1); return buildPalin(s, leftLen, rightLen, n); } return null; } // Method 1 方向和leetcode test case不一致 public String shortestPalindrome1(String s) { if (s == null || s.length() < 2) return s; int n = s.length(); // round 1: 从中心开始,左右开弓,找到的首个以当前字符为中心且边界之前左右都相等即是这种找法下最短回文串中心点 int left = n / 2, right = left + 1; int minLen = -1; String ans = null; while (left >= 0 && right < n) { minLen = getPalin(s, left, left, n); if (minLen == n) return s; if (minLen > 0) { ans = buildPalin(s, left, n - left - 1, n); break; } else { minLen = getPalin(s, right, right, n); if (minLen > 0) { ans = buildPalin(s, right, n - right - 1, n); break; } } left--; right++; } if (ans == null && left >= 0) { // minLen = getPalin(s, left, left, n); ans = buildPalin(s, left, n - left - 1, n); } // round 2: 以相邻两个字符为中心向外辐射查找最短回文串 int mid = n / 2; for (int i = 0; i < n - 1; i++) { int len = getPalin(s, i, i + 1, n); if (len == n) return s; if (len > 0 && len < minLen) { int leftLen = i + 1, rightLen = n - i - 1; ans = buildPalin(s, leftLen, rightLen, n); } } return ans; } // 以left, right为中心向外辐射,某一方向能到达边界则可以以(left, right)为中心创建一个回文串 private int getPalin(String s, int left, int right, int n) { int i = left, j = right; while (i >= 0 && j < n) { if (s.charAt(i--) != s.charAt(j++)) return -1; } if (i > 0) { return left == right ? (2 * left + 1) : (2 * left + 2); } else { return left == right ? (2 * (n - right) - 1) : (2 * (n - right)); } } private String buildPalin(String s, int leftLen, int rightLen, int n) { String ans = null; if (leftLen >= rightLen) {// left part is longer StringBuilder extraLeft = new StringBuilder(s.substring(0, leftLen - rightLen)); StringBuilder tmp = new StringBuilder(s); tmp.append(extraLeft.reverse().toString()); ans = tmp.toString(); } else { StringBuilder extraRight = new StringBuilder(s.substring(n - (rightLen - leftLen), n)); StringBuilder tmp = new StringBuilder(extraRight.reverse().toString()); tmp.append(s); ans = tmp.toString(); } return ans; }
发表评论
-
Leetcode - Integer to English Words
2015-09-04 20:53 1126[分析] 这题通过率之所以非常低是因为有很多corner ca ... -
Leetcode - Read N Characters Given Read4 II - Call Multiple Times
2015-08-28 09:00 879The API: int read4(char *buf) r ... -
Leetcode - Read N Characters Given Read4
2015-08-27 20:56 713The API: int read4(char *buf) r ... -
Leetcode - One Edit Distance
2015-08-27 20:26 570[分析] 两字符串相同或者长度差异大于等于2都不符合要求,只需 ... -
Leetcode - Isomorphic Strings
2015-08-23 09:51 573[分析] 思路1:维护两个哈希表,char[] map, bo ... -
Leetcode - Group Shifted String
2015-08-22 16:20 1754Given a string, we can "sh ... -
Leetcode - Strobogrammatic Number
2015-08-22 10:48 1118A strobogrammatic number is a n ... -
Leetcode - Text Justification
2015-06-22 18:29 409Given an array of words and a l ... -
Leetcode - Valid Number
2015-06-21 10:42 685Validate if a given string is n ... -
Leetcode - Substring with Contentaion of All Words
2015-06-18 10:01 533You are given a string, s, and ... -
Leetcode - Simplify Path
2015-06-17 21:58 449Given an absolute path for a fi ... -
Leetcode - ZigZag Conversion
2015-06-15 21:31 566The string "PAYPALISHIRING ... -
Leetcode - Multiply String
2015-06-15 09:39 710Given two numbers represented a ... -
Leetcode - Minimum Window String
2015-06-14 19:33 605Given a string S and a string T ... -
Leetcode - Longest Substring Without Repeating Characters
2015-06-14 15:34 582Given a string, find the length ... -
Leetcode - Implement strStr()
2015-06-13 19:54 780Implement strStr(). Returns the ... -
Leetcode - Add Binary
2015-06-13 17:34 324Given two binary strings, retu ... -
Leetcode - Compare Version Numbers
2015-06-13 16:36 488Compare two version numbers ver ... -
Leetcode - Longest Palindrome Substring
2015-06-11 09:48 476<div class="iteye-blog- ...
相关推荐
3. leetcode-214-Shortest-Palindrome.md:第214题,寻找最短回文串,可能涉及到字符串操作和动态规划。 4. leetcode-145-Binary-Tree-Postorder-Traversal.md:第145题,二叉树的后序遍历,是关于树结构和递归的...
leetcode category other hot keywords:Palindrome(mic), Subsequence Array 螺旋矩阵Spiral Matrix 顺时针打印矩阵 Next Permutation Product of Array Except Self 189.rotate-array 283.move-zero Range Sum ...
leetcode 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...
# [LeetCode](https://leetcode.com/problemset/algorithms/)  [![License]...
字符串处理题目也是LeetCode的重要部分,例如"Reverse Words in a String"(翻转字符串中的单词)和"Valid Palindrome"(验证回文串)。这些题目通常涉及到字符串的遍历、分割、比较以及特殊字符的处理。 四、位...
214-shortest-palindrome.c。 使用二分搜索更新 287-find-the-duplicate-number.c 和弗洛伊德的龟兔赛跑(循环检测)算法。 (完毕) 使用哈希表更新 496-next-greater-element-ic。 (完毕) 使用优化算法更新 798-...
3. **栈和队列**:栈(Last In First Out, LIFO)和队列(First In First Out, FIFO)是两种基础数据结构,常见题目如"有效的括号"(Valid Parentheses)用栈来检查括号匹配,"最短回文串"(Shortest Palindrome)则...
leetcode添加元素使和等于 本项目为Njueers所共享 仓库内容主要为平时刷题的submit、遇到的一些经典题解、coding时所作的笔记等 Basic Knowledge文件夹下为一些基础但相对重要的C++知识点/笔记 Cpp文件夹下主要为...