LeetCode 刷题记录: 31. Next Permutation [Python]

原题

https://leetcode.com/problems/next-permutation/

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

LeetCode 刷题记录: 42. Trapping Rain Water [Python]

原题

https://leetcode.com/problems/trapping-rain-water/

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

思路

使用双指针,分别从两头往最高处逼近。每次经过刷新左边和右边的最高值,该处结果等于最高值与当前值的差。

LeetCode 刷题记录: 19. Remove Nth Node From End of List [Python]

原题

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Given a linked list, remove the n-th node from the end of list and return its head.

Follow up:

Could you do this in one pass?

思路

使用两个指针fast以及slow,fast先出发,slow相隔n位再出发。当fast走到尽头时slow跳过下一指针即可。

LeetCode 刷题记录: 22. Generate Parentheses [Python]

原题

https://leetcode.com/problems/generate-parentheses/

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

思路

使用动态规划,分析子问题:每次加括号要么加在外面,要么加在旁边。

LeetCode 刷题记录: 11. Container With Most Water [Python]

原题

https://leetcode.com/problems/container-with-most-water/

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). nvertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

思路

贪心算法,从左右两边开始,从短的一边往中间缩进并记录最大值。由于短板效应从短的一边往中间缩进是最有利的。

LeetCode 刷题记录: 1. Two Sum [Java]

原题

https://leetcode.com/problems/two-sum/

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

思路

使用hashmap查表,拿到数字首先查找余值是否在表内,若在的话直接返回表内的对应值。接着将数字以及index存入表内。

LeetCode 刷题记录: 5. Longest Palindromic Substring [Python]

原题

https://leetcode.com/problems/longest-palindromic-substring/

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

思路

马拉车方法 (Manacher’s Algorithm) 利用回文的性质减少运算。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×