LC演算法題目

Ⅰ LC-檢索（請各位幫助）

2005年軟考的上午試題

Ⅱ 演算法 LC 島嶼的最大面積

給你一個大小為 m x n 的二進制矩陣 grid 。

島嶼 是由一些相鄰的 1 (代表土地) 構成的組合，這里的「相鄰」要求兩個 1 必須在 水平或者豎直的四個方向上 相鄰。你可以假設 grid 的四個邊緣都被 0（代表水）包圍著。

島嶼的面積是島上值為 1 的單元格的數目。

計算並返回 grid 中最大的島嶼面積。如果沒有島嶼，則返回面積為 0 。

示例1:

輸入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
輸出：6
解釋：答案不應該是 11 ，因為島嶼只能包含水平或垂直這四個方向上的 1 。

示例 2：
輸入：grid = [[0,0,0,0,0,0,0,0]]
輸出：0

思路1：深度優先 遞歸

使用變數book記錄已經搜索過的點，避免重復搜索導致死循環
邊界條件：

和上面解法一樣

思路2:廣度優先

使用隊列，每次從隊首取出土地，並將接下來想要遍歷的土地放在隊尾，就實現了廣度優先搜索演算法

和上面的解法一樣

鏈接： https://leetcode-cn.com/problems/max-area-of-island

https://leetcode-cn.com/problems/max-area-of-island/solution/-yu-de-zui-da-mian-ji-by-leetcode-solution/

Ⅲ 演算法 LC 數學 - 快樂數

編寫一個演算法來判斷一個數 n 是不是快樂數。

「快樂數」 定義為：

對於一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
然後重復這個過程直到這個數變為 1，也可能是 無限循環 但始終變不到 1。
如果這個過程 結果為 1，那麼這個數就是快樂數。
如果 n 是 快樂數 就返回 true ；不是，則返回 false 。

示例 1：
輸入：n = 19
輸出：true
解釋：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：
輸入：n = 2
輸出：false

思路1:數學

不是快樂數的數最終都會落入 4->16->37->58->89->145->42->20->4的循環中

思路2:哈希集合檢測循環

根據規則，最終可能有3種情況：
最終會得到1
最終會進入循環。
值會越來越大，最後接近無窮大

第三個情況比較難以檢測和處理。我們怎麼知道它會繼續變大，而不是最終得到1呢？我們可以仔細想一想，每一位數的最大數字的下一位數是多少。
1位數時，最大是9，Next為81
2位數時，最大是99，Next為162
3位數時，最大是999，Next為243
4位數時，最大是9999，Next為324
13位數時，最大9999999999999，Next為1053

對於3位數的數字，它不可能大於243。這意味著它要麼被困在243以下的循環內，要麼跌到1。4位或4位以上的數字在每一步都會丟失一位，直到降到3位為止。所以我們知道，最壞的情況下，演算法可能會在243以下的所有數字上循環，然後回到它已經到過的一個循環或者回到1。但它不會無限期地進行下去，所以我們排除第三種選擇。

我們使用一個集合來記錄已經生成過的數字，如果下一個要生成的數字在集合里，則意味著在循環里，返回false

思路3:快慢指針法

通過反復調用 getNext(n) 得到的鏈是一個隱式的鏈表。隱式意味著我們沒有實際的鏈表節點和指針，但數據仍然形成鏈表結構。起始數字是鏈表的頭 「節點」，鏈中的所有其他數字都是節點。next 指針是通過調用 getNext(n) 函數獲得。

意識到我們實際有個鏈表，那麼這個問題就可以轉換為檢測一個鏈表是否有環。因此我們在這里可以使用弗洛伊德循環查找演算法。這個演算法是兩個奔跑選手，一個跑的快，一個跑得慢。在龜兔賽跑的寓言中，跑的慢的稱為 「烏龜」，跑得快的稱為 「兔子」。

不管烏龜和兔子在循環中從哪裡開始，它們最終都會相遇。這是因為兔子每走一步就向烏龜靠近一個節點（在它們的移動方向上）。

