Monday, August 18, 2014

[LeetCode]Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.

解题思路:
这题还是挺巧妙的。由于每个node有一个指向随机结点的指针,而要找到此随机结点事很困难的。如果按照传统思路,新旧linkedlist分别为两个独立的linkedlist, 那对于新的linkedlist中的每个node来说,我们只知道对应的node在原来的linkedlist里指向的random 的node. 这是非常困难的,这的记住每个random node 在linkedlist 中的index, 这是非常复杂的。
所以,如果我们想到将新的node放到原来的linkedlist里,然后每个新的node都在对应旧的node的后面一位,那么我们就能很容易的找到新的random node了。因为每个新点的random node就是旧点的random node 的下一位。
总结下来,我们有三步:

1. copy the node
2. copy the random pointer
3. decouple the new linkedlist

Java Code:
public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode safehead = new RandomListNode(0);
           RandomListNode currP = head;
           
           //copy the node
           while(currP != null){
               RandomListNode tmp = new RandomListNode(currP.label);
               tmp.next = currP.next;
               currP.next = tmp;
               currP = tmp.next;
           }
           
           currP = head;
           //copy the random pointer
           while(currP != null){
               
               if(currP.random != null){
                  currP.next.random = currP.random.next;    
               }
               
               currP = currP.next.next;
           }
           
           //decouple the list
            RandomListNode p = safehead;
            currP = head;
            
            while(currP != null){
                p.next = currP.next;
                currP.next = currP.next.next;
                currP = currP.next;
                 p = p.next;
            }
           
            return safehead.next;
    }

[LeetCode] Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.


解题思路:
找到中间点,然后左边就为其左子树,右边部分就为其右子树。
1. 找中间点,可以先扫描一遍list, 然后得出node的总数n, 然后n/2就是其中间点
2. 可以用两个pointer, 一个每次走1一步,另一个每次走2步。等走2步的pointer到达尾部时,走一步的pointer刚好走到中间位置。由于我们要找到中间位置的pointer. 所以我们找到了中间pointer的前一个node。
Java Code:
public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        ListNode safehead = new ListNode(0);
        safehead.next = head;
        
        ListNode prev = safehead;
        ListNode p = head;
        
        while( p != null && p.next != null){
            p = p.next.next;
            prev = prev.next;
        }
            
        TreeNode root = new TreeNode(prev.next.val);
        p = prev.next.next;
        prev.next = null;
        root.left = sortedListToBST(safehead.next);
        root.right = sortedListToBST(p);
            
        return root;
    }

[LeetCode] Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization: Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
       1
      / \
     /   \
    0 --- 2
         / \
         \_/ 
 
解题思路:
无向图的邻居,要注意避免重复建设node. 所以我们用一个hashmap来存储已经有的点。当遇到了已经有的点,直接从hahmap里取。
 
Java Code:
 
 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
       
        if(node == null){
            return null;
        }
        
        HashMap allnodes = new HashMap(); 
        List newnodes= new ArrayList();
        List oldnodes= new ArrayList();
       
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
        allnodes.put(node.label, newNode);
        
        newnodes.add(newNode);
        oldnodes.add(node);
        
      do{  
          List newNext= new ArrayList();
          List oldNext= new ArrayList();
        
          for(int i = 0; i < oldnodes.size(); i++){
              UndirectedGraphNode oldnode = oldnodes.get(i);
            
            if(oldnode.neighbors == null){
                continue;
            }
            
            List oldneibors = oldnode.neighbors;
            List newneibors = new ArrayList();
            
            for(UndirectedGraphNode curr : oldneibors){
                UndirectedGraphNode newnode = null;
                if(allnodes.containsKey(curr.label)){
                   newnode = allnodes.get(curr.label);
                }else{
                  newnode = new UndirectedGraphNode(curr.label);
                  allnodes.put(curr.label, newnode);
                  newNext.add(newnode);
                  oldNext.add(curr);
                }
                newneibors.add(newnode);
            }                  
            newnodes.get(i).neighbors = newneibors;
        }
        
        oldnodes = oldNext;
        newnodes = newNext;
      }while(!oldnodes.isEmpty());
      
      return newNode;
    }

Friday, August 15, 2014

[LeetCode] Flattern Binary Tree To LinkedList

Given a binary tree, flatten it to a linked list in-place.
For example,
Given
         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6 
 
