LeetCode 五月挑战专题每日随缘更新，点击类别 2020 May LeetCoding Challenge 查看更多。

## May 15th: Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

Note:

• -30000 <= A[i] <= 30000

• 1 <= A.length <= 30000

### 题目解析

• 一种是正常的，即 A 的某一子数组。

对于这种情况，可以这样处理：在遍历过程中，**curMx = max(curMx+num, num); 语句表示 curMx 要么延续之前的子数组，要么放弃之前的子数组，即是否重新组织子数组，然后使用 mx = max(mx, curMx); 语句寻找子数组和的最大值。**

• 另一种是两段的，即 A 的开头一段和结束一段组合而成的某一子数组。

对于这种情况，可以这样处理：仿照第一种情况的方法，寻找子数组和的最小值 mn，使用 A 的总和 sum 减去 mn 就可以得到子数组和的最大值。

## May 16th: Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Example 2:

Note:

• The relative order inside both the even and odd groups should remain as it was in the input.

• The first node is considered odd, the second node even and so on …

## May 17th: Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Example 2:

### 题目解析

P.S. 一开始还使用 multiset<char> 做记录，然后就超时了。

## May 18th: Permutation in String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

Example 2:

Note:

• The input strings only contain lower case letters.

• The length of both given strings is in range [1, 10,000].

## May 19th: Online Stock Span

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock’s price for the current day.

The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today’s price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Example 1:

Note:

• Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.

• There will be at most 10000 calls to StockSpanner.next per test case.

• There will be at most 150000 calls to StockSpanner.next across all test cases.

• The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.

## May 20th: Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:

You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:

Example 2:

## May 21st: Count Square Submatrices with All Ones

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Example 2:

Constraints:

• 1 <= matrix.length <= 300

• 1 <= matrix[0].length <= 300

• 0 <= matrix[i][j] <= 1

### 题目解析

P.S. 印象中碰到过这道题，那次没做出来，看了别人的解法之后，这次就记着了。