面試-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);
}
㈡ 非對稱加密演算法 (RSA、DSA、ECC、DH)
非對稱加密需要兩個密鑰：公鑰(publickey) 和私鑰 (privatekey)。公鑰和私鑰是一對，如果用公鑰對數據加密，那麼只能用對應的私鑰解密。如果用私鑰對數據加密，只能用對應的公鑰進行解密。因為加密和解密用的是不同的密鑰，所以稱為非對稱加密。
非對稱加密演算法的保密性好，它消除了最終用戶交換密鑰的需要。但是加解密速度要遠遠慢於對稱加密，在某些極端情況下，甚至能比對稱加密慢上1000倍。
演算法強度復雜、安全性依賴於演算法與密鑰但是由於其演算法復雜，而使得加密解密速度沒有對稱加密解密的速度快。對稱密碼體制中只有一種密鑰，並且是非公開的，如果要解密就得讓對方知道密鑰。所以保證其安全性就是保證密鑰的安全，而非對稱密鑰體制有兩種密鑰，其中一個是公開的，這樣就可以不需要像對稱密碼那樣傳輸對方的密鑰了。這樣安全性就大了很多。
RSA、Elgamal、背包演算法、Rabin、D-H、ECC (橢圓曲線加密演算法)。使用最廣泛的是 RSA 演算法，Elgamal 是另一種常用的非對稱加密演算法。
收信者是唯一能夠解開加密信息的人，因此收信者手裡的必須是私鑰。發信者手裡的是公鑰，其它人知道公鑰沒有關系，因為其它人發來的信息對收信者沒有意義。
客戶端需要將認證標識傳送給伺服器，此認證標識 (可能是一個隨機數) 其它客戶端可以知道，因此需要用私鑰加密，客戶端保存的是私鑰。伺服器端保存的是公鑰，其它伺服器知道公鑰沒有關系，因為客戶端不需要登錄其它伺服器。
數字簽名是為了表明信息沒有受到偽造，確實是信息擁有者發出來的，附在信息原文的後面。就像手寫的簽名一樣，具有不可抵賴性和簡潔性。
簡潔性：對信息原文做哈希運算，得到消息摘要，信息越短加密的耗時越少。
不可抵賴性：信息擁有者要保證簽名的唯一性，必須是唯一能夠加密消息摘要的人，因此必須用私鑰加密 (就像字跡他人無法學會一樣)，得到簽名。如果用公鑰，那每個人都可以偽造簽名了。
問題起源：對1和3，發信者怎麼知道從網上獲取的公鑰就是真的？沒有遭受中間人攻擊？
這樣就需要第三方機構來保證公鑰的合法性，這個第三方機構就是 CA (Certificate Authority)，證書中心。
CA 用自己的私鑰對信息原文所有者發布的公鑰和相關信息進行加密，得出的內容就是數字證書。
信息原文的所有者以後發布信息時，除了帶上自己的簽名，還帶上數字證書，就可以保證信息不被篡改了。信息的接收者先用 CA給的公鑰解出信息所有者的公鑰，這樣可以保證信息所有者的公鑰是真正的公鑰，然後就能通過該公鑰證明數字簽名是否真實了。
RSA 是目前最有影響力的公鑰加密演算法，該演算法基於一個十分簡單的數論事實：將兩個大素數相乘十分容易，但想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰，即公鑰，而兩個大素數組合成私鑰。公鑰是可發布的供任何人使用，私鑰則為自己所有，供解密之用。
A 要把信息發給 B 為例，確定角色：A 為加密者，B 為解密者。首先由 B 隨機確定一個 KEY，稱之為私鑰，將這個 KEY 始終保存在機器 B 中而不發出來；然後，由這個 KEY 計算出另一個 KEY，稱之為公鑰。這個公鑰的特性是幾乎不可能通過它自身計算出生成它的私鑰。接下來通過網路把這個公鑰傳給 A，A 收到公鑰後，利用公鑰對信息加密，並把密文通過網路發送到 B，最後 B 利用已知的私鑰，就能對密文進行解碼了。以上就是 RSA 演算法的工作流程。
由於進行的都是大數計算，使得 RSA 最快的情況也比 DES 慢上好幾倍，無論是軟體還是硬體實現。速度一直是 RSA 的缺陷。一般來說只用於少量數據加密。RSA 的速度是對應同樣安全級別的對稱密碼演算法的1/1000左右。
比起 DES 和其它對稱演算法來說，RSA 要慢得多。實際上一般使用一種對稱演算法來加密信息，然後用 RSA 來加密比較短的公鑰，然後將用 RSA 加密的公鑰和用對稱演算法加密的消息發送給接收方。
這樣一來對隨機數的要求就更高了，尤其對產生對稱密碼的要求非常高，否則的話可以越過 RSA 來直接攻擊對稱密碼。
和其它加密過程一樣，對 RSA 來說分配公鑰的過程是非常重要的。分配公鑰的過程必須能夠抵擋中間人攻擊。假設 A 交給 B 一個公鑰，並使 B 相信這是A 的公鑰，並且 C 可以截下 A 和 B 之間的信息傳遞，那麼 C 可以將自己的公鑰傳給 B，B 以為這是 A 的公鑰。C 可以將所有 B 傳遞給 A 的消息截下來，將這個消息用自己的密鑰解密，讀這個消息，然後將這個消息再用 A 的公鑰加密後傳給 A。理論上 A 和 B 都不會發現 C 在偷聽它們的消息，今天人們一般用數字認證來防止這樣的攻擊。
(1) 針對 RSA 最流行的攻擊一般是基於大數因數分解。1999年，RSA-155 (512 bits) 被成功分解，花了五個月時間（約8000 MIPS 年）和224 CPU hours 在一台有3.2G 中央內存的 Cray C916計算機上完成。
RSA-158 表示如下：
2009年12月12日，編號為 RSA-768 (768 bits, 232 digits) 數也被成功分解。這一事件威脅了現通行的1024-bit 密鑰的安全性，普遍認為用戶應盡快升級到2048-bit 或以上。
RSA-768表示如下：
(2) 秀爾演算法
量子計算里的秀爾演算法能使窮舉的效率大大的提高。由於 RSA 演算法是基於大數分解 (無法抵抗窮舉攻擊)，因此在未來量子計算能對 RSA 演算法構成較大的威脅。一個擁有 N 量子位的量子計算機，每次可進行2^N 次運算，理論上講，密鑰為1024位長的 RSA 演算法，用一台512量子比特位的量子計算機在1秒內即可破解。
DSA (Digital Signature Algorithm) 是 Schnorr 和 ElGamal 簽名演算法的變種，被美國 NIST 作為 DSS (DigitalSignature Standard)。 DSA 是基於整數有限域離散對數難題的。
簡單的說，這是一種更高級的驗證方式，用作數字簽名。不單單只有公鑰、私鑰，還有數字簽名。私鑰加密生成數字簽名，公鑰驗證數據及簽名，如果數據和簽名不匹配則認為驗證失敗。數字簽名的作用就是校驗數據在傳輸過程中不被修改，數字簽名，是單向加密的升級。
橢圓加密演算法（ECC）是一種公鑰加密演算法，最初由 Koblitz 和 Miller 兩人於1985年提出，其數學基礎是利用橢圓曲線上的有理點構成 Abel 加法群上橢圓離散對數的計算困難性。公鑰密碼體制根據其所依據的難題一般分為三類：大整數分解問題類、離散對數問題類、橢圓曲線類。有時也把橢圓曲線類歸為離散對數類。
ECC 的主要優勢是在某些情況下它比其他的方法使用更小的密鑰 (比如 RSA)，提供相當的或更高等級的安全。ECC 的另一個優勢是可以定義群之間的雙線性映射，基於 Weil 對或是 Tate 對；雙線性映射已經在密碼學中發現了大量的應用，例如基於身份的加密。不過一個缺點是加密和解密操作的實現比其他機制花費的時間長。
ECC 被廣泛認為是在給定密鑰長度的情況下，最強大的非對稱演算法，因此在對帶寬要求十分緊的連接中會十分有用。
比特幣錢包公鑰的生成使用了橢圓曲線演算法，通過橢圓曲線乘法可以從私鑰計算得到公鑰， 這是不可逆轉的過程。
https://github.com/esxgx/easy-ecc
Java 中 Chipher、Signature、KeyPairGenerator、KeyAgreement、SecretKey 均不支持 ECC 演算法。
https://www.jianshu.com/p/58c1750c6f22
DH，全稱為"Diffie-Hellman"，它是一種確保共享 KEY 安全穿越不安全網路的方法，也就是常說的密鑰一致協議。由公開密鑰密碼體制的奠基人 Diffie 和 Hellman 所提出的一種思想。簡單的說就是允許兩名用戶在公開媒體上交換信息以生成"一致"的、可以共享的密鑰。也就是由甲方產出一對密鑰 (公鑰、私鑰)，乙方依照甲方公鑰產生乙方密鑰對 (公鑰、私鑰)。
以此為基線，作為數據傳輸保密基礎，同時雙方使用同一種對稱加密演算法構建本地密鑰 (SecretKey) 對數據加密。這樣，在互通了本地密鑰 (SecretKey) 演算法後，甲乙雙方公開自己的公鑰，使用對方的公鑰和剛才產生的私鑰加密數據，同時可以使用對方的公鑰和自己的私鑰對數據解密。不單單是甲乙雙方兩方，可以擴展為多方共享數據通訊，這樣就完成了網路交互數據的安全通訊。
具體例子可以移步到這篇文章： 非對稱密碼之DH密鑰交換演算法
參考：
https://blog.csdn.net/u014294681/article/details/86705999
https://www.cnblogs.com/wangzxblog/p/13667634.html
https://www.cnblogs.com/taoxw/p/15837729.html
https://www.cnblogs.com/fangfan/p/4086662.html
https://www.cnblogs.com/utank/p/7877761.html
https://blog.csdn.net/m0_59133441/article/details/122686815
https://www.cnblogs.com/muliu/p/10875633.html
https://www.cnblogs.com/wf-zhang/p/14923279.html
https://www.jianshu.com/p/7a927db713e4
https://blog.csdn.net/ljx1400052550/article/details/79587133
https://blog.csdn.net/yuanjian0814/article/details/109815473