我們不是只跟蹤鏈表中的一個值，而是跟蹤兩個值，稱為快跑者和慢跑者。在演算法的每一步中，慢速在鏈表中前進 1 個節點，快跑者前進 2 個節點（對 getNext(n) 函數的嵌套調用）。

定義兩個指針fast,slow,fast=getNext(n),
如果n是一個快樂數，即沒有循環，那麼fast最終會比慢跑者先到達數字 1
如果n不是一個快樂的數字，那麼fast和slow將在同一個數字上相遇。

參考： https://leetcode-cn.com/problems/happy-number

https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/

Ⅳ 演算法題套路總結（三）——動態規劃

前兩篇我總結了鏈表和二分查找題目的一些套路，這篇文章來講講動態規劃。動態規劃從我高中開始參加NOIP起就一直是令我比較害怕的題型，除了能一眼看出來轉移方程的題目，大部分動態規劃都不太會做。加上後來ACM更為令人頭禿的動態規劃，很多題解看了之後，我根本就不相信自己能夠想出來這種解法，看著大佬們談笑間還加一些常數優化，一度懷疑自己的智商。以前一直覺得動態規劃是給大佬准備的，所以刻意地沒有去攻克它，主要也是沒有信心。但是後來慢慢的，我再做LC的時候，發現很多DP的題目我自己慢慢能夠推出轉移方程了，而且似乎也沒那麼難。我一直在思考，到底是我變強了，還是因為LC的題目相比ACM或者NOI太簡單了。其實主要還是後者，但是同時我也發現，動態規劃其實是有套路的，我以前方法不對，總結太少。
主要就是，站在出題人的角度，他幾乎不太可能完全憑空想出一個新的DP模型，因為動態規劃畢竟要滿足：

因此，能夠利用DP來解決的問題實際上是有限的，大部分題目都是針對現有的模型的一些變種，改改題目描述，或者加點限制條件。所以要想攻克DP題目，最根本的就是要充分理解幾個常見的DP模型。而要充分理解常見經典DP模型，就需要通過大量的做題和總結，而且二者不可偏廢。通過做題進行思考和量的積累，通過總結加深理解和融會貫通進而完成質的提升。

動態規劃是求解一個最優化問題，而最核心的思想就是：

解一道DP題目，先問自己幾個問題：

當然以上內容看起來比較抽象，雖然它深刻地揭露了動態規劃的本質，但是如果臨場要去想明白這些問題，還是有些難度。如果只是針對比賽和面試，就像前面說的，DP題型是有限的。只要刷的題目足夠多，總結出幾個經典模型，剩下的都是些變種+優化而已。

一般來說，動態規劃可以分成4個大類:

線性DP就是階段非常線性直觀的模型，比如：最長（上升|下降）序列，最長公共子序列(LCS)等，也有一些簡單的遞推，甚至都算不上是 經典模型 。

最長上升序列是一個非常經典的線性模型。說它是個模型，是因為它是一類題的代表，很多題目都只是換個說法，或者要求在這基礎上進一步優化而已。最長上升序列最基礎的轉移方程就是 f[i] = max{f[j]}+1 (a[i] > a[j]) , f[i] 表示一定要以 a[i] 結尾的序列，最長長度是多少。很顯然就是在前面找到一個最大的 f[j] 同時滿足 a[j]<a[i] 。因此是 N^2 的時間復雜度和N的空間復雜度。這種方法是最樸素直觀的，一定要理解。它非常簡單，因此很少有題目直接能夠這么做。大部分相關題目需要進一步優化，也就是有名的單調隊列優化，能夠把復雜度優化到nlogn。

