面試字元串常用演算法

① 面試演算法知識梳理(14) - 數字演算法

面試演算法知識梳理(1) - 排序演算法
面試演算法知識梳理(2) - 字元串演算法第一部分
面試演算法知識梳理(3) - 字元串演算法第二部分
面試演算法知識梳理(4) - 數組第一部分
面試演算法知識梳理(5) - 數組第二部分
面試演算法知識梳理(6) - 數組第三部分
面試演算法知識梳理(7) - 數組第四部分
面試演算法知識梳理(8) - 二分查找演算法及其變型
面試演算法知識梳理(9) - 鏈表演算法第一部分
面試演算法知識梳理(10) - 二叉查找樹
面試演算法知識梳理(11) - 二叉樹演算法第一部分
面試演算法知識梳理(12) - 二叉樹演算法第二部分
面試演算法知識梳理(13) - 二叉樹演算法第三部分

斐波那契數列 滿足下面的通項公式，要求給出 N ，輸出第 N 項的 F(N)

這里介紹兩種解決辦法， 循環演算法 和 矩陣演算法 。循環演算法比較容易理解，就是從 F(0) 開始，根據通項公式，得到下一個斐波那契數列中的數字即可。

對於上面的通項公式，可以用下面的矩陣乘法的形式來表示

一個台階總共有 n 級，如果一次可以跳 1 級，也可以跳 2 級，求總共有多少總跳法。

由於有兩種跳台階方式，因此跳 n 級台階可以轉換為下面兩個問題之和：

這就和之前的斐波那契數列的通項公式相同。

這個問題，需要先總結一下規律，我們根據數字 N 的 位數 來進行分析：

那麼 N>=1 時才會出現 1 ，並且出現 1 的次數為 1 次

在這種情況下，出現 1 的次數等於個位上出現 1 的次數加上十位上出現 1 的個數。

例如，如果要計算百位上 1 出現的次數，它要受到三方面的影響：百位上的數字，百位以下的數字，百位以上的數字。

對於一個二進制數，例如 1010 ，將其減 1 後得到的結果是 1001 ，也就是將最後一個 1 （倒數第二位）及其之後的 0 變成 1 ， 1 變成 0 ，再將該結果與原二進制數相與，也就是 1010 & 1001 = 1000 ，那麼就可以去掉最後一個 1 。

因此，如果需要計算兩個數的二進製表示中有多少位是不同的，可以 先將這兩個數異或 ，那麼不相同的位數就會變成 1 ，之後利用上面的技巧，通過每次去掉最後一個 1 ，來 統計該結果中 1 的個數 ，就可以知道兩個數的二進製表示中有多少是不同的了。

N! 的含義為 1*2*3*...*(N-1)*N ，計算 N! 的十進製表示中，末尾有多少個 0 。

N! 中能產生末尾是 0 的質數組合是 2*5 ，所以 N! 末尾的 0 的個數取決了 2 的個數和 5 的個數的最小值，有因為被 2 整除的數出現的概率大於 5 ，因此 5 出現的次數就是 N! 末尾 0 的個數。因此，該問題就轉換成為計算從 1~N ，每個數可以貢獻 5 的個數，也就是每個數除以 5 的值。

上面的解法需要從 1 到 N 遍歷每一個數，當然還有更加簡便的方法。以 26! 為例，貢獻 5 的數有 5、10、15、20、25 ，一共貢獻了 6 個 5 ，可以理解為 5 的倍數 5、10、15、20、25 貢獻了一個 5 ，而 25 的倍數又貢獻了一個 5 ，得到下面的公式：

首先，讓我們換一個角度考慮，其實這個問題就是求解二進製表示中從最低位開始 0 的個數，因為二進制最低位為 0 代表的是偶數，能夠被 2 整除，所以質因數 2 的個數就是二進製表示中最低位 1 後面的 0 的個數。

因此，我們的實現這就和上面 2.7 中求解質因數 5 的個數是一樣的。

最大公約數 的定義為 兩個或多個整數的共有約數中最大的一個 。這里採用的是 更相止損法 ，其操作步驟為：

