15. 3Sum

This question is similar with 1. Two Sum.But they have some different,the main different is this question is the solution set must not contain duplicate triplets.So we can't just use enumeration method,we need to think about how to avoid duplication.In the past,there were two main ways to avoid duplication.One is use HashMap,the other one is this array is ordered.If we just use enumeration method to traverse the entire array and then use HashMap.It will cost a lot of time and lost of space.So we should sort this array at first.And we can set center pointn.There three pointer are n,n+1,nums.length-1.Because this array is ordered,so if the n is the head of the array,so it means the all elements after n are all >0.So we don't need to traverse all the elements.But this is just a special situation.

And how can we avoid duplication?This is a easy question,there three pointercenter n,left n+1,right nums.length-1.If the value of their next position is equal to the current,we move the current position to the next.

Solution

  public List<List<Integer>> threeSum(int[] nums) {
    ArrayList<List<Integer>> lists = new ArrayList<>();
    //the special situation
    if (nums.length < 3) {
      return lists;
    }
    //sort the array
    Arrays.sort(nums);
    //traversal the array
    for (int i = 0; i < nums.length; i++) {
      //if the smallest element is larger than 0,so all the elements are larger than 0,just break
      if (nums[i] > 0) {
        break;
      }
      //repetitive situation,just update the location
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }
      //use two pointers,search from both sides
      int left = i + 1, right = nums.length - 1;
      while (left < right) {
        //find the 3sum
        if (nums[i] + nums[left] + nums[right] == 0) {
          //use Arrays.aslist make array to list
          lists.add(Arrays.asList(nums[i], nums[left], nums[right]));
          //repetitive situation,just update the location
          while (left < right && nums[left] == nums[left + 1]) {
            left++;
          }
          while (left < right && nums[right] == nums[right - 1]) {
            right--;
          }
          //update location
          left++;
          right--;
        } else if (nums[i] + nums[left] + nums[right] > 0) {
          //if larger than 0,it means right pointer is too bigger
          right--;
        } else {
          //if smaller than 0,it means left pointer is too smaller
          left++;
        }
      }
    }
    return lists;
  }

16. 3Sum Closest

This question is very similar with question 15. 3Sum.But it does not query to repeat this step,you can use double pointers directly.So i think this question is easier than question 15.

Solution

  public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int result = 0, min = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
      //if find the same number,just continue
      if (i > 0 && nums[i - 1] == nums[i]) {
        continue;
      }
      int left = i + 1, right = nums.length - 1;
      while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];
        //if find the target,just return
        if (sum == target) {
          return sum;
        }
        //find the closest
        if (Math.abs(sum - target) < min) {
          min = Math.abs(sum - target);
          result = sum;
        }
        //move the double pointers
        if (sum > target) {
          right--;
        } else {
          left++;
        }
      }
    }
    return result;
  }

17. Letter Combinations of a Phone Number

This question is a little difficult,the difficulty lies in how to stitch different letters together.It cannot use enumeration methods,because we don't know how many digits it will enter. So we can't use how many for to use enumeration methods.At this time,we should think of the problem of finding all branches of a binary tree.We didn't know the number of layers of the binary tree at the time.We need to judge the left subtree and the right subtree whether is null.And use recursive methods to return the values found in each layer.

So we can use the same method in this problem.First traverse the value of digits,each of its values is a layer.Finally,concatenating the traversed values is one of the answer.

And how do we associate phone numbers with letters.We can use HashMap,and use StringBuilder to connect the letters.

Solution

  public List<String> letterCombinations(String digits) {
    ArrayList<String> list = new ArrayList<>();
    //the special situation
    if (digits.length() == 0) {
      return list;
    }
    //create the HashMap
    HashMap<Character, String> map = new HashMap<>();
    map.put('2', "abc");
    map.put('3', "def");
    map.put('4', "ghi");
    map.put('5', "jkl");
    map.put('6', "mno");
    map.put('7', "pqrs");
    map.put('8', "tuv");
    map.put('9', "wxyz");
    backTracking(0, list, map, new StringBuffer(), digits);
    return list;
  }

  /**
   * use recursion to connect the letters
   */
  private void backTracking(int i, ArrayList<String> list, HashMap<Character, String> map,
      StringBuffer buffer, String digits) {
    //if it reaches the end,just return the letters you find
    if (i == digits.length()) {
      list.add(buffer.toString());
    } else {
      //such as digits.charAt(i) is '2',and search 2 in HashMap
      String s = map.get(digits.charAt(i));
      //traverse the number
      for (int i1 = 0; i1 < s.length(); i1++) {
        //add the last letters
        buffer.append(s.charAt(i1));
        //recursion
        backTracking(i + 1, list, map, buffer, digits);
        /*it also writes buffer.deleteCharAt(buffer.length()-1),if you don't write,StringBuilder
         will pollute the buff,StringBuilder passes in the same object, 
         so the last operation must be withdrawn after the recursion is completed,
         and the last added character needs to be deleted*/
        buffer.deleteCharAt(i);
      }
    }
  }

18. 4Sum

This problem is an upgraded version of 15. 3Sum.The main idea to the original question is the same as question 13.It also use double pointer.But i think if this question change to nSum,are there still double pointers used?Because this question is already very complicated to solve with double pointers.So i want to use recursion to solve this question.

There are two situations in recursion.First we still sort the array,and we remove the first element of the array every time.

1. the result we want include the nums[0]
2. the result we want does not include nums[0]

So this question becomes

1. findtarget-nums[0] from nums[1] to nums[nums.length]
2. find target from nums[1] to nums[nums.length]

But if the elements behind the first element are the same as the first element.We must skip all the elements in this paragraph.

Because recursion takes more time and space.So we must reduce the time spent.nums[0]>target/n is a good thinking.But we do LeetCode question not only to solve the problem,but to learn this kind of thinking,just like recursion.Will make the code we write more code robustness.

Solution

  public List<List<Integer>> fourSum(int[] nums, int target) {
    //this question requires us 4
    return nSum(nums, target, 4);
  }

  /**
   * n is the number of digits we need
   */
  private List<List<Integer>> nSum(int[] nums, int target, int n) {
    //first sort the array
    Arrays.sort(nums);
    //then use recursion
    return nSum(nums, target, n, 0, new ArrayList<Integer>(), new ArrayList<List<Integer>>());
  }

  /**
   * startIndex is position to start looking for
   */
  private List<List<Integer>> nSum(int nums[], int target, int n, int startIndex,
      ArrayList<Integer> preArray, ArrayList<List<Integer>> result) {
    //if length is 5,start begin 4,we need find 3 numbers,this is impossible,so just return
    if (nums.length - startIndex < n) {
      return result;
    }
    //if only find one element,we just traversal the array,until we find the element
    if (n == 1) {
      for (int i = startIndex; i < nums.length; i++) {
        if (nums[i] == target) {
          preArray.add(target);
          result.add(preArray);
          break;
        }
      }
      return result;
    }
    //special situation
    if (nums[startIndex] > target / n) {
      return result;
    }
    //filter out the same elements at the beginning
    int same = 0;
    for (int i = startIndex + 1; i < nums.length; i++) {
      if (nums[i] == nums[i - 1]) {
        //record the number of identical elements
        same++;
      } else {
        break;
      }
    }
    //the situation 2,the first element is not we need to find
    nSum(nums, target, n, startIndex + same + 1, preArray, result);
    //the situation 1,the first element is we need to find
    ArrayList<Integer> copyPre = new ArrayList<>(preArray);
    copyPre.add(nums[startIndex]);
    nSum(nums, target - nums[startIndex], n - 1, startIndex + 1, copyPre, result);
    return result;
  }

19. Remove Nth Node From End of List

This question is a very interesting question,as we all know how to remove the n node.But how to remove the node from the end of the list.Search from the beginning,but delete from the end.This situation reminds me about Stack FILO .So we can push elements into stack at first,and pop n-1 elements.So we can remove the n element.

• There is one thing we must be notice,If the n node from the end of the list.The number n is the list's length.So we remove the head,so we can't return the head,we must return the n next node.

Solution1

  public ListNode removeNthFromEnd(ListNode head, int n) {
    //create a stack,and push all elements into stack
    Stack<ListNode> stackNode = new Stack<>();
    ListNode temp = head;
    while (temp != null) {
      stackNode.push(temp);
      temp = temp.next;
    }
    //pop n-1 elements
    for (int i = 0; i < n - 1; i++) {
      stackNode.pop();
    }
    //pop the n element
    ListNode node = stackNode.pop();
    //if the n is the first of the lists,so this stack is empty,just return the node.next
    //else just remove the n element
    if (!stackNode.isEmpty()) {
      ListNode deleteNode = stackNode.peek();
      deleteNode.next = deleteNode.next.next;
    } else {
      return node.next;
    }
    return head;
  }

This question we also can use two pointers.The fast pointer moves n more nodes than slow pointer.When they move together,when the fast pointer reaches the tail node,the slow pointer also reaches the n node.

Solution2

  public ListNode removeNthFromEnd(ListNode head, int n) {
    //the slow pointer is one node slower than the fast pointer
    ListNode pre = new ListNode(0);
    pre.next = head;
    ListNode fast = head;
    ListNode slow = pre;
    //fast pointer moves n more nodes than slow
    for (int i = 0; i < n; i++) {
      fast = fast.next;
    }
    //because fast move to tail node,still move to the null node,so move one more step
    while (fast != null) {
      fast = fast.next;
      slow = slow.next;
    }
    //if the n node the head of the list,so we can't return the head,we must return the pre next
    slow.next = slow.next.next;
    return pre.next;
  }