說單調隊列優化之前必須明白一個貪心策略。因為要求的是最長上升序列，那麼很顯然長度為k的上升序列的最大值（最後一個數）越小越好，這樣後面的數才有更大的概率比它大。如果我們記錄下來不同長度的上升序列的最後一個數能達到的最小值，那麼對於後續每個數t，它要麼能放到某個長度為y的序列之後，組成長度為y+1的上升序列，要麼放到某個長度為x的序列後面，把長度為x+1的序列的最大值替換成t。同時我們可以發現，如果x<y，那麼長度為x序列的最後一個數一定比長度為y的序列最後一個數小。因此這個上升序列我們可以用一個數組來維護（所謂的單調隊列），數組下標就代表序列長度。 opt[i]=t 表示長度為i的上升序列最後一個數最小是t。那麼當我們在面對後續某個數x時，可以對單調隊列opt進行二分，把它插到對應的位置。因此總體復雜度就是NlogN。
相關題目比如：

但是你可以發現，其實這個題型其實變種很有限，吃透了也就那麼回事。所以一定要總結。

最長公共子序列也是線性DP中的一種比較常見的模型。說它是一種「模型」其實有點拔高了，其實它就是一類比較常見的題目。很多題目都是在LCS的基礎上進行簡單的擴展，或者僅僅就是換一個說法而已。
求兩個數組的最長公共子序列，最直觀地做法就是：設f[i][j]表示S[..i]和T[..j]的最長公共子序列，則有:

這個轉移方程也非常好理解，時間復雜度是 N^2 ，空間復雜度也是 N^2 。不過仔細觀察你可以發現，當我們計算第i行時只與i-1和i行有關。因此我們可以利用01滾動來優化空間復雜度為2N。
相關題目：

線性DP除了上述的兩種常見題型，還有很多別的類型，包括背包。我們要努力去嘗試理解這些題目的異同，它們的轉移方程，以及思路，可能的變化，這樣才能更好的應對未知的題目。以下是一些我總結的題型：

最終結果就是max(0, f[n][2]+f[n][4])。
不過實際上你可以發現，由於各個狀態只和前一維有關，且只能由固定的一個狀態轉移過來，因此我們可以省掉一維，只用4個變數來存儲：

剩下的，同123題類似，由於最多進行k次交易，那麼一天就有2k個狀態：第1次買/賣……第k次買/賣，結合123題的優化，我們只需要2k個變數就能存儲這些狀態。因此設f[i×2]為第i次買入的最優值，f[i×2+1]為第i次賣出的最優值：

以上都是對一些常見的線性DP的一些小結，實際上線性DP還有一個重要的題型就是背包。關於背包，有很多相關的講解，我這里就不多說了，推薦大家看看 背包九講 。下一章依然是DP專題，我講總結一些區間DP的題型。大部分區間DP都是hard級的，對於希望提高自己水平的人來說，需要投入更多精力去理解。

Ⅳ 設計一個演算法，將兩個遞增鏈表La、Lb合並成一個遞增鏈表Lc。

