實用演算法題

1. 前端演算法入門一：刷演算法題常用的JS基礎掃盲

此篇屬於前端演算法入門系列的第一篇，主要介紹常用的 數組方法 、 字元串方法 、 遍歷方法 、 高階函數 、 正則表達式 以及相關 數學知識 。

在尾部追加，類似於壓棧，原數組會變。

在尾部彈出，類似於出棧，原數組會變。數組的 push & pop 可以模擬常見數據結構之一：棧。

在頭部壓入數據，類似於入隊，原數組會變。

在頭部彈出數據，原數組會變。數組的 push（入隊） & shift（出隊） 可以模擬常見數據結構之一：隊列。

concat會在當前數組尾部拼接傳入的數組，然後返回一個新數組，原數組不變。

在數組中尋找該值，找到則返回其下標，找不到則返回-1。

在數組中尋找該值，找到則返回true，找不到則返回false。

將數組轉化成字元串，並返回該字元串，不傳值則默認逗號隔開，原數組不變。

翻轉原數組，並返回已完成翻轉的數組，原數組改變。

從start 開始截取到end，但是不包括end

可參考 MDN：Sort

將數組轉化成字元串，並返回該字元串，逗號隔開，原數組不變。

返回指定索引位置處的字元。類似於數組用中括弧獲取相應下標位置的數據。

類似數組的concat()，用來返回一個合並拼接兩個或兩個以上字元串。原字元串不變。

indexOf,返回一個字元在字元串中首次出現的位置,lastIndexOf返回一個字元在字元串中最後一次出現的位置。

提取字元串的片斷，並把提取的字元串作為新的字元串返回出來。原字元串不變。

使用指定的分隔符將一個字元串拆分為多個子字元串數組並返回，原字元串不變。

match()方法可在字元串內檢索指定的值，或找到一個或多個正則表達式的匹配，並返回一個包含該搜索結果的數組。

注意事項 :如果match方法沒有找到匹配，將返回null。如果找到匹配，則 match方法會把匹配到以數組形式返回，如果正則規則未設置全局修飾符g，則 match方法返回的數組有兩個特性：input和index。input屬性包含整個被搜索的字元串。index屬性包含了在整個被搜索字元串中匹配的子字元串的位置。

replace接收兩個參數，參數一是需要替換掉的字元或者一個正則的匹配規則，參數二，需要替換進去的字元，仔實際的原理當中，參數二，你可以換成一個回調函數。

在目標字元串中搜索與正則規則相匹配的字元，搜索到，則返回第一個匹配項在目標字元串當中的位置，沒有搜索到則返回一個-1。

toLowerCase把字母轉換成小寫，toUpperCase()則是把字母轉換成大寫。

includes、startsWith、endsWith，es6的新增方法，includes 用來檢測目標字元串對象是否包含某個字元，返回一個布爾值，startsWith用來檢測當前字元是否是目標字元串的起始部分，相對的endwith是用來檢測是否是目標字元串的結尾部分。

返回一個新的字元串對象，新字元串等於重復了指定次數的原始字元串。接收一個參數，就是指定重復的次數。原字元串不變。

最常用的for循環，經常用的數組遍歷，也可以遍歷字元串。

while、do while主要的功能是，當滿足while後邊所跟的條件時，來執行相關業務。這兩個的區別是，while會先判斷是否滿足條件，然後再去執行花括弧裡面的任務，而do while則是先執行一次花括弧中的任務，再去執行while條件，判斷下次還是否再去執行do裡面的操作。也就是說 do while至少會執行一次操作 .

拷貝一份遍歷原數組。

for…of是ES6新增的方法，但是for…of不能去遍歷普通的對象， for…of的好處是可以使用break跳出循環。

面試官：說一下 for...in 和 for...of 區別？

返回一個布爾值 。當我們需要判定數組中的元素是否滿足某些條件時，可以使用every / some。這兩個的區別是，every會去判斷判斷數組中的每一項，而 some則是當某一項滿足條件時返回。

rece 從左到右將數組元素做「疊加」處理，返回一個值。receRight 從右到左。

Object.keys方法的參數是一個對象，返回一個數組。該數組的成員都是該對象自身的（而不是繼承的）所有屬性名，且只返回可枚舉的屬性。

Object.getOwnPropertyNames方法與Object.keys類似，也是接受一個對象作為參數，返回一個數組，包含了該對象自身的所有屬性名。但它能返回不可枚舉的屬性。

這里羅列一些我在刷演算法題中遇到的正則表達式，如果有時間可認真學一下正則表達式不要背。

持續更新，敬請期待……

