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

資訊專欄INFORMATION COLUMN

July算法習(xí)題 - 字符串1

Betta / 1019人閱讀

摘要:反轉(zhuǎn)上述步驟得到的結(jié)果字符串,即反轉(zhuǎn)字符串的兩部分和給予反轉(zhuǎn),得到,形式化表示為,這就實(shí)現(xiàn)了整個(gè)反轉(zhuǎn)。例如,原字符串為,,輸出結(jié)果為。同單詞翻轉(zhuǎn)輸入一個(gè)英文句子,翻轉(zhuǎn)句子中單詞的順序,但單詞內(nèi)字符的順序不變,句子中單詞以空格符隔開。

</>復(fù)制代碼

  1. July 程序員編程藝術(shù):面試和算法心得題目及習(xí)題

旋轉(zhuǎn)字符串 題目描述

給定一個(gè)字符串,要求把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部,如把字符串 “abcdef” 前面的 2 個(gè)字符"a"和"b"移動(dòng)到字符串的尾部,使得原字符串變成字符串 “cdefab”。請(qǐng)寫一個(gè)函數(shù)完成此功能,要求對(duì)長(zhǎng)度為 n 的字符串操作的時(shí)間復(fù)雜度為 O(n),空間復(fù)雜度為 O(1)。

解題思路:三步反轉(zhuǎn)法

對(duì)于這個(gè)問(wèn)題,換一個(gè)角度思考一下。

將一個(gè)字符串分成 X 和 Y 兩個(gè)部分,在每部分字符串上定義反轉(zhuǎn)操作,如 X^T,即把 X 的所有字符反轉(zhuǎn)(如,X="abc",那么 X^T="cba"),那么就得到下面的結(jié)論:(X^TY^T)^T=YX,顯然就解決了字符串的反轉(zhuǎn)問(wèn)題。

例如,字符串 abcdef ,若要讓 def 翻轉(zhuǎn)到 abc 的前頭,只要按照下述 3 個(gè)步驟操作即可:

首先將原字符串分為兩個(gè)部分,即 X:abc,Y:def;

將 X 反轉(zhuǎn),X->X^T,即得:abc->cba;將 Y 反轉(zhuǎn),Y->Y^T,即得:def->fed。

反轉(zhuǎn)上述步驟得到的結(jié)果字符串 X^TY^T,即反轉(zhuǎn)字符串 cbafed 的兩部分(cba 和 fed)給予反轉(zhuǎn),cbafed 得到 defabc,形式化表示為 (X^TY^T)^T=YX,這就實(shí)現(xiàn)了整個(gè)反轉(zhuǎn)。

</>復(fù)制代碼

  1. java
    public class RotateString {
  2. public void solution(char[]s , int k){
  3. reverse(s,0,k-1);
  4. reverse(s,k,s.length-1);
  5. reverse(s,0,s.length-1);
  6. }
  7. private void reverse(char[]s, int start, int end){
  8. while(start <= end)
  9. {
  10. char temp;
  11. temp = s[end];
  12. s[end] = s[start];
  13. s[start] = temp;
  14. start++;
  15. end--;
  16. }
  17. }

這就是把字符串分為兩個(gè)部分,先各自反轉(zhuǎn)再整體反轉(zhuǎn)的方法,時(shí)間復(fù)雜度為 O(n),空間復(fù)雜度為 O(1),達(dá)到了題目的要求。

習(xí)題 1、鏈表翻轉(zhuǎn)

給出一個(gè)鏈表和一個(gè)數(shù) k,比如,鏈表為 1→2→3→4→5→6,k=2,則翻轉(zhuǎn)后 2→1→6→5→4→3,若 k=3,翻轉(zhuǎn)后 3→2→1→6→5→4,若 k=4,翻轉(zhuǎn)后 4→3→2→1→6→5,用程序?qū)崿F(xiàn)。

有介紹鏈表完全反轉(zhuǎn)

這道題是基于鏈表反轉(zhuǎn),鏈表分成兩部分:AB, 先反轉(zhuǎn)A,然后再反轉(zhuǎn)B,把AB相連即可。如圖

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

