Add Two Numbers

Problem:

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Analysis:
Need to create a new ListNode other than the returned one. Because each iteration would cause the new ListNode point to its next node, keep the head is necessary.

Solution:

1:  /**  
2:   * Definition for singly-linked list.  
3:   * public class ListNode {  
4:   *   int val;  
5:   *   ListNode next;  
6:   *   ListNode(int x) {  
7:   *     val = x;  
8:   *     next = null;  
9:   *   }  
10:   * }  
11:   */  
12:  public class Solution {  
13:    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
14:      int carry=0;  
15:      ListNode result=new ListNode(0);  
16:      ListNode l3=result;  
17:      while(l1!=null || l2!=null)  
18:      {  
19:        if(l1!=null)  
20:        {  
21:          carry+=l1.val;  
22:          l1=l1.next;  
23:        }  
24:        if(l2!=null)  
25:        {  
26:          carry+=l2.val;  
27:          l2=l2.next;  
28:        }  
29:        l3.next=new ListNode(carry%10);  
30:        carry/=10;  
31:        l3=l3.next;  
32:      }  
33:      if(carry==1)  
34:      {  
35:       l3.next=new ListNode(1);    
36:      }  
37:      return result.next;  
38:    }  
39:  }  

Two Sum

Problem:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution:

1:  public class Solution {  
2:    public int[] twoSum(int[] numbers, int target) {  
3:      HashMap<Integer,Integer> map= new HashMap<Integer,Integer>();  
4:      int[] result=new int[2];  
5:      for(int i=0;i<numbers.length;i++)  
6:        {  
7:          if(map.containsKey(numbers[i]))  
8:         {  
9:           int index=map.get(numbers[i]);  
10:           result[0]=index+1;  
11:           result[1]=i+1;  
12:           break;  
13:         }   
14:         else  
15:          map.put(target-numbers[i],i);  
16:        }  
17:       return result;  
18:    }  
19:  }  

String to Integer (atoi)

Problem:

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Analysis:

1. The initial plus or minus sign is optional.. 

2. When encounter a non digit character, ignore the rest of the string.

3. When converts char to int, use str.charAt(i)-'0'. The difference of the unicodes. 

4. Need to check integer overflow before add up to the next digit. 

Solution:

1:  public class Solution {  
2:    public int atoi(String str) {  
3:      int i=0;//the counter  
4:      boolean isNeg=false;  
5:      int result=0;  
6:      if(str==null || str.length()<1)  
7:       return 0;  
8:      str=str.trim(); //Elimilate spaces   
9:      if(str.charAt(i)=='-')  
10:      {  
11:        isNeg=true;  
12:        i++;  
13:      }  
14:      else if(str.charAt(i)=='+')  
15:      {  
16:        i++;  
17:      }  
18:      while(i<str.length()&& str.charAt(i) >= '0' && str.charAt(i) <= '9') {  
19:        //Check overflow  
20:      if(Integer.MAX_VALUE/10<result||Integer.MAX_VALUE/10==result&&Integer.MAX_VALUE%10<(str.charAt(i) - '0'))  
21:       return isNeg==false?Integer.MAX_VALUE:Integer.MIN_VALUE;  
22:            result = result * 10 + (str.charAt(i) - '0');  
23:            i++;  
24:      }  
25:     return isNeg==false?result:-result;  
26:    }  
27:  }