国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

July算法習題 - 字符串1

Betta / 1001人閱讀

摘要：反轉上述步驟得到的結果字符串，即反轉字符串的兩部分和給予反轉，得到，形式化表示為，這就實現了整個反轉。例如，原字符串為，，輸出結果為。同單詞翻轉輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變，句子中單詞以空格符隔開。

  
July 程序員編程藝術：面試和算法心得題目及習題
旋轉字符串 題目描述

給定一個字符串，要求把字符串前面的若干個字符移動到字符串的尾部，如把字符串 “abcdef” 前面的 2 個字符"a"和"b"移動到字符串的尾部，使得原字符串變成字符串 “cdefab”。請寫一個函數完成此功能，要求對長度為 n 的字符串操作的時間復雜度為 O(n)，空間復雜度為 O(1)。

解題思路：三步反轉法

對于這個問題，換一個角度思考一下。

將一個字符串分成 X 和 Y 兩個部分，在每部分字符串上定義反轉操作，如 X^T，即把 X 的所有字符反轉（如，X="abc"，那么 X^T="cba"），那么就得到下面的結論：(X^TY^T)^T=YX，顯然就解決了字符串的反轉問題。

例如，字符串 abcdef ，若要讓 def 翻轉到 abc 的前頭，只要按照下述 3 個步驟操作即可：

首先將原字符串分為兩個部分，即 X:abc，Y:def；

將 X 反轉，X->X^T，即得：abc->cba；將 Y 反轉，Y->Y^T，即得：def->fed。

反轉上述步驟得到的結果字符串 X^TY^T，即反轉字符串 cbafed 的兩部分（cba 和 fed）給予反轉，cbafed 得到 defabc，形式化表示為 (X^TY^T)^T=YX，這就實現了整個反轉。

java
public class RotateString {
    public void solution(char[]s , int k){
        reverse(s,0,k-1);
        reverse(s,k,s.length-1);
        reverse(s,0,s.length-1);
    }
    private void reverse(char[]s, int start, int end){
        while(start <= end)
        {
            char temp;
            temp = s[end];
            s[end] = s[start];
            s[start] = temp;
            start++;
            end--;
        }

    }

這就是把字符串分為兩個部分，先各自反轉再整體反轉的方法，時間復雜度為 O(n)，空間復雜度為 O(1)，達到了題目的要求。

習題 1、鏈表翻轉

給出一個鏈表和一個數 k，比如，鏈表為 1→2→3→4→5→6，k=2，則翻轉后 2→1→6→5→4→3，若 k=3，翻轉后 3→2→1→6→5→4，若 k=4，翻轉后 4→3→2→1→6→5，用程序實現。

有介紹鏈表完全反轉

這道題是基于鏈表反轉，鏈表分成兩部分：AB， 先反轉A,然后再反轉B，把AB相連即可。如圖

這里需要注意的是指針要記錄鏈接位置，不要斷鏈。

    // S = AB S" =ATBT
    public Node solution(Node phead, int k){
        Node p = phead;
        int i = 1; // A 部分反轉次數
        int j = 1; // B部分反轉次數
        if(p!=null){
            // A 部分反轉
            Node q = p.next;
            p.next = null;
            while(q != null && i< k ){              
                Node r = q.next;
                q.next = p;
                p = q;
                q = r;
                i++;
            } // A部分反轉結束，p指向結果的頭指針，q指向B部分的第一個元素

            // B 部分反轉
            Node qnext = q.next;
            q.next = null;
            while(qnext != null && j< n-k){             
                Node r = qnext.next;
                qnext.next = q;
                q = qnext;
                qnext = r;
                j++;
            }// B部分反轉結束，q指向結果的頭指針
            //連接AB兩部分
            phead.next = q;
        }

        return p;
    }
2、編寫程序

在原字符串中把字符串尾部的 m 個字符移動到字符串的頭部，要求：長度為 n 的字符串操作時間復雜度為 O(n)，空間復雜度為 O(1)。 例如，原字符串為 ”Ilovebaofeng”，m=7，輸出結果為：”baofengIlove”。

同1

3、單詞翻轉

輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變，句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。例如，輸入 “I am a student.”，則輸出 “student. a am I”。