</>復(fù)制代碼

  1. // S = AB S" =ATBT
  2. public Node solution(Node phead, int k){
  3. Node p = phead;
  4. int i = 1; // A 部分反轉(zhuǎn)次數(shù)
  5. int j = 1; // B部分反轉(zhuǎn)次數(shù)
  6. if(p!=null){
  7. // A 部分反轉(zhuǎn)
  8. Node q = p.next;
  9. p.next = null;
  10. while(q != null && i< k ){
  11. Node r = q.next;
  12. q.next = p;
  13. p = q;
  14. q = r;
  15. i++;
  16. } // A部分反轉(zhuǎn)結(jié)束,p指向結(jié)果的頭指針,q指向B部分的第一個(gè)元素
  17. // B 部分反轉(zhuǎn)
  18. Node qnext = q.next;
  19. q.next = null;
  20. while(qnext != null && j< n-k){
  21. Node r = qnext.next;
  22. qnext.next = q;
  23. q = qnext;
  24. qnext = r;
  25. j++;
  26. }// B部分反轉(zhuǎn)結(jié)束,q指向結(jié)果的頭指針
  27. //連接AB兩部分
  28. phead.next = q;
  29. }
  30. return p;
  31. }
2、編寫程序

在原字符串中把字符串尾部的 m 個(gè)字符移動(dòng)到字符串的頭部,要求:長(zhǎng)度為 n 的字符串操作時(shí)間復(fù)雜度為 O(n),空間復(fù)雜度為 O(1)。 例如,原字符串為 ”Ilovebaofeng”,m=7,輸出結(jié)果為:”baofengIlove”。

同1

3、單詞翻轉(zhuǎn)

輸入一個(gè)英文句子,翻轉(zhuǎn)句子中單詞的順序,但單詞內(nèi)字符的順序不變,句子中單詞以空格符隔開。為簡(jiǎn)單起見,標(biāo)點(diǎn)符號(hào)和普通字母一樣處理。例如,輸入 “I am a student.”,則輸出 “student. a am I”。