//設計一個演算法，將兩個遞增鏈表La、Lb合並成一個遞增鏈表Lc;La,Lb,Lc均為帶頭結點的鏈表
#include<stdio.h>
typedef int datatype;
struct PNode
{
datatype data; //定義鏈表中結點的數據域，DATATYPE為數據類型
struct PNode *next; //定義鏈表中結點的指針域
};
typedef struct PNode linklist;
linklist *ListCreateNull()
//建立帶頭結點的空單鏈表，返回頭結點的地址
{ linklist *list;
list =(linklist *)malloc(sizeof(linklist));
//申請表頭結點空間
if(list!=NULL) list->next=NULL;
else printf("Out of space! \n");
return list;
}
int ListInsert(linklist *L,datatype x)
//在鏈表L的尾部插入X,返回1表示成功，0表示失敗
{
linklist *p,*q;
p=L;
while(p->next!=NULL)
p=p->next;
q=(linklist *)malloc(sizeof(struct PNode));
if(!q)return 0;
q->data=x;
p->next=q;
q->next=NULL;
return 1;
}
linklist *fun(linklist *La,linklist *Lb,linklist *Lc)
//將兩個遞增鏈表La、Lb合並成一個遞增鏈表Lc
{
linklist *p;
p=Lc;
while(La->next!=NULL&&Lb->next!=NULL)
{
if(La->next->data>Lb->next->data)
{
ListInsert(p,Lb->next->data);
Lb=Lb->next;
}
else
{
ListInsert(p,La->next->data);
La=La->next;
}
}
if(La->next==NULL)
{
while(Lb->next!=NULL)
{
ListInsert(p,Lb->next->data);
Lb=Lb->next;
}
}
if(Lb->next==NULL)
{
while(La->next!=NULL)
{
ListInsert(p,La->next->data);
La=La->next;
}
}
return Lc;
}
main()
{
linklist *La,*Lb,*Lc;
int temp=1,i;
//初始化鏈表La
La=(linklist *)ListCreateNull();
printf("請輸入數據以零結束：\n");
for(i=0;i<3;i++)
{
scanf("%d",&temp);
ListInsert(La,temp);
}
//初始化鏈表Lb
temp=1;
Lb=(linklist *)ListCreateNull();
printf("請輸入數據以零結束：\n");
for(i=0;i<3;i++)
{
scanf("%d",&temp);
ListInsert(Lb,temp);
}
//初始化鏈表Lc
Lc=(linklist *)malloc(sizeof(struct PNode));
Lc->next=NULL;
Lc->data=NULL;
Lc=fun(La,Lb,Lc);
while(Lc->next!=NULL)
{
printf("%d ",Lc->next->data);
Lc=Lc->next;
}
printf("\n");
}

Ⅵ 設計演算法，將一個帶頭節點的遞增有序單鏈表LA拆分成2個帶頭節點的單鏈表LB和LC

先排序，把奇數的都放在左邊，偶數的放在右邊，記錄中間位置，並把NEXT指針設為null，再把LC指向右邊的鏈表。

Ⅶ C語言 有兩個單鏈表LA和LB，其元素均為非遞減有序排列，編寫一個演算法。將他們合並成一個單鏈表LC

#include<stdio.h>
#include<stdlib.h>

typedefintElemtype;
typedefstructnode{
Elemtypedata;
structnode*next;
}NODE,*LinkList,*pNode;

LinkListGetNewList(){
pNodehead=(pNode)malloc(sizeof(NODE));
if(head==NULL)returnNULL;
head->data=0;
head->next=NULL;
returnhead;
}

LinkListmerge(LinkListLA,LinkListLB){
pNodea,b,c,head;
a=LA;
b=LB;
c=head=GetNewList();
head->data=LA->data+LB->data;
while(a->next&&b->next){
c->next=(pNode)malloc(sizeof(NODE));
if(c->next==NULL){
printf("內存分配失敗！ ");
returnNULL;
}
if(a->next->data>=b->next->data){
c->next->data=a->next->data;
a=a->next;
}
else{
c->next->data=b->next->data;
b=b->next;
}
c=c->next;
}
while(a->next){
c->next=(pNode)malloc(sizeof(NODE));
if(c->next==NULL){
printf("內存分配失敗！ ");
returnNULL;
}
c->next->data=a->next->data;
a=a->next;
c=c->next;
}
while(b->next){
c->next=(pNode)malloc(sizeof(NODE));
if(c->next==NULL){
printf("內存分配失敗！ ");
returnNULL;
}
c->next->data=b->next->data;
b=b->next;
c=c->next;
}
c->next=NULL;
returnhead;
}

LinkListCreat(LinkListhead,inta[],intn){
inti;
pNodep=head;
head->data=n;
for(i=0;i<n;++i){
p->next=(pNode)malloc(sizeof(NODE));
if(p->next==NULL){
printf("內存分配失敗！ ");
returnNULL;
}
p->next->data=a[i];
p=p->next;
}
p->next=NULL;
returnhead;
}

voidShow(LinkListhead){
pNodep=head->next;
while(p){
printf("%d",p->data);
p=p->next;
}
printf(" ");
}

