在经历惨烈的春招后，还是回头看看，好好总结总结。还是需要多练习、多见识，锻炼自己的编程思想，这样在临场时思路更清晰、编码更稳健、排错更及时。

需要申明的是，下面都是自己的解题思路或者查询到的解题方法，不见得是最优解法，欢迎交流，指错扔砖。

腾讯

1、构造回文

题目描述：给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。

输入例子：

abcda

google
输出例子：
2

2
第一时间想到的是递归遍历出这个最长回文串，但是提交发现运行超时，输出描述上写着1<=s.length<=1000 ，看来确实很大。

后来看讨论中给出一个思路：将求最长回文串问题转化为，求原字符串和其反串(即原字符串逆转)的最长公共子序列(不是子串，可不连续但是顺序一致)的长度，通过动态规划法即可简洁的写出。详尽的关于求最长公共子序列的动态规划算法可参考万仓一黍 http://www.cnblogs.com/grenet/archive/2010/06/03/1750454.html

import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        Scanner sc= new Scanner(System.in);
        while(sc.hasNext()){
            String input=sc.next();
            int len=input.length();
            int i,j;
            char str[]=input.toCharArray();
            int alth[][]=new int[len+1][len+1];
            for(i=0;i<=len;i++)
                alth[0][i]=alth[i][0]=0;
            for(i=1;i<=len;i++)//动态规划
                for(j=1;j<=len;j++){
                    if (str[j-1]==str[len-i])
                        alth[i][j]=alth[i-1][j-1]+1;
                    else
                        alth[i][j]=Math.max(alth[i-1][j],alth[i][j-1]);
                }
            System.out.println(len-alth[len][len]);
        }
        sc.close();
    }
}

2、字符移位

题目描述：小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。你能帮帮小Q吗？

输入例子：

AkleBiCeilD
输出例子：
kleieilABCD
题目中的不能申请额外空间一开始让我很迷惑，原来是指空间复杂度为O(1) 常数级而不是不能定义变量之类的。

但是后来在java 实现中会发现：标准输入中只能等到String 对象，但是显然String 对字符操作不方便(当然你要是转空子直接遍历、CharAt()判断、输出也能得到想要的输出)，在String 类的一些操作类中char [] 的一些方法如：replace()、replaceAll() ，看似很简洁其实你查看java源码会发现其中使用了很多StringBuffer、StringBuilder，不符合空间复杂度。

所以建议用C、C++来编写，核心代码：

do{
    swap=0;same=0;//swap记录交换次数，name记录遇到大写相遇次数
    for(int i=begin;i<len-1;i++){//begin初始为0，标记下一次遍历开始点
        if(str[i]<'a'&&str[i+1]>='a'){//遇到aA情况，交换
        tmp=str[i];str[i]=str[i+1];str[i+1]=tmp;
        swap++;
    }
    else if(str[i]<'a'&&str[i+1]<'a') {//遇到AA情况
        same++ ;if(same==1) begin=i;
    }
    }
}while(swap!=0&&same!=0);//两个记录中有一为0表明排序完成

3、有趣的数字

题目描述：：有n个数，两两组成二元组，差最小的有多少对呢？差最大呢？

输入描述：输入包含多组测试数据，对于每组测试数据：N - 本组测试数据有n个数，a1,a2…an - 需要计算的数据，1<=N<=100000,0<=ai<=INT_MAX.

输出描述：对每组，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。

输入例子：

6

45 12 45 32 5 6
输出例子：
1 2
其中也没有什么特殊算法，咋一看感觉只需要n^2，不过时间复杂度太大。

    1.先排序
        1.1.特殊情况：如果排完序之后发现数组中所有数都相同，直接输出结果
             结果为：差最大个数 = 差最小个数 = （n * (n-1))/2;(两两组合)
    2.统计数组中每种数字的个数（可用map）
    3.计算差最小个数
        3.1.如果数组中没有重复数字，说明最小差不为0，最小差肯定是数组中相邻两个数的差
            因此，遍历一边数组，计算并统计最小差。
        3.2.如果数组中有重复数字，说明最小差是0，此时，遍历一边map，数字个数不为0的
            数字会产生最小差0，利用公式计算即可
    4.计算差最大个数
        只有一种情况，最大值与最小值的两两组合，即最大值个数 * 最小值个数
    算法复杂度：排序O(nlogn), 统计O(n)
    就是很细，有些情况容易忽略