22. Generate Parentheses

This question is very similar with Binary Tree traversal.As we all know ( must match ).And the number of ( is the same as the number of ).If the number of ) is bigger than the number of (,it is a wrong match.So we can summarize 2 points.

1. If the n bracket combinations,there are n ( and n )
2. If at this time the number of ( is m.The number of ) at most m

So we can use the same solution in Binary Tree.We start at a root node,this node is empty.We can add ( or ) latter.( is just like the left subtree.) is just like the right subtree.When the number of subtree is less than n,it will continue to depth first traversal.

Solution

  /**
   * define a ArrayList to store the parentheses
   */
  ArrayList result = new ArrayList<String>();

  public List<String> generateParenthesis(int n) {
    //the default number of left subtree and right subtree are all 0
    dfs(n, 0, 0, "");
    return result;
  }

  /**
   * Depth first traversal
   */
  private void dfs(int n, int left, int right, String str) {
    if (left == n && right == n) {
      //traversed to the bottom of the tree,just return the result
      result.add(str);
    } else {
      if (left < n) {
        //add the `(`
        dfs(n, left + 1, right, str + "(");
      }
      //the number of `)` at most the number of `(`
      if (right < n && right < left) {
        dfs(n, left, right + 1, str + ")");
      }
    }
  }

24. Swap Nodes in Pairs

This question is a very interesting question,because it has many solutions.Can develop our thinking to think more.

Queue

Of course,we can use Queue.Because the characteristic of Queue is first in first out.I make a example.

• 1 2 3 4

  1. Queue1:1 3
  2. Queue2:2 4

First we create two Queues,and alternate each element.And then take out each element alternately.

1. Queue:1 3
2. Queue:4

• 2

1. Queue1:3
2. Queue2:4

• 2 1

1. Queue1:3
2. Queue2:

• 2 1 4

1. Queue1
2. Queue2

• 2 1 4 3

This difficulty of this solution is when to put it in Queue1 and when to put it in Queue2.And when to pop out.

  public ListNode swapPairs(ListNode head) {
    //the special situation
    if (head == null || head.next == null) {
      return head;
    }
    //make two Queue
    LinkedList<ListNode> list1 = new LinkedList<>();
    LinkedList<ListNode> list2 = new LinkedList<>();
    //we can use boolean,if it is true,add Queue1,if it is false,add Queue2
    boolean add = true;
    while (head != null) {
      if (add) {
        list1.add(head);
        add = false;
      } else {
        list2.add(head);
        add = true;
      }
      head = head.next;
    }
    //We must remove a node to be the head of the result listnode
    ListNode res = list2.remove();
    ListNode temp = res;
    //we also can make a boolean to minus each Queue,if it is true,minus Queue1,else minus Queue2
    boolean minus = true;
    while (!list1.isEmpty() || !list2.isEmpty()) {
      if (!list1.isEmpty() && minus == true) {
        temp.next = list1.remove();
        minus = false;
      } else {
        //there are two situations in else,one is list2 is empty,we just need to minus Queue1 at
        // last,the another one is list1 is not empty
        if (!list2.isEmpty()) {
          temp.next = list2.remove();
          minus = true;
        } else if (!list1.isEmpty()) {
          temp.next = list1.remove();
        }
      }
      //update temp node
      temp = temp.next;
    }
    //if don't add this,it will happen infinite loop
    if (temp != null) {
      temp.next = null;
    }
    return res;
  }

recursion

We can also use recursion.Let's analyze this question.We can decompose the problem into

• A B C
• B A C

So this fake code is

//swap is like B
swap = A.next;
//swap.next is like C 
A.next=recursion(swap.next);
swap.next=A;
return swap;

  public ListNode swapPairs(ListNode head) {
    //the special situation
    if (head == null || head.next == null) {
      return head;
    }
    ListNode swap = head.next;
    head.next = swapPairs(swap.next);
    swap.next = head;
    return swap;
  }

Iteration

In iteration,we can also consider ABC as a group.Iteration is very complicated to tell,but it will be easy to understand if it is shown in a diagram.

  public ListNode swapPairs(ListNode head) {
    //the special situation
    if (head == null || head.next == null) {
      return head;
    }
    //make a result node,to point to head
    ListNode result = new ListNode(0);
    result.next = head;
    ListNode temp = result;
    //iteration
    while (temp.next != null && temp.next.next != null) {
      ListNode list1 = temp.next;
      ListNode list2 = temp.next.next;
      temp.next = list2;
      list1.next = list2.next;
      list2.next = list1;
      temp = list1;
    }
    //return the head
    return result.next;
  }