則第一步中約掉的若干個 2 與第二步中等數的乘積就是所求的最大公約數。

有限小數或者無限循環小數都可以轉化為分數，例如：

在 http://blog.csdn.net/flyfish1986/article/details/47783545 這邊文章中，詳細地描述了該題的解決思路，核心思想就是將原小數分為 有限部分 和 無限循環小數 部分，對於這兩部分別進行處理。

② 面試會出哪些經典演算法題

如下：

1、排序演算法∶快速排序、歸並排序、計數排序

2、搜索演算法∶回溯、遞歸、剪枝技巧

3、圖論∶最短路、最小生成樹、網路流建模

4、動態規劃：背包問題、最長子序列、計數問題

5、基礎技巧：分治、倍增、二分、貪心

6、數組與鏈表：單/雙向鏈表、跳舞鏈

7、棧與隊列

8、樹與圖：最近公共祖先、並查集

9、哈希表

10、堆：大/小根堆、可並堆

11、字元串∶字典樹、後綴樹

演算法簡介：

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。

如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。

演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。

形式化演算法的概念部分源自嘗試解決希爾伯特提出的判定問題，並在其後嘗試定義有效計算性或者有效方法中成形。

這些嘗試包括庫爾特·哥德爾、Jacques Herbrand和斯蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義為形式化演算法的情況。

③ 面試演算法題：你的任務就是計算出長度為n的字元串(只包含『A』、『B』和『C』)，有多少個是暗黑字元串。

程序肯定不是判斷一個字元串是純潔的還是黑暗的。從現有的題目描述看，程序和題目沒有關系。

題目是否不全？

④ 大公司筆試面試有哪些經典演算法題目

大公司的筆試面試一般是針對你所面試的崗位進行一些專業知識的考核，不會出現想考公員裡面的行測似得，當然也有哪些逆向思維的計算題。

⑤ 面試題 描述java中字元串的比較方式有哪些

java中的字元串比較方法：
1）string1.equals(string2)
2） str1==str2 。
java中字元串的比較是==比較引用，equals 比較值的做法。但是不同的聲明方法字元串的比較結果也是不同的。
例如： String str1=new String("a");
String str2=new String("a");
str1==str2 輸出false
str1.equals(str2) 輸出true
而如果這樣聲明
String str1="a";
String str2="a";
str1==str2 輸出true
str1.equals(str2) 輸出true
這是因為 equals 方法本來也是比較引用的字元串類在實現的時候重寫了該方法。
第一種聲明方法等於是聲明了兩個對象，用』==『比較是時候比較的是引用輸出的是false 由於他們的值相同用equals的時候就比較的是值了，輸出true。

第二種情況不是因為比較有與第一種有差異，而是因為聲明有差異，第二種聲明方法在聲明的時候有堆或堆棧 共用的現象，也就是說
在聲明的時候如果如果聲明為類屬性他會檢查在堆棧中有沒有與現在聲明的是相同結構的字元串。如果有就直接將地址指向已有內存地址。聲明在方法內部的局部變
量原理一樣只不過他是堆棧共享。

⑥ 大公司筆試面試有哪些經典演算法題目

1、二維數組中的查找

