Plus One, Largest Number, Pow(x, n), Sqrt(x) , Min Stack, Word Ladder, Word Ladder II

Posted on 2015-09-06   |   In 刷题   |  

Plus One

Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.

Solution

Just find the last 9…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] plusOne(int[] digits) {
          int i=digits.length-1;
          for(;i>=0;i--){
              if(digits[i]!=9) break;
          }
            
          if(i==-1){
              int[] res=new int[digits.length+1];
                      res[0]=1;
                      return res;
          }   
           
          else{
             int[] res=new int[digits.length];
             for(int j=0;j<=i;j++){
                 res[j]=digits[j];
             }
             res[i]+=1;
             return res;
          } 
 
      }

Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.

Solution

Rewirte comparator (to desc), sort and add.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private class StringComparator implements Comparator<String> {
       public int compare(String x, String y) {
           if (x.equals(y)) return 0;            
           return -(x+y).compareTo(y+x);
       }
   }
public String largestNumber(int[] num){
  String[] nums = new String[num.length];
  for(int i =0 ;i<num.length;i++){
    nums[i]=String.valueOf(num[i]);
  }
  Comparator<String> comparator = new StringComparator();
  Arrays.sort(nums,comparator);
  StringBuilder str = new StringBuilder();
  for(String n:nums){
    str.append(n);
  }
  return str.charAt(0)=='0'?"0":str.toString();
}

Pow(x, n)

Implement pow(x, n).

Recursive Solution

1
2
3
4
5
6
7
8
9
10
11
public double pow(double x, int n) {
    
    if(n==0) return 1;
    
    if(n<0)
    {
        n=-n;
        x=1/x;
    }
    return n%2==0 ? pow(x*x,n/2) : x*pow(x*x,n/2);
}

Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.

Solution

Beware of overflow problems…
mid*mid could overflow, instead of using long, compare mid with x/mid
but now we have to treat 0 and 1 as special cases…

1
2
3
4
5
6
7
8
9
10
11
12
public int sqrt(int x) {     
       int l=0,r=x;
       if(x==0) return 0;
       if(x==1) return 1;
       while(l<=r){
        int mid=(l+r)/2;
        if(x/mid==mid) return mid;
        else if(mid>x/mid){r=mid-1;}
        else {l=mid+1;}
       }
       return r;      
    }

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.

Solution

Just use an extra stack to keep track of the min values…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Stack<Integer> stk=new Stack<Integer>();
   Stack<Integer> minstk=new Stack<Integer>();
   
   public void push(int x) {
       stk.push(x);
       if(minstk.isEmpty() || x<=minstk.peek()){minstk.push(x);}
   }
   public void pop() {
    if(stk.isEmpty()) return;     
       int tmp=stk.pop();
       if(!minstk.isEmpty() && tmp==minstk.peek()){minstk.pop();}
   }
   public int top() {
    if(stk.isEmpty()) return 0;
    else return stk.peek();
   }
   public int getMin() {
       if(!minstk.isEmpty()) return minstk.peek();
       return 0;
   }

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

BFS Search Solution

Naive approach might not give the shortest length, this problem is equavlent to finding the shortes path between start and end characters, in a graph where chars in dict are vertexes and vertexes with one char difference are connected.

Few more details to attend to:

length should start at 1, and return length+1
queue.size() and q.poll() is changing within each loop, so keep track of them

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
  
  public int ladderLength(String start, String end, HashSet<String> dict) {
    LinkedList<String> q=new LinkedList<String>();
    if(start==null || end==null || dict==null || dict.size()==0) return 0;
    int length=1;
    q.offer(start);
    dict.remove(start);
    while(!q.isEmpty()){
        int count_level=q.size();
        for(int i=0;i<count_level;i++){
            String cur=q.poll();
            for(int j=0;j<cur.length();j++){
                for(char c='a'; c<='z';c++){
                    String tmp=reorg(cur, j, c);
                    if(tmp.equals(end)) return length+1;
                    else if(dict.contains(tmp)){dict.remove(tmp); q.offer(tmp);}
                } 
            }
        } length++;
    }
    return 0;
}
private String reorg(String s, int i, char c)
{
    char[] tmparr=s.toCharArray();
    tmparr[i]=c;
    String res=new String(tmparr);
    return res;
}

Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
Return

