July 算法習題 - 字符串2 + Leetcode 8,9

timger 發布于2019-08-14 15:07 / 2906人閱讀

摘要：判斷一條單向鏈表是不是回文解法可以借助棧，將遍歷到的前半段鏈表節點放入棧，后半段每當遍歷到一個，都要與出棧的節點相比較。如果中間出現不相等的情況，則不是回文。

  [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)
解法2：
分析：對于單鏈表結構，可以用兩個指針從兩端或者中間遍歷并判斷對應字符是否相等。但這里的關鍵就是如何朝兩個方向遍歷。由于單鏈表是單向的，所以要向兩個方向遍歷的話，可以采取經典的快慢指針的方法，即先位到鏈表的中間位置，再將鏈表的后半逆置，最后用兩個指針同時從鏈表頭部和中間開始同時遍歷并比較即可。
缺陷：破壞了鏈表的結構

判斷一個棧是不是 “回文”

分析：對于棧的話，只需要將字符串全部壓入棧，然后依次將各字符出棧，這樣得到的就是原字符串的逆置串，分別和原字符串各個字符比較，就可以判斷了

GPU云服務器云服務器字符串轉2進制算法 ehcache 2 8 3 jquery 1 8 2 幻想云服務器1.8.9

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65296.html

字符串處理文章outline

摘要：遇到問題查查，看看，大神的講解問問島胖君下面是我最近整理出來的關于字符串的文章的怎么翻譯匯集目錄非常希望強化博客的功能，比如分類，置頂。雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨最近在看算法和語言，基本屬于看知識 --> java實現 --> 整理blog 這個路線。遇到問題查查st...

Karuru 2019-08-14 15:07 評論0 收藏0
July算法習題 - 字符串1

摘要：反轉上述步驟得到的結果字符串，即反轉字符串的兩部分和給予反轉，得到，形式化表示為，這就實現了整個反轉。例如，原字符串為，，輸出結果為。同單詞翻轉輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變，句子中單詞以空格符隔開。 July 程序員編程藝術：面試和算法心得題目及習題旋轉字符串題目描述給定一個字符串，要求把字符串前面的若干個字符移動到字符串的尾部，如...

Betta 2019-08-14 12:09 評論0 收藏0
July 算法習題 - 字符串4（全排列和全組合）

摘要：求字符串的全排列字符串的全排列設計一個算法，輸出一個字符串字符的全排列。的做法沒有結果的，都是在一個字符串上進行的操作。字符串的全組合輸入三個字符，則它們的組合有。因此可以循環字符串長度，然后輸出對應代表的組合即可。求字符串的全排列字符串的全排列設計一個算法，輸出一個字符串字符的全排列。比如，String = abc 輸出是abc,bac,cab,bca,cba,...

tuniutech 2019-08-14 12:11 評論0 收藏0
字符串的全排列

摘要：問題輸入一個字符串按字典序打印出該字符串中字符的所有排列。如此遞歸處理，從而得到所有字符的全排列。記斐波那契數列的第位這件事為，則有。其中，表示去掉那個開頭字符的剩余字符串的全排列。問題輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串abc,則打印出由字符a,b,c所能排列出來的所有字符串abc,acb,bac,bca,cab和cba。地址：https://...

sunny5541 2019-08-23 11:38 評論0 收藏0