算法题类型

‘壹’ 一个算法题

python">#py3
deffun(lis,n):
foriinlis:#循环从lis中取出i
if(n-i)inlis://如果n-i在lis中，即找到了两个和街于n的数
returni,n-i//返回
li=[1,2,3,4,5,6,8,9]
print(fun(li,7))

‘贰’ c语言方面的 类型：算法设计题 题目：求3个数中的最大者(用传统流程图描述) 写出步骤最好是照片，

#include <stdio.h>
void main()
{
int base,upn,i;
long sum=1;

printf("input base & upn:");
scanf("%d %d",&base,&upn);
for(i=0;i<upn;i++)
{
sum*=base;
}
printf("%ld",sum);
}

求最大数
#include<stdio.h>
void main()
{
int a,b,c,max;
printf("input a & b & c:");
scanf("%d %d %d",&a,&b,&c);
max=a>b?a:b;
max=max>c?max:c;
printf("The biggest number is:%d",max);
}

‘叁’ 求助一道算法题！

计算机解决胜这类问题的关键是要找出问题的规律，或者说是要制定一套计算机行动的规则。分析本题，先用人来解决问题，可总结出以下规则：
(1) 黑子向左跳过白子落入空格，转(5)
(2) 白子向右跳过黑子落入空格，转(5)
(3) 黑子向左移动一格落入空格(但不应产生棋子阻塞现象)，转(5)
(4) 白子向右移动一格落入空格(但不应产生棋子阻塞现萌)，转(5)
(5) 判断游戏是否结束，若没有结束，则转(1)继续。
所谓的“阻塞”现象就是：在移动棋子的过程中，两个尚未到位的同色棋子连接在一起，使棋盘中的其它棋子无法继续移动。例如按下列方法移动棋子：
0
○ ○ ○ . ● ● ●
1 ○ ○ . ○ ● ● ●
2 △ ○ ○ ● ○ . ● ●
3
○ ○ ● . ○ ● ●
4 两个●连在一起产生阻塞
○ ○ ● ● ○ . ●
或4 两个白连在一起产生阻塞
○ . ● ○ ○ ● ●

产生阻塞的现象的原因是在第2步(△状态)时，棋子○不能向右移动，只能将●向左移动。
总结产生阻塞的原因，当棋盘出现“黑、白、空、黑”或“白、空、黑、白”状态时，不能向左或向右移动中间的棋子，只移动两边的棋子。
按照上述规则，可以保证在移动棋子的过程中，不会出现棋子无法移动的现象，且可以用最少的步数完成白子和黑子的位置交换。

‘肆’ java中的算法，一共有多少种，哪几种，怎么分类。

就好比问，汉语中常用写作方法有多少种，怎么分类。

算法按用途分,体现设计目的、有什么特点
算法按实现方式分，有递归、迭代、平行、序列、过程、确定、不确定等等
算法按设计范型分，有分治、动态、贪心、线性、图论、简化等等

作为图灵完备的语言，理论上”Java语言“可以实现所有算法。
“Java的标准库'中用了一些常用数据结构和相关算法.

像apache common这样的java库中又提供了一些通用的算法

‘伍’ 算法如何刷题

1、原题
我自己感觉原题的概率还是挺大的，特别是剑指offer的66题更是如此。千万别小看这66题，这几十道题里面基本所有的算法类型都有包括在内，常用的数据结构，操作方式，常用算法思路都有不少的题。

如果真的能够充分理解这几十道题的最优解，我感觉其实已经形成基本的算法思维了。

另外，leetcode的原题也很常见，因为LC本身题量大，在里面出原题不是为了考倒你，而是检验你的刷题质量。

毕竟那些大公司面试官也不是傻子，知道你在面试前肯定会大规模刷题的。所以把刷过的题完全搞懂才是最重要的。

2、改编题
改编题就很显而易见了。改编题大多需要从基本的算法原理中找到处理的思维，然后结合实际题干进行性能优化，就能够搞定。

这里要记得一点的是，正常的算法考察不会故意刁难你（正常情况），也不会给过多的时间让你思考和敲代码。

所以遇到改编题不要想得太复杂，尽量要找到它的算法思维是什么。怎么说呢，透过现象看本质。我总结的改编题有以下几种思路：

1）新的数据结构，换汤不换药。比如最常见的排序算法的改编，原来是对数字进行排序，现在对链表排序等等。比较难一点的可能会遇到自定义的数据结构。但是算法本质不会变。

2）算法类型改编。

这里要说的就是一个比较大的范围，比如动态规划、贪心算法、递归、回溯和分治等等。这种是从算法大的类型上进行改编，很难用相同的套路去解题。

遇到这类题的关键就是要先弄明白算法核心。比如动态规划的状态方程，贪心算法的局部最优情况，递归回溯的边界判断，分治的子问题划分等等。这种类型的确比较难把握，怎么硕呢，每种类型的都来搞几道感觉感觉吧。

3）添加应用题背景。

这种题目看起来不难，但是难就难在对应用题背景的理解，需要去理解题意，然后考虑合适的数据结构和处理算法。这里面有数学建模的思维在里面，需要把一堆无用的信息剔除，筛选出有效的信息，然后才能选择正确的算法。

