9.8小米秋招笔试软件开发方向编程题

时间限制： 3000MS

内存限制： 589824KB

题目描述： 给定两个字符串str1和str2，输出两个字符串的最长公共子序列的长度。如果最长公共子序列为空， 则返回"0"。目前给出的数据，仅仅会存在一个最长的公共子序列

输入示例：
    1A2C3D4E56 A1B2345C6D

输出示例：6

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();
            int[][] dp = new int[str1.length() + 1][str2.length() + 1];
            for (int i = 1; i <= str1.length(); i++) {
                for (int j = 1; j <= str2.length(); j++) {
                    if (str1.charAt(i - 1) == str2.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]);
                    }
                }
            }
            System.out.println(dp[str1.length()][str2.length()]);
        }
    }
}

时间限制： 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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[10];
        for (int i = 0; i < a.length; i++) {
            a[i] = sc.nextInt();
        }
        //Arrays.sort(a);
        int[] sort = quickSort(a, 0, a.length - 1);
        for (int j : sort) {
            System.out.print(j + " ");
        }
    }

    public static int[] quickSort(int[] array, int L, int R) {
        if (L >= R)
            return array;
        //定义子串的左下标和右下标
        int left = L;
        int right = R;
        //得到基数
        int pivot = array[left];
        while (left < right) {
            //左边的下标小右边的下标且 基数右边的值大于基数
            while (left < right && array[right] >= pivot) {
                right--;
            }
            if (left < right) {
                array[left] = array[right];
            }
            while (left < right && array[left] <= pivot) {
                left++;
            }
            if (left < right) {
                array[right] = array[left];
            }
            //如果两个下标相等那么将基数赋值在相等的下标的位置
            if (left >= right) {
                array[left] = pivot;
            }
        }
        //分配左右子串遍历
        //遍历左子串
        quickSort(array, L, right - 1);
        //遍历右子串
        quickSort(array, right + 1, R);
        return array;
    }
}