Remove Duplicates From Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

01 public ListNode deleteDuplicates(ListNode head) {
02     ListNode prev=null;
03     ListNode curr=head;
04   
05     while(curr!=null && curr.next!=null)
06     {
07         if(curr.val!=curr.next.val)
08         {
09             prev=curr;
10             curr=curr.next;              
11         }          
12         else
13         {
14             while(curr.next!=null && curr.val==curr.next.val)
15             {
16                 if(head==curr)
17                 {
18                     head=head.next;
19                 }                      
20                 curr=curr.next;                  
21             }              
22             if(prev==null)
23             {
24                 prev=curr.next;                  
25             }              
26             else
27             {
28                 prev.next=curr.next;                  
29             }              
30             if(head==curr)
31             {                  
32                 head=head.next;
33             }            
34             curr=curr.next;              
35         }
36     }
37     return head;
38 }

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

Hint: simulate the process just as you are doing decimal division by hand.

01 public int divide(int dividend, int divisor) {
02    long dividend_long=dividend;
03    long divisor_long=divisor;
04    boolean isNegative=false;
05  
06    if(dividend_long<0)
07    {
08        isNegative=true;
09        dividend_long=-dividend_long;
10    }
11  
12    if(divisor_long<0)
13    {
14        isNegative=!isNegative;
15        divisor_long=-divisor_long;
16    }
17  
18    int quotient=0;      
19    while(dividend_long>=divisor_long)
20    {
21        long sum=divisor_long;
22        int digit=1;
23        while((sum+sum)<=dividend_long)
24        {
25            sum+=sum;
26            digit<<=1;
27        }
28        quotient+=digit;
29        dividend_long-=sum;
30    }
31  
32    if(isNegative)
33        quotient=-quotient;
34  
35    return quotient;
36 }

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

01 public boolean isPalindrome(String s) {
02     if(s=="") return true;
03     char[] str=s.toCharArray();
04     if(str.length==1) return true;
05     int start=0, end=str.length-1;
06     while(start<end)
07     {
08         while(start<str.length && !isAlphanumeric(str[start]))  start++;
09         while(end>= 0 && !isAlphanumeric(str[end])) end--;
10         if(start>=end)  return true;
11         if(!isEqual(str[start],str[end]))
12         {
13             return false;
14         }
15         start++;
16         end--;
17     }
18     return true;
19   
20 }
21 public boolean isAlphanumeric(char c)
22 {
23     return isLetter(c)||isNumber(c);
24 }
25 public boolean isLetter(char c)
26 {
27     if(c>='a' && c<='z' ||c>='A' && c<='Z')
28         return true;
29     else
30         return false;
31 }
32 public boolean isNumber(char c)
33 {
34     if(c>='0' && c<='9') return true;
35     else return false;
36 }
37 
38 public boolean isEqual(char a, char b)
39 {
40     if(isLetter(a) && isLetter(b) && Character.toUpperCase(a)==Character.toUpperCase(b))
41         return true;
42     else if(isNumber(a) && isNumber(b) && a==b)
43         return true;
44     else
45         return false;
46 }

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

01 public int removeElement(int[] A, int elem) {
02     int last=A.length-1;
03     int i=0;
04     while(i<last)
05     {
06         if(A[i]==elem)
07         {
08             while(last>i&&A[last]==elem)
09             {
10               
11                 last--;
12             }
13             A[i]=A[last];
14             i++;
15             last--;
16         }
17         else
18         {
19             i++;
20         }
21     }
22     if(last>=0 && A[last]==elem)
23         last--;
24     return last+1;
25 }

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

01 public boolean isValid(String s) {
02     char[] str=s.toCharArray();
03     if(str.length%2==1)
04         return false;
05     char [] stack =new char[str.length];
06     int index=0;
07     for(int i=0;i<str.length;i++)
08     {
09         char curr=str[i];
10         if(curr=='(' || curr=='[' || curr=='{')
11         {
12             stack[index++]=str[i];
13         }
14         else
15         {
16             if(index==0)
17                 return false;
18             else
19             {
20                 char left=stack[--index];
21                 if(!isMatch (left,curr))
22                     return false;
23             }
24         }
25     }
26     if(index==0)
27         return true;
28     else
29         return false;
30 }
31 public boolean isMatch(char left, char right)
32 {
33     if(left=='(' && right == ')'|| left=='[' && right==']' || left=='{' && right=='}')
34         return true;
35     else
36         return false;
37 }

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Hint: use dynamic programming. However, instead of using n arrays which in total cost n^2 space, we just use 2 arrays interchangeably to store the minimum path sum until the current row.

