[LeetCode] Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321 

 注意：overflow and underflow

Java Code:

public int reverse(int x) {
        long reversedInt = 0;
        
        while(x!=0){
            reversedInt = reversedInt * 10 + x%10;
            x = x/10;
            if(reversedInt >= Integer.MAX_VALUE) return Integer.MAX_VALUE;     
            if(reversedInt <= Integer.MIN_VALUE) return Integer.MIN_VALUE;
        }
        
        return (int) reversedInt;
    }

[LeetCode] Reorder List

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

解题思路：
1，找出中间位置的element，将linkedlist分为两半
2，反转后半部分的linkedlist
3，将2部分的linkedlist合成

注意：在找出median的element的时候，我用了最基本的方法，统计出element的总数，然后count/2. 这样就会重复遍历list. 可以设置2个指针，一个每次走一步，另一个每次走2步，走到2步为null的时候，走一步的指针就指向的为中间的element


Java Code:

public void reorderList(ListNode head) {
        int count = 0;
        ListNode p = head;
        
        while( p != null){
            p = p.next;
            count++;
        }
        
        if(count < 3) return;
        
        //find the median element starting with p
        ListNode prev = head;
        p = head;
        int i = 0;
        while( p != null && i <= count/2){
            i++;
            prev = p;
            p = p.next;
        }
        
        //reverse the after half linkedList
        prev.next = null;
        prev = prev.next;
        
        while(p != null){
               ListNode tmp = p;
               p = p.next;
               tmp.next = prev;
               prev = tmp;
        }
        
        p = prev;
        prev = head;
        //merge the two half linkedlist 
        while(p != null && prev != null){
            ListNode tmp = p;
            p = p.next;
            tmp.next = prev.next;
            prev.next = tmp;
            prev = tmp.next;
        }
        
    }

[LeetCode] 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.


Java Code

 public int removeElement(int[] A, int elem) {
        int num = 0;
        
        for(int i = 0; i < A.length; i++){
            if(A[i] == elem){
                num++;
                continue;
            }
            
            A[i-num] = A[i];
        }
        
        return A.length - num;
    }

[LeetCode] Remove Duplicates from LinkedList

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
 
解题思路：
  用2个指针，将重复的给删除掉

Java Code:

public ListNode deleteDuplicates(ListNode head) {
         if(head == null) return head;
        
         ListNode prev = head;
         ListNode p = prev.next;
         
        while(p != null){
            if(p.val != prev.val){
                prev = p;
                p = p.next;
            }else{
                p = p.next;
                prev.next = p;
            }
        }
        
        return head;
    }

[LeetCode] Remove Duplicates from Sorted Array2

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].

 解题思路：
与1类似有一个movesteps来记录i位置需要往前移动几位，另外加一个变量来统计每个不同元素的个数。

Java Code:

 public int removeDuplicates(int[] A) {
       int moveSteps = 0;
       int count = 1;
       
       for(int i = 1; i < A.length; i++){
           if(A[i] == A[i-1]){
               count++;
           }else{
                if(count > 2) moveSteps += count - 2;
               
                count = 1;
           }
           
           if(count <= 2){
                A[i-moveSteps] = A[i];
           }
       }
       
       if(count > 2) moveSteps += count - 2;
       
       return A.length - moveSteps;
    }

[LeetCode] Remove Duplicate Elements from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

 解题思路：
          用一个变量来统计在i位置以前总共有多少个duplicate，然后将此元素向前移动几步
Java Code:

public int removeDuplicates(int[] A) {
       int moveStep = 0;
        
        for(int i = 1; i < A.length; i++){
            if(A[i] == A[i-1]){
                moveStep++;
            }
            A[i-moveStep] = A[i];
        }
        
        return A.length - moveStep; 
    }

[LeetCode] Pow(x,n)

Implement pow(x, n). 

解题思路：二分法，注意n < 0的情况


Java Code:

public double pow(double x, int n) {
        if(n == 0) return 1.0;
        int m = Math.abs(n);
        double result = 0.0;
        
        double tmp = pow(x, m/2);
        
        if(m%2 == 0){
            result = tmp*tmp;
        }else{
            result = tmp*tmp*x;
        }
        
        result = n < 0? 1.0/result : result;
        return result;
    }