1 沙滩排石头

题目

沙滩摆放着一排大小不一的球形石头，已知第i个石头的半径为ri，不存在两个石头半径相等。现要求通过移动石头使摆放的石头从左往右半径递增。每次可选择一块石头，并把它放在剩下n-1块石头的最左边或最右边。求最少操作次数.

输入：第一行一个整数n，表示石头个数。（1 <= n <= 100000）.第二行n个整数，表示从左往右石头的半径r1，r2，…，rn（ 1<= ri <= n）。保证不存在两个不同的石头半径相等。

输出：最少操作次数。

样例输入

6
3 2 1 4 6 5

样例输出

3

分析

这道题的关键在于，我们只需要关心怎么选，而不用考虑选好之后怎么放的问题。

保持原序列中最大递增1的子序列（样例中3 4 5）不变，移动其他石头，只需求出最大递增1的子序列长度，再用总长度减去子序列长度，即为需移动数目。

C++ 通过用例90%+，超时

#include <iostream>
using namespace std ;
int main()
{
    int n, num = 1, maxr = 1;
    cin>>n;
    int *r = new int[n];//创建长为n的数组
    int *r1 = new int[n];//备用数组
    for (int i = 0; i < n; i++)
    {
        cin>>r[i];//写入数字
    }
    for (int i = 0; i < n; i++)
    {
        r1[i] = r[i];//从原数组中复制第i个数字,以防止原数组在计算过程中被改变
        for (int j = i+1; j < n; j++)
        {
            r1[j] = r[j];//从原数组中复制第j个数字
            if (r1[i]+1 == r1[j])//判断相邻两数字是否递增1
            {
                num = num + 1;//递增1子序列的长度    
                r1[i] = r1[j];
            }
        }
        if (num > maxr)//更新递增1子序列的长度
        {
            maxr = num;
        }
        num = 1;
    }
    cout<<n-maxr<<endl;
    system("PAUSE");
}

Java 动态规划 通过用例90%+，超时

public static  void main(String[] sb)
   {
       int max=0;
       int label=0;
       Scanner input=new Scanner(System.in);
       int n=input.nextInt();
       int[] r=new int[n];
       for(int i=0;i<n;i++)
           r[i]=input.nextInt();
       int[] dp=new int[n+1];
       dp[0]=0;
       for(int i=0;i<n-1;i++)
       {
           for(int j=i+1;j<n;j++) {
               int a=i;
               if (r[j] - r[a] == 1||r[j] - r[a] == 0) {
                   dp[j] = dp[a]+ 1;
                   if (max < dp[j])
                       max = dp[j];
                   a = j;
               }
           }

       }
       System.out.println(n-max-1);
   }
}

Python 哈希 ，时间复杂度同上

tList = [4, 1, 2, 5, 3]
sDict = {}
ans = {}
start = tList[0]
for i in range(len(tList)):
    key = tList[i] - start
    sDict[key] = i

for i in range(len(tList)):
    num = 0
    j = i
    each = tList[i]
    key = each - start + 1
    while j < len(tList):
        if key in sDict and sDict[key] > j:
            num += 1
        else:
            break
        key += 1
        j += 1
    ans[each] = num
print(max(list(ans.values())))

改进算法：二分法+动态规划

def lengthOfLIS(self, nums):
    mem = list()
    len_nums = len(nums)
    for i in range(len_nums):
        low, upper = 0, len(mem)
        while low < upper:
            mid = (upper - low) // 2 + low
            if mem[mid] < nums[i]:
                low = mid + 1
            else:
                upper = mid
        if upper == len(mem):
            mem.append(nums[i])
        else:
            mem[upper] = nums[i]
    return len(mem)

2 01交替

题目

给出长度为n的01组成的字符串，可以选择任意的连续片段做翻转（0变1/1变0），问修改后最大01交替子序列的长度（子序列意味着可以不连续）

参考大佬

分析

找规律。如果原串中只有1个00（或11）出现=>翻转后可以得到最长n位的交替序列；如果有多个00（或11）出现，统计相邻位不同的数cnt，可以得到最长cnt+2位的交替序列。也就是需要遍历字符串记录相邻两位不相同的位数，例如10100010，其中有6位和它的相邻位（前一位）不同，意味着有多个连续的00（或11），那么答案为6+2；例如10101001，翻转最后的01，答案为8，也就是n。

C++ 用例AC

int cnt = 1;
for (int i = 0;i < n - 1;i++) {
    if (s[i] != s[i + 1]) cnt++;
}
if (cnt < n - 1) cout << cnt + 2 << endl;
else cout << n << endl;

3 被砍掉的树

题目

某街道两侧分别种了一排树木，并按如下编号

1 3 5 7 9 ... 45 47 49... 99

2 4 6 8 10 ... 46 48 50 ... 100

输入：第一行一个整数N

第二行N个整数，表示被砍去的树的编号

输出描述：M和X，表示从第M棵树开始，共有连续的X棵大树

样例输入

5
9 15 27 35 6

样例输出

8 47

Java 用例63+

public static  void main(String[] sb)
   {
       int[] r={1};
       int n=r.length;
       int[] tree=new int[101];
       for(int i=1;i<101;i++)
       {
           tree[i]=1;
       }
       for(int i=0;i<n;i++)
       {
           tree[r[i]]=0;
       }
       int max=0;
       int start=0;
       int label;
       int x=0;
       int flag=0;
       for(int i=1;i<=99;i=i+2)
       {
           if(tree[i]==0)
           {
               start=0;
               x=i;
               continue;
           }
           start++;
           if(start>max) {
               x=i;
               max = start;
           }
       }
       start=0;
       for(int i=2;i<=100;i=i+2)
       {
           if(tree[i]==0)
           {
               start=0;
               x=i;
               continue;
           }
           start++;
           if(start>max) {
               x=i;
               max = start;
           }
       }
       if(x%2==0)
       System.out.println(max-1+" "+(x-(max-2)*2));
       else
           System.out.println(max+" "+(x-(max-1)*2));
}