01 public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
02     // Start typing your Java solution below
03     // DO NOT write main() function
04     int size=triangle.size();
05     if(size==0)
06         return 0;
07     //get the numbers of each row in the original triangle
08     ArrayList<Integer> row=triangle.get(0);
09   
10     //keeps the minimum path sum to reach each node of the current line
11     //starts from the 0-th line
12     ArrayList<Integer> al=new ArrayList<Integer>();
13     al.add(row.get(0));
14     if(size==1)
15         return al.get(0);
16   
17     //Iterate from the 1-st line
18     for(int i=1;i<size;i++)
19     {
20        //keep the numbers of the previous line in al
21        //use another array al2 to calculate the new path sum
22        //then copy the new result in al2 back to al
23         ArrayList<Integer> al2=new ArrayList<Integer>();
24         for(int k=0;k<al.size();k++)
25         {
26             al2.add(al.get(k));
27         }
28       
29         row=triangle.get(i);          
30         int lmost=row.get(0)+al.get(0);
31         al2.set(0,lmost);
32         for(int j=1;j<i;j++)
33         {
34             //minimum of the left index and itself in the previous line
35             //plus its own value
36             int value=Math.min(al.get(j-1),al.get(j))+row.get(j);
37             al2.set(j,value);
38         }
39         int rmost=al.get(i-1)+row.get(i);
40         al2.add(rmost);
41         al=al2;
42     }
43   
44     //find min
45     int min=al.get(0);
46     for(int i=0;i<al.size();i++)
47     {
48         if(al.get(i)<min)
49         {
50             min=al.get(i);
51         }
52     }
53   
54     return min;
55           
56 }

Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Hint: for a set of N distinct numbers, the total number of subsets is 2^N. The idea is to use a boolean array used[], which has the same length with S, to indicate whether a number of S at position i is selected.

Solution 1: 

01 public ArrayList<ArrayList<Integer>> subsets(int[] S) {

02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();        

03     if(S.length==0)

04         return results;

05   

06     //use a boolean array to indicate whether a number is selected

07     boolean [] used =new boolean [S.length];

08   

09     //first sort S, so that outputs are in correct order

10     Arrays.sort(S);

11     findSubsets(used, 0, S, results);

12     return results;

13 }

14 public void findSubsets(boolean [] used, int pos, int [] S, ArrayList<ArrayList<Integer>> results)

15 {

16     //reach the last position, output our selection

17     if(pos==S.length)

18     {

19         ArrayList<Integer> out =new ArrayList<Integer>();

20         for(int i=0;i<used.length;i++)

21         {

22             if(used[i])

23             {

24                 out.add(S[i]);

25             }

26         }

27         results.add(out);

28         return;

29     }

30   

31     //each position can be false or true,

32     //indicating whether the number at this position is selected or not

33     //then handle the next position

34     used[pos]=false;

35     findSubsets(used, pos+1, S, results);

36   

37     used[pos]=true;

38     findSubsets(used, pos+1, S, results);

39 }

Solution 2:

Instead of using an additional boolean array to store the information of which numbers are selected, we can use an integer to do so. In this manner, we pre-calculate how many subsets we will have in total, say, N. Then we use number 0 to N-1 to represent each subset. For example, we use 0, 1, 2, 3 to represent the subsets of 2 numbers, i.e., 00, 01, 10, 11. This is an iterative solution instead of a recursion one.

Java语言: Subsets

01 public ArrayList<ArrayList<Integer>> subsets(int[] S) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();        
03     Arrays.sort(S);              
04     //calculate total number of subsets        
05     for(int i=0;i<(1<<S.length);i++)
06     {
07         ArrayList<Integer> set=new ArrayList<Integer>();          
08         //convert this number representation into set
09         int number=i;          
10         for(int j=0;j<S.length;j++)
11         {              
12             if(number==0)
13                 break;
14             //the digit is 1, indicate the number is selected
15             if(number%2==1)
16             {
17                 set.add(S[j]);
18             }
19             //shift one bit to right, then check the next digit
20             number>>=1;
21         }
22         results.add(set);
23     }
24     return results;      
25 }