3、创新题
这类题考察的是你的扩展思维，如果说上面的题考查的是你的思维深度，这种题就是考察算法的广度。可能一看题目，完全没见过这种类型。但是算法本身其实不就是让计算机代替人脑进行高重复性的计算嘛。

首先你需要想到你应该去怎么算这个题，然后再换到计算机上，会发生什么问题（空间时间问题，运行效率，代码冗余等等），之后再想通过经典的算法原理来解决这些

1、题型分类
按照个人的习惯，喜欢按照一种类型狂刷，然后再刷另外一种类型。一般常见的算法类型可分为：

数组、链表

包含基本排序算法、二分查找、链表的一系列操作。

栈、队列、堆

利用栈、队列互相实现，堆的使用

二叉树与图

主要是遍历算法和节点的计算：
二叉树四种遍历方式、广度优先遍历（BFS）和广度优先遍历（DFS），节点到节点距离等等。

哈希表

使用标准库自带的模板或者函数就很简单了，一般会与其它数据结构相结合来提升时间复杂度。

字符串操作

字符串的操作也很多，本质上可以看作是数组的操作。另外字符串的一些匹配和寻求字串的算法还是非常具有思考价值的。KMP，马拉车等等。

递归

重点掌握边界判断条件。

回溯

重点掌握边界判断条件。

分治

重点掌握如何划分子问题。

动态规划

题太多了，可从一阶dp到二阶dp理解不同的状态方程。

贪心及其它

这个就很容易理解了，遇到贪心题应该要偷笑了。

2、高频热点多刷
这不多说了吧，Leetcode热题HOT 100。你值得拥有。

在不知道怎么刷的情况下，不如先刷起来。刷个题没那么多捷径，只有坚持刷起来了，才会形成自己的思维方式和学习习惯。

我建议是先按照类型刷，每个类型刷十几二十道。然后打混按照算法热度排序重新查漏补缺。

3、思路回顾
许多同学在一股脑刷了很多题之后，再看做过的题会发现忘了不少。可能大家都是这样的吧。我觉得是因为在刷题的时候过于心急，理解了大概就过了，或者类型做的太杂，没有留下印象。

我比较喜欢的方式是偶尔会重新看看曾经做过的题，就看题目然后想思路，再画一画步骤演进，没时间就不细敲了。这样可以增强一下思维记忆，之前理解过的东西，再回忆起来还是非常快的。

‘陆’ 什么是算法算法有哪些分类

分类算法是在数学和计算机科学之中，算法为一个计算的具体步骤，常用于计算、数据处理和自动推理。

精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数，算法分类可以根据算法设计原理、算法的具体应用和其他一些特性进行分类。

具体意义：

如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

‘柒’ 数据结构高手来帮忙（简答题、算法题）

waited

‘捌’ 算法题和数学题有什么区别

两者都是数学题，数学题是一个大范畴，算法题是数学题的一种类型。

‘玖’ 什么是专项计算题

简便算法类型的题目，专门练习一个知识点的题目等等。

专项计算题指的就是一种特别的题型，在这种专项计算题里面就会专门的去练一个知识点，比如专项计算题的类型就有简便算法，乘法相关的计算题，除法计算题等等，然后在专项计算题里面的话多数是出现在小学或者初中这样子的一个层次。

在小学里面的专项计算题可能比较多，并且在简便算法这样子的一个项目的计算题是出现的最多的，因为小学生的话需要掌握的简便算法比较多，老师也比较喜欢考核这样子的一个内容，而且会设置这样子的一个专项计算题，在考试里面或者是在作业里面的一些题目。

‘拾’ 阿里面试算法题合集一

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

输入: n = 5, m = 3
输出: 3
示例 2：

输入: n = 10, m = 17
输出: 2

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

输入：
输出：3
解释：输入的二进制串 中，共有三位为 '1'。

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：

输入：n = 3
输出：3
示例 2：

输入：n = 11
输出：0

注意这里必须是long 类型

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"
示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。
示例 1:

输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

贪心的思路是，只要总和大于0 就可以绕一圈，
开始位置的贪心思路是，如果从刚开始sum小于0，一定不是从之前开始，而是从当前下一个位置，sum = 0 清空

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

这里一定注意 第一个数为0 的情况，s.charAt(0) == '0' 第一个为0 要直接返回0 才行

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

输入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。

使用带记忆的可以避免超时

使用动态规划解题

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

示例 1:

输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

说明:
不允许旋转信封。

示例:

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

标准的动态规划

一只青蛙想要过河。 假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。 青蛙可以跳上石头，但是不可以跳入水中。

给定石子的位置列表（用单元格序号升序表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一个石子上）。 开始时， 青蛙默认已站在第一个石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格1跳至单元格2）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

请注意：

石子的数量 ≥ 2 且 < 1100；
每一个石子的位置序号都是一个非负整数，且其 < 231；
第一个石子的位置永远是0。
示例 1:

[0,1,3,5,6,8,12,17]

true

使用数组+ 链表枚举所有的可能

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：S = "rabbbit", T = "rabbit"
输出：3

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4

使用二分查询

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3

思路是忽略第一个求一个结果，忽略最后一个求一个结果，只要一个时一个结果

// 可以使用rangeCopy 将其放入一个函数中求解

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

示例 1:

输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2