資訊專欄INFORMATION COLUMN
摘要：判斷一條單向鏈表是不是回文解法可以借助棧，將遍歷到的前半段鏈表節(jié)點(diǎn)放入棧，后半段每當(dāng)遍歷到一個(gè)，都要與出棧的節(jié)點(diǎn)相比較。如果中間出現(xiàn)不相等的情況，則不是回文。
字符串轉(zhuǎn)換成整數(shù)[July 程序員編程藝術(shù)：面試和算法心得題目及習(xí)題][1]
also Leetcode 8 String to Integer (atoi)
題目描述輸入一個(gè)由數(shù)字組成的字符串，把它轉(zhuǎn)換成整數(shù)并輸出。例如：輸入字符串 "123"，輸出整數(shù) 123。
給定函數(shù)原型int StrToInt(const char *str) ，實(shí)現(xiàn)字符串轉(zhuǎn)換成整數(shù)的功能，不能使用庫函數(shù) atoi。
實(shí)現(xiàn)是簡單的，但是這道題主要考的是程序的魯棒性?？梢哉f要正確及完整的實(shí)現(xiàn)這道題，需要考慮所有常見的邊界條件。
空指針輸入：輸入的是指針，在訪問空指針時(shí)程序會(huì)崩潰，因此在使用指針之前需要先判斷指針是否為空。
正負(fù)符號(hào)：整數(shù)不僅包含數(shù)字，還有可能是以"+"或"-"開頭表示正負(fù)整數(shù)，因此如果第一個(gè)字符是"-"號(hào)，則要把得到的整數(shù)轉(zhuǎn)換成負(fù)整數(shù)。
非法字符：輸入的字符串中可能含有不是數(shù)字的字符。因此，每當(dāng)碰到這些非法的字符，程序應(yīng)停止轉(zhuǎn)換。
整型溢出：輸入的數(shù)字是以字符串的形式輸入，因此輸入一個(gè)很長的字符串將可能導(dǎo)致溢出
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;
}
}
習(xí)題：實(shí)現(xiàn) string 到 double 的轉(zhuǎn)換
分析：此題雖然類似于 atoi 函數(shù)，但畢竟 double 為 64 位，而且支持小數(shù)，因而邊界條件更加嚴(yán)格，寫代碼時(shí)需要更加注意。
回文判斷 一個(gè)整形數(shù)是否是回文also leetcode 9 Palindrome Number
要求空間復(fù)雜度O(1)
按位判斷一般是/和%的游戲，首先取首位 a/h (h是最接近a的10的次方，比如12321，h預(yù)計(jì)算出是10000), 再取末位a%10; 比較首位和末位是否相等，不等就返回false;
如圖：
然后舍棄掉已經(jīng)比較過的兩個(gè)位數(shù)，從a中去掉首尾 12321 --> 232.
a = a % h; // 去掉首 a = a /10; //去掉尾 h = 100; // 因?yàn)橐呀?jīng)去掉了兩位
如圖：
重復(fù)之前操作即可，如圖：
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;
}
一個(gè)字符串是否是回文
指一個(gè)順著讀和反過來讀都一樣的字符串，判斷一個(gè)字串是否是回文？
這個(gè)比較簡單用charAt 取字符串的首尾位比較即可。
判斷一條單向鏈表是不是 “回文”解法1 ： 可以借助棧，將遍歷到的前半段鏈表節(jié)點(diǎn)放入棧，后半段每當(dāng)遍歷到一個(gè)，都要與出棧的節(jié)點(diǎn)相比較。直到鏈表結(jié)尾。如果中間出現(xiàn)不相等的情況，則不是回文。
時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(n)
如何進(jìn)一步降低空間復(fù)雜度為O(1)
解法2：
分析：對(duì)于單鏈表結(jié)構(gòu)，可以用兩個(gè)指針從兩端或者中間遍歷并判斷對(duì)應(yīng)字符是否相等。但這里的關(guān)鍵就是如何朝兩個(gè)方向遍歷。由于單鏈表是單向的，所以要向兩個(gè)方向遍歷的話，可以采取經(jīng)典的快慢指針的方法，即先位到鏈表的中間位置，再將鏈表的后半逆置，最后用兩個(gè)指針同時(shí)從鏈表頭部和中間開始同時(shí)遍歷并比較即可。
缺陷： 破壞了鏈表的結(jié)構(gòu)
分析：對(duì)于棧的話，只需要將字符串全部壓入棧，然后依次將各字符出棧，這樣得到的就是原字符串的逆置串，分別和原字符串各個(gè)字符比較，就可以判斷了
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65296.html
摘要：遇到問題查查，看看，大神的講解問問島胖君下面是我最近整理出來的關(guān)于字符串的文章的怎么翻譯匯集目錄非常希望強(qiáng)化博客的功能，比如分類，置頂。 雖是讀書筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 最近在看算法和語言，基本屬于看知識(shí) --> java實(shí)現(xiàn) --> 整理blog 這個(gè)路線。 遇到問題查查st...
摘要：反轉(zhuǎn)上述步驟得到的結(jié)果字符串，即反轉(zhuǎn)字符串的兩部分和給予反轉(zhuǎn)，得到，形式化表示為，這就實(shí)現(xiàn)了整個(gè)反轉(zhuǎn)。例如，原字符串為，，輸出結(jié)果為。同單詞翻轉(zhuǎn)輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變，句子中單詞以空格符隔開。 July 程序員編程藝術(shù)：面試和算法心得題目及習(xí)題 旋轉(zhuǎn)字符串 題目描述 給定一個(gè)字符串，要求把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部，如...
摘要：求字符串的全排列字符串的全排列設(shè)計(jì)一個(gè)算法，輸出一個(gè)字符串字符的全排列。的做法沒有結(jié)果的，都是在一個(gè)字符串上進(jìn)行的操作。字符串的全組合輸入三個(gè)字符，則它們的組合有。因此可以循環(huán)字符串長度，然后輸出對(duì)應(yīng)代表的組合即可。 求字符串的全排列 字符串的全排列 設(shè)計(jì)一個(gè)算法，輸出一個(gè)字符串字符的全排列。 比如，String = abc 輸出是abc,bac,cab,bca,cba,...
閱讀 2124·2021-11-16 11:45
閱讀 1214·2021-10-22 09:53
閱讀 4018·2021-09-07 10:26
閱讀 1223·2021-09-06 15:00
閱讀 2081·2019-08-28 18:09
閱讀 2811·2019-08-26 14:06
閱讀 3978·2019-08-26 13:48
閱讀 1307·2019-08-26 12:11