具體例題：如果一個數字序列逆置之後跟原序列是一樣的就稱這樣的數字序列為迴文序列。例如：{1, 2, 1}, {15, 78, 78, 15} , {112} 是迴文序列, {1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是迴文序列。現在給出一個數字序列，允許使用一種轉換操作：選擇任意兩個相鄰的數，然後從序列移除這兩個數，並用這兩個數字的和插入到這兩個數之前的位置(只插入一個和)。現在對於所給序列要求出最少需要多少次操作可以將其變成迴文序列？

⑦ 測試開發面試必知演算法

測試開發的技能之一就是需要掌握一些開發的語言，而針對於考察開發語言，業界內比較容易採用的方式就是考察各種演算法。在此做一個簡單的總結（最近比較喜歡玩Python，所以都是以Python為例子，其它的語言類推。）

冒泡排序

冒泡排序演算法的運作如下：（從後往前）
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
針對所有的元素重復以上的步驟，除了最後一個。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

實例：對列表 [2, 8, 4, 7, 5, 9, 0]進行冒泡排序

遞歸

遞歸過程一般通過函數或子過程來實現。遞歸方法：在函數或子過程的內部，直接或者間接地調用自己的演算法。

實例：要計算1-10的10位數字的乘積，直觀的演算法是1 2 3 4 5 6 7 8 9，利用遞歸則思路是循環執行n*n-1,直到n=1時

二叉樹遍歷演算法
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
⑴訪問結點本身（N），
⑵遍歷該結點的左子樹（L），
⑶遍歷該結點的右子樹（R）。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。

二叉樹的節點表示可以使用

前序遍歷：根節點->左子樹->右子樹
中序遍歷：左子樹->根節點->右子樹
後序遍歷：左子樹->右子樹->根節點

實例：求二叉樹深度和寬度
求深度用遞歸；求寬度用隊列，然後把每層的寬度求出來，找出最大的就是二叉樹的寬度

字元串倒序輸出

思路一：索引的方法

思路二：借組列表進行翻轉

後續還有的話會繼續添加的。

⑧ java面試有哪些演算法

面試-java演算法題：
1.編寫一個程序，輸入n,求n！（用遞歸的方式實現）。
public static long fac(int n){ if(n<=0) return 0; else if(n==1) return 1; else return n*fac(n-1);
} public static void main(String [] args) {
System.out.println(fac(6));
}
2.編寫一個程序，有1，2,3,4個數字，能組成多少個互不相同且無重復數字的三位數？都是多少？
public static void main(String [] args) { int i, j, k; int m=0; for(i=1;i<=4;i++) for(j=1;j<=4;j++) for(k=1;k<=4;k++){ if(i!=j&&k!=j&&i!=k){
System.out.println(""+i+j+k);
m++;
}
}
System.out.println("能組成："+m+"個");
}
3.編寫一個程序，將text1.txt文件中的單詞與text2.txt文件中的單詞交替合並到text3.txt文件中。text1.txt文件中的單詞用回車符分隔，text2.txt文件中用回車或空格進行分隔。
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;

public class text{
public static void main(String[] args) throws Exception{
String[] a = getArrayByFile("text1.txt",new char[]{'\n'});
String[] b = getArrayByFile("text2.txt",new char[]{'\n',' '});
FileWriter c = new FileWriter("text3.txt");
int aIndex=0; int bIndex=0;

while(aIndex<a.length){
c.write(a[aIndex++] + "\n");
if(bIndex<b.length)
c.write(b[bIndex++] + "\n");
}

while(bIndex<b.length){
c.write(b[bIndex++] + "\n");
}
c.close();
}

public static String[] getArrayByFile(String filename,char[] seperators) throws Exception{
File f = new File(filename);
FileReader reader = new FileReader(f);
char[] buf = new char[(int)f.length()];
int len = reader.read(buf);
String results = new String(buf,0,len);
String regex = null;
if(seperators.length >1 ){
regex = "" + seperators[0] + "|" + seperators[1];
}else{
regex = "" + seperators[0];
}
return results.split(regex);
}

}
4.639172每個位數上的數字都是不同的，且平方後所得數字的所有位數都不會出現組成它自身的數字。（639172*639172=408540845584），類似於639172這樣的6位數還有幾個？分別是什麼？
這題採用的HashMap結構判斷有無重復，也可以採用下題的數組判斷。
public void selectNum(){
for(long n = 100000; n <= 999999;n++){
if(isSelfRepeat(n)) //有相同的數字，則跳過
continue;
else if(isPingFangRepeat(n*n,n)){ //該數的平方中是否有與該數相同的數字
continue;
} else{ //符合條件，則列印 System.out.println(n);
}
}
} public boolean isSelfRepeat(long n){
HashMap<Long,String> m=new HashMap<Long,String>(); //存儲的時候判斷有無重復值
while(n!=0){ if(m.containsKey(n%10)){ return true;
} else{
m.put(n%10,"1");
}
n=n/10;
} return false;
} public boolean isPingFangRepeat(long pingfang,long n){
HashMap<Long,String> m=new HashMap<Long,String>(); while(n!=0){
m.put(n%10,"1");
n=n/10;
} while(pingfang!=0){ if(m.containsKey(pingfang%10)){ return true;
}
pingfang=pingfang/10;
} return false;
} public static void main(String args[]){ new test().selectNum();
}
5.比如，968548+968545=321732732它的答案里沒有前面兩個數里的數字，有多少這樣的6位數。
public void selectNum(){
for(int n = 10; n <= 99;n++){
for(int m = 10; m <= 99;m++){ if(isRepeat(n,m)){ continue;
} else{
System.out.println("組合是"+n+","+m);
}
}
}
} public boolean isRepeat(int n,int m){ int[] a={0,0,0,0,0,0,0,0,0,0}; int s=n+m; while(n!=0){
a[n%10]=1;
n=n/10;
} while(m!=0){
a[m%10]=1;
m=m/10;
} while(s!=0){ if(a[s%10]==1){ return true;
}
s=s/10;
} return false;
} public static void main(String args[]){ new test().selectNum();
}
6.給定String,求此字元串的單詞數量。字元串不包括標點，大寫字母。例如 String str="hello world hello hi";單詞數量為3，分別是：hello world hi。
public static void main(String [] args) { int count = 0;
String str="hello world hello hi";
String newStr="";
HashMap<String,String> m=new HashMap<String,String>();
String [] a=str.split(" "); for (int i=0;i<a.length;i++){ if(!m.containsKey(a[i])){
m.put(a[i],"1");
count++;
newStr=newStr+" "+a[i];
}
}
System.out.println("這段短文單詞的個數是："+count+","+newStr);
}
7.寫出程序運行結果。
public class Test1 { private static void test(int[]arr) { for (int i = 0; i < arr.length; i++) { try { if (arr[i] % 2 == 0) { throw new NullPointerException();
} else {
System.out.print(i);
}
} catch (Exception e) {
System.out.print("a ");
} finally {
System.out.print("b ");
}
}
}
public static void main(String[]args) { try {
test(new int[] {0, 1, 2, 3, 4, 5});
} catch (Exception e) {
System.out.print("c ");
}
}

}
運行結果：a b 1b a b 3b a b 5b
public class Test1 { private static void test(int[]arr) { for (int i = 0; i < arr.length; i++) { try { if (arr[i] % 2 == 0) { throw new NullPointerException();
} else {
System.out.print(i);
}
}
finally {
System.out.print("b ");
}
}
}
public static void main(String[]args) { try {
test(new int[] {0, 1, 2, 3, 4, 5});
} catch (Exception e) {
System.out.print("c ");
}
}

}
運行結果：b c
8.單詞數
統計一篇文章里不同單詞的總數。
Input
有多組數據，每組一行，每組就是一篇小文章。每篇小文章都是由小寫字母和空格組成，沒有標點符號，遇到#時表示輸入結束。
Output
每組值輸出一個整數，其單獨成行，該整數代表一篇文章里不同單詞的總數。
Sample Input
you are my friend
#
Sample Output
4
public static void main(String [] args) {
List<Integer> countList=new ArrayList<Integer>(); int count;
HashMap<String,String> m;
String str; //讀取鍵盤輸入的一行（以回車換行為結束輸入） String[] a;

Scanner in=new Scanner(System.in);
while( !(str=in.nextLine()).equals("#") ){
a=str.split(" ");
m=new HashMap<String,String>();
count = 0; for (int i=0;i<a.length;i++){ if(!m.containsKey(a[i]) && (!a[i].equals(""))){
m.put(a[i],"1");
count++;
}
}
countList.add(count);
}s for(int c:countList)
System.out.println(c);
}

⑨ 面試難點！常用演算法技巧之「滑動窗口」

滑動窗口，顧名思義，就是有一個大小可變的窗口，左右兩端方向一致的向前滑動（右端固定，左端滑動；左端固定，右端滑動）。

可以想像成隊列，一端在push元素，另一端在pop元素，如下所示：

假設有數組[a b c d e f g h]
一個大小為3的滑動窗口在其上滑動，則有:

1、單層循環

2、雙層循環

模板只是一個解題思路，具體的題目可能需要具體分析，但是大體框架是不變的。
記住: 多刷題，多總結，是王道

1、最長不含重復字元的子字元串

2、絕對差不超過限制的最長連續子數組

3、無重復字元的最長子串

4、替換後的最長重復字元

滑動窗口演算法就是用以解決數組/字元串的子元素問題
滑動窗口演算法可以將嵌套的for循環問題，轉換為單循環問題，降低時間復雜度

生命不止堅毅魚奮斗，有夢想才是有意義的追求
給大家推薦一個免費的學習交流群：
最後，祝大家早日學有所成，拿到滿意offer，快速升職加薪，走上人生巔峰。
Java開發交流君樣：756584822

⑩ 經典C語言面試演算法題

經典C語言面試演算法題

1.寫一個函數,它的原形是int continumax(char *outputstr,char *intputstr)

功能：

在字元串中找出連續最長的數字串，並把這個串的長度返回，並把這個最長數字串付給其中一個函數參數outputstr所指內存。例如："abcd12345ed125ss123456789"的首地址傳給intputstr後，函數將返回

9，outputstr所指的值為123456789。

#include

#include

#include

int FindMax_NumStr(char *outputstr,char *inputstr)

{

char *in = inputstr,*out = outputstr,*temp;

char *final;

int count = 0;

int maxlen = 0;

int i;

while(*in!='')

{

if(*in > 47 && *in < 58)

{

for(temp = in;*in> 47 && *in <58;in++)

count++;

}

else

in++;

if(maxlen < count)

{

maxlen = count;

count = 0;

final = temp;

}

}

for(i =0;i

{

*out = *final;

out++;

final++;

}

*out = '';

return maxlen;

}

void main(void)

{

char input[]="abc123def123456eec123456789dd";

char output[50] = {0};

int maxlen;

maxlen = FindMax_NumStr(output,input);

printf("the str %s ",output);

printf("the maxlen is %d ",maxlen);

}

2.求1000!的未尾有幾個0;

求出1->1000里,能被5整除的數的個數n1,能被25整除的數的個數n2,能被125整除的'數的個數n3,能被625整除的數的個數n4.1000!末尾的零的個數=n1+n2+n3+n4;

只要是末尾是5的數它乘以一個偶數就會出現一個0，而末尾是0的數乘以任何數也都會出現0

而末尾是0的如果是一個0肯定能被5整除，兩個0肯定能被25整數，以此類推3個0就能被5的三次方整除，也就是125

1000!就是1-1000數的相乘，能被5整除的所有數分別乘以一個偶數就會出現這些個的0，而例如100，既能被5整除，也能被25整除，所以就是兩個0

1000，既能被5，25，也能被125整除，所以算三個0

例如是10!=1*2*3*4*5*6*7*8*9*10，裡面有兩個數能被5整除，就是10和5，而

5隨便乘以一個偶數就出現一個0，而10乘以其它數也會出現一個0，所以10!會有兩個0

#include

#define NUM 1000

int find5(int num)

{

int ret = 0;

while(num%5==0)

{

num/=5;

ret++;

}

return ret;

}

int main(void)

{

int result = 0;

int i;

for(i=5;i<=NUM;i+=5)

result +=find5(i);

printf("the total zero number is %d ",result);

return 0;

}

3。編寫一個 C 函數，該函數在一個字元串中找到可能的最長的子字元串，且該字元串是由同一字元組成的。

char * search(char *cpSource, char ch)

{

char *cpTemp=NULL, *cpDest=NULL;

int iTemp, iCount=0;

while(*cpSource)

{

if(*cpSource == ch)

{

iTemp = 0;

cpTemp = cpSource;

while(*cpSource == ch)

++iTemp, ++cpSource;

if(iTemp > iCount)

iCount = iTemp, cpDest = cpTemp;

if(!*cpSource)

break;

}

++cpSource;

}

return cpDest;

}