[July 程序员编程艺术：面试和算法心得题目及习题][1]
字符串转换成整数
also Leetcode 8 String to Integer (atoi)
题目描述
输入一个由数字组成的字符串，把它转换成整数并输出。例如：输入字符串 "123"，输出整数 123。
给定函数原型int StrToInt(const char *str) ，实现字符串转换成整数的功能，不能使用库函数 atoi。解题思路
实现是简单的，但是这道题主要考的是程序的鲁棒性。可以说要正确及完整的实现这道题，需要考虑所有常见的边界条件。
- 空指针输入：输入的是指针，在访问空指针时程序会崩溃，因此在使用指针之前需要先判断指针是否为空。
- 正负符号：整数不仅包含数字，还有可能是以'+'或'-'开头表示正负整数，因此如果第一个字符是'-'号，则要把得到的整数转换成负整数。
- 非法字符：输入的字符串中可能含有不是数字的字符。因此，每当碰到这些非法的字符，程序应停止转换。
- 整型溢出：输入的数字是以字符串的形式输入，因此输入一个很长的字符串将可能导致溢出
public class Solution { public int atoi(String str) { int digit=0; int positive = 1; double number=0; str = str.trim(); if(str.length() == 0 || str == null){ return 0; } if(str.charAt(0) =='+'){ positive = 1; digit++; } if(str.charAt(0) == '-'){ positive = -1; digit++; } while(digit<=str.length()-1){ int k = 0; if(str.charAt(digit)<='9'&&str.charAt(digit)>='0'){ k = str.charAt(digit) -'0'; number = k + number * 10; digit++; } else{ break; } } number = number * positive; System.out.println(""+number); if(number > Integer.MAX_VALUE ){ return Integer.MAX_VALUE; } if(number < Integer.MIN_VALUE){ return Integer.MIN_VALUE; } return (int)number; }} 习题：实现 string 到 double 的转换
分析：此题虽然类似于 atoi 函数，但毕竟 double 为 64 位，而且支持小数，因而边界条件更加严格，写代码时需要更加注意。
回文判断
一个整形数是否是回文
also leetcode 9 Palindrome Number
要求空间复杂度O(1) 按位判断一般是/和%的游戏，首先取首位 a/h (h是最接近a的10的次方，比如12321，h预计算出是10000), 再取末位a%10; 比较首位和末位是否相等，不等就返回false; 如图：
然后舍弃掉已经比较过的两个位数，从a中去掉首尾 12321 --> 232.
a = a % h; // 去掉首a = a /10; //去掉尾h = 100; // 因为已经去掉了两位
如图：
重复之前操作即可，如图：
public boolean isPalindrome(int x) { int a = x, h =1; if(a < 0) return false; while(a / h>= 10) { h = h*10; } //compare the last and first digit and will not overflow while(a> 0) { if(a/h != a%10) return false; a = a%h; a = a/10; h = h/100; } return true; } 
一个字符串是否是回文
指一个顺着读和反过来读都一样的字符串，判断一个字串是否是回文？
这个比较简单用charAt 取字符串的首尾位比较即可。
判断一条单向链表是不是 “回文”
解法1 ： 可以借助栈，将遍历到的前半段链表节点放入栈，后半段每当遍历到一个，都要与出栈的节点相比较。直到链表结尾。如果中间出现不相等的情况，则不是回文。
时间复杂度O(n),空间复杂度O(n) 如何进一步降低空间复杂度为O(1)
判断一个栈是不是 “回文”
分析：对于栈的话，只需要将字符串全部压入栈，然后依次将各字符出栈，这样得到的就是原字符串的逆置串，分别和原字符串各个字符比较，就可以判断了