search
HomeBackend DevelopmentPython Tutoriallintcode question record 3

lintcode question record 3

Jun 23, 2017 pm 03:49 PM
Record

Expression Expand Word Break II Partition Equal Subset Sum

Expression Expand

String expansion problem, expand according to the number before [] Strings mainly maintain two stacks, one is to expand the number stack and the other is to expand the content stack. The content stack is added [to determine whether to push out all the content to be expanded, and then note that the number may be more than one digit, and the rest does not matter

class Solution:# @param {string} s  an expression includes numbers, letters and brackets# @return {string} a stringdef expressionExpand(self, s):# Write your code herenl=[]
        sl=[]
        sc=''res=''lstr=''for i in s:if i.isdigit():if not lstr.isdigit():
                    sl.append(sc)
                    sc=''sc = sc + ielse:if i=='[':
                    nl.append(int(sc))
                    sc = ''sl.append('[')elif i==']':
                    n=nl.pop()while len(sl)>0:
                        k=sl.pop()if k== '[':breaksc = k+ sc
                    ts=''for j in range(n):ts= ts + sc
                    sc=''if len(nl) > 0:sl.append(ts)else:
                        res = res + tselse:if len(nl)>0:
                        sc = sc + ielse:
                        res = res + i
            lstr=ireturn res

Word Break II

Word segmentation problem, search from the beginning of the string in the array, add it to the stack when found, and then loop pop every time to determine pop Is the string that comes out complete? If it is complete, add the result. If it is incomplete, look for the follow-up. If you can find the follow-up, add it to the stack without continuing to the next cycle. There must be ambiguity here. Can the string in wordDict be reused?

This thing will be very slow when the string is very long and there are many dictionary arrays behind it. I haven’t thought of any optimization algorithm for the time being. There seems to be no such situation in the test data given by lintcode. There is only one special case, so the previous After adding a filter, it passed, and you should also pay attention to python's startwith function

If the parameter is '', it always returns True, which is a bit cheating...

class Solution:# @param {string} s a string# @param {set[str]} wordDict a set of wordsdef wordBreak(self, s, wordDict):# Write your code herehead=[]
        ss=''for i in s:if ss=='':
                ss=ielse:if i not in ss:
                    ss = ss + ifor i in ss:
            flag=Falsefor di in wordDict:if i in di:
                    flag=Truebreak;if not flag:return []for di in wordDict:if di !='' and  s.startswith(di):
                head.append(di)if len(head)0:
            h=head.pop()
            le=len(h.replace(' ',''))
            cur=s[le:]if cur == '': 
                res.append(h)continuefor di in wordDict:if cur.startswith(di):
                    head.append(h+' '+di)                    return res

Partition Equal Subset Sum

Array grouping and summing problem, the question says that the conditions are that many numbers are integers and do not exceed 100, and the length of the array does not exceed 200, that is, let Use dynamic programming to do it, which is a simplified version of the knapsack problem. First find the sum of all numbers. If it is an even number, it can be divided into two groups. Otherwise, it returns false directly, and then divides by 2 to find the final sum of the groups. This value is similar to the knapsack problem. Capacity, the numbers in the array are similar to things that need to be put into a backpack. Different from the backpack problem, the backpack problem requires traversing to the last grid. Here, it only needs that the grid value is equal to this sum. It does not have to be traversed to the last grid.

class Solution:# @param {int[]} nums a non-empty array only positive integers# @return {boolean} return true if can partition or falsedef canPartition(self, nums):# Write your code heresum=0for n in nums:
            sum = sum +nif sum%2!=0:return False
        k=sum//2a=[None]*len(nums)for i in range(len(nums)):
            a[i]=[0]*k            for i in range(len(nums)):for j in range(k):if i == 0:
                    a[i][j] = nums[i] if nums[i]  j+1:
                        a[i][j]=a[i-1][j]else:
                        a[i][j]=max(nums[i]+a[i-1][j+1-nums[i]],a[i-1][j])                        if a[i][j] ==k:return Truereturn False

The above is the detailed content of lintcode question record 3. For more information, please follow other related articles on the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Python vs. C  : Understanding the Key DifferencesPython vs. C : Understanding the Key DifferencesApr 21, 2025 am 12:18 AM

Python and C each have their own advantages, and the choice should be based on project requirements. 1) Python is suitable for rapid development and data processing due to its concise syntax and dynamic typing. 2)C is suitable for high performance and system programming due to its static typing and manual memory management.

Python vs. C  : Which Language to Choose for Your Project?Python vs. C : Which Language to Choose for Your Project?Apr 21, 2025 am 12:17 AM

Choosing Python or C depends on project requirements: 1) If you need rapid development, data processing and prototype design, choose Python; 2) If you need high performance, low latency and close hardware control, choose C.

Reaching Your Python Goals: The Power of 2 Hours DailyReaching Your Python Goals: The Power of 2 Hours DailyApr 20, 2025 am 12:21 AM

By investing 2 hours of Python learning every day, you can effectively improve your programming skills. 1. Learn new knowledge: read documents or watch tutorials. 2. Practice: Write code and complete exercises. 3. Review: Consolidate the content you have learned. 4. Project practice: Apply what you have learned in actual projects. Such a structured learning plan can help you systematically master Python and achieve career goals.

Maximizing 2 Hours: Effective Python Learning StrategiesMaximizing 2 Hours: Effective Python Learning StrategiesApr 20, 2025 am 12:20 AM

Methods to learn Python efficiently within two hours include: 1. Review the basic knowledge and ensure that you are familiar with Python installation and basic syntax; 2. Understand the core concepts of Python, such as variables, lists, functions, etc.; 3. Master basic and advanced usage by using examples; 4. Learn common errors and debugging techniques; 5. Apply performance optimization and best practices, such as using list comprehensions and following the PEP8 style guide.

Choosing Between Python and C  : The Right Language for YouChoosing Between Python and C : The Right Language for YouApr 20, 2025 am 12:20 AM

Python is suitable for beginners and data science, and C is suitable for system programming and game development. 1. Python is simple and easy to use, suitable for data science and web development. 2.C provides high performance and control, suitable for game development and system programming. The choice should be based on project needs and personal interests.

Python vs. C  : A Comparative Analysis of Programming LanguagesPython vs. C : A Comparative Analysis of Programming LanguagesApr 20, 2025 am 12:14 AM

Python is more suitable for data science and rapid development, while C is more suitable for high performance and system programming. 1. Python syntax is concise and easy to learn, suitable for data processing and scientific computing. 2.C has complex syntax but excellent performance and is often used in game development and system programming.

2 Hours a Day: The Potential of Python Learning2 Hours a Day: The Potential of Python LearningApr 20, 2025 am 12:14 AM

It is feasible to invest two hours a day to learn Python. 1. Learn new knowledge: Learn new concepts in one hour, such as lists and dictionaries. 2. Practice and exercises: Use one hour to perform programming exercises, such as writing small programs. Through reasonable planning and perseverance, you can master the core concepts of Python in a short time.

Python vs. C  : Learning Curves and Ease of UsePython vs. C : Learning Curves and Ease of UseApr 19, 2025 am 12:20 AM

Python is easier to learn and use, while C is more powerful but complex. 1. Python syntax is concise and suitable for beginners. Dynamic typing and automatic memory management make it easy to use, but may cause runtime errors. 2.C provides low-level control and advanced features, suitable for high-performance applications, but has a high learning threshold and requires manual memory and type safety management.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools