星网锐捷2020校招笔试编程题解

一共四道题，时间是90分钟，今天刚答过，记录一下解题思路。

1. 题一

   1. 对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
      给定字符串A以及它的长度n，请返回最长回文子串的长度。
      测试样例：
      "abc1234321ab",12
      返回：7

   1. 暴力法
      枚举子串的两个端点i和j，判断在[i,j]区间子串是否回文。复杂度 ，详细代码略。
   2. 动态规划
      令dp[i][j]表示s[i]到s[j]的子串是否为回文子串，若是则为1，不是为0。接下来把转移情况分为两类：
      1.若s[i]==s[j]，只要s[i+1]到s[j-1]为回文子串，则就是，否则不是。
      2.若s[i]!=s[j]，则不是回文子串。
      注意到边界为：dp[i][i]=1，dp[i][i+1]=(s[i]==s[j])?1:0。

   static int getLongestPalindrome(String A, int n) {
        int len = A.length();
        char[] cs=A.toCharArray();
        int[][] dp = new int[len][len];
        int ans=1;
        //边界
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
            if (i < len - 1) {
                if(cs[i]==cs[i+1]){
                    dp[i][i+1]=1;
                    ans=2;
                }
            }
        }
        //转移
        for(int L=3;L<=len;L++){
            for(int i=0;i+L-1<len;i++){
                int j=i+L-1;
                if(cs[i]==cs[j]&&dp[i+1][j-1]==1){
                    dp[i][j]=1;
                    ans=L;
                }
            }
        }
        return ans;
    }

2. 题二

   对于不同的字符串，我们希望能有办法判断相似程度，我们定义了一套操作方法来把两个不相同的字符串变得相同，具体的操作方法如下：
   1 修改一个字符，如把“a”替换为“b”。
   2 增加一个字符，如把“abdd”变为“aebdd”。
   3 删除一个字符，如把“travelling”变为“traveling”。
   比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加和减少一个“g”的方式来达到目的。上面的两种方案，都只需要一次操作。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离＋1”的倒数。也就是说，“abcdefg”和“abcdef”的距离为1，相似度为1/2=0.5.
   给定任意两个字符串，你是否能写出一个算法来计算出它们的相似度呢？
   请实现如下接口
   public static String calculateStringDistance(String expressionA, String expressionB)
   {
   /* 请实现*/
   return null;
   }
   约束：
   1、PucAExpression/ PucBExpression字符串中的有效字符包括26个小写字母。
   2、PucAExpression/ PucBExpression算术表达式的有效性由调用者保证;
   3、超过result范围导致信息无法正确表达的，返回null。

   解题思路：令dp[i][j]表示长度为i和j的字符串之间的字符距离。对于dp[i][j]当s1[i]==s2[j]时字符距离等于dp[i-1][j-1]。不相等时，则考虑dp[i-1][j-1]+1，和dp[i][j-1]+1，dp[i-1][j]+1的最小值。
   注意到边界条件为dp[i][0]=i和dp[0][i]=i，即其中一字符串为空串。

    public  static  String calculateStringDistance(String expressionA,String expressionB){
        if(expressionA==null||expressionB==null)return null;
        int len1=expressionA.length();
        int len2=expressionB.length();
   
        int[][] dif=new int[len1+1][len2+1];
        //边界
        for(int i=0;i<=len1;i++){
            dif[i][0]=i;
        }
        for(int i=0;i<=len2;i++){
            dif[0][i]=i;
        }
        int temp;
        //转移
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(expressionA.charAt(i-1)==expressionB.charAt(j-1)) {
                    temp = 0;
                }else{
                    temp=1;
                }
                //取三值最小的
                dif[i][j]=min(dif[i-1][j-1]+temp,dif[i][j-1]+1,dif[i-1][j]+1);
            }
        }
        dif[len1][len2]+=1;
        return "1/"+dif[len1][len2];
    }
    private static  int min(int a,int b,int c){
        int min=Integer.MAX_VALUE;
        if(min>a)min=a;
        if(min>b)min=b;
        if(min>c)min=c;
        return  min;
    }

3. 题三

   判断一含有“，”和“。”的字符串是否是回文的，忽略大小写。

   解题思路： 去除符号，其他的和回文字符串的比较无差异。

   java
   public boolean isPalindrome(String s) {
        if(s.isEmpty())return  false;
        int i=0,j=s.length()-1;
        while (i<j){
            while (i<j&&!Character.isLetterOrDigit(s.charAt(i)))i++;
            while (i<j&&!Character.isLetterOrDigit(s.charAt(j)))j--;
            if(Character.toLowerCase(s.charAt(i))!=Character.toLowerCase(s.charAt(j)))return  false;
            i++;j--;
        }
        return true;
    }

4. 题4

   Given a linked list and a value x, partition it such that all nodes less thanx come before nodes greater than or equal to x.You should preserve the original relative order of the nodes in each of the two partitions.
   示例：
   For example,
   Given 1->4->3->2->5->2 and x = 3,
   return 1->2->2->4->3->5.

   解题思路：需要调整小于x的顺序。可以使用两次遍历，第一次先放入小于x的节点，第二次放入大于的节点即可。使用队列实现：

   import java.util.*;
   public class Solution {
   public ListNode partition(ListNode head, int x) {
        //用队列存放顺序
        Deque<ListNode> dq=new LinkedList<>();
        ListNode pre=head;         //记录头结点
        while(head!=null){            //放入小节点
            if(head.val<x)dq.addLast(head);
            head=head.next;
        }
        while(pre!=null){         //放入大节点
            if(pre.val>=x)dq.addLast(pre);
            pre=pre.next;
        }
        //重组list
        head=dq.peekFirst();
        while(!dq.isEmpty()){
            ListNode temp=dq.pollFirst();
            temp.next=dq.peekFirst();
        }
        return head;
    }
   }