</>復(fù)制代碼

  1. public void solution(char[]s){
  2. int start = 0;
  3. for(int i=0;i
  4. 字符串包含
  5. 給定兩個(gè)分別由字母組成的字符串 A 和字符串 B,字符串 B 的長(zhǎng)度比字符串 A 短。請(qǐng)問(wèn),如何最快地判斷字符串 B 中所有字母是否都在字符串 A 里?

  6. 為了簡(jiǎn)單起見,我們規(guī)定輸入的字符串只包含大寫英文字母,請(qǐng)實(shí)現(xiàn)函數(shù) bool StringContains(string &A, string &B)

  7. 比如,如果是下面兩個(gè)字符串:

  8. </>復(fù)制代碼

    1. String 1:ABCD
    2. String 2:BAD
  9. 答案是 true,即 String2 里的字母在 String1 里也都有,或者說(shuō) String2 是 String1 的真子集。

  10. 如果是下面兩個(gè)字符串:

  11. </>復(fù)制代碼

    1. String 1:ABCD
    2. String 2:BCE
  12. 答案是 false,因?yàn)樽址?String2 里的 E 字母不在字符串 String1 里。

  13. 同時(shí),如果 string1:ABCD,string 2:AA,同樣返回 true

  14. 解題思路
  15. 可以構(gòu)建一個(gè)hash表,26位的數(shù)組,可以先把長(zhǎng)字符串 a 中的所有字符都放入一個(gè) Hashtable 里,比如a 放入 hash[0], d放入 hash3. 然后輪詢短字符串 b,看短字符串 b 的每個(gè)字符是否都在 Hashtable 里,如果都存在,說(shuō)明長(zhǎng)字符串 a 包含短字符串 b,否則,說(shuō)明不包含。

  16. 這樣時(shí)間復(fù)雜度O(n+m),空間復(fù)雜度O(n)

  17. 還有一個(gè)更簡(jiǎn)單的方法,時(shí)間復(fù)雜度O(n+m),空間復(fù)雜度O(1)

  18. 用到了|& 操作,補(bǔ)充下:

  19. </>復(fù)制代碼

    1. 0001 | 0010 = 0011
    2. 0010 & 0001 = 0000
    3. 0111 & 0100 = 0100
  20. </>復(fù)制代碼

    1. boolean solution(String a, String b){
    2. int hash = 0;
    3. // 對(duì)字符串A,用位運(yùn)算計(jì)算一個(gè)簽名
    4. for(int i=0;i
    5. 變位詞
    6. 編程珠璣關(guān)于變位詞

    7. 如果兩個(gè)字符串的字符一樣,但是順序不一樣,被認(rèn)為是兄弟字符串,比如 bad 和 adb 即為兄弟字符串,現(xiàn)提供一個(gè)字符串,如何在字典中迅速找到它的兄弟字符串,請(qǐng)描述數(shù)據(jù)結(jié)構(gòu)和查詢過(guò)程。

    8. 解題思路:使用散列表 (Hash), 判斷字符出現(xiàn)次數(shù).

    9. 哈希表

    10. (1)先創(chuàng)建hashmap,key是字符串的字符,value:統(tǒng)計(jì)字符串1中出現(xiàn)的次數(shù);

    11. (2)將哈希表掃描第二個(gè)字符串時(shí),掃描到每個(gè)字符時(shí)候,為哈希表減去1,
    12. (3)如果最后哈希表所有的值都為0,則為變位詞,否則不是變位詞

    13. </>復(fù)制代碼

      1. public static boolean checkBrother_2(char[] s1, char[] s2){
      2. HashMap recordTable = new HashMap();
      3. for(char s: s1){
      4. if(!recordTable.containsKey(s))
      5. recordTable.put(s, 1);
      6. else{
      7. recordTable.put(s, recordTable.get(s) + 1);
      8. }
      9. }
      10. for(char s : s2){
      11. recordTable.put(s, recordTable.get(s) - 1);
      12. }
      13. int count = 0;
      14. Collection c = recordTable.values();
      15. Iterator iter = c.iterator();
      16. while(iter.hasNext()){
      17. count += Math.abs((Integer) iter.next());
      18. }
      19. if(count == 0)
      20. return true;
      21. else
      22. return false;
      23. }

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/64326.html

相關(guān)文章

  • July 算法習(xí)題 - 符串4(全排列和全組合)

    摘要:求字符串的全排列字符串的全排列設(shè)計(jì)一個(gè)算法,輸出一個(gè)字符串字符的全排列。的做法沒(méi)有結(jié)果的,都是在一個(gè)字符串上進(jìn)行的操作。字符串的全組合輸入三個(gè)字符,則它們的組合有。因此可以循環(huán)字符串長(zhǎng)度,然后輸出對(duì)應(yīng)代表的組合即可。 求字符串的全排列 字符串的全排列 設(shè)計(jì)一個(gè)算法,輸出一個(gè)字符串字符的全排列。 比如,String = abc 輸出是abc,bac,cab,bca,cba,...

    tuniutech 評(píng)論0 收藏0
  • July 算法習(xí)題 - 符串2 + Leetcode 8,9

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

    timger 評(píng)論0 收藏0
  • 符串處理文章outline

    摘要:遇到問(wèn)題查查,看看,大神的講解問(wèn)問(wèn)島胖君下面是我最近整理出來(lái)的關(guān)于字符串的文章的怎么翻譯匯集目錄非常希望強(qiáng)化博客的功能,比如分類,置頂。 雖是讀書筆記,但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 最近在看算法和語(yǔ)言,基本屬于看知識(shí) --> java實(shí)現(xiàn) --> 整理blog 這個(gè)路線。 遇到問(wèn)題查查st...

    Karuru 評(píng)論0 收藏0
  • 符串的全排列

    摘要:?jiǎn)栴}輸入一個(gè)字符串按字典序打印出該字符串中字符的所有排列。如此遞歸處理,從而得到所有字符的全排列。記斐波那契數(shù)列的第位這件事為,則有。其中,表示去掉那個(gè)開頭字符的剩余字符串的全排列。 問(wèn)題 輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來(lái)的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。 地址:https://...

    sunny5541 評(píng)論0 收藏0
  • 面試算法實(shí)踐與國(guó)外大廠習(xí)題指南

    摘要:面試算法實(shí)踐與國(guó)外大廠習(xí)題指南翻譯自維護(hù)的倉(cāng)庫(kù),包含了在線練習(xí)算法概述與大廠習(xí)題實(shí)戰(zhàn)等內(nèi)容。面試算法實(shí)踐與國(guó)外大廠習(xí)題指南在線練習(xí)在線面試編程數(shù)據(jù)結(jié)構(gòu)鏈表即是由節(jié)點(diǎn)組成的線性集合,每個(gè)節(jié)點(diǎn)可以利用指針指向其他節(jié)點(diǎn)。 面試算法實(shí)踐與國(guó)外大廠習(xí)題指南 翻譯自 Kevin Naughton Jr. 維護(hù)的倉(cāng)庫(kù) interviews,包含了在線練習(xí)、算法概述與大廠習(xí)題實(shí)戰(zhàn)等內(nèi)容。筆者發(fā)現(xiàn)正好和...

    genedna 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<