侧边栏壁纸
博主头像
峰峰火火

一条咸鱼罢了

  • 累计撰写 120 篇文章
  • 累计创建 85 个标签
  • 累计收到 57 条评论

目 录CONTENT

文章目录

腾讯暑期实习题目

峰峰火火
2021-02-24 / 0 评论 / 0 点赞 / 227 阅读 / 5,339 字 / 正在检测是否收录...
温馨提示:
若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1.构造回文

给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢?
输出需要删除的字符个数。
image.png

代码

可以删除不连续的字符,所以可以将字符串反转,求两个字符串的最长公共子序列,像这种字符串比较一般都可以使用动态规划求解。
有关字符串比较的可以看文本比较算法Needleman/Wunsch算法,动态规划算法之:最长公共子序列 & 最长公共子串(LCS)。

import java.util.Scanner;
public class Main{

    public static void main(String[] args) {

        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
            String str1=in.nextLine();
            String str2=new StringBuilder(str1).reverse().toString();
            System.out.println(str1.length()-LCS(str1,str2));
        }
        in.close();
    }
    public static int LCS(String str1,String str2){
        // 设置字符串长度
        int len1= str1.length();
        int len2=str2.length(); // 具体大小可自行设置

        // 构造二维数组记录子问题x[i]和y[i]的LCS的长度
        int[][] record = new int[len1 + 1][len2 + 1];

        // 从后向前,动态规划计算所有子问题。
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1))
                    record[i][j] = record[i-1][j-1] + 1;// 状态转移方程
                else{
                    record[i][j] = Math.max(record[i-1][j], record[i][j-1]);// 状态转移方程
                    //record[i][j] = Math.max(tmp,record[i-1][j-1]);
                }    
            }
        }
        return record[len1][len2];
    }
}

2.算法基础-字符移位

小Q最近遇到了一个难题:把一个字符串的大写字母放到字符串的后面,各个字符的相对位置不变,且不能申请额外的空间。
你能帮帮小Q吗?
image.png

代码

这道题不能采用额外的空间,所以必须两两进行交换,所以采用类似于冒泡的算法,把小写字符冒到大写字母之前就可以了。

import java.util.Scanner;
public class Main{

    public static void main(String[] arg){
        Scanner in=new Scanner(System.in);
        while(in.hasNextLine()){
            String s=in.nextLine();
            StringBuilder sb=new StringBuilder(s);
            System.out.println(change(sb));
        }
        in.close();
    }   
    public static String change(StringBuilder sb){
        int len=sb.length();
        for(int i=1;i<len;i++){
            if(isLowerCase(sb.charAt(i))){
                int x=i;
                while(x>=1 && !isLowerCase(sb.charAt(x-1))){
                    char tmp=sb.charAt(x-1);
                    sb.setCharAt(x-1, sb.charAt(x));
                    sb.setCharAt(x, tmp);
                    x=x-1;
                }
            }   
        }
        return sb.toString();
    }
    public static boolean isLowerCase(char c){
        if(c>='a' && c<='z')
            return true;
        return false;
    }
}

3. 有趣的数字

小Q今天在上厕所时想到了这个问题:有n个数,两两组成二元组,差最小的有多少对呢?差最大呢?
image.png

代码

这道题刚开始我用的是先排序,再统计,时间复杂度是nlogn。过后我发现有些人用的是map来统计,最优情况下时间复杂度更好一些,算差最大的对数就是最小的个数乘以最大数的个数,算差最小的对数要区分是否有重复的数,如果没有需要先排序,再相邻两个数最小的差。

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in=new Scanner(System.in);
        while(in.hasNext())
        {
            int n=in.nextInt();
            int[] nums=new int[n];
            Map<Integer,Integer> map=new HashMap<Integer,Integer>();
            for(int i=0;i<n;i++){
                nums[i]=in.nextInt();              
                if(map.containsKey(nums[i]))
                {
                    int t=map.get(nums[i]);
                    map.put(nums[i], ++t);
                }
                else
                {
                    map.put(nums[i], 1);
                }
            }                   
            int minResult=getMinResult(map);
            int maxResult=getMaxResult(nums, map); 
            System.out.println(minResult+" "+maxResult);
        }
        in.close();
    }
    public static int getMaxResult(int[] nums,Map<Integer,Integer> map){
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++)
        {
            if(nums[i]>max)
                max=nums[i];

            if(nums[i]<min)
                min=nums[i];
        }

        int maxNumberCount=map.get(max);
        int minNumberCount=map.get(min);

        int maxResult=maxNumberCount*minNumberCount;
        return maxResult;
    }
    public static int getMinResult(Map<Integer,Integer> map){
        int minResult=0;
        boolean containSameNumber=false;
        Set<Integer> keySet=map.keySet();
        Iterator<Integer> it=keySet.iterator();
        //查看是否有重复数字
        while(it.hasNext())
        {
            int t=it.next();
            int times=map.get(t);
            if(times>1)
            {
                containSameNumber=true;
                minResult+=times*(times-1)/2;
            }
        }  
        //如果没有重复,进行排序.找相邻最小的对数
        if(!containSameNumber)
        {
            ArrayList<Integer> list=new ArrayList<Integer>();
            list.addAll(keySet);
            Collections.sort(list);
            int distance=Integer.MAX_VALUE;
            for(int i=0;i<list.size()-1;i++)
            {
                int x=list.get(i+1) - list.get(i);
                if( x<distance)
                {
                    distance = x;
                    minResult=1;
                }
                else if(x == distance)
                {
                    minResult++;
                }

            }
        }
        return minResult;
    }
}
0

评论区