解题思路:
1. 如果root同时有left, right, 则把right存到stack
2. 如果root有left, 则将root.right = root.left,即将左子 树移到右子树
3. 如果root == null, 则从stack pop出一个,将此作为root的右子树
4. 每次都将root.right 作为新的root, repeat 1-4
 
Java Code:
 
 
 public void flatten(TreeNode root) {
        TreeNode p = root;
        Stack tmp = new Stack();
        
        while(p != null){ 
            
         if(p.right != null && p.left != null){
             tmp.add(p.right);
         }
         
         if(p.left != null){
             p.right = p.left;
             p.left = null;
         }
         
         if(p.right == null && !tmp.isEmpty()){
             p.right = tmp.pop();
         }
         
         p = p.right;
        }
    }

[LeetCode] Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
       1
      / \
     2   3
Return 6.

 解题思路:
 1. 对于任何一个node, 有四种path情况需要考虑:
  1.1 仅有node
  1.2 左子树+node
  1.3 node + 右子树
  1.4 左子树 + node + 右子树

为了求最大的path sum. 我们需要从1-3中选出最大的返回给parent,从1-4中选出最大的作为备选的最后结果path sum.

Java Code:

public int maxPathSum(TreeNode root){
       int[] max = new int[1];
       max[0] = Integer.MIN_VALUE;
       maxSum(root, max);
       
       return max[0];
    }
    
    public int maxSum(TreeNode root, int[] max){
        int val = 0, left = 0, right = 0;
        
        val = root != null ? root.val : 0;   
        left = root.left != null? maxSum(root.left, max) : 0;
        right = root.right != null ? maxSum(root.right, max) : 0;
        
        int currMax = val;
        
        if(left > 0) currMax += left;
        if(right > 0) currMax += right;
        max[0] = max[0] > currMax? max[0] : currMax;
        
        if(left > 0 && left >= right) return val + left;
        if(right > 0 && right > left) return val + right;
        
        return val;
    }
    

[LeetCode] Best Time to Buy and Sell stock III

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

解题思路:
1. 扫描数组从左到右,算出leftmaxprofit
2. 扫描数组从右到左,算出rightmaxprofit
3. 同时从左到右扫描 leftmaxprofit and rightmaxprofit, 算出最大收益,leftmaxprofit + rightmaxprofit

Java code:

 public int maxProfit(int[] prices) {
       int maxProfit = 0;
        int[] leftMaxProfit = new int[prices.length];
        int[] rightMaxProfit = new int[prices.length];
        
        int minPrice = Integer.MAX_VALUE;
        
        for(int i = 0; i < prices.length; i++){   
            minPrice = minPrice < prices[i]? minPrice : prices[i];
            int profit = prices[i] - minPrice;
            leftMaxProfit[i] = maxProfit > profit ? maxProfit : profit;
        }
        
        int maxPrice = 0;
        maxProfit = 0;
        
        for(int i = prices.length; i > 0; i--){
            int profit = maxPrice - prices[i-1];
            maxProfit = maxProfit > profit ? maxProfit : profit;
            rightMaxProfit[i-1] = maxProfit;
            maxPrice = maxPrice > prices[i-1]? maxPrice : prices[i-1];
        }
        
        maxProfit = 0;
        
        for(int i = 0; i < prices.length; i++){
           int profit = leftMaxProfit[i] + rightMaxProfit[i];
           maxProfit = profit > maxProfit? profit : maxProfit;
        }
        
        return maxProfit;
    }

[LeetCode] Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

 解题思路:
 计算每两相邻的2天的stock price, 将所有收益为正的加起来就是我们想要

Java code:
public int maxProfit(int[] prices) {
        int profit = 0;
        
        for(int i = 1; i < prices.length; i++){
            int diff = prices[i] - prices[i-1];
            profit += diff > 0 ? diff : 0;
        }
        
        return profit;
    }

[LeetCode] Best Time to buy and sell stock

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

 解题思路:
    动态规划: 局部最优 以及 全局最优
    要获得最大收益,最理想的状态就是:在最低价买进,最高价卖出。
    在第 i 天卖出最大收益 profit[i] = price[i] - minPrice。
    在0...n中的最大收益就为 max(profit[0..n])
    在这个过程中最主要的就是要track出第i天的最小价格