若一個正整數無法被除了1 和它自身之外的任何自然數整除，則稱該數為質數（或素數），否則稱該正整數為合數。

持續更新，敬請期待……

作者：擺草猿
鏈接：https://juejin.cn/post/7087134135193436197

2. 幾種常用的演算法簡介

1、窮舉法窮舉法是最基本的演算法設計策略，其思想是列舉出問題所有的可能解，逐一進行判別，找出滿足條件的解。
窮舉法的運用關鍵在於解決兩個問題：
在運用窮舉法時，容易出現的問題是可能解過多，導致演算法效率很低，這就需要對列舉可能解的方法進行優化。
以題1041--純素數問題為例，從1000到9999都可以看作是可能解，可以通過對所有這些可能解逐一進行判別，找出其中的純素數，但只要稍作分析，就會發現其實可以大幅度地降低可能解的范圍。根據題意易知，個位只可能是3、5、7，再根據題意可知，可以在3、5、7的基礎上，先找出所有的二位純素數，再在二位純素數基礎上找出三位純素數，最後在三位純素數的基礎上找出所有的四位純素數。
2、分治法分治法也是應用非常廣泛的一種演算法設計策略，其思想是將問題分解為若乾子問題，從而可以遞歸地求解各子問題，再綜合出問題的解。
分治法的運用關鍵在於解決三個問題：
我們熟知的如漢諾塔問題、折半查找演算法、快速排序演算法等都是分治法運用的典型案例。
以題1045--Square Coins為例，先對題意進行分析，可設一個函數f(m, n)等於用面值不超過n2的貨幣構成總值為m的方案數，則容易推導出：
f(m, n) = f(m-0*n*n, n-1)+f(m-1*n*n, n-1)+f(m-2*n*n, n-1)+...+f(m-k*n*n, n-1)
這里的k是幣值為n2的貨幣最多可以用多少枚，即k=m/(n*n)。
也很容易分析出，f(m, 1) = f(1, n) = 1
對於這樣的題目，一旦分析出了遞推公式，程序就非常好寫了。所以在動手開始寫程序之前，分析工作做得越徹底，邏輯描述越准確、簡潔，寫起程序來就會越容易。
3、動態規劃法
動態規劃法多用來計算最優問題，動態規劃法與分治法的基本思想是一致的，但處理的手法不同。動態規劃法在運用時，要先對問題的分治規律進行分析，找出終結子問題，以及子問題向父問題歸納的規則，而演算法則直接從終結子問題開始求解，逐層向上歸納，直到歸納出原問題的解。
動態規劃法多用於在分治過程中，子問題可能重復出現的情況，在這種情況下，如果按照常規的分治法，自上向下分治求解，則重復出現的子問題就會被重復地求解，從而增大了冗餘計算量，降低了求解效率。而採用動態規劃法，自底向上求解，每個子問題只計算一次，就可以避免這種重復的求解了。
動態規劃法還有另外一種實現形式，即備忘錄法。備忘錄的基本思想是設立一個稱為備忘錄的容器，記錄已經求得解的子問題及其解。仍然採用與分治法相同的自上向下分治求解的策略，只是對每一個分解出的子問題，先在備忘錄中查找該子問題，如果備忘錄中已經存在該子問題，則不須再求解，可以從備忘錄中直接得到解，否則，對子問題遞歸求解，且每求得一個子問題的解，都將子問題及解存入備忘錄中。
例如，在題1045--Square Coins中，可以採用分治法求解，也可以採用動態規劃法求解，即從f(m, 1)和f(1, n)出發，逐層向上計算，直到求得f(m, n)。
在競賽中，動態規劃和備忘錄的思想還可以有另一種用法。有些題目中的可能問題數是有限的，而在一次運行中可能需要計算多個測試用例，可以採用備忘錄的方法，預先將所有的問題的解記錄下來，然後輸入一個測試用例，就查備忘錄，直接找到答案輸出。這在各問題之間存在父子關系的情況下，會更有效。例如，在題1045--Square Coins中，題目中已經指出了最大的目標幣值不超過300，也就是說問題數只有300個，而且各問題的計算中存在重疊的子問題，可以採用動態規劃法，將所有問題的解先全部計算出來，再依次輸入測試用例數據，並直接輸出答案。
4、回溯法回溯法是基於問題狀態樹搜索的求解法，其可適用范圍很廣。從某種角度上說，可以把回溯法看作是優化了的窮舉法。回溯法的基本思想是逐步構造問題的可能解，一邊構造，一邊用約束條件進行判別，一旦發現已經不可能構造出滿足條件的解了，則退回上一步構造過程，重新進行構造。這個退回的過程，就稱之為回溯。
回溯法在運用時，要解決的關鍵問題在於：
回溯法的經典案例也很多，例如全排列問題、N後問題等。
5、貪心法貪心法也是求解最優問題的常用演算法策略，利用貪心法策略所設計的演算法，通常效率較高，演算法簡單。貪心法的基本思想是對問題做出目前看來最好的選擇，即貪心選擇，並使問題轉化為規模更小的子問題。如此迭代，直到子問題可以直接求解。
基於貪心法的經典演算法例如：哈夫曼演算法、最小生成樹演算法、最短路徑演算法等。