    public void solution(char[]s){
        int start = 0;
        for(int i=0;i

字符串包含


給定兩個分別由字母組成的字符串 A 和字符串 B，字符串 B 的長度比字符串 A 短。請問，如何最快地判斷字符串 B 中所有字母是否都在字符串 A 里？



為了簡單起見，我們規定輸入的字符串只包含大寫英文字母，請實現函數 bool StringContains(string &A, string &B)



比如，如果是下面兩個字符串：



String 1：ABCD
String 2：BAD




答案是 true，即 String2 里的字母在 String1 里也都有，或者說 String2 是 String1 的真子集。



如果是下面兩個字符串：



String 1：ABCD
String 2：BCE




答案是 false，因為字符串 String2 里的 E 字母不在字符串 String1 里。



同時，如果 string1：ABCD，string 2：AA，同樣返回 true。


解題思路


可以構建一個hash表，26位的數組，可以先把長字符串 a 中的所有字符都放入一個 Hashtable 里，比如a 放入 hash[0], d放入 hash3. 然后輪詢短字符串 b，看短字符串 b 的每個字符是否都在 Hashtable 里，如果都存在，說明長字符串 a 包含短字符串 b，否則，說明不包含。



這樣時間復雜度O(n+m),空間復雜度O(n)



還有一個更簡單的方法，時間復雜度O(n+m),空間復雜度O(1)



用到了|和& 操作，補充下：



0001 | 0010 = 0011
0010 & 0001 = 0000
0111 & 0100 =  0100




    boolean solution(String a, String b){
        int hash = 0;
        // 對字符串A，用位運算計算一個簽名
        for(int i=0;i

變位詞


編程珠璣關于變位詞



如果兩個字符串的字符一樣，但是順序不一樣，被認為是兄弟字符串，比如 bad 和 adb 即為兄弟字符串，現提供一個字符串，如何在字典中迅速找到它的兄弟字符串，請描述數據結構和查詢過程。



解題思路：使用散列表 (Hash), 判斷字符出現次數.



哈希表



(1)先創建hashmap，key是字符串的字符，value:統計字符串1中出現的次數；

(2)將哈希表掃描第二個字符串時，掃描到每個字符時候，為哈希表減去1，

(3)如果最后哈希表所有的值都為0，則為變位詞，否則不是變位詞



public static boolean checkBrother_2(char[] s1, char[] s2){
    HashMap recordTable = new HashMap();
    for(char s: s1){
        if(!recordTable.containsKey(s))
            recordTable.put(s, 1);
        else{
            recordTable.put(s, recordTable.get(s) + 1);
        }
    }

    for(char s : s2){
        recordTable.put(s, recordTable.get(s) - 1);
    }

    int count = 0;
    Collection c = recordTable.values();
    Iterator iter = c.iterator();

    while(iter.hasNext()){
        count += Math.abs((Integer) iter.next());
    }

    if(count == 0)
        return true;
    else
        return false;
}

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

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

相關文章

  • July 算法習題 - 字符串4（全排列和全組合）

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

    tuniutech 評論0 收藏0

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

    摘要：判斷一條單向鏈表是不是回文解法可以借助棧，將遍歷到的前半段鏈表節點放入棧，后半段每當遍歷到一個，都要與出棧的節點相比較。如果中間出現不相等的情況，則不是回文。 [July 程序員編程藝術：面試和算法心得題目及習題][1] 字符串轉換成整數 also Leetcode 8 String to Integer (atoi) 題目描述 輸入一個由數字組成的字符串，把它轉換成整...

    timger 評論0 收藏0

  • 字符串處理文章outline

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

    Karuru 評論0 收藏0

  • 字符串的全排列

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

    sunny5541 評論0 收藏0

  • 面試算法實踐與國外大廠習題指南

    摘要：面試算法實踐與國外大廠習題指南翻譯自維護的倉庫，包含了在線練習算法概述與大廠習題實戰等內容。面試算法實踐與國外大廠習題指南在線練習在線面試編程數據結構鏈表即是由節點組成的線性集合，每個節點可以利用指針指向其他節點。 面試算法實踐與國外大廠習題指南 翻譯自 Kevin Naughton Jr. 維護的倉庫 interviews，包含了在線練習、算法概述與大廠習題實戰等內容。筆者發現正好和...

    genedna 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<