首页 > itarticle > crack leetcode 2

crack leetcode 2

admin 11月 24, 2020 0

#950. Reveal Cards In Increasing Order

We need to find out an order of deck which will reveal the cards in increasing order after several steps.

One intuitive way is reverse the steps, suppose there is deck A which has incresing order, and deck B which is empty at first.
(1) Take one card from the bottom of A, put it at the top of B
(2) Take one card from the bottom of B, put it at the top of B

For example, if A = {1,2,3,4,5,6,7}, then
(1)we first take 7 and put it in B. B = {7}
(2)take 6 from A, then put it on the top of B. B = {6,7};
(3) take 7 from B, then put it on the top of B. B = {7,6};
(4) take 5 from A, then put it on the top of B. B = {5,7,6};
(5) take 6 from B, then put it on the top of B. B = {6,5,7};
…
As you can see, B is a queue. So we can do it with Queue.

The thinking is kind of complex (at lease for me), because we need to think it reversely.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
class  {
    public int[] deckRevealedIncreasing(int[] deck) {
       Arrays.sort(deck);
       Queue<Integer> queue = new LinkedList<Integer>();
       for(int i=deck.length-1;i>0;i--) {
          queue.add(deck[i]);
          int temp = queue.poll();
            queue.add(temp);
     }
        queue.add(deck[0]);
      int[] result = new int[deck.length];
      for(int i=deck.length - 1;i>= 0;i--) {
          result[i] = queue.remove();
      }
        return result;
    }
}

I saw a cool solution in the discuss section and it is simple and clear. It is kind of tricky to me. But it does not need to think reversely.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
class  {
    
    public int[] deckRevealedIncreasing(int[] deck) {
      Arrays.sort(deck);
       Queue<Integer> queue = new LinkedList<Integer>();
       for(int i=0;i<deck.length;i++) {
            queue.add(i);
        }
        int[] result = new int[deck.length];
      for(int i=0;i<deck.length;i++) {
            result[queue.poll()] = deck[i];
          queue.add(queue.poll());
     }
        return result;
    }
}

We suppose the original deck is a queue structure and use index to initialize the queue. It is quite like solving an equation with x,y,z… variables. When we pick the card and put the next card to the bottom of the deck, we manipulate the deck. In the end, the order of the queue will be increasing and we use the index to assign value to queue.

#905. Sort Array By Parity

We can use two pointer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
class  {
    public int[] sortArrayByParity(int[] A) {
        int[] B = new int[A.length];
        int evenPointer = 0;
        int oddPointer = A.length -1;
        for(int i=0;i<A.length;i++){
            if(A[i] %2 ==0){
                B[evenPointer] = A[i];
                evenPointer++;
            }else{
                B[oddPointer] = A[i];
                oddPointer--;
            }
        }   
        return B;
    }
}

Below is the code for in place one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
class  {
    public int[] sortArrayByParity(int[] A) {
        //inplace version
        int j = 0;
        for(int i=0;i<A.length;i++){
            if(A[i] % 2 == 0){
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                j++;     
            }
        }
        return A;
    }
}

#701. Insert into a Binary Search Tree

Two solutions can be found. One is recursion, one is not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
class  {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode temproot = root;
        while(true){
            if(temproot.right != null && temproot.val <val){
                temproot = temproot.right;
            }else if(temproot.left != null && temproot.val > val){
                temproot = temproot.left;
            }else {
               break;
            }
        }
        if(temproot.val < val) {
           temproot.right = new TreeNode(val);
        }else {
          temproot.left = new TreeNode(val);
        }
        return root;
    }
}
 

1
2
3
4
5
6
7
8
 
//Recursion algo
public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (root.val > val) root.left = insertIntoBST(root.left, val);
        else root.right = insertIntoBST(root.right, val);

        return root;
    }
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能