模拟 2016-7-14

[wolfogre]

LeedCode12

POJ1068

[wolfogre]

//LeedCode 12 AC 参考http://jeankorte.ca/jk-roman-numeral-converter.html

#include <string>
class Solution {
public:
    string intToRoman(int num) {
        if(num < 1 || num > 3999)
            return "out of range";

        #define ARRAY_LENGHT 13
        std::string chars[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int nums[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};

        std::string roman = "";
        for (int i = 0;  i < ARRAY_LENGHT; ++i){
            while(num >= nums[i]){
                roman += chars[i];
                num -= nums[i];
            }
            if(num <= 0)
                break;
        }

        return roman;
    }
};

速度提高4ms

#include <string>
class Solution {
public:
    string intToRoman(int num) {
        if(num < 1 || num > 3999)
            return "out of range";

        #define ARRAY_LENGHT 13
        static std::string chars[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        static int nums[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};

        std::string roman = "";
        for (int i = 0;  i < ARRAY_LENGHT; ++i){
            while(num >= nums[i]){
                roman += chars[i];
                num -= nums[i];
            }
            if(num <= 0)
                break;
        }

        return roman;
    }
};

[wolfogre]

poj1068

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T-- > 0){
        vector<int> input;
        int n;
        cin >> n;
        while(n-- > 0){
            int temp;
            cin >> temp;
            input.push_back(temp);
        }

        string str;
        int left_count = 0;
        for(int i = 0; i < input.size(); ++i){
            while(left_count < input[i]){
                str += "(";
                ++left_count;
            }
            str += ")";
        }

        vector<int> result;
        for(int i = 0; i < str.length(); ++i){
            if(str[i] == '(')
                continue;
            int right_count = 1;
            int other_right_count = 0;
            for(int j = i - 1; j >= 0; --j){
                if(str[j] == ')'){
                    ++other_right_count;
                    ++right_count;
                } else {
                    if(other_right_count > 0){
                        --other_right_count;
                    } else{
                        result.push_back(right_count);
                        break;
                    }
                }
            }
        }

        for(int i = 0; i < result.size(); ++i) {
            cout << result[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

[SnackMen]

/*
粗暴方法 Runtime 12ms
LeedCode12  AC
*/
public class Solution {
    public String intToRoman(int num) {
        String string="P";
        int tho = num/1000;
        int hund = (num-tho*1000)/100;
        int ten = (num-tho*1000-hund*100)/10;
        int unit = num-tho*1000-hund*100-ten*10;
        for(int i=0;i<tho;i++){
            string+="M";
        }
        if(hund<=3){
            for(int i=0;i<hund;i++){
                string+="C";
            }
        }else{
            if(hund==4)
                string+="CD";
            else if(hund==5)
                string+="D";
            else if(hund==6)
                string+="DC";
            else if(hund==7)
                string+="DCC";
            else if(hund==8)
                string+="DCCC";
            else if(hund==9)
                string+="CM";
        }
        if(ten<=3){
            for(int i=0;i<ten;i++){
                string+="X";
            }
        }else{
            if(ten==4)
                string+="XL";
            else if(ten==5)
                string+="L";
            else if(ten==6)
                string+="LX";
            else if(ten==7)
                string+="LXX";
            else if(ten==8)
                string+="LXXX";
            else
                string+="XC";
        }
        if(unit<=3){
            for(int i=0;i<unit;i++){
                string+="I";
            }
        }else{
            if(unit==4)
                string+="IV";
            else if(unit==5)
                string+="V";
            else if(unit==6)
                string+="VI";
            else if(unit==7)
                string+="VII";
            else if(unit==8)
                string+="VIII";
            else
                string+="IX";
        }
        return string.substring(1,string.length());
    }
}

[zhaokuohaha]

Leecode12-C#-投机取巧

public class Solution
    {
        public string IntToRoman(int num)
        {
            string[,] rBase = { 
                { "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" },
                { "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" },
                { "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" },
                { "M", "MM", "MMM", "", "", "", "", "", "" }
            };

            string s = "";
            int b = 1000;
            int r  = 3;
            while(num != 0)
            {
                int c = num / b;
                if (c != 0)
                {
                    s += rBase[r, c-1];
                    num %= b;
                }
                b /= 10;
                r--;
            }
            return s;
        }
    }

[dayang]

/**
  * [AC] LeetCode 12
 * @param {number} num
 * @return {string}
 */
var intToRoman = function (num) {
    var trans = {
        1: 'I',
        4: 'IV',
        5: 'V',
        9: 'IX',
        10: 'X',
        40: 'XL',
        50: 'L',
        90: 'XC',
        100: 'C',
        400: 'CD',
        500: 'D',
        900: 'CM',
        1000: 'M'
    };

    var res = '';
    var b = 1000;
    while (num > 0) {
        var c = Math.floor(num / b);
        if (c > 0) {
            if (trans[c * b]) {
                res += trans[c * b];
            } else {
                var base;
                base = c < 4 ? '': trans[b*5];
                for (var i = 0; i < c % 5; i++) {
                    base += trans[b];
                }
                res += base;
            }
            num %= b;
        }
        b /= 10;
    }

    return res;
};

[dayang]

//[AC] poj 1068
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int p[25];
int pos[25];

int main()
{
    int t,n;
    cin >> t;
    while(t--){
        cin >> n;
        string s = "";
        for(int i = 0; i < n; i++){
            cin >> p[i];
            int len = i == 0 ? p[i] : p[i]-p[i-1];
            for(int j = 0;j <len;j++){
                s += "(";
            }
            s+=")";
            pos[i] = p[i] + i;
        }
        for(int i = 0; i < n; i++){
            int count = 1;
            int num = 0;
            for(int j = pos[i] - 1; j>=0; j--){
                if(s[j] == ')'){
                    count ++;
                }else{
                    count --;
                    num++;
                    if(count == 0)
                        break;
                }
            }
            cout << num << (i == n - 1 ? "" : " ");
        }
        cout << endl;
    }

    // system("pause");
    return 0;
}

[SnackMen]

/*
POJ 1068
*/
import java.util.Scanner;

/**
 * Created by laowang on 2016/7/14.
 */
public class Main {
    public static int number[];
    public static int m = 0;
    public static int k = 0;
    public static int right[];

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        while ((N--) > 0) {
            int n = scanner.nextInt();
            int num[] = new int[n];
            number = new int[n * 2];
            for (int i = 0; i < n; i++) {
                num[i] = scanner.nextInt();
            }
            for (int i = 0; i < n; i++) {
                number[num[i] + i] = 1;
            }
            boolean isUsed[] = new boolean[2 * n];
            for (int i = 0; i < 2 * n; i++) {
                if (number[i] == 1) {
                    int a = 0;
                    for (int j = i - 1; j >= 0; j--) {
                        if (isUsed[j] && number[j] == 0) {
                            a++;
                        }
                        if (!isUsed[j] && number[j] == 0) {
                            a++;
                            isUsed[j] = true;
                            break;
                        }
                    }
                    System.out.print(a + " ");
                }
            }
            System.out.println();
        }
    }
}