Original link: He Xiaodong blog
Reference to Offer 57-II. And a sequence of consecutive positive numbers for S
Enter a positive integer target and print all consecutive sequences of positive integers (at least two numbers) that sum to target.
The numbers in the sequence are arranged from smallest to largest, and different sequences are arranged from smallest to largest according to the first number.
Example 1:
Enter: target =9Output: [[2.3.4], [4.5]]
Copy the codeExample 2:
Enter: target =15Output: [[1.2.3.4.5], [4.5.6], [7.8] ' '** limit: **1 <= target <= 10^5Source: LeetCode//leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof##### Classic sliding window, direct limit to slide up to half, can save a lot of calculation. ** ' 'PHP class Solution {/** * @param Integer $target * @return Integer[][] */
function findContinuousSequence($target) {
$i = 1;
$j = 2; $result = []; # The right margin of the sliding window cannot exceed the median value of targetwhile ($j <= $target / 2 + 1$curSum = array_sum(range($I, $j +)) $curSum = array_sum(range($I, $j +)1)); # If and is less than the target, move the right pointer to the right to enlarge the windowif($curSum < $target) { $j++; } elseif ($curSum > $target) {$i++; } # add the pointer window to the output listelse {
$result[] = range($i, $j + 1); I'm going to use j plus lambda1I + =1I + =2$j++; }}return$result; }}Copy the codeSword finger Offer 42. Maximum sum of contiguous subarrays
Enter an array of integers. One or more integers form a subarray. Find the maximum sum of all subarrays.
The time complexity is O(n).
Example 1:
Enter: nums = [2 -.1.- 3.4.- 1.2.1.- 5.4] output:6Continuous subarrays [4.- 1.2.1] and maximum, for6.Copy the codeSource: LeetCode link: leetcode-cn.com/problems/li…
1 Sliding a window
Continue to slide the window, larger than the current maximum value will move the pointer right, smaller than the current maximum value will start to shrink the left pointer.
Code implementation:
class Solution {
/ * * *@param Integer[] $nums
* @return Integer
*/
function maxSubArray($nums) {
//sum is used to record the sum of all numbers in the sliding window
$sum = 0; $left = 0; $result = PHP_INT_MIN;
$count = count($nums);
for ($right = 0; $right < $count; $right{+ +)$sum+ =$nums[$right];
// Every time the right pointer moves one space, a comparison is required
$result = max($result.$sum);
// Note that when left==right, the left pointer also moves
while ($left< =$right && $sum< =0) {
$sum- =$nums[$left];
$left++;
}
}
return $result; }}Copy the code2. Dynamic planning
Dynamic programming solution: first define whether the big problem given can be divided into small problems, the most direct is some array properties, can be regarded as a smaller array of small problems. These small problems constitute a small state, to figure out how to go from these small states to the big state, and then solve the big problem (this is the state transition equation). The core is: ○ How to abstract, define the state dp[I] ○ Determine the state transition equation dp[I] how to get from the previous state ○ Some initial states can be seen such as DP [0], DP [1]
Code implementation:
class Solution {
/ * * *@param Integer[] $nums
* @return Integer
*/
function maxSubArray($nums) {
$count = count($nums);
if ($count= = =0) {
return 0;
}
$dp = $nums[0];
$max = $nums[0];
for ($i = 1;$i < $count; $i{+ +)$dp = max($dp + $nums[$i].$nums[$i]);
$max = max($max.$dp);
}
return $max; }}Copy the codeThe best time to buy and sell stocks I: leetcode-cn.com/problems/be… Similar to the above, stock price changes [7,1,5,3,6,4] can be converted to [-6, 4, -2, 3, -2], buy and sell once, can be converted to find the maximum sum ** of the continuous subarray
For example, given an integer array nums, find one or more contiguous subarrays with the maximum sum (the subarrays contain at least one element) and return the maximum sum. If the maximum sum is less than 0, return 0. [– 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 12 explanation: continuous subarray [1], [4], [2, 1], [4] and the largest, to 12. It’s actually taking all the positive numbers in the array, and the sum is the maximum sum
This leads to another similar question:
122. The best time to Buy and sell stocks II
Given an array, its ith element is the price of a given stock on the ith day.
Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.
Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).
Example 1:
Input:7.1.5.3.6.4] output:7Explanation: In no2Day (stock price =1) time to buy, at No3Day (stock price =5), the trade can make a profit5- 1 = 4. Then, at No4Day (stock price =3) time to buy, at No5Day (stock price =6), the trade can make a profit6- 3 = 3 。
Copy the codeExample 2:
Input: [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the codeExample 3:
Input:7.6.4.3.1] output:0Explanation: In this case, no transaction is completed, so the maximum profit is0.Copy the codeSource: LeetCode link: leetcode-cn.com/problems/be…
Code implementation:
class Solution {
/ * * *@param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$ans = 0;
$count = count($prices);
for ($i = 1; $i < $count; $i{+ +)if ($prices[$i] - $prices[$i-1] > 0) {
$ans+ =$prices[$i] - $prices[$i - 1]; }}return $ans; }}Copy the codeReference links:
- Geek time algorithm interview pass Lecture 40