小米前端笔试编程题

第一题阶梯问题比较简单略过。

第三题：给一个数字，将其变为字母字符串（规则1->a,2->b,...,26->z）,如输入123，按字典序输出'abc','aw','lc'（123可以拆成1，2，3；12，3；1，23，三种）。
用dp，不太熟练，花了好久，通过率67%，估计是0的锅，没来得及在线上改完就提交了orz

下面是改好的版本，也不知道能不能ac：

function solution(n) {
    let dp = [];
    dp[0] = [[]];
    n = String(n).split('');
    for (let i = 0; i < n.length; i++) {
        dp[i+1] = [];
        if (i === 0) {
            dp[1] = [[int(n[0])]];
        }
        else if (n[i - 1] === '1') {
            if (n[i] !== '0') {
                for (let item of dp[i]) {
                    dp[i + 1].push(item.concat(int(n[i])));
                }
            }
            for (let item of dp[i - 1]) {
                dp[i + 1].push(item.concat(int(n[i - 1] + n[i])));
            }
        }
        else if (n[i - 1] === '2' && int(n[i]) <= 6) {
            if (n[i] !== '0') {
                for (let item of dp[i]) {
                    dp[i + 1].push(item.concat(int(n[i])));
                }
            }
            for (let item of dp[i - 1]) {
                dp[i + 1].push(item.concat(int(n[i - 1] + n[i])));
            }
        } else if (n[i] !== '0') {
            for (let item of dp[i]) {
                dp[i + 1].push(item.concat(int(n[i])));
            }
        }
    }
    let r = dp[dp.length - 1];
    let result = [];
    for (let item of r) {
        let str = '';
        for (let num of item) {
            str += (String.fromCharCode(num + 96));
        }
        result.push(str);
    }
    return result;
}
function int(n) {
    return parseInt(n);
}
let input;
while(input = readInt()) {
    let result = solution(input);
    result.sort();
    let resultStr = '';
    for (let item of result) {
        resultStr += item + ' ';
    }
    print(resultStr.trim());
}

所以第二题呢？没来得及写，感觉也像是dp？求一个解答

#笔试题目##小米#

全部评论

推荐最新楼层

请继续，○◇

西安石油大学安卓

同学，你的第二题是IP地址码？我记得是LeetCode 的原题，以前刷过 import java.util.Scanner; public class Main1 { public static void main(String[] args) { // TODO Auto-generated method stub System.out.println("hello world"); Scanner in = new Scanner(System.in); String s=in.nextLine(); vavidIP(s); } private static void vavidIP(String s) { // TODO Auto-generated method stub int len = s.length(); for (int i = 1; i <=3; ++i){ // first cut if (len-i > 9) continue; for (int j = i+1; j<=i+3; ++j){ //second cut if (len-j > 6) continue; for (int k = j+1; k<=j+3 && k<len; ++k){ // third cut int a,b,c,d; // the four int's seperated by "." a = Integer.parseInt(s.substring(0,i)); b = Integer.parseInt(s.substring(i,j)); // notice that "01" can be parsed into 1. Need to deal with that later. c = Integer.parseInt(s.substring(j,k)); d = Integer.parseInt(s.substring(k)); if (a>255 || b>255 || c>255 || d>255) continue; String ip = a+"."+b+"."+c+"."+d; if (ip.length()<len+3) continue; // this is to reject those int's parsed from "01" or "00"-like substrings System.out.println(ip); } } } } public static boolean isValid(String s){ if(s.length()>3 || s.length()==0 || (s.charAt(0)=='0' && s.length()>1) || Integer.parseInt(s)>255) return false; return true; } }

点赞回复分享

发布于 2018-04-10 21:24

Jinac

UM Java

DFS做法，能满足需求，有改进的地方欢迎大家提出 import java.util.*; //Author: Zhenjie Hao public class Main { public static void main(String[] args){ int input = 123; List<List<String>> result = new ArrayList<>(); result = converse(input); display(result); } public static List<List<String>> converse(int input){ String str = String.valueOf(input); List<List<String>> result = new ArrayList<>(); dfs(str, 0 , new ArrayList<>(), result); return result; } public static void dfs(String str, int startIndex, List<String> path, List<List<String>> result){ if(startIndex == str.length()){ result.add(new ArrayList<String>(path)); } for(int i = startIndex + 1; i <= str.length(); i++){ String sub = str.substring(startIndex, i); if(!isValid(sub)){ break; } path.add(numToAlg(sub)); dfs(str, i, path, result); path.remove(path.size()-1); } } public static boolean isValid(String str){ //str = "12" or "27" if(str.charAt(0) == '0'){ return false; } int num = Integer.parseInt(str); if(num < 1 || num > 26){ return false; } return true; } public static String numToAlg(String str){ //str = "12" //putput = "d" int num = Integer.parseInt(str); return String.valueOf((char)('a' + num - 1)); } public static void display(List<List<String>> result){ for(int i = 0; i < result.size(); i++){ StringBuilder sb = new StringBuilder(); for(int j = 0; j < result.get(i).size(); j++){ sb.append(result.get(i).get(j)); } System.out.println(sb.toString()); } } }

点赞回复分享

发布于 2018-09-20 15:50