InterviewBit-Day9

发表于 | 分类于
| 字数统计 700 | 阅读时长 4

Practice

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

Example:

Given s = "Hello World",

return 5 as length("World") = 5.

Please make sure you try to solve this problem without using library functions. Make sure you only traverse the string once.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int lengthOfLastWord(final String A) {
        int len = A.length();
        if (len == 0) {
            return 0;
        }
        
        int count = 0;
        int i = len - 1;
        int end = len - 1;
        while (i >= 0 && A.charAt(i) == ' ') {
            i--;
        }
        
        while (i >= 0 && A.charAt(i) != ' ') {
            i--;
            count++;
        }
        
        return count;
    }
}

Roman To Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Read more details about roman numerals at Roman Numeric System

Example :

1
2
Input : "XIV"
Return : 14
1
2
Input : "XX"
Output : 20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public int romanToInt(String A) {
        int l = A.length();
        if(l==0) return 0;
        
        
        int sum = 0;
        for(int i=0;i<l-1;i++) {
            char c = A.charAt(i);
            char cn = A.charAt(i+1);
            
            int valc = value(c);
            int valcn = value(cn);
            if(valc == 0) continue;
            else if(valcn == 0 || valc>=valcn) sum += valc;
            else sum -= valc;
        }
        
        sum += value(A.charAt(l-1));
        
        return sum;
    }
    
    static int value(char c) {
        if(c == 'I') return 1;
        else if(c == 'V') return 5;
        else if(c == 'X') return 10;
        else if(c == 'L') return 50;
        else if(c == 'C') return 100;
        else if(c == 'D') return 500;
        else if(c == 'M') return 1000;
        
        return 0;
    }
}

Justified Text

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line.

Pad extra spaces ‘ ‘ when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible.
If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.

Your program should return a list of strings, where each string represents a single line.

Example:

words: ["This", "is", "an", "example", "of", "text", "justification."]

L: 16.

Return the formatted lines as:

1
2
3
4
5
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Solution {
    public ArrayList<String> fullJustify(ArrayList<String> A, int B) {
        ArrayList<String> ans = new ArrayList<>();
        int i = 0, j = 0;
        while (i < A.size()) {
            int len = 0;
            StringBuilder sb = new StringBuilder();
            while (i < A.size() && len <= B) {
                len += A.get(i++).length() + 1;
            }
            len--;
            if (len > B) {
                len -= A.get(--i).length() + 1;
                int space = 0, w = 0;
                if(i!=j+1) {
                    space = (B - len)/(i - j-1);
                    w = (B - len)%(i - j-1);
                }
                for (int k = j; k < i; k++) {
                    sb.append(A.get(k));  
                    if(k == i-1)
                        break;
                for(int a = 0; a < space; a++)
                    sb.append(" ");
                    if(w > 0) {
                        w--;
                        sb.append(" ");
                    }
                    sb.append(" ");
                }
                j = i;                
            }
            else {
                for (int k = j; k < i; k++) {
                    sb.append(A.get(k)).append(" ");
                }
                
                if (sb.length() > B)
                    sb.deleteCharAt(sb.length()-1);
                j = i;
            }
             while (sb.length() < B) {
                    sb.append(" ");
                } 
            ans.add(sb.toString());
        }
        return ans;
    }
}
0%