1
2
3
4
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Note:
All words have the same length.
All words contain only lowercase alphabetic characters.

人家的解法都看晕了…

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
public class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        
        // Start typing your Java solution below
        // DO NOT write main() function              
        
        HashMap<String, HashSet<String>> neighbours = new HashMap<String, HashSet<String>>();
        
        dict.add(start);
        dict.add(end);
        
        // init adjacent graph        
        for(String str : dict){
            calcNeighbours(neighbours, str, dict);
        }
        
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        
        // BFS search queue
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(new Node(null, start, 1));
        
        // BFS level
        int previousLevel = 0;
        
        // mark which nodes have been visited, to break infinite loop
        HashMap<String, Integer> visited = new HashMap<String, Integer>(); 
        while(!queue.isEmpty()){
            Node n = queue.pollFirst();            
            if(end.equals(n.str)){ 
                // fine one path, check its length, if longer than previous path it's valid
                // otherwise all possible short path have been found, should stop
                if(previousLevel == 0 || n.level == previousLevel){
                    previousLevel = n.level;
                    findPath(n, result);                    
                }else {
                    // all path with length *previousLevel* have been found
                    break;
                }                
            }else {
                HashSet<String> set = neighbours.get(n.str);                 
                
                if(set == null || set.isEmpty()) continue;
                // note: I'm not using simple for(String s: set) here. This is to avoid hashset's
                // current modification exception.
                ArrayList<String> toRemove = new ArrayList<String>();
                for (String s : set) {
                    
                    // if s has been visited before at a smaller level, there is already a shorter 
                    // path from start to s thus we should ignore s so as to break infinite loop; if 
                    // on the same level, we still need to put it into queue.
                    if(visited.containsKey(s)){
                        Integer occurLevel = visited.get(s);
                        if(n.level+1 > occurLevel){
                            neighbours.get(s).remove(n.str);
                            toRemove.add(s);
                            continue;
                        }
                    }
                    visited.put(s,  n.level+1);
                    queue.add(new Node(n, s, n.level + 1));
                    if(neighbours.containsKey(s))
                        neighbours.get(s).remove(n.str);
                }
                for(String s: toRemove){
                    set.remove(s);
                }
            }
        }
        return result;
    }
    
    public void findPath(Node n, ArrayList<ArrayList<String>> result){
        ArrayList<String> path = new ArrayList<String>();
        Node p = n;
        while(p != null){
            path.add(0, p.str);
            p = p.parent; 
        }
        result.add(path);
    }
    /*
     * complexity: O(26*str.length*dict.size)=O(L*N)
     */
    void calcNeighbours(HashMap<String, HashSet<String>> neighbours, String str, HashSet<String> dict) {
        int length = str.length();
        char [] chars = str.toCharArray();
        for (int i = 0; i < length; i++) {
            
            char old = chars[i]; 
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == old)  continue;
                chars[i] = c;
                String newstr = new String(chars);                
                
                if (dict.contains(newstr)) {
                    HashSet<String> set = neighbours.get(str);
                    if (set != null) {
                        set.add(newstr);
                    } else {
                        HashSet<String> newset = new HashSet<String>();
                        newset.add(newstr);
                        neighbours.put(str, newset);
                    }
                }                
            }
            chars[i] = old;
        }
    }
    
    private class Node {
        public Node parent;
        public String str;
        public int level;
        public Node(Node p, String s, int l){
            parent = p;
            str = s;
            level = l;
        }
    }
}
#Math #Array #String
Sudoku Solver, N-Queens, N-Queens II
Single Number, Single Number II, Decode Ways, Triangle