百度

1、回家

题目描述：一个数轴上共有N个点，第一个点的坐标是度度熊现在位置，第N-1个点是度度熊的家。现在他需要依次的从0号坐标走到N-1号坐标。

但是除了0号坐标和N-1号坐标，他可以在其余的N-2个坐标中选出一个点，并直接将这个点忽略掉，问度度熊回家至少走多少距离？

输入例子：

4

1 4 -1 3
输出例子：
4
求解是先找出那个需要直接忽略掉的坐标点，而判断一个点是不是最值得忽略，判断去除这个点后能让要走的距离减少最多。这样题目就很清晰了

    //当n为2或3，直接输出
    if(n==2) System.out.println(Math.abs(pos[0]-pos[1]));
    else if(n==3) System.out.println(Math.abs(pos[0]-pos[2]));
    else{
        int []log=new int[n-2];//记录中间坐标去除后可减少长度
        for(i=1;i<n-1;i++){
            log[i-1]=Math.abs(pos[i]-pos[i-1])+Math.abs(pos[i+1]-pos[i])
                    -Math.abs(pos[i+1]-pos[i-1]);//坐标i去除后减少的长度
             if(log[i-1]>log[max]) max=i-1;//记录最值得去除点
         }
         pos[max+1]=(pos[max]+pos[max+2])/2;//将最值得去除点改值，使不影响计算
         for(i=1;i<n;i++) sum+=Math.abs(pos[i]-pos[i-1]);//总路径
         System.out.println(sum);
    }

2、不等式数列

题目描述：对于1到n的一个排列，度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 ‘>’ 和 ‘<’ )使其成为一个合法的不等式数列。但是现在手中只有k个小于符号即(‘<’’)和n-k-1个大于符号(即’>’)，想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。

如n=3、k=1，则有3>1<2、2>1<3、1<3>2，1<3>2，满足条件的有4种

输入描述：

包含两个整数n和k(k < n ≤ 1000)
输出描述：
满足条件的排列数，对2017取模
解题思路：

用dp[i][j]表示有 i 个数字及 j 个小于号所能组成的数量(大于号数量当然是i - j - 1 个)

归纳：在dp[i][j]的前提下，加入第 i+1 个数字即 i+1，分为四种情况

如果将i+1插入当前序列的开头，即有了1<2（或2>1），加入后成为3>1<2，会发现等于同时加入了一个大于号！(此时可以无视1与2内部的关系，因为 i+1>i )
如果将i+1插入当前序列末尾,即1<2（或2>1）变成了 1<2<3，会发现等于同时加入了一个小于号！ (此时可以无视1与2之间的关系，因为i+1>i)
如果将i+1加入一个小于号之间，即已经有 1<2了，向中间加入3,会发现变成了1<3>2，等于同时加入了一个大于号！
如果将i+1加入一个大于号中间，即有了2>1，变成了2<3>1，等于同时加入了一个小于号！
则可知dp[i][j]的值等于上述值的和:
dp[i-1][j]—-只加了一个大于号及 i
dp[i - 1][j - 1] —-只加了一个小于号及 i
dp[i - 1][j] * j —-在其中的每个小于号之间，加入 i 和大于号
dp[i - 1][j - 1] * (i- j - 1) —-在其中的每个大于号之间，加入 i 和小于号
可得 dp[i][j] = (dp[i - 1][j - 1] * (i - j) + dp[i - 1][j] * (j + 1)) 再对2017取模

之后问题便迎刃而解。

        int[][] dp = new int[n+1][k+1];  
        for (int i = 1; i < n+1; i++)
            dp[i][0] = 1;  //初始值全为1
        for (int i = 2; i < n+1; i++) {  
            for (int j = 1; j <= k && j < i; j++) {  
                dp[i][j] = (dp[i-1][j-1]*(i-j)+dp[i-1][j]*(j+1))%2017;  
            }  
        }