第一题太简单，就是要偶数在奇数前面，可以2头指针SWAP达到空间O1。
第二题是一道滑动窗口题
904. Fruit Into Baskets
https://leetcode.com/problems/fruit-into-baskets/description/
根据题目的描述，理解就是找一个窗口，里面DISTINCT 的ITEM只有2个，并且长度最长。
那么就2个指针滑一下，就好了。
public int totalFruit(int[] tree) {
Map<Integer,Integer> m = new HashMap<>();
int max = 0;
int i = 0, j = 0;
while(j < tree.length){
if(m.size()<=2){
max = Math.max(max,i-j);
}
if(i < tree.length && m.size()<=2){
m.put(tree[i],m.getOrDefault(tree[i],0)+1);
i++;
}else{
m.compute(tree[j],(k,v)->{
if(v == 1) return null;
return v-1;
});
j++;
}
}
return max;
}
第三题，就复杂一点，你首先要分析每多加一个元素，是应该对SUM有哪些影响，然后分析出公式便可求解。
907. Sum of Subarray Minimums
https://leetcode.com/problems/sum-of-subarray-minimums/description/
首先当比如起始元素是[2,4] 这时候来了一个5，我们会发现以5为结尾，分别可以构成【5】【4,5】【2,4,5】
也就是说除了单独的一个5，前面都按4 算出来的值计算和
因为
【4,5】【2,4,5】 = 【4】【2,4】最小值都是 4,2
那么便有了第一个公式。
如果大于前一项，新加的值为dp[i]= A[i]+dp[i-1]，在想一下，等于也适用哦
所以是大于等于都是上面这个公式。
如果小于的话，就麻烦一点。
比如【2,4】 这个时候来了个1，我们会发现新加的sum 是 1*3 因为 [1] [4,1] [2,4,1]
如果来了个3，我们会发现 新加的SUM 是 2*3+2 因为【3】【4,3】 是3为最小值
【2,4,3】 依然保持2是最小值。
所以我们要知道新进来的这个元素，连续往前走第一个比它小的那个元素是谁，找到那个元素，再找到和那个元素中间的距离
就有
dp[i] = A[i]*(距离）+dp[i-距离]
所以为了知道距离，我们可以用单调栈，来存下标。同时把DP的值也存进去。
Stack<int[]> st = new Stack<>();
所以我们往栈里放一个数组，第一个是A[I], 第二个是存下标I，第三个是存DP[I]
public int sumSubarrayMins(int[] A) {
int l = A.length;
if(l == 0) return 0;
long ans = A[0];
int n = 1000000007;
Stack<int[]> st = new Stack<>();
st.push(new int[]{A[0],0,A[0]});
for(int i = 1; i < A.length; i++){
if(A[i]>=st.peek()[0]){
st.push(new int[]{A[i],i,(A[i]+st.peek()[2])%n});
}else{
while(!st.isEmpty()&&A[i]<st.peek()[0]){
st.pop();
}
int preIdx = st.isEmpty()?-1:st.peek()[1];
int preVal = st.isEmpty()?0:st.peek()[2];
st.push(new int[]{A[i],i,(A[i]*(i-preIdx)+preVal)});
}
ans = (ans+st.peek()[2])%n;
}
return (int)ans;
}
第四题，一开就朝着巧妙的数学推导去思考了，推了半天没推出来，就用暴力解法，就过了。
首先我们先找出所有开完根号的范围里的，回文数。
其次对这些回文数平方，再看还是不是回文，是的话CNT++
就结束了。
这里有个基本功，如何高效求出某一个范围的所有回文数。
我们从1开始，来做奇数和偶数的翻转。
比如当奇数位的时候，1翻转就是1.
偶数位1翻转是11.
然后I++，就能得到 2,22
一直++到10，就能得到 101,1001等。
这样可以很快找到小于一个RANGE的回文数，因为你但翻转超过了上界，就没必要++了
public int superpalindromesInRange(String L, String R) {
int l = (int) Math.sqrt(Long.parseLong(L));
int r = (int) Math.sqrt(Long.parseLong(R));
List<Integer> allP = new ArrayList<>();
help(allP,l,r);
int cnt = 0;
for(int p : allP){
long k = (long)p*p;
if(isP(k)) cnt++;
}
return cnt;
}
private boolean isP(long n){
long rev = 0;
for (long i = n; i > 0; i /= 10)
rev = rev * 10 + i % 10;
return(n == rev);
}
int createP(int input, int b, int isOdd) {
long n = input;
long palin = input;
if (isOdd == 1)
n /= b;
while (n > 0) {
palin = palin * b + (n % b);
n /= b;
}
return (int)palin;
}
void help(List<Integer> allP,int k,int n) {
int number;
for (int j = 0; j < 2; j++) {
int i = 1;
while ((number = createP(i, 10, j % 2)) <= n) {
if(number >= k)
allP.add(number);
i++;
}
}
}