3. 10個常用演算法

原理：
二分法查找，也稱為折半法，是一種在有序數組中查找特定元素的搜索演算法。

一般步驟：
（1）確定該區間的中間位置K；
（2）將查找的值T與array[k]比較。
若相等，查找成功返回此位置；否則確定新的查找區域，繼續二分查找。每一次查找與中間值比較，可以確定是否查找成功，不成功當前查找區間將縮小一半，遞歸查找即可。

原理：
一種通過重復將問題分解為同類的子問題而解決問題的方法

典型例子：
斐波那契數列
描述： 斐波那契數列 指的是這樣一個數列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368.....自然中的斐波那契數列") 自然中的斐波那契數列，這個數列從第3項開始，每一項都等於前兩項之和。

解決方式：

原理：
在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就「回溯」返回，嘗試別的路徑。
回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。
但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。

解決問題一般步驟：
1、 針對所給問題，定義問題的解空間，它至少包含問題的一個（最優）解。

2 、確定易於搜索的解空間結構,使得能用回溯法方便地搜索整個解空間 。

3 、以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索。

典型例子：
八皇後問題
描述：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。

解決方式： https://blog.csdn.net/weixin_41865447/article/details/80034433

概念：
將雜亂無章的數據元素，通過一定的方法按關鍵字順序排列的過程叫做排序。

分類：
非穩定排序演算法：快速排序、希爾排序、堆排序、直接選擇排序
穩定的排序演算法：基數排序、冒泡排序、直接插入排序、折半插入排序、歸並排序

十個常用排序演算法

利用計算機的高性能來有目的的窮舉一個問題解空間的部分或所有的可能情況，從而求出問題的解的一種方法。

分類：
枚舉演算法、深度優先搜索、廣度優先搜索、A*演算法、回溯演算法、蒙特卡洛樹搜索、散列函數等演算法。

將一個數據轉換為一個標志，這個標志和源數據的每一個位元組都有十分緊密的關系。

很難找到逆向規律

只要符合散列思想的演算法都可以被稱為是Hash演算法

對不同的關鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現象稱為 碰撞 。

原理
在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在 某種意義上的局部最優解 。
從問題的某一個初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加演算法停止。

一種近似演算法

一般步驟：
1、建立數學模型來描述問題；
2、把求解的問題分成若干個子問題；
3、對每一子問題求解，得到子問題的局部最優解；
4、把子問題的解局部最優解合成原來解問題的一個解。

典型例子：
0/1背包問題
馬踏棋盤
均分紙牌

例題： https://www.cnblogs.com/hust-chen/p/8646009.html

概念：
分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序演算法，簡單問題可用二分法完成。

一般步驟：
（1）分解，將要解決的問題劃分成若干規模較小的同類問題；
（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；
（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。

典型例子：
排序中：歸並排序、堆排序、快速排序；
實例：找偽幣、求最值、棋盤覆蓋

https://ke..com/item/%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95/3263297

概念：
用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。

動態規劃一般可分為線性動規，區域動規，樹形動規，背包動規四類。

舉例：
線性動規：攔截導彈，合唱隊形，挖地雷，建學校，劍客決斗等；
區域動規：石子合並， 加分二叉樹，統計單詞個數，炮兵布陣等；
樹形動規：貪吃的九頭龍，二分查找樹，聚會的歡樂，數字三角形等；
背包問題：01背包問題，完全背包問題，分組背包問題，二維背包，裝箱問題，擠牛奶（同濟）等；

應用實例：
最短路徑問題 ，項目管理，網路流優化等；

https://ke..com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408?fromtitle=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95&fromid=15742703&fr=aladdin

概念：
在一個給定的字元文本內搜尋出自己想要找的一個字元串，平常所用的各種文本編輯器里的ctrl+F大多就是使用的這些字元匹配演算法。

分類：
KMP、BM、Sunday、Horspool、RK

參考：
https://cloud.tencent.com/developer/news/282694
https://blog.csdn.net/paincupid/article/details/81159320

4. 數據結構演算法設計題

