首页 > 其他分享 >day23-back tracking-part02-7.25

day23-back tracking-part02-7.25

时间:2024-07-29 15:55:00浏览次数:13  
标签:tracking target 7.25 self part02 used candidates result path

tasks for today:

1.39.组合总和

2.40.组合总和II

3.131.分割回文串

----------------------------------------------------------

1.39.组合总和

IN this practice, the key change is the requirement that the element can be repetatively used, which can be achieved by control the startIndex in each loop of backtracking, when it is not allow to repete, the index will be i+1, but in this practice, it should be i;

but this brings the time exceeding limits issue if no cut branching is execute, this should be noted.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        path = []
        self.backtracking(candidates, target, 0, path, result)
        return result

    def backtracking(self, candidates, target, startIndex, path, result):
        # in this practice, cutting branch is important, or it will exceed the time limit
        if sum(path) > target:
            return

        if sum(path) == target:
            result.append(path[:])
            return
        
        for i in range(startIndex, len(candidates)):
            path.append(candidates[i])
            self.backtracking(candidates, target, i, path, result)
            path.pop()

在求和问题中,排序之后加剪枝是常见的套路!

本题:(1)list不包含重复元素(2)list每个元素可以重复使用

2.40.组合总和II

本题:(1)list包含重复元素(2)list每个元素不可以重复使用(3)最终结果不包含重复组合

here if we only use "if i > 0 and candidates[i] == candidates[i - 1]:" as condition, this will cut off some circumstance that from one tree branch, instead of trimming the same level, so an additional used list recording the usage condition for each level is added as a new factor

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()
        path = []
        used = [False] * len(candidates)
        self.backtracking(candidates, target, 0, path, result, used)
        return result

    def backtracking(self, candidates, target, startIndex, path, result, used):
        if sum(path) > target:
            return
        
        if sum(path) == target:
            result.append(path[:])
            return
        
        for i in range(startIndex, len(candidates)):
            # here if we only use "if i > 0 and candidates[i] == candidates[i - 1]:" as condition, 
            # this will cut off some circumstance that from one tree branch, instead of trimming the same level
            # so an additional used list recording the usage condition for each level is added as a new factor
            if i > 0 and candidates[i] == candidates[i - 1] and used[i-1] == False:
                continue
            path.append(candidates[i])
            used[i] = True
            self.backtracking(candidates, target, i + 1, path, result, used)
            used[i] = False
            path.pop()

Note: do not forget to sort the candidates list before doing operation

3.131.分割回文串

in this practice, the individual traversed is not a digit as previous practice, instead, it is a part of string from s, which is s[startIndex, i+1];

then another function used to judge if a string is a palindrome should be composed to check the qualification of ann individual string cut. 

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        path = []
        self.backtracking(s, 0, path, result)
        return result

    def backtracking(self, s, startIndex, path, result):
        if startIndex >= len(s):
            result.append(path[:])
            return
        
        for i in range(startIndex, len(s)):
            s_cut = s[startIndex:i+1]
            if self.isPalindrom(s_cut):
                path.append(s_cut)
                self.backtracking(s, i+1, path, result)
                path.pop()
    
    def isPalindrom(self, s):
        left = 0
        times = len(s) // 2
        right = len(s) - 1
        for i in range(times):
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        
        return True

标签:tracking,target,7.25,self,part02,used,candidates,result,path
From: https://blog.csdn.net/bbrruunnoo/article/details/140685733

相关文章

  • day22-back tracking-part01-7.24
    tasksfortoday:1.回溯理论基础2.77.组合3.216.组合总和III4.17.电话号码的字母组合-------------------------------------------------------------------1.回溯理论基础-什么是回溯:在二叉树系列中,我们已经不止一次,提到了回溯,回溯是递归的副产品,只要有递归就......
  • 2024.7.25 模拟赛总结
    T1icanStatement:给定一个有\(n(1\len\le10^7)\)个元素的序列\(a(a_i\le10^9)\),求满足\(i<j\)且\(a_i<a_j\)的点对\((i,j)\)中\(j-i\)的最大值。Solution:考虑什么样的\(a_i\)可能作为点对中较靠左边的元素出现。显然对于一个\(k>i\)且\(a_k......
  • GitHub每日最火火火项目(7.25)
    1. 项目名称:public-apis/public-apis项目介绍:这是一个集体列表,收集了各种免费的APIs。在当今的软件开发中,API(应用程序编程接口)扮演着至关重要的角色,它们允许不同的应用程序和服务之间进行交互和数据共享。这个项目的目的是提供一个集中的资源,让开发者能够更容易地找到......
  • 实训day14(7.25)
    Git一种分布式版本控制系统,用于跟踪和管理代码的变更一.Git的主要功能:二.准备git机器修改静态ip,主机名三.git仓库的建立:1.安装git[root@git~]#yum-yinstallgit2.创建一个目录----用来放置git文件[root@git~]#mkdir/yy0003.使用git指令,一定要cd到初始化之后的目......
  • 实训day14(7.25)
    一、Git概述Git是一种分布式版本控制系统,用于跟踪和管理代码的变更。它是由LinusTorvalds创建的,最初被设计用于Linux内核的开发。Git允许开发人员跟踪和管理代码的版本,并且可以在不同的开发人员之间进行协作。Github用的就是Git系统来管理它们的网站,Github是一个社......
  • ACM日常训练日记——7.25
    Atcoder训练Harlequin思维题博弈论,思考每一次怎么转化最优,存在两个答案说明f可以赢,打表发现当所有数字都是偶数时,答案为second,否则为first#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intmain(){ lln; cin>>n; llans=0; vector<ll>v(......
  • 2024.7.25(Git、gitlab以及分支管理)
    分布式版本控制系统一、Git概述Git是一种分布式版本控制系统,用于跟踪和管理代码的变更。它是由LinusTorvalds创建的,最初被设计用于Linux内核的开发。Git允许开发人员跟踪和管理代码的版本,并且可以在不同的开发人员之间进行协作。Github用的就是Git系统来管理它们的网......
  • 7.25第二周周四学习总结
    算法竞赛(差分)(上午)初始化#include<algorithm>intarr[100];std::fill(arr,arr+100,0);//比memset更高效intarr[100]={};//所有元素都初始化为0栈溢出为局部变量每次运行时都在运行栈中分配,如果数组很大,结果会造成运行栈溢出,自然就运行不了另外,使用全局变......
  • Day23 回溯算法Part02
    39.组合总和与216.组合总和III不同,不要求每个数字仅能使用一次。但这样很容易出现重复的结果,剪枝还是要注意。不过这道题让我更认识到把回溯问题看成是一个多叉树的遍历的问题,当遇到一个题目,先画出它的树结构,也就是代码随想录中的这张图,for循环(横向遍历)怎么做,递归(纵向遍历)......
  • (三)复习第三课(07.20- 07.25第二轮):HTML标签元素练习大全
    <!DOCTYPEhtml><!--练习时间:2024.07.20-2024.07.25--><htmllang="en"><!--添加了en可以让你的网站打开时会提示翻译--><head> <pid="head1"></p><metacharset="utf-8"><!--对于中文网页需要使用此标签声明编码,否则会出现......