# LeetCode Weekly Contest 102

https://leetcode.com/contest/weekly-contest-102

## Sort Array By Parity

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Note:

1. 1 <= A.length <= 5000
2. 0 <= A[i] <= 5000

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

Move to the next tree to the right of the current tree. If there is no tree to the right, stop.
Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1:

Example 2:

Example 3:

Example 4:

Note:

1. 1 <= tree.length <= 40000
2. 0 <= tree[i] < tree.length

tree的元素不超过两种时，显然返回tree的长度即可。

tree的元素数量大于2时，使用一个next向量把向右第一个与tree[i]不同的元素坐标j记录到next[i]=j，遍历时迭代找next[j]下标的元素是否还在两种元素内，如果不在则从j开始继续遍历，之前的长度next[j]-i作为候选的结果。如果在则从j=next[j]开始找到第三种元素出现的地方。当然，当next[j]已经到达数组末尾len(tree)时，也没必要再从j开始遍历了。

## Sum of Subarray Minimums

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Note:

1. 1 <= A.length <= 30000
2. 1 <= A[i] <= 30000

## Super Palindromes

Let’s say a positive integer is a superpalindrome if it is a palindrome, and it is also the square of a palindrome.

Now, given two positive integers L and R (represented as strings), return the number of superpalindromes in the inclusive range [L, R].

Example 1:

Note:

1. 1 <= len(L) <= 18
2. 1 <= len(R) <= 18
3. L and R are strings representing integers in the range [1, 10^18).
4. int(L) <= int(R)

$$x=10^{n-1} d_{n-1}+10^{n-2} d_{n-2}+\cdots+10 d_1 +d_0$$且有$$d_i=d_{n-1-i}$$那么$x^2$天然可以被表达为某种palindrome结构
\begin{align} x^2 & = 10^{2n - 2}d_{n - 1}^2 + 10^{2n - 3}({d_{n - 1}}d_{n - 2} + d_{n - 2}d_{n - 1}) + 10^{2n - 4}(d_{n - 1}d_{n - 3} + d_{n - 2}^2 + d_{n - 3}d_{n - 1}) + \cdots \\ & + 10^{n - 1}(d_{n - 1}d_0 + \cdots + d_0d_{n - 1}) + \cdots \\ & + 10^2(d_2d_0 + d_1^2 + d_0d_2) + 10(d_1d_0 + d_0d_1) + d_0^2 \end{align}

• 1xxxxxxxx1，前n位可以放1-4个1，其中第一位必然为1，那么共有${n-1 \choose 1}+{n-1 \choose 2}+{n-1 \choose 3}+1$种情况
• 2xxxxxxxx2，其他位必须全为0，共有1种情况

• 1xxxx1xxxx1，前n位可以放1-4个1，其中第一位必然为1，那么共有${n-1 \choose 1}+{n-1 \choose 2}+{n-1 \choose 3}+1$种情况
• 1xxxx0xxxx1,前n位可以放1-4个1，其中第一位必然为1，那么共有${n-1 \choose 1}+{n-1 \choose 2}+{n-1 \choose 3}+1$种情况
• 2xxxx0xxxx2，其他位必须全为0，共有1种情况
• 2xxxx1xxxx2，其他位必须全为0，共有1种情况
• 1xxxx2xxxx1，前n位可以放1-2个1，其中第一位必然为1，共有$n-1+1$种情况

sqrt(L)d1位数，sqrt(R)d2位数时，d1+1d2-1位的superpalindrome平方根有多少个可以直接按照上面给的计数方法计算。接下来需要从大到小遍历找到大于等于sqrt(L)的palindrome，从小到大找到小于等于sqrt(R)的palindrome，并进行验证这些边界情况。另外，d1==d2可能需要另外讨论。