java code:
 public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;
        
        for(int i = 0; i < prices.length; i++){   
            minPrice = minPrice < prices[i]? minPrice : prices[i];
            int profit = prices[i] - minPrice;
            maxProfit = maxProfit > profit ? maxProfit : profit;
        }
          
        return maxProfit;
    }

Wednesday, August 6, 2014

[LeetCode] Two Sum

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 

解题思路:
最直接的思路,就是遍历整个数组,对每个元素,从在它以后的数组中寻找是否存在一个元素,它们之和等于target。这种思路的时间复杂度为N*N。

我们要从数组中寻找一组数据,那至少会扫描一遍数组,也就是时间复杂度至少为N。那我们就想到可用HashMap来将搜素元素的时间复杂度降低为O(1)。当遍历数组时,对每个元素,我们用时间复杂度为O(N)来确认是否存在一个元素,它们的和为target. 但只需要O(1)用HashMap搜索target - num[i]是否存在。如果存在,则返回Index。这样我们就可以想到当遍历数组的时候,同时也建立HashMap, target-num[i]为Key, Index为value。

JavaCode:
public int[] twoSum(int[] numbers, int target) {
         HashMap index = new HashMap ();
           int[] result = new int[2];
           
           for(int i = 0; i < numbers.length; i ++){
               if(index.containsKey(numbers[i])){
                   result[0] = index.get(numbers[i]);
                   result[1] = i + 1;
                   
                   break;
               }
               
               index.put(target - numbers[i], i+1);
           }
           
           return result;
    }

Python:
class Solution:
 # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
     dict = {}
     for i in xrange(len(num)):
      newNum = target - num[i]
      if newNum in dict:
       return (dict[newNum] + 1, i + 1)
      dict.update({num[i]: i})

Tuesday, August 5, 2014

[LeetCode] WildCard Matching


Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

 解题思路:
1. 最开始想到的就是递归,但通不过大数据。
2. 后来又想到用数组,类似edit distance的dp。 如果 p(j) == '*', 则match[i][j] = match[i][j-1] || match[i-1][j]. 当p(j) == '?' or p(j) = s(i) 则,match[i][j] = match[i-1][j-1]. 但这样会需要很大的额外空间并且又多了很多不必要的计算。
3. 就是将解法1递归添加一个stack来存储 *和当前s的位置。但是同样通不过大数据,所以我们要进行进一步分析,进行剪枝优化
    3.1 首先想到的就是当多个*连续出现时,它等同于一个*
    3.2 每次回溯时,我们仅需要回溯到最近的一个*的相关位置,对之前出现的*, 我们可以舍弃.
   比如,s="accbcbccx", p="a*b*d",  "a*b" 可以与"accb" 或者 "accbcb" 匹配,当我们发现"cbccx"不能与"*d"匹配时,我们也不回溯到 "accbcb" 然后 匹配 "ccx" 与"*b"
因为第二个*可以匹配任何的字符。

Java Code:


 public boolean isMatch(String s, String p) {
        int s0 = 0;
        int p0 = 0;
        int pre_p = -1, pre_s = -1;
       
       while(s0 < s.length()){
           if(s0 < s.length() && p0 < p.length() && (s.charAt(s0) == p.charAt(p0) || p.charAt(p0) == '?')){
               s0++;
               p0++;
           }else if(p0 < p.length() && p.charAt(p0) == '*'){
               while(p0 < p.length() && p.charAt(p0) == '*') p0++;
               if(p0 == p.length()) return true;
               
               pre_p = p0;
               pre_s = s0;
           }else if(pre_p > -1){
               pre_s++;
               s0 = pre_s;
               p0 = pre_p;
           }else{
               return false;
           }    
       }
       
       while(p0 < p.length() && p.charAt(p0) == '*') p0++;
       
      return p0 == p.length();
    }

Monday, August 4, 2014

[LeetCode] Search Insert Position


Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Java Code:

public int searchInsert(int[] A, int target) {
      int start = 0;
      int end = A.length - 1;
      int index = start;
      
      while(start <= end){
          int middle = (start + end)/2;
          if(A[middle] == target) return middle;
          
          if(target < A[middle]){
              end = middle - 1;
              index = middle;
          }else{
              start = middle + 1;
              index = start;
          }
      }
      
      return index;
    }

[LeetCode] Search for a range


Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].


解题思路:
利用二分搜索法分别找到beginindex 和 endindex.

