Blue Rain

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution
{
    public ListNode removeNthFromEnd(ListNode head, int n)
    {
        //1. create a dummyHead before the real head
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode first = head;
        int length = 0;
        
        //as long as first is not null, we increase length
        //and keep moving first
        while(first != null)
        {
            length++;
            first = first.next;
        }
        //use length - n to locate the node we are going to delete
        length -=n;
        first = dummyHead;
        while(length > 0)
        {
            length--;
            first = first.next;
        }
        first.next = first.next.next;
        return dummyHead.next;
    }
}

class Solution {
  Map<String, String> phone = new HashMap<String, String>() {{
    put("2", "abc");
    put("3", "def");
    put("4", "ghi");
    put("5", "jkl");
    put("6", "mno");
    put("7", "pqrs");
    put("8", "tuv");
    put("9", "wxyz");
  }};

  List<String> output = new ArrayList<String>();

  public void backtrack(String combination, String next_digits) {
    // if there is no more digits to check
    if (next_digits.length() == 0) {
      // the combination is done
      output.add(combination);
    }
    // if there are still digits to check
    else {
      // iterate over all letters which map
      // the next available digit
      String digit = next_digits.substring(0, 1);
      String letters = phone.get(digit);
      for (int i = 0; i < letters.length(); i++) {
        String letter = phone.get(digit).substring(i, i + 1);
        // append the current letter to the combination
        // and proceed to the next digits
        // letter往后一直移动是因为从a到b,b到c， c到d。。。这样
        backtrack(combination + letter, next_digits.substring(1));
        // backtrack(letter + combination, next_digit.substring(1));
//Output ["da","ea","fa","db","eb","fb","dc","ec","fc"]
      }
    }
  }

  public List<String> letterCombinations(String digits) {
    if (digits.length() != 0)
      backtrack("", digits);
    return output;
  }
}

class Solution
{
    public List<List<Integer>> threeSum(int[] nums)
    {
        //1.Sort array
        Arrays.sort(nums);
        //2. Creat a double Linkedlist
        List<List<Integer>> res = new LinkedList<>();
        for(int i = 0; i < nums.length - 2; i++)
        {
            //3. if i = 0 or the 2nd number is not equal to previous number
            //为了保证不加入重复的 list,因为是有序的，所以如果和前一个元素相同，只需要继续后移就可以
            if(i == 0 || (i > 0 && nums[i] != nums[i - 1]))
            {
                 //两个指针,并且头指针从i + 1开始，防止加入重复的元素
                int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];
                while(lo < hi)
                {
                    if(nums[lo] + nums[hi] == sum)
                    {
                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                        while(lo < hi && nums[lo] == nums[lo + 1]) lo++;
                        while(lo < hi && nums[hi] == nums[hi - 1]) hi--;
                        lo++;
                        hi--;
                    }
                    else if(nums[lo] + nums[hi] < sum) lo++;
                    else hi--;
                    
                }
            }
        }
        return res;
    }
}

class Solution
{
    public int maxArea(int[] height)
    {
        //initialize area, most left side and right side
       int area = 0, l = 0, r = height.length - 1;
        //as long as left is on the "left"
        while(l < r)
        {
            area = Math.max(area, Math.min(height[l], height[r]) * (r - l));
            if(height[l] < height[r])
            {
                l++;
            }
            else
            {
                r--;
            }
        }
        return area;
        
    }
}

class Solution
{
    public String longestPalindrome(String s)
    {
        if(s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for(int i = 0; i < s.length(); i++)
        {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if(len > end - start)
            {
                start = i - (len-1)/2;
                end = i + len/2;
            }
        }
        return s.substring(start, end + 1);
    }
    
    private int expandAroundCenter(String s, int left, int right)
    {
        int L = left, R = right;
        while(L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R))
        {
            L--;
            R++;
        }
        return R - L - 1;
    }
}

          

class Solution 
{
    public int lengthOfLongestSubstring(String s) 
    {
        // s: "abcabcbb"
        
        HashMap<Character, Integer> map = new HashMap<>();
        // s: "abcabcbb"
           map: {} 
        
        int ans = 0;
        // s: "abcabcbb"
           map: {}
           ans: 0
        
        for(int i = 0, j = 0; j < s.length(); j++)
        {
        /*
        s: "abcabcbb"
        map: {}
        ans: 0
        i: 0
        j: 0
        */
            if(map.containsKey(s.charAt(j)))
            {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            /*
            s: "abcabcbb"
            map: {}
            ans: 1
            i: 0
            j: 0
            */
            
            map.put(s.charAt(j), j + 1);
            /*
            s: "abcabcbb"
            map: {"a":1}
            ans: 1
            i: 0
            j: 0
            */
            
            /*
            Second round
            s: "abcabcbb"
            map: {"a":1,"b":2}
            ans: 2
            i: 0
            j: 1
            */
            
            /*
            s: "abcabcbb"
            map: {"a":1,"b":2,"c":3}
            ans: 3
            i: 0
            j: 2
            */
            
        }
        return ans;
    }
   
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution
{
    public ListNode addTwoNumbers(ListNode l1, ListNode l2)
    {
        //initiate new dummyHead, it points to first node
        ListNode dummyHead = new ListNode(0);
        //ListNode should have p, q, curr
        ListNode p = l1, q = l2, curr = dummyHead;
        //Initiate a carry value
        int carry = 0;
        while(p != null || q != null)
        {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = x + y + carry;
            //re-value carry
            carry = sum / 10;
            //curr next node is backward
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if(p != null) p = p.next;
            if(q != null) q = q.next;
        }
        if(carry > 1)
        {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

class Solution
{
    public int[] twoSum(int[] nums, int target)
    {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++)
        {
            int n = target - nums[i];
            if(map.containsKey(n))
            {
                return new int[] {map.get(n), i};
            }
        map.put(nums[i], i);
        }
    throw new IllegalArgumentException("No two sum solution");
    }
}

<font size=5 color="#3cff00"> Set Color and Font</font>