- 浏览: 131079 次
文章分类
- 全部博客 (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
<div class="iteye-blog-content-contain" style="font-size: 14px"></div>
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
[balabala] Method1从小到大逐一check不同长度的子串是否为回文,使用DP保存中间计算,但仍然会超时,Method3是非DP版的Method1,1年前的历史记录竟然是Accept的,估计当时leetcode 打瞌睡了。Method2 同样是DP,能够被Accept,分析计算次数和Method1一样,在Eclipse下实际运行超时的case,后者比前者快三、四ms,我认为差异主要是因为Method1 访问数组的模式不如Method2优,将二维数组看成一个矩阵,Method1 不断在各行间跳跃访问,而Method2 在一次外层循环中逐列访问同一行的数组。Method4是从当前1个字符或当前两个字符向两边辐射求得最长回文,该方法比Method2效率更高,因为它避免了一些无意义的计算,比如“abcdefg”, Method1和2均需要计算全部子串,而Method4不会计算诸如abcde这样的子串,在计算bcd时即停止计算其余以c为中心的子串。还有一种O(n)的实现,还未看懂,http://www.cnblogs.com/tenosdoit/p/3675788.html 先备忘着。
[ref]
http://www.cnblogs.com/tenosdoit/p/3675788.html
http://www.cnblogs.com/jdflyfly/p/3810674.html
http://codeganker.blogspot.com/2014/02/longest-palindromic-substring-leetcode.html
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
[balabala] Method1从小到大逐一check不同长度的子串是否为回文,使用DP保存中间计算,但仍然会超时,Method3是非DP版的Method1,1年前的历史记录竟然是Accept的,估计当时leetcode 打瞌睡了。Method2 同样是DP,能够被Accept,分析计算次数和Method1一样,在Eclipse下实际运行超时的case,后者比前者快三、四ms,我认为差异主要是因为Method1 访问数组的模式不如Method2优,将二维数组看成一个矩阵,Method1 不断在各行间跳跃访问,而Method2 在一次外层循环中逐列访问同一行的数组。Method4是从当前1个字符或当前两个字符向两边辐射求得最长回文,该方法比Method2效率更高,因为它避免了一些无意义的计算,比如“abcdefg”, Method1和2均需要计算全部子串,而Method4不会计算诸如abcde这样的子串,在计算bcd时即停止计算其余以c为中心的子串。还有一种O(n)的实现,还未看懂,http://www.cnblogs.com/tenosdoit/p/3675788.html 先备忘着。
[ref]
http://www.cnblogs.com/tenosdoit/p/3675788.html
http://www.cnblogs.com/jdflyfly/p/3810674.html
http://codeganker.blogspot.com/2014/02/longest-palindromic-substring-leetcode.html
// Method 1: O(n^2), time out public String longestPalindrome1(String s) { if (s == null || s.equals("")) return ""; int n = s.length(); boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) dp[i][i] = true; String ans = s.substring(0, 1); for (int i = 0; i < n - 1; i++) { dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1); if (ans.length() == 1 && dp[i][i + 1]) ans = s.substring(i, i + 2); } for (int l = 3; l <= n; l++) { for (int i = 0; i + l <= n; i++) { int j = i + l - 1; dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]; if (ans.length() < l && dp[i][j]) ans = s.substring(i, i + l); } } return ans; } // Method 2: O(n^2) 另一种DP实现 // http://codeganker.blogspot.com/2014/02/longest-palindromic-substring-leetcode.html public String longestPalindrome(String s) { if (s == null || s.equals("")) return ""; int n = s.length(); String ans = ""; int maxLen = 0; boolean[][] dp = new boolean[n][n]; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) { dp[i][j] = true; if (maxLen < j - i + 1) { maxLen = j - i + 1; ans = s.substring(i, j + 1); } } } } return ans; } // Method 3: O(n^2), from up to bottom, once accept, time out now public String longestPalindrome3(String s) { if (s == null || s.equals("")) return ""; int n = s.length(); for (int len = n; len >= 1; len--) { for (int i = 0; i + len <= n; i++) { String sub = s.substring(i, i + len); if (isPalin(sub)) { return sub; } } } return ""; } private boolean isPalin(String s) { int i = 0, j = s.length() - 1; while (i < j) { if (s.charAt(i) != s.charAt(j)) return false; i++; j--; } return true; } // Method 4: O(n^2) 以当前字符或者当前字符及下一个字符向外辐射找出最长的子串 // http://www.cnblogs.com/jdflyfly/p/3810674.html public String longestPalindrome4(String s) { if (s == null || s.equals("")) return ""; int n = s.length(); int maxLen = 1; int tmpLen = 0; String ans = s.substring(0, 1); for (int i = 0; i < n - 1; i++) { tmpLen = getPalin(s, i - 1, i + 1); if (tmpLen > maxLen) { int start = i - tmpLen / 2; ans = s.substring(start, start + tmpLen); maxLen = tmpLen; } tmpLen = getPalin(s, i, i + 1); if (tmpLen > maxLen) { int start = i - tmpLen / 2 + 1; ans = s.substring(start, start + tmpLen); maxLen = tmpLen; } } return ans; } private int getPalin(String s, int left, int right) { int n = s.length(); int len = right - left - 1; while (left >= 0 && right < n) { if (s.charAt(left--) == s.charAt(right++)) { len += 2; } else { return len; } } return len; }
发表评论
-
Leetcode - Integer to English Words
2015-09-04 20:53 1068[分析] 这题通过率之所以非常低是因为有很多corner ca ... -
Leetcode - Read N Characters Given Read4 II - Call Multiple Times
2015-08-28 09:00 804The API: int read4(char *buf) r ... -
Leetcode - Read N Characters Given Read4
2015-08-27 20:56 649The API: int read4(char *buf) r ... -
Leetcode - One Edit Distance
2015-08-27 20:26 503[分析] 两字符串相同或者长度差异大于等于2都不符合要求,只需 ... -
Leetcode - Isomorphic Strings
2015-08-23 09:51 512[分析] 思路1:维护两个哈希表,char[] map, bo ... -
Leetcode - Group Shifted String
2015-08-22 16:20 1687Given a string, we can "sh ... -
Leetcode - Strobogrammatic Number
2015-08-22 10:48 1066A strobogrammatic number is a n ... -
Leetcode - Text Justification
2015-06-22 18:29 360Given an array of words and a l ... -
Leetcode - Valid Number
2015-06-21 10:42 626Validate if a given string is n ... -
Leetcode - Substring with Contentaion of All Words
2015-06-18 10:01 473You are given a string, s, and ... -
Leetcode - Simplify Path
2015-06-17 21:58 399Given an absolute path for a fi ... -
Leetcode - ZigZag Conversion
2015-06-15 21:31 512The string "PAYPALISHIRING ... -
Leetcode - Multiply String
2015-06-15 09:39 642Given two numbers represented a ... -
Leetcode - Minimum Window String
2015-06-14 19:33 539Given a string S and a string T ... -
Leetcode - Longest Substring Without Repeating Characters
2015-06-14 15:34 531Given a string, find the length ... -
Leetcode - Implement strStr()
2015-06-13 19:54 733Implement strStr(). Returns the ... -
Leetcode - Add Binary
2015-06-13 17:34 270Given two binary strings, retu ... -
Leetcode - Compare Version Numbers
2015-06-13 16:36 433Compare two version numbers ver ... -
Leetcode - Shortest Palindrome
2015-06-13 10:55 530Given a string S, you are allow ...
相关推荐
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
3-longest-substring-without-repeating-characters 7 cargo run --bin 7-reverse-integer 9 cargo run --bin 9-palindrome-number 13 cargo run --bin 13-roman-to-integer 14 cargo run --bin 14-longest-common-...
leetcode题库 LeetCode-Go 理论基础 见Note 脑图 TODO 待填充 算法题 面试高频出现,以及一些非常经典重要的算法题优先 题目列表 ...Longest Substring ...Longest ...Substring ...Palindrome Number 49.4% Easy
分割数组求最大差值leetcode ...Palindrome Number 56.7% 简单 10 Regular Expression Matching 25.3% 困难 11 Container With Most Water 59.3% 中等 12 Integer to Roman 61.8% 中等 13 Roman to In
Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container With Most Water 盛最多水的容器 13 Roman to Integer 罗马数字转整数 14 Longest Common Prefix 最长公共前缀 20 ...
Palindrome Number 回文数字 10. Regular Expression Matching 动态规划,列出转换方程即可,注意初值 记T[i][j] = 是否S[0:i]和P[0:j]匹配 再分类讨论,其中pattern *分为0, 1, more三种类型 0: i不变, j+1
Substring Without Repeating Characters 经典字符串,查找,哈希表,双指针法 2019/09/10 0004 Median of Two Sorted Arrays 二分查找,归并排序 2019/09/11 0006 ZigZag Conversion 逻辑 2019/09/13 0007 Reverse ...
Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 LeetCode 3 Longest Substring Without Repeating ...
./0003-longest-substring-without-repeating-characters.cpp ./0004-median-of-two-sorted-arrays.cpp ./0005-longest-palindromic-substring.cpp ./0006-zigzag-conversion.cpp ./0007-reverse-integer.cpp ./0008...
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
Palindrome Number.cpp 12 整数转罗马数字 Integer to Roman.cpp 13 罗马数字转整数 Roman to Integer.cpp 15 三数之和 3Sum.cpp 最接近的三数之和 3Sum Closest .cpp 20 有效的括号 Valid Parentheses.cpp 22 括号...
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....
Palindrome :star: 有效回文,小写字母转换 0005 Longest Palindromic Substring :star: :star: :star: 最长回文子串,Manacher算法 0010 RegularExpressionMatching :star: :star: :star: 正则表达式匹配,dp 0012 ...
leetcode ...Substring Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
5-longest-palindromic-substring.c。 (完毕) 使用优化算法更新 214-shortest-palindrome.c。 使用二分搜索更新 287-find-the-duplicate-number.c 和弗洛伊德的龟兔赛跑(循环检测)算法。 (完毕) 使用哈希表...
Substring 006 ZigZag Conversion 007 Reverse Integer 008 String to Integer (atoi) 009 Palindrome Number 010 Regular Expression Matching 011 Container With Most Water 012 Integer to Roman 013 Roman to ...
leetcode 516 8/13 - 8/18 周:leetcode#: ...Palindrome 28. Implement strStr() 5. Longest Palindromic Substring option: 516. Longest Palindromic Subsequence string replacement strStr II 链接:
Palindrome Number 回文数 10. Regular Expression Matching 正则表达式匹配 11. Container With Most Water 盛最多水的容器 12. Integer to Roman 整数转罗马数字 13. Roman to Integer 罗马数字转
Palindrome Number 简单 11 Container With Most Water 中等 12 Integer to Roman 中等 13 Roman to Integer 简单 14 Longest Common Prefix 简单 15 3Sum 中等 16 3Sum Closest 中等 17 Letter Combinations of a ...
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...