Java Code:

  public int[] searchRange(int[] A, int target) {
        int[] result = new int[2];
        
        result[0] = searchRange1(A, target, true);
        result[1] = searchRange1(A, target, false);
        
        return result;
    }
    
    //binary search for beginIndex and endIndex respectily 
     public int searchRange1(int[] A, int target, boolean first){
           int start = 0, end = A.length - 1;
           int index = -1;
           
           while(start <= end){
               int middle = (start + end)/2;
               
               if(A[middle] > target){
                   end = middle - 1;
               }
               
               if(A[middle] < target){
                   start = middle + 1;
               }
               
               if(A[middle] == target){
                   index = middle;
                   
                   if(first) end = middle-1;
                   else start = middle + 1;
               }
           }
          
           return index;
    }

[LeetCode] Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

解题思路:
1. 最开始做的是统计0,1,2的数目。然后要扫2遍
2. 这题只有3个数,想到可以用3个指针分别指向一个数字,2边的指针s, e分别指向0,和2。中间的指针 i扫描 s-e 数。碰到0,则swap( i, s),移动s . 碰到2, swap(i, e), 移动e.

第二个方法,注意移动i, s, e的移动。 由于等于2的时候, i 会和e 交换,也就是当i扫描到0的时候,i 交换的数一定为1,所以交换后,i也要移动。

Java Code:
 public void sortColors(int[] A) {
        int[] count = new int[3];

        for (int i = 0; i < A.length; i++) {
            switch (A[i]) {
                case 0:
                    count[0]++;
                    continue;
                case 1:
                    count[1]++;
                    continue;
                case 2:
                    count[2]++;
                    continue;
            }
        }

        for (int i = 0; i < A.length; i++) {
            if (i < count[0]) {
                A[i] = 0;
            } else if (i < count[0] + count[1]) {
                A[i] = 1;
            } else {
                A[i] = 2;
            }
        }
  public void sortColors(int[] A) {
        int s = 0;
        int e = A.length - 1;

        int i = s;

        while (i <= e) {
            if (A[i] == 0) {
                A[i] = A[s];
                A[s] = 0;
                s++;
                i++;
                continue;
            }
            
            if (A[i] == 2) {
                A[i] = A[e];
                A[e] = 2;
                e--;
                continue;
            }
                i++;
        }
    }

[LeetCode] Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Java Code:
 public boolean isSameTree(TreeNode p, TreeNode q) {
        if( p == null && q == null) return true;
        
        if( p != null && q != null && p.val == q.val){
            return isSameTree(p.left, q.left)&&isSameTree(p.right, q.right);
        }
        
        return false;
    }

Friday, August 1, 2014

[LeetCode] Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

解题思路: 因为n可能会大于list的总长度,所以我们先遍历整个list,然后将tail指向head,组成一个圈,然后再走num - n%num步,就将圈解开即可。
最开始自己是一遍一遍的遍历list。看了水中的鱼的讲解,觉得很赞。

Java Code:


public ListNode rotateRight(ListNode head, int n) {
        if(head == null || n == 0) return head;
        
        ListNode p = head;
        
        int count = 1;
        while(p.next != null){
             count++;
             p = p.next;
        }
        
        if(n%count == 0) return head;
        
       p.next = head;
       int i = 0;
        
       while( i < count - n%count){
           i++;
           p = p.next;
       }
       
       ListNode newhead = p.next;
       p.next = null;
       
       return newhead;
    }

[LeetCode] Reverse Linked List

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ mn ≤ length of list.

解题思路:
 1. reverse linkedlist,通常需要2个指针和一个temp 指针。这里最后要将reversedlist和原来的list链接起来,所以我们还需要一个指针来存储m-1的node。
2. 这里会考虑到m == 1的情况,所以我们加一个dummy node
 
Java Code:

 public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode p = head;
        ListNode safehead = new ListNode(0);
        safehead.next = head;
        ListNode prevM = safehead;
        ListNode prev = null;
         
        int i = 1;
        
        while( p != null && i <= n){
            if(i >= m){
               ListNode tmp = p;
               p = p.next;
               tmp.next = prev;
               prev = tmp;
            }else{
              prevM = prevM.next;
              p = p.next;
            }
            i++;
        }
       
        prevM.next.next = p;
        prevM.next = prev;
        
        return safehead.next;
    }

[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: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-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;
    }