DAY 7 Interview

1. Container with Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container

public class Solution {
    public int maxArea(int[] height) {

    }
}

 

2. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
基本递归题目,使用一个数组定义键盘。
注意convert char to int / convert int to char

 
public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> results=new ArrayList<String>();
        StringBuilder re=new StringBuilder();
        String[] board=new String[10];
        board[0]=" ";board[1]="1";board[2]="abc";
        board[3]="def";board[4]="ghi";board[5]="jkl";
        board[6]="mno";board[7]="pqrs";board[8]="tuv";board[9]="wxyz";
        helper(results,re,digits,board,0);
        return results;
    }
    public void helper(ArrayList<String> results, StringBuilder re, String digits, String[] board, int step){
        if(step==digits.length()){
            results.add(re.toString());
            return;
        }
        String s=board[digits.charAt(step)-'0'];
        //or
        //int num=digits.charAt(step);
        //String s=board[num];
        for(int i=0;i<s.length();i++){
            re.append(s.charAt(i));
            helper(results,re,digits,board,step+1);
            re.deleteCharAt(step);
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s