首页 > 编程语言 >代码随想录算法训练营第二十七天 | 90.子集II , 78.子集, 93.复原IP地址

代码随想录算法训练营第二十七天 | 90.子集II , 78.子集, 93.复原IP地址

时间:2024-02-24 11:55:22浏览次数:25  
标签:nums int res 随想录 II 子集 path startPos

93. 复原 IP 地址

  已解答 中等  

相关标签

相关企业  

有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。

  • 例如:"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址,但是 "0.011.255.245""192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

 

示例 1:

输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]

示例 2:

输入:s = "0000"
输出:["0.0.0.0"]

示例 3:

输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

 

提示:

  • 1 <= s.length <= 20
  • s 仅由数字组成

 


func isVaild(s string) bool { if s == "" { returnfalse } if s == "0" { returntrue } if s[0] == '0' { returnfalse } iflen(s) > 3 { returnfalse } iflen(s) < 3 { returntrue } if s[0] > '2' || (s[0] == '2' && s[1] > '5') || (s[0] == '2' && s[1] == '5' && s[2] > '5') { returnfalse } returntrue }

 

func restoreIpAddresses(s string) []string { varres []string varpath []string varbacktracingfunc(surplusPoint int, startPos int) backtracing = func(surplusPoint int, startPos int) { if surplusPoint == 0 && startPos == len(s) { res = append(res, strings.Join(path, ".")) return } if surplusPoint == 0 || startPos == len(s) { return } surplusLen := len(s) - startPos if surplusLen > 3*surplusPoint || surplusLen < surplusPoint { return } forright := startPos + 1; right <= len(s); right++ { if !isVaild(s[startPos:right]) { continue } path = append(path, s[startPos:right]) backtracing(surplusPoint-1, right) path = path[:len(path)-1] } } backtracing(4, 0) return res }

78. 子集

  已解答 中等  

相关标签

相关企业  

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 

示例 1:

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

示例 2:

输入:nums = [0]
输出:[[],[0]]

 

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

 


func subsets(nums []int) [][]int { sort.Ints(nums)

 

var res [][]int var path []int var backtracing func(startPosint) backtracing = func(startPos int) { res = append(res, append([]int{}, path...)) if startPos == len(nums) { return } for i := startPos; i < len(nums); i++ { path = append(path, nums[i]) backtracing(i +1) path = path[:len(path)-1] } } backtracing(0) return res }

90. 子集 II

  已解答 中等  

相关标签

相关企业  

给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。

 

示例 1:

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

示例 2:

输入:nums = [0]
输出:[[],[0]]

 

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

 


func subsetsWithDup(nums []int) [][]int { sort.Ints(nums) var res [][]int var path []int var backtracing func(startPosint) backtracing = func(startPos int) { res = append(res, append([]int{}, path...)) if startPos == len(nums) { return } for i := startPos; i < len(nums); i++ { if i > startPos && nums[i] == nums[i-1] { continue } path = append(path, nums[i]) backtracing(i +1) path = path[:len(path)-1] } } backtracing(0) return res }

标签:nums,int,res,随想录,II,子集,path,startPos
From: https://www.cnblogs.com/suxinmian/p/18030926

相关文章

  • 代码随想录算法训练营day03 | leetcode 203. 移除链表元素、707. 设计链表、206. 反转
    目录题目链接:203.移除链表元素-简单题目链接:707.设计链表-中等题目链接:206.反转链表-简单题目链接:203.移除链表元素-简单题目描述:给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例1:输入:head=[1,2,6......
  • 代码随想录 day59 两个字符串的删除操作 编辑距离
    两个字符串的删除操作两种思路如果是以最长公共子序列去理解求出这个子序列长度然后原长减一下就行如果是直接正面求解就是如下解法递推式很好理解初始化意思是当一个串为0长度时需要操作另一个字符串长度次也就是直接赋予下标编辑距离dp[i-1][j-1]+1意......
  • 同一字母的大小写,ASCII码的低5位是相同的
    按键变更的次数【力扣周赛382】题目描述给你一个下标从0开始的字符串s,该字符串由用户输入。按键变更的定义是:使用与上次使用的按键不同的键。例如s="ab"表示按键变更一次,而s="bBBb"不存在按键变更。返回用户输入过程中按键变更的次数。注意:shift或capslock......
  • 代码随想录算法训练营第二十六天| 39. 组合总和 40.组合总和II 131.分割回文串
    组合总和题目链接:39.组合总和-力扣(LeetCode)思路:依然一是套用回溯模板,但是我们这里用回溯的是i而不是i+1,因为元素可以重复使用,注意for循环里if(sum(path)<=target)的等号不能少。classSolution{public:vector<int>path;vector<vector<int>>result;intsu......
  • 代码随想录:数组
    二分查找二分查找是对数组中的区间进行查找。有两种写法:一种是在闭区间内进行查找,另一种是在左闭右开区间内进行查找。每次查找的时候只有按照这个方法就不会出错。二分查找写法一:classSolution{public:intsearch(vector<int>&nums,inttarget){intle......
  • day41 动态规划part3 代码随想录算法训练营 96. 不同的二叉搜索树
    题目:96.不同的二叉搜索树我的感悟:这题,考的概率不大,听一遍,过一遍就行。理解难点:二叉搜索树定义为什么是累加的听课笔记:代码示例:classSolution:defnumTrees(self,n:int)->int:dp=[0]*(n+1)#创建一个长度为n+1的数组,初始化为0d......
  • day40 动态规划part3 代码随想录算法训练营 343. 整数拆分
    题目:343.整数拆分我的感悟:题目很难,但我动力十足!!理解难点:如何拆分为什么要保留dp[i]听课笔记:代码示例:classSolution:defintegerBreak(self,n:int)->int:#思路:#dp[i]是到目前为止能拆分取的最大值#dp[i]可以拆成j*(集合)......
  • 代码随想录 day58 判断子序列 不同的子序列
    判断子序列dp[i][j]表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]。if(s[i-1]==t[j-1])t中找到了一个字符在s中也出现了if(s[i-1]!=t[j-1])相当于t要删除元素,继续匹配不同的子序列dp[i][j]:以i-1为结尾的s子序列中......
  • 代码随想录算法训练营day02 | leetcode 977. 有序数组的平方、35.搜索插入位置、34.在
    题目链接:977.有序数组的平方-简单题目描述:给你一个按非递减顺序排序的整数数组nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。示例1:输入:nums=[-4,-1,0,3,10]输出:[0,1,9,16,100]解释:平方后,数组变为[16,1,0,9,100]排序后,数组变为[0,1,9,16,100]......
  • 代码随想录算法训练营第二十五天| 216.组合总和III 17.电话号码的字母组合
    组合总和III题目链接:216.组合总和III-力扣(LeetCode)思路:仿照昨天的递归模板写的,同样是for循环横向遍历,递归纵向遍历。注意当k>n时要直接跳出,否则会判断栈溢出。额外发现一个问题就是在累加sum时,用for(autoi:path)sum+=path[i];会出现奇怪数字,原因是auto遍历用法错误,正确写......