2021小米秋招笔试算法题（热乎）

小米集团 2022校招 软件开发方向在线考试

编程题|20.0分 1/2

求最长公共子序列的长度

时间限制： 3000MS

内存限制： 589824KB

题目描述：

给定两个字符串str1和str2，输出两个字符串的最长公共子序列的长度。

如果最长公共子序列为空，则返回”0″。目前给出的数据，仅仅会存在一个最长的公共子序列

输入描述

输入:

“1A2C3D4B56”

“B1D23A456A”

输出描述

输出: 6

解题：用动态规划，动态规划的例题多看几遍（头条之前发的文章有），这题套路一样

package xiaomi;


import java.util.Scanner;


public class T1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();


        int res = longestComStr(s1, s2);
        System.out.println(res);


    }

		
    private static int longestComStr(String s1, String s2){
        int m = s1.length();
        int n = s2.length();

        int[][] dp = new int[m+1][n+1];

        dp[0][0] = 0;
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] +1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }

            }

        }

        return dp[m][n];
    }
}

package xiaomi;

import java.util.Arrays;
import java.util.Scanner;

//小米集团 2022校招 软件开发方向在线考试
//        编程题|20.0分2/2
//        红白蓝彩条排序
//        时间限制： 3000MS
//        内存限制： 589824KB
//        题目描述：
//        给你一个仅有红，白，蓝三种颜色组成的10个条块序列，现需要你将这些条块按照红，白，蓝的顺序排好，
//        可用1代表红色，2代表白色，3代表蓝色，要求时间复杂度为O(n)。例如，给定彩色条块序列为：
//
//        ｛蓝、白、红、白、蓝、红、白、白、红、蓝｝
//
//        则要求排列结果为：
//
//        ｛红、红、红、白、白、白、白、蓝、蓝、蓝｝
//
//
//
//        输入描述
//        ｛蓝、白、红、白、蓝、红、白、白、红、蓝｝
//
//        输出描述
//        ｛红、红、红、白、白、白、白、蓝、蓝、蓝｝
//
//
//        样例输入
//        3 2 1 2 3 1 2 2 1 3
//        样例输出
//        1 1 1 2 2 2 2 3 3 3
//
//        规则
//        请尽量在全场考试结束10分钟前调试程序，否则由于密集排队提交，可能查询不到编译结果
//        点击“调试”亦可保存代码
//        编程题可以使用本地编译器，此页面不记录跳出次数
public class T2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String[] ss = s1.split("\ ");
        Arrays.sort(ss);
        for (String a:ss
             ) {
            System.out.print(a);
            System.out.print(" ");

        }






    }
}

第二题的正确解法：//要求O(n)

class Solution {
    public void sortColors(int[] nums) {
        //要求O(n)
        int zeroIndex = 0, twoIndex = nums.length - 1, i = 0;
				while( i <= twoIndex ) {
							if( nums[i] == 0 ) 
											swap(nums, zeroIndex++, i++);
							else if( nums[i] == 2)
											swap(nums, twoIndex--, i);    
							else
											i++;
	}

    }
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}