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/