算法

2022-04-14 07:42:21   82  举报





AI智能生成

算法是一系列解决问题或执行任务的清晰指令。它以逻辑和数学规则为基础，用于处理数据、执行计算和自动化决策。算法可以应用于各种领域，如计算机科学、工程学、金融等。它们通常具有输入、输出和有限步骤的特点，能够提供准确且一致的结果。算法的效率和正确性对于解决复杂问题至关重要。通过优化算法，可以提高计算速度和准确性，从而节省时间和资源。算法的设计和分析是计算机科学的核心内容之一，也是现代科技发展的关键驱动力之一。

算法

作者其他创作

大纲/内容

pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）

动态规划

打家劫舍

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

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

dp[i]=max(dp[i−2]+nums[i],dp[i−1])

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合

过滤条件：如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号

每一个括号序列可以用 (a)b 来表示，递归调用 generate(i) 即可计算 a 的所有可能性；
递归调用 generate(n - i - 1) 即可计算 b 的所有可能性

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢

状态方程：f(x)=f(x−1)+f(x−2)

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

f(i)=max{f(i−1)+nums[i],nums[i]}

三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1

f[i][j]=min(f[i−1][j−1],f[i−1][j])+c[i][j]

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0

字符相等 dp[i][j] = dp[i-1][j-1] +1
字符不相等 dp[i][j] = max(dp[i-1][j],dp[i][j-1])

凑硬币

给你 k 种⾯值的硬币，⾯值分别为 c1, c2 ... ck ，每种硬币的数量⽆限，再给⼀个总⾦额 amount ，问你最少需要⼏枚硬币凑出这个
⾦额

回溯

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回

套用回溯模板

类型

组合

排列

子集

分割

棋盘问题

双指针法

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组

排序+三指针，一个指针当做目标值，左指针和右指针向中心逼近

盛最多水的容器

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水

利用双指针，分别从左边界和右边界向中心移动

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序

利用双指针，右指针移动，遇到非0的数据，左右指针数据交换，左指针移动一步

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度

跟移动零是一个逻辑

数据结构

数组

旋转数组

将数组中的后k位，移到数组的开头

利用首尾交换实现，先全部翻转，然后分别翻转0到k-1和k到数组末尾

二分查找

滑动窗口

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0

链表

相交链表

编写一个程序，找到两个单链表相交的起始节点

利用双指针，当 pA 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pB到达链表的尾部时，将它重定位到链表 A 的头结点

环形链表

给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况

利用hash表判重，还可以使用快慢指针

反转链表

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null

两两交换链表中的节点

虚拟头节点

删除链表的倒数第N个节点

快慢指针+虚拟头节点

哈希表

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词

排序、hash表

栈