某鏈表中最常用的操作是在最後一個元素之後插入一個元素和刪除最後一個元素,則採用( )存儲方式最節省運算時間. (A)...已知帶頭結點的單鏈表L中的結點是按整數值遞增排列的,試寫一演算法,將值為x 的結點插入到表L中,使得L仍然有序

5. 演算法分析與設計題目

第一題用貪心思想 找出用時最短的m個作業交給機器同時開始加工 然後再依次將剩下的作業中最短完成作業取出放入已完成的機器加工 當最後一台機器完工時間就是所用最短時間 思路是這樣子 具體演算法實現的話。。由於我也是學生=、=寫代碼還不是很熟練。。可能等我寫好了你考試來不及。。。你還是自己來吧

第二題
1.背包問題是什麼=、=我們教材不一樣 不了解具體問題。。
2.4皇後
#include<iostream.h>
const int n = 4 ;
const int n_sub = n - 1 ;
int queen[n] ;
bool row[n] ;
bool passive[2*n-1];
bool negative[2*n-1];
int main()
{
int cur = 0 ;
bool flag = false ;
queen[0] = -1 ;
int count = 0 ;
while(cur>=0)
{
while(cur>=0 && queen[cur]<n && !flag)
{
queen[cur]++ ;
if(queen[cur] >= n)
{
queen[cur] = -1 ;
cur-- ;
if(cur>=0)
{
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
false ;
}
else
{
if(row[queen[cur]] == false)
{
flag = true ;
if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {
flag = false ;
}
else
flag = true ;
if(flag) {
if(cur == n-1)
{
count++ ;
}
row[queen[cur]] = true ;
passive[queen[cur] + cur] = true ;
negative[n_sub + cur - queen[cur]] = true ;
cur++ ;
if(cur >= n) {
cur-- ;
row[queen[cur]] = false ;
passive[queen[cur] + cur] = false ;
negative[n_sub + cur - queen[cur]] = false ;
}
flag = false ;
}
}
}
}
}
cout<<n<<"皇後問題一共有"<<count<<"種解法"<<endl ;
return 0 ;
}
這個是代碼。。。狀態空間樹這里畫不出來。。。

第三題
你網路下基本都有的=、=。。。我網路出來不好意思貼了你自己去看下吧
比如1.的答案：
最壞情況給出了演算法執行時間的上界，我們可以確信，無論給什麼輸入，演算法的執行時間都不會超過這個上界，這樣為比較和分析提供了便利。

6. c語言常用演算法有哪些

0） 窮舉法
窮舉法簡單粗暴，沒有什麼問題是搞不定的，只要你肯花時間。同時對於小數據量，窮舉法就是最優秀的演算法。就像太祖長拳，簡單，人人都能會，能解決問題，但是與真正的高手過招，就頹了。
1） 貪婪演算法
貪婪演算法可以獲取到問題的局部最優解，不一定能獲取到全局最優解，同時獲取最優解的好壞要看貪婪策略的選擇。特點就是簡單，能獲取到局部最優解。就像打狗棍法，同一套棍法，洪七公和魯有腳的水平就差太多了，因此同樣是貪婪演算法，不同的貪婪策略會導致得到差異非常大的結果。
2） 動態規劃演算法
當最優化問題具有重復子問題和最優子結構的時候，就是動態規劃出場的時候了。動態規劃演算法的核心就是提供了一個memory來緩存重復子問題的結果，避免了遞歸的過程中的大量的重復計算。動態規劃演算法的難點在於怎麼將問題轉化為能夠利用動態規劃演算法來解決。當重復子問題的數目比較小時，動態規劃的效果也會很差。如果問題存在大量的重復子問題的話，那麼動態規劃對於效率的提高是非常恐怖的。就像斗轉星移武功，對手強它也會比較強，對手若，他也會比較弱。
3）分治演算法
分治演算法的邏輯更簡單了，就是一個詞，分而治之。分治演算法就是把一個大的問題分為若干個子問題，然後在子問題繼續向下分，一直到base cases，通過base cases的解決，一步步向上，最終解決最初的大問題。分治演算法是遞歸的典型應用。
4） 回溯演算法
回溯演算法是深度優先策略的典型應用，回溯演算法就是沿著一條路向下走，如果此路不同了，則回溯到上一個
分岔路，在選一條路走，一直這樣遞歸下去，直到遍歷萬所有的路徑。八皇後問題是回溯演算法的一個經典問題，還有一個經典的應用場景就是迷宮問題。
5） 分支限界演算法
回溯演算法是深度優先，那麼分支限界法就是廣度優先的一個經典的例子。回溯法一般來說是遍歷整個解空間，獲取問題的所有解，而分支限界法則是獲取一個解（一般來說要獲取最優解）。