資訊專欄INFORMATION COLUMN
摘要：反轉(zhuǎn)上述步驟得到的結(jié)果字符串，即反轉(zhuǎn)字符串的兩部分和給予反轉(zhuǎn)，得到，形式化表示為，這就實(shí)現(xiàn)了整個(gè)反轉(zhuǎn)。例如，原字符串為，，輸出結(jié)果為。同單詞翻轉(zhuǎn)輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變，句子中單詞以空格符隔開。
旋轉(zhuǎn)字符串 題目描述July 程序員編程藝術(shù)：面試和算法心得題目及習(xí)題
給定一個(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è)問題，換一個(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)問題。
例如，字符串 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)。
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--; } }
這就是把字符串分為兩個(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相連即可。如圖
這里需要注意的是指針要記錄鏈接位置，不要斷鏈。
// S = AB S" =ATBT
public Node solution(Node phead, int k){
Node p = phead;
int i = 1; // A 部分反轉(zhuǎn)次數(shù)
int j = 1; // B部分反轉(zhuǎn)次數(shù)
if(p!=null){
// A 部分反轉(zhuǎn)
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部分反轉(zhuǎn)結(jié)束，p指向結(jié)果的頭指針，q指向B部分的第一個(gè)元素
// B 部分反轉(zhuǎn)
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部分反轉(zhuǎn)結(jié)束，q指向結(jié)果的頭指針
//連接AB兩部分
phead.next = q;
}
return p;
}
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”。
public void solution(char[]s){
int start = 0;
for(int i=0;i
字符串包含
給定兩個(gè)分別由字母組成的字符串 A 和字符串 B，字符串 B 的長(zhǎng)度比字符串 A 短。請(qǐng)問，如何最快地判斷字符串 B 中所有字母是否都在字符串 A 里？
為了簡(jiǎn)單起見，我們規(guī)定輸入的字符串只包含大寫英文字母，請(qǐng)實(shí)現(xiàn)函數(shù) bool StringContains(string &A, string &B)
比如，如果是下面兩個(gè)字符串：
String 1：ABCD
String 2：BAD
答案是 true，即 String2 里的字母在 String1 里也都有，或者說 String2 是 String1 的真子集。
如果是下面兩個(gè)字符串：
String 1：ABCD
String 2：BCE
答案是 false，因?yàn)樽址?String2 里的 E 字母不在字符串 String1 里。
同時(shí)，如果 string1：ABCD，string 2：AA，同樣返回 true。
解題思路
可以構(gòu)建一個(gè)hash表，26位的數(shù)組，可以先把長(zhǎng)字符串 a 中的所有字符都放入一個(gè) Hashtable 里，比如a 放入 hash[0], d放入 hash3. 然后輪詢短字符串 b，看短字符串 b 的每個(gè)字符是否都在 Hashtable 里，如果都存在，說明長(zhǎng)字符串 a 包含短字符串 b，否則，說明不包含。
這樣時(shí)間復(fù)雜度O(n+m),空間復(fù)雜度O(n)
還有一個(gè)更簡(jiǎn)單的方法，時(shí)間復(fù)雜度O(n+m),空間復(fù)雜度O(1)
用到了|和& 操作，補(bǔ)充下：
0001 | 0010 = 0011
0010 & 0001 = 0000
0111 & 0100 = 0100
boolean solution(String a, String b){
int hash = 0;
// 對(duì)字符串A，用位運(yùn)算計(jì)算一個(gè)簽名
for(int i=0;i
變位詞
編程珠璣關(guān)于變位詞
如果兩個(gè)字符串的字符一樣，但是順序不一樣，被認(rèn)為是兄弟字符串，比如 bad 和 adb 即為兄弟字符串，現(xiàn)提供一個(gè)字符串，如何在字典中迅速找到它的兄弟字符串，請(qǐng)描述數(shù)據(jù)結(jié)構(gòu)和查詢過程。
解題思路：使用散列表 (Hash), 判斷字符出現(xiàn)次數(shù).
哈希表
(1)先創(chuàng)建hashmap，key是字符串的字符，value:統(tǒng)計(jì)字符串1中出現(xiàn)的次數(shù)；
(2)將哈希表掃描第二個(gè)字符串時(shí)，掃描到每個(gè)字符時(shí)候，為哈希表減去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;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64326.html
摘要：求字符串的全排列字符串的全排列設(shè)計(jì)一個(gè)算法，輸出一個(gè)字符串字符的全排列。的做法沒有結(jié)果的，都是在一個(gè)字符串上進(jìn)行的操作。字符串的全組合輸入三個(gè)字符，則它們的組合有。因此可以循環(huán)字符串長(zhǎng)度，然后輸出對(duì)應(yīng)代表的組合即可。 求字符串的全排列 字符串的全排列 設(shè)計(jì)一個(gè)算法，輸出一個(gè)字符串字符的全排列。 比如，String = abc 輸出是abc,bac,cab,bca,cba,...
摘要：判斷一條單向鏈表是不是回文解法可以借助棧，將遍歷到的前半段鏈表節(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)換成整...
摘要：遇到問題查查，看看，大神的講解問問島胖君下面是我最近整理出來的關(guān)于字符串的文章的怎么翻譯匯集目錄非常希望強(qiáng)化博客的功能，比如分類，置頂。 雖是讀書筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 最近在看算法和語言，基本屬于看知識(shí) --> java實(shí)現(xiàn) --> 整理blog 這個(gè)路線。 遇到問題查查st...
摘要：面試算法實(shí)踐與國(guó)外大廠習(xí)題指南翻譯自維護(hù)的倉庫，包含了在線練習(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ù)的倉庫 interviews，包含了在線練習(xí)、算法概述與大廠習(xí)題實(shí)戰(zhàn)等內(nèi)容。筆者發(fā)現(xiàn)正好和...
閱讀 1563·2021-11-17 09:33
閱讀 1113·2021-11-12 10:36
閱讀 2425·2019-08-30 15:54
閱讀 2449·2019-08-30 13:14
閱讀 2924·2019-08-26 14:05
閱讀 3300·2019-08-26 11:32
閱讀 3012·2019-08-26 10:09
閱讀 3005·2019-08-26 10:09