intmain(){
Elemtypea[]={98,89,86,80,76,69,68,54,50,29};
intm=sizeof(a)/sizeof(a[0]);
Elemtypeb[]={96,85,74,69,68,67,65,60,58};
intn=sizeof(b)/sizeof(b[0]);
LinkListLA=GetNewList();
LA=Creat(LA,a,m);
LinkListLB=GetNewList();
LB=Creat(LB,b,n);
LinkListLC;
printf("LA:");
Show(LA);
printf("LB:");
Show(LB);
LC=merge(LA,LB);
printf("LC:");
Show(LC);
return0;
}

Ⅷ lc濾波的計算

上圖是常用經典演算法，巴特沃斯型濾波電路的基本參數，截止頻率為1/2π HZ(0.159)，特徵阻抗1Ω，首先要確定需要幾階，比如二階，先歸一化，再變換截止頻率，M=200/0.159 L(new)=L(old)/M,C(new)=C(old)/M,再變換特徵阻抗K=50/1,L(new)=L(old)*K,C(new)=C(old)/K,算出來的值便是最終待設計LC濾波的值。

可選擇 定K型濾波器則 L=R/(2πF)=1.5K/6.28*4K=59.7mH；
C=1/(2πRF)=1/1.5K*6.28*4K=26.54nF

也可選擇巴特沃斯型 L=2Sin（2k-1/2n）π*R/(2πF)=84.4mH
C=2Sin（2k-1/2n）π/(2πRF)=37.53nF （其中k，n=2）

Ⅸ 演算法 LC 動態規劃 - 最大遞增子序列

給你一個整數數組 nums ，找到其中最長嚴格遞增子序列的長度。
子序列 是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其餘元素的順序。例如，[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的子序列。

示例 1：
輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。

示例 2：
輸入：nums = [0,1,0,3,2,3]
輸出：4

示例 3：
輸入：nums = [7,7,7,7,7,7,7]
輸出：1

思路1:動態規劃

定義dp[i]為以i元素結尾的最長遞增子序列的長度

我們從小到大計算dp數組的值，在計算dp[i]之前，我們已經計算出dp[0…i−1] 的值，則狀態轉移方程為
dp[i] = max(dp[j]) + 1 (0<=j<i 且 num[i]>nums[j])
邊界條件：dp[0] = 1

思路2:貪心演算法+二分法查找

想獲得最長遞增子序列，我們需要讓遞增子序列上升得盡可能的慢，也就是說每次在遞增子序列最後加上的那個數盡可能的小

定義dp[len]為長度為len的遞增子序列末尾最小元素，邊界條件：dp[1] = nums[0]

d[len]是關於len單調遞增的

對於任意長度為i的遞增子序列(末尾元素為x)，我們在末尾刪除一個元素，都可以得到一個長度為i-1的遞增子序列(末尾元素為y),很明顯y<x。
dp[i] 表示長度為i的遞增子序列的最小元素，即dp[i] = min(x0,x1,x2...),dp[i-1] 表示長度為i-1的遞增子序列的最小元素，即dp[j] = min(y0,y1,y2...),又由於x0>y0,x1>y1,...,則dp[i]>dp[i-1]
因而d[len]是關於len單調遞增的。

我們從小遍歷數組nums，比較nums[i]和dp[len],更新len和dp[len]
如果nums[i] > dp[len],表示當前長度len的遞增子序列的末尾元素小於nums[i],則len=len+1,dp[len] = nums[i];
如果nums[i] < dp[len],則在dp數組中查找，找到一個k(0<k<=len)，dp[k-1]<nums[i]<dp[k],更新dp[k] = nums[i],如果找不到k，則說明所有dp j 都比nums[i],則更新dp[0] = nums[i]

在nums[i] < dp[len]，查找k的過程中，由於dp是單調遞增的，我們可以通過二分法查找，即查找第一個比nums[i]小的數d[k],更新d[k+1]=nums[i]

參考： https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xwhvq3/
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/