正文
链表回文串判断&&链式A+B
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
有段时间没有练习了,链表回文串判断用到了栈。链式A+B将没有的项用0补充。链表有没有头节点,及结点和链表的区别,即pNode和pHead。
//#include<iostream> //using namespace std; // //class Base { //public: // Base(int j) : i(j) {} // virtual~Base() {} // void func1() { // i *= 10; // func2(); // } // int getValue() { // return i; // } //protected: // virtual void func2() { // i++; // } //protected: // int i; //}; // //class Child : public Base { //public: // Child(int j) : Base(j) {} // void func1() { // i *= 100; // func2(); // } //protected: // void func2() { // i += 2; // } //}; //int main() { // Base * pb = new Child(1); // pb->func1(); // cout << pb->getValue() << endl; ///12 // delete pb; //}
题目分析:
《方法1》:反转链表
可以将原始链表反转,判断反转以后的链表与原始链表是否完全一致,如果一致便返回true,如果不一致则返回false。反转链表需要额外的存储空间,不是特别优秀的方法。
《方法2》:栈实现
我们可以想到从中间节点向两侧开始比较,如果全部相同,则返回true,否则返回false,因为无法获得一个节点的前一个节点,这个时候我们可以想到用栈实现,先将链表前半部分的元素分别压入堆栈,然后在遍历后半部分元素的时候同时和栈顶元素进行比较,如果全部相等则返回true,否则返回false。
特别注意: 因为我们不知道链表的的长度,可以通过快慢指针(一个指针每次移动两个,一个指针每次移动一个)来找到中间元素,这样整体只需要遍历链表一次,所需要的栈空间缩小为方法1的一半。
《方法3》:递归法
递归方法分为尾部递归和首部递归,还有中间递归,一般的尾部递归都可以用循环来实现,对于我们这道题目,递归的时候无法比较第一个元素和最后一个元素,即使知道最后一个元素,也无法获得最后一个元素的前一个元素。所以我们选择首部递归,先递归直到中间的元素,然后比较中间的元素,把比较结果返回,同时保存后半部分下一个要比较的元素(用引用传递可以,用二级指针也可以),递归返回后,如果是true,则继续比较,如果是false,则直接返回false。
《程序员面试金典》程序详解:
http://blog.csdn.net/zdplife/article/category/5799903
/***************************************************** * \file Palindrome listNode.cpp * \date 2016/05/05 17:16 题目描述 请编写一个函数,检查链表是否为回文。 给定一个链表ListNode* pHead,请返回一个bool,代表链表是否为回文。 测试样例: {1,2,3,2,1} 返回:true {1,2,3,2,3} 返回:false *****************************************************/ struct ListNode { int val; struct ListNode *next; ListNode(int x) :val(x), next(nullptr){} }; #include <iostream> #include <stack> using namespace std; class Palindrome { public: bool isPalindrome(ListNode* pHead) { // write code here ListNode *pNode = pHead; stack<int> s; while (pNode) { s.push(pNode->val); pNode = pNode->next; } pNode = pHead; while (pNode) { if (pNode->val==s.top()) { pNode=pNode->next; s.pop(); } else { return false; } } return true; } };
这个哥们总结的不错:
《程序员面试金典》程序详解:
http://blog.csdn.net/zdplife/article/category/5799903
题目描述
有两个用链表表示的整数,每个结点包含一个数位。这些数位是反向存放的,也就是个位排在链表的首部。编写函数对这两个整数求和,并用链表形式返回结果。
给定两个链表ListNode*
A
,ListNode*
B
,请返回A+B的结果(ListNode*)。
测试样例:
{1,2,3},{3,2,1}
返回:{4,4,4}
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Plus {
public:
ListNode* plusAB(ListNode* a, ListNode* b) {
;
ListNode *retHead = );
ListNode *p = retHead;
while (a || b || carry) {
;
;
;
carry = (vala + valb + carry) / ; //进位
ListNode *tmp = new ListNode(val);
p->next = tmp;
p = p->next;
a = a ? a->next : nullptr;
b = b ? b->next : nullptr;
}
p->next = nullptr;
return retHead->next;
}
};
链表回文串判断&&链式A+B的更多相关文章
-
链表回文串判断&&链式A+B
有段时间没有练习了,链表回文串判断用到了栈.链式A+B将没有的项用0补充.链表有没有头节点,及结点和链表的区别,即pNode和pHead. //#include<iostream> //u ...
-
Openjudge-计算概论(A)-回文串判断
描述: 任意给定一个非空的字符串,判断其是否是回文串.回文串是指正向看和反向看均相等的串,如AbcDcbA和cDDc.如果是回文串,则输出1,否则,输出0 输入长度不小于1不大于100的字符串输出如果 ...
-
《LeetBook》leetcode题解(5):Longest Palindromic [M]——回文串判断
我现在在做一个叫<leetbook>的免费开源书项目,力求提供最易懂的中文思路,目前把解题思路都同步更新到gitbook上了,需要的同学可以去看看 书的地址:https://hk029.g ...
-
openjudge-回文串判断【递归】
回文串判断 总时间限制: 1000ms 内存限制: 65536kB 描述 任意给定一个非空的字符串,判断其是否是回文串.回文串是指正向看和反向看均相等的串,如AbcDcbA和cDDc.如果是回文串,则 ...
-
分割回文串 · Palindrome Partitioning
[抄题]: 给定一个字符串s,将s分割成一些子串,使每个子串都是回文串. 返回s所有可能的回文串分割方案. 给出 s = "aab",返回 [ ["aa", & ...
-
lintcode-415-有效回文串
415-有效回文串 给定一个字符串,判断其是否为一个回文串.只包含字母和数字,忽略大小写. 注意事项 你是否考虑过,字符串有可能是空字符串?这是面试过程中,面试官常常会问的问题. 在这个题目中,我们将 ...
-
HDOJ/HDU 2163 Palindromes(判断回文串~)
Problem Description Write a program to determine whether a word is a palindrome. A palindrome is a s ...
-
HDU_2029——回文串的判断
Problem Description “回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串.请写一个程序判断读入的字符串是否是“回文”. Input 输入包 ...
-
leetcode:Palindrome Number (判断数字是否回文串) 【面试算法题】
题目: Determine whether an integer is a palindrome. Do this without extra space. Some hints: Could neg ...
随机推荐
-
如何配置svn服务器
如果你已经安装好了VisualServer服务器,现在让我们一起来配置svn服务器吧. 工具/原料 VisualServer 配置VisualServer 找到VisualServer Manager ...
-
字符编解码的故事–ASCII,ANSI,Unicode,Utf-8区别(转)
很久很久以前,有一群人,他们决定用8个可以开合的晶体管来组合成不同的状态,以表示世界上的万物.他们认为8个开关状态作为原子单位很好,于是他们把这称为”字节”. 再后来,他们又做了一些可以处理这些字节的 ...
-
(1)WinForm和WebForm
如上所述,WinForm程序通常分为四层,而WebForm程序通常分为三层. 举例说明,winForm程序: IEnumerable<BatchUpdateResult<string, ...
-
windows和mac下分别配置虚拟主机
windows下配置 1.找到apache的配置文件,httpd.conf 2.找到 LoadModule rewrite_module modules/mod_rewrite.so 去掉前边的# 3 ...
-
vi 编辑内容中查找字符位置
[root@localhost gdm]# vi /etc/X11/gdm/gdm.conf # You can also use the gdm-restart and gdm-safe-resta ...
-
SQL中查询优化的主要策略
为了能提高查询效率按优先级主要有一下策略: 1.尽可能早的执行选择操作(最基本的一条) 2.把笛卡尔积和随后的选择操作合并成F连接运算 3.同时计算一连串的选择和投影运算 4.保留同一子式的结果 5. ...
-
Go Deeper(2010成都现场赛题)(2-sat)
G - Go Deeper Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu Description ...
-
HDU 1425 sort 【哈希入门】
题意:给出n个数,输出前m大的数 和上一题一样,将输入的数加上一个极大地值作为地址 #include<iostream> #include<cstdio> #include&l ...
-
BZOJ2594: [Wc2006]水管局长数据加强版
题解: 裸LCT+离线+二分+MST... 代码:(几乎摘抄自hzwer) #include<cstdio> #include<cstdlib> #include<cma ...
-
javascript倒计时代码
其实就是用两个时间戳相减,余数转换为日期,就是所剩的年月日时分秒,不过年份-1970 $scope.timerID = null; $scope.timerRunning = false;$scope ...
有两个用链表表示的整数,每个结点包含一个数位。这些数位是反向存放的,也就是个位排在链表的首部。编写函数对这两个整数求和,并用链表形式返回结果。
给定两个链表ListNode* A ,ListNode* B ,请返回A+B的结果(ListNode*)。
测试样例:
{1,2,3},{3,2,1}
返回:{4,4,4}
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Plus { public: ListNode* plusAB(ListNode* a, ListNode* b) { ; ListNode *retHead = ); ListNode *p = retHead; while (a || b || carry) { ; ; ; carry = (vala + valb + carry) / ; //进位 ListNode *tmp = new ListNode(val); p->next = tmp; p = p->next; a = a ? a->next : nullptr; b = b ? b->next : nullptr; } p->next = nullptr; return retHead->next; } };
-
链表回文串判断&&链式A+B
有段时间没有练习了,链表回文串判断用到了栈.链式A+B将没有的项用0补充.链表有没有头节点,及结点和链表的区别,即pNode和pHead. //#include<iostream> //u ...
-
Openjudge-计算概论(A)-回文串判断
描述: 任意给定一个非空的字符串,判断其是否是回文串.回文串是指正向看和反向看均相等的串,如AbcDcbA和cDDc.如果是回文串,则输出1,否则,输出0 输入长度不小于1不大于100的字符串输出如果 ...
-
《LeetBook》leetcode题解(5):Longest Palindromic [M]——回文串判断
我现在在做一个叫<leetbook>的免费开源书项目,力求提供最易懂的中文思路,目前把解题思路都同步更新到gitbook上了,需要的同学可以去看看 书的地址:https://hk029.g ...
-
openjudge-回文串判断【递归】
回文串判断 总时间限制: 1000ms 内存限制: 65536kB 描述 任意给定一个非空的字符串,判断其是否是回文串.回文串是指正向看和反向看均相等的串,如AbcDcbA和cDDc.如果是回文串,则 ...
-
分割回文串 · Palindrome Partitioning
[抄题]: 给定一个字符串s,将s分割成一些子串,使每个子串都是回文串. 返回s所有可能的回文串分割方案. 给出 s = "aab",返回 [ ["aa", & ...
-
lintcode-415-有效回文串
415-有效回文串 给定一个字符串,判断其是否为一个回文串.只包含字母和数字,忽略大小写. 注意事项 你是否考虑过,字符串有可能是空字符串?这是面试过程中,面试官常常会问的问题. 在这个题目中,我们将 ...
-
HDOJ/HDU 2163 Palindromes(判断回文串~)
Problem Description Write a program to determine whether a word is a palindrome. A palindrome is a s ...
-
HDU_2029——回文串的判断
Problem Description “回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串.请写一个程序判断读入的字符串是否是“回文”. Input 输入包 ...
-
leetcode:Palindrome Number (判断数字是否回文串) 【面试算法题】
题目: Determine whether an integer is a palindrome. Do this without extra space. Some hints: Could neg ...
随机推荐
-
如何配置svn服务器
如果你已经安装好了VisualServer服务器,现在让我们一起来配置svn服务器吧. 工具/原料 VisualServer 配置VisualServer 找到VisualServer Manager ...
-
字符编解码的故事–ASCII,ANSI,Unicode,Utf-8区别(转)
很久很久以前,有一群人,他们决定用8个可以开合的晶体管来组合成不同的状态,以表示世界上的万物.他们认为8个开关状态作为原子单位很好,于是他们把这称为”字节”. 再后来,他们又做了一些可以处理这些字节的 ...
-
(1)WinForm和WebForm
如上所述,WinForm程序通常分为四层,而WebForm程序通常分为三层. 举例说明,winForm程序: IEnumerable<BatchUpdateResult<string, ...
-
windows和mac下分别配置虚拟主机
windows下配置 1.找到apache的配置文件,httpd.conf 2.找到 LoadModule rewrite_module modules/mod_rewrite.so 去掉前边的# 3 ...
-
vi 编辑内容中查找字符位置
[root@localhost gdm]# vi /etc/X11/gdm/gdm.conf # You can also use the gdm-restart and gdm-safe-resta ...
-
SQL中查询优化的主要策略
为了能提高查询效率按优先级主要有一下策略: 1.尽可能早的执行选择操作(最基本的一条) 2.把笛卡尔积和随后的选择操作合并成F连接运算 3.同时计算一连串的选择和投影运算 4.保留同一子式的结果 5. ...
-
Go Deeper(2010成都现场赛题)(2-sat)
G - Go Deeper Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu Description ...
-
HDU 1425 sort 【哈希入门】
题意:给出n个数,输出前m大的数 和上一题一样,将输入的数加上一个极大地值作为地址 #include<iostream> #include<cstdio> #include&l ...
-
BZOJ2594: [Wc2006]水管局长数据加强版
题解: 裸LCT+离线+二分+MST... 代码:(几乎摘抄自hzwer) #include<cstdio> #include<cstdlib> #include<cma ...
-
javascript倒计时代码
其实就是用两个时间戳相减,余数转换为日期,就是所剩的年月日时分秒,不过年份-1970 $scope.timerID = null; $scope.timerRunning = false;$scope ...
如果你已经安装好了VisualServer服务器,现在让我们一起来配置svn服务器吧. 工具/原料 VisualServer 配置VisualServer 找到VisualServer Manager ...
很久很久以前,有一群人,他们决定用8个可以开合的晶体管来组合成不同的状态,以表示世界上的万物.他们认为8个开关状态作为原子单位很好,于是他们把这称为”字节”. 再后来,他们又做了一些可以处理这些字节的 ...
如上所述,WinForm程序通常分为四层,而WebForm程序通常分为三层. 举例说明,winForm程序: IEnumerable<BatchUpdateResult<string, ...
windows下配置 1.找到apache的配置文件,httpd.conf 2.找到 LoadModule rewrite_module modules/mod_rewrite.so 去掉前边的# 3 ...
[root@localhost gdm]# vi /etc/X11/gdm/gdm.conf # You can also use the gdm-restart and gdm-safe-resta ...
为了能提高查询效率按优先级主要有一下策略: 1.尽可能早的执行选择操作(最基本的一条) 2.把笛卡尔积和随后的选择操作合并成F连接运算 3.同时计算一连串的选择和投影运算 4.保留同一子式的结果 5. ...
G - Go Deeper Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu Description ...
题意:给出n个数,输出前m大的数 和上一题一样,将输入的数加上一个极大地值作为地址 #include<iostream> #include<cstdio> #include&l ...
题解: 裸LCT+离线+二分+MST... 代码:(几乎摘抄自hzwer) #include<cstdio> #include<cstdlib> #include<cma ...
其实就是用两个时间戳相减,余数转换为日期,就是所剩的年月日时分秒,不过年份-1970 $scope.timerID = null; $scope.timerRunning = false;$scope ...