算法打卡day25

2024-04-04 09:04
文章标签 算法 打卡 day25

本文主要是介绍算法打卡day25,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

今日任务:

1)491.递增子序列

2)46.全排列

3)47.全排列 II

491.递增子序列

题目链接:491. 非递减子序列 - 力扣(LeetCode)

给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

说明:
给定数组的长度不会超过15。
数组中的整数范围是 [-100,100]。
给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况

文章讲解:代码随想录 (programmercarl.com)

视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列哔哩哔哩bilibili

思路:

  1. 使用回溯算法,遍历数组中的每个元素。
  2. 对于当前元素,尝试将其加入当前子序列中,然后递归地向后探索更长的子序列。
  3. 在向后探索过程中,需要进行剪枝操作,以排除重复的结果和不满足递增条件的情况。
  4. 当遍历完所有可能的情况时,将满足要求的子序列加入结果列表中

 下面是一个错误代码

class Solution:def findSubsequences(self, nums: List[int]) -> List[List[int]]:self.result = []self.backtrack(nums, 0, [])return self.resultdef backtrack(self, nums, start, path):# 如果当前路径长度大于1,则将该路径加入结果列表中if len(path) > 1:self.result.append(path[:])# 遍历数组中从start索引开始的所有元素for i in range(start, len(nums)):# 剪枝条件1:如果当前元素与前面的元素相同,则跳过,避免重复结果if i > start and nums[i] in nums[:i]:continue# 剪枝条件2:如果当前元素小于路径中的最后一个元素,跳过,确保生成的子序列是递增的if not path or nums[i] >= path[-1]:# 递归path.append(nums[i])self.backtrack(nums, i + 1, path)path.pop()

在第一个剪枝部分,不能直接去用当前nums[i]与数组之前的部分判断重复,这样是判断当前元素是否出现在路径中
这样导致的我们找的子集是没有重复元素的,但[1,2,1,1]这种是符合要求的,所以这样剪枝是错的
而是应该判断当前层,元素nums[i]是否遍历过 

46.全排列

题目链接:46. 全排列 - 力扣(LeetCode)

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

文章讲解:代码随想录 (programmercarl.com)

视频讲解:组合与排列的区别,回溯算法求解的时候,有何不同?| LeetCode:46.全排列哔哩哔哩bilibili

思路:

使用回溯算法来生成全排列。
维护一个结果列表 result 来存储所有可能的全排列。
回溯函数 backtrack 的参数包括当前要排列的数组 nums 和当前已生成的部分排列 path。
在回溯函数中,首先判断是否满足终止条件,即 path 的长度是否等于 nums 的长度,如果满足则将 path 加入 result 中。
然后遍历数组 nums 中的每个元素,如果该元素已经在 path 中,则跳过,否则将其加入 path 中,递归调用回溯函数,完成后需要撤销选择,以便尝试其他未选择的元素。

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:self.result = []self.backtrack(nums, [])return self.resultdef backtrack(self, nums, path):# 当遍历完时,path长度等于原数组长度if len(path) == len(nums):self.result.append(path[:])for i in range(len(nums)):# 剪枝:如果当前元素已经遍历则跳过if nums[i] in path:continue# 递归层path.append(nums[i])self.backtrack(nums, path)path.pop()

感想:

这题比较简单,递归遍历时,起始位置与之前的不一样,这次从头遍历

47.全排列 II

题目链接:47. 全排列 II - 力扣(LeetCode)

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

示例 1:
输入:nums = [1,1,2]
输出: [[1,1,2], [1,2,1], [2,1,1]]

示例 2:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示:
1 <= nums.length <= 8
-10 <= nums[i] <= 10

文章讲解:代码随想录 (programmercarl.com)

视频讲解:回溯算法求解全排列,如何去重?| LeetCode:47.全排列 II哔哩哔哩bilibili

思路:

1)使用回溯算法来生成全排列。
2)首先对原数组进行排序,这样重复元素会相邻,方便后续剪枝操作。
3)回溯函数 backtrack 的参数包括当前要排列的数组 nums、当前已生成的部分排列 path 和一个数组 used,用于记录每个数字是否已被使用。
4)在回溯函数中,首先判断是否满足终止条件,即 path 的长度是否等于 nums 的长度,如果满足则将 path 加入 result 中。
5)然后遍历数组 nums 中的每个元素,如果该元素已经被使用过,则跳过,否则标记该元素为已使用,选择当前元素并递归调用回溯函数,完成后需要撤销选择,并将当前元素标记为未使用,以便尝试其他未选择的元素。

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:nums.sort()self.result = []self.backtrack(nums, [], [False] * len(nums))return self.resultdef backtrack(self, nums, path,used):# 终止条件:当路径长度等于原数组长度时,表示已经生成了一个全排列if len(path) == len(nums):self.result.append(path[:])for i in range(len(nums)):# 剪枝:如果当前元素已经遍历则跳过if used[i]:continue# 剪枝:同一层不能重复取相同的数字,若前一个相同数字未被使用,则跳过当前数字if i > 0 and nums[i] == nums[i - 1] and used[i-1] == False:continueused[i] = True # 标记当前元素已被使用# 递归层path.append(nums[i])self.backtrack(nums, path,used)path.pop()used[i] = False

感想:

这一题有两个剪枝,第一个是每一个树层上,也就是同一级的for循环上,如果有重复的,我们就不用继续了,因为第一个元素出现时就已经涵盖所有可能性。我们可以对数组排序,然后比较当前nums[i]是否等于前一个,还需要补充的限制是,前一个已经遍历过了
第二个剪枝就是与上一题一样的,每一个树枝上已经使用的放进path中的就跳过

这篇关于算法打卡day25的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/875365

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

最大公因数:欧几里得算法

简述         求两个数字 m和n 的最大公因数,假设r是m%n的余数,只要n不等于0,就一直执行 m=n,n=r 举例 以18和12为例 m n r18 % 12 = 612 % 6 = 06 0所以最大公因数为:6 代码实现 #include<iostream>using namespace std;/