- 浏览: 174162 次
- 性别:
- 来自: 济南
文章分类
最新评论
这篇文章总结leetcode中回文的题目,其中关于palindrome partition有两道题目,第二道属于动态规划的题目,我们动态规划的总结中讨论。简单的讲回文就是将它翻转后和原来一样。
1,Palindrome Number
给定一个数字,判断它是否为回文数。
对于数字来讲,负数不属于回文数,对于正数,我们将它逆转,然后与原始值比较,如果相等就为回文数。代码如下:
2,Valid Palindrome
给定一个字符串判断是否为回文,只考虑数字和字母,并且不考虑字母大小写问题。
例如:"A man, a plan, a canal: Panama" 是回文字符串
"race a car" 不是回文字符串
既然只考虑数字和字母,我们就要想办法把其它的字符去除,这里我们用到正则表达式来处理,我们替换掉除字母和数字以外其它的字符,正则表达式为[^0-9a-z-A-Z],代码如下:
3,Palindrome Linked List
给定一个链表,判断是否为回文链表。
解决这道题我们要用快慢指针,找到中间点,接下来我们可以用栈操作,把前半段压入到堆栈中,然后和后半段比较;也可以将后半段反转与前半段进行比较。注意的问题是用堆栈的时候要考虑链表元素个数为奇数还是偶数。
堆栈解法:
反转解法:
4,Palindrome Partitioning
给定一个字符串s,把s分为很多子串,每个子串都为回文字符串,列出所有可能的结果。
例如:给定s = "aab"
输出: [ ["aa","b"], ["a","a","b"] ]
因为要列出所有的结果,很容易想到用回溯法。代码如下:
1,Palindrome Number
给定一个数字,判断它是否为回文数。
对于数字来讲,负数不属于回文数,对于正数,我们将它逆转,然后与原始值比较,如果相等就为回文数。代码如下:
public class Solution { public boolean isPalindrome(int x) { if(x < 0) return false; int result = 0; int tem = x; while(x != 0) { result = result * 10 + x % 10; x /= 10; } if(result == tem) return true; return false; } }
2,Valid Palindrome
给定一个字符串判断是否为回文,只考虑数字和字母,并且不考虑字母大小写问题。
例如:"A man, a plan, a canal: Panama" 是回文字符串
"race a car" 不是回文字符串
既然只考虑数字和字母,我们就要想办法把其它的字符去除,这里我们用到正则表达式来处理,我们替换掉除字母和数字以外其它的字符,正则表达式为[^0-9a-z-A-Z],代码如下:
public class Solution { public boolean isPalindrome(String s) { s = s.replaceAll("[^a-zA-Z0-9]","").toLowerCase(); int l = 0; int r = s.length() - 1; while(l < r) { if(s.charAt(l) != s.charAt(r)) { return false; } else { l ++; r --; } } return true; } }
3,Palindrome Linked List
给定一个链表,判断是否为回文链表。
解决这道题我们要用快慢指针,找到中间点,接下来我们可以用栈操作,把前半段压入到堆栈中,然后和后半段比较;也可以将后半段反转与前半段进行比较。注意的问题是用堆栈的时候要考虑链表元素个数为奇数还是偶数。
堆栈解法:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public boolean isPalindrome(ListNode head) { Stack<Integer> stack = new Stack<Integer>(); if(head == null) return true; ListNode fast = head; ListNode slow = head; while(fast.next != null && fast.next.next != null) { stack.push(slow.val); slow = slow.next; fast = fast.next.next; } head = slow.next; // 对奇偶数的判断 if(fast.next != null) stack.push(slow.val); //比较前后半段 while(!stack.isEmpty()) { if(stack.pop() != head.val){ return false; } else { head = head.next; } } return true; } }
反转解法:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public boolean isPalindrome(ListNode head) { if(head == null) return true; ListNode fast = head; ListNode slow = head; //得到中间节点 while(fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } fast = head; head = slow.next; //反转后半段 ListNode pre = null; ListNode tem = null; while(head != null) { tem = head.next; head.next = pre; pre = head; head = tem; } //比较前半段与后半段 while(pre != null) { if(fast.val != pre.val) { return false; } else { fast = fast.next; pre = pre.next; } } return true; } }
4,Palindrome Partitioning
给定一个字符串s,把s分为很多子串,每个子串都为回文字符串,列出所有可能的结果。
例如:给定s = "aab"
输出: [ ["aa","b"], ["a","a","b"] ]
因为要列出所有的结果,很容易想到用回溯法。代码如下:
public class Solution { public List<List<String>> partition(String s) { List<List<String>> llist = new ArrayList<List<String>>(); LinkedList<String> list = new LinkedList<String>(); if(s == null) return llist; partitionPalindro(0, s, llist, list); return llist; } public void partitionPalindro(int start, String s, List<List<String>> llist, LinkedList<String> list) { if(start == s.length()) { llist.add(new LinkedList<String>(list)); return; } for(int i = start; i < s.length(); i++) { if(isPalindrom(s.substring(start, i + 1))) { list.add(s.substring(start, i + 1)); partitionPalindro(i + 1, s, llist, list); list.removeLast(); } } } private boolean isPalindrom(String s) { int l = 0; int r = s.length() - 1; while(l < r) { if(s.charAt(l) != s.charAt(r)) { return false; } else { l ++; r --; } } return true; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 228Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 231You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 344Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 337Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 456Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 519Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 434Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 623Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 432The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 390Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 522Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 537Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 374All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 866Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 884Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 558Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 604Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 766Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 738You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 634For a undirected graph with tre ...
相关推荐
Determine whether an integer is a palindrome. Do this without extra space. Java AC版本
北大POJ1159-Palindrome 解题报告+AC代码
C++实现的Palindrome,回文 C++实现的Palindrome,回文
Pku acm 第1159题 Palindrome 代码,有详细的注释,动态规划
各位帮帮忙吧
Palindrome Sub-Array,Problem Description A palindrome sequence is a sequence which is as same as its reversed order. For example, 1 2 3 2 1 is a palindrome sequence, but 1 2 3 2 2 is not. Given a 2-...
palindrome22.in
回文数Java
北大POJ1159-Palindrome
LeetCode Palindrome Number解决方案
palindrome_prime.c
Palindrome.py
检查字符串是否为palindrome, 从前后分别检查,并计算出相同或不同的数量。
GET /java-palindrome-example/palindrome/ 解析提供的字符串,并找到其中包含的最大回文。 在此情况下,也可以将type的可选查询参数设置为slow在这种情况下,服务将使用慢得多的递归算法。 例子 GET /java-...
palindrome number in c
安装要安装bencreating_palindrome ,请将此行添加到应用程序的Gemfile : gem 'bencreating_palindrome'然后安装如下: $ bundle install或者直接使用gem安装它: $ gem install bencreating_palindrome用法...
palindrome(STACK,QUEUE).cpp
JAVA程序 Palindrome.java 输入任何字母数字组合 检查是否是回文结构? 例:abccba 从左往右看 和 从右往左看一样 为回文结构 包括检查是否带标点符号 检查是否有空格 如a bccba 输入带空格 仍为回文结构
1-99999位数回文数判断,银行管理包括利率,密码,剩余额