2. Add Two Numbers

This question is mathematics question. Each of us must have learned addition.So this is a carry sums of addition question.The question becomes clear.

  • Addition of the same rank from left to right,when there is one carry left,ten digits will be added in the next calculation
  • When the last number is reached,it is also necessary to judge whether to carry

Solution

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    //create a ListNode of head
    ListNode head = new ListNode(0);
    //move pointer
    ListNode pre = head;
    //n is tens  digit,cur is to judge the last number whether plus 1
    int n = 0, cur = 0;
    while (l1 != null || l2 != null) {
      //if l1 ot l2 is to the end,just let it 0
      int n1 = 0, n2 = 0;
      if (l1 != null) {
        n1 = l1.val;
      }
      if (l2 != null) {
        n2 = l2.val;
      }
      //count the sum of all this location number
      int sum = n1 + n2 + n;
      //refresh n,otherwise the last result will retained
      n = 0;
      //judge whether it is greater than 10
      if (sum >= 10) {
        //tens digit
        n = 1;
        //digit
        sum = sum - 10;
      }
      //if n is 0,don't need add 1 at last
      cur = n;
      //create the new node
      pre.next = new ListNode(sum);
      //update the move pointer and two ListNode
      pre = pre.next;
      if (l1 != null) {
        l1 = l1.next;
      }
      if (l2 != null) {
        l2 = l2.next;
      }
    }
    //whether to add 1 at last
    if (cur == 1) {
      pre.next = new ListNode(cur);
    }
    return head.next;
  }

3. Longest Substring Without Repeating Characters

This question is a dynamic window problem.We need begin from the head,use two pointer.If the right pointer find the repeating character.Just move the left pointer one step.Record the distance between the left pointer and the right pointer each time.The max value is the answer.

Solution

public int lengthOfLongestSubstring(String s) {
    //use HashSet to mark the character
    HashSet<Character> hashSet = new HashSet<>();
    //if j is 0,j++ is 1,equivalent to ignoring the first,so j must -1
    int j = -1, length = 0;
    for (int i1 = 0; i1 < s.length(); i1++) {
      //this situation must find a repeating characters,so remove the first,if still repeating,
      // just continue
      if (i1 != 0) {
        hashSet.remove(s.charAt(i1 - 1));
      }
      //if don't find the repeating characters,just continue move right pointer
      while (j + 1 < s.length() && !hashSet.contains(s.charAt(j + 1))) {
        hashSet.add(s.charAt(j + 1));
        j++;
      }
      //calculate the length of each time,marked the max length
      length = Math.max(length, j - i1 + 1);
    }
    return length;
  }

5. Longest Palindromic Substring

This question is not easy to think about.The most basic method is enumeration,list every different string.Verify whether it is a palindrome string.So you can get the begin location and the end location of the maximum length string.But this solution time is $O(n^2)$.It will be time out,so we must consider another solution.

We can find a pattern.If this string is palindromic string.It must have a symmetry point.

  • a the symmetry point is odd number
  • a a the symmetry point is even number

So we can begin from the string head,verify each characters whether is the symmetry point.

Solution

public String longestPalindrome(String s) {
    //special cases
    if (s == null || s.length() < 1) {
      return "";
    }
    //record every palindromic string location
    int left = 0, right = 0, length = 0;
    for (int i = 0; i < s.length(); i++) {
      //odd number
      int len1 = findLength(s, i, i);
      //even number
      int len2 = findLength(s, i, i + 1);
      length = Math.max(len1, len2);
      if (length > right - left) {
        //-1 is distinguish between odd and even cases
        left = i - (length - 1) / 2;
        right = i + length / 2;
      }
    }
    return s.substring(left, right + 1);
  }

  private int findLength(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
      left--;
      right++;
    }
    //if there is only have a character,if do not -1,it will return false
    return right - left - 1;
  }

6. ZigZag Conversion

This question is hard to understand at first.Because you have no idea to how to change it shape. But after you come down and observe carefully,you can find a law.

Each layer is like an array,start traversing from the top,return to the top after reaching the bottom,move back and forth.Let's find out its law.

  • We can find when the law is 0 and numRows,it will reverse.

The result need us return a string,so we need use StringBuilder.And each row is a list.

Solution

public String convert(String s, int numRows) {
    //special cases "AB" "A"
    if (numRows < 2) {
      return s;
    }
    //each row is a arraylist to store each element,so StringBuilder
    ArrayList<StringBuilder> list = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
      list.add(new StringBuilder());
    }
    //row1 begin is 0
    int i = 0, reverse = -1;
    for (char c : s.toCharArray()) {
      //each element add to their own row list
      list.get(i).append(c);
      //will row number is 0 or numRows -1.switch direction
      if (i == 0 || i == numRows - 1) {
        reverse = -reverse;
      }
      i += reverse;
    }
    //connect each row of the list
    StringBuilder Builder = new StringBuilder();
    for (StringBuilder s1 : list) {
      Builder.append(s1);
    }
    return Builder.toString();
  }

8. String to Integer (atoi)

This is a simulate development issues,we will meet it usually in our work.We should calm down analysis the question.Understand its needs and think about how to meet its need.Write down the flow chart if necessary.It's much easier to write code again.

In fact,many times work requirements are similar to this kind of problem,if you encounter

  • There are ready-made tools and libraries that need to be used as much as possible,because they have better performance,have undergone more rigorous testing,and are relatively reliable.
  • It can be extracted into tools and tool methods as much as possible,highlighting the main logic,and facilitating code reuse in the future
  • When you have to write more cumbersome and lengthy,you need to write clear notes and reflect the logical level to troubleshoot problems and follow-up maintenance after going online
  1. There may be characters that are not plus or minus signs or numbers in front,remove theme.
  2. When you encounter the first number,you can add a minus again,if it is not a plus sign but a positive number,the default is a positive number.
  3. How to verify whether a symbol is encountered,we can set a boolean,the default value is true,if is a negative symbol,we change it into false.
  4. Every time you read a new number,you need to verify whether its value is out of range
  5. Stop when reading a non-number,and return to the number read if it does not out of range

Solution

public int myAtoi(String s) {
    //change it into array
    char[] array = s.toCharArray();
    //pointer
    int index = 0;
    //remove the character which is not number of "+" "-"
    while (index < array.length && array[index] == ' ') {
      index++;
    }
    //the special situation
    if (index == array.length) {
      return 0;
    }
    //default situation
    boolean positive = true;
    //if find the sign,judge whether is negative or positive sign
    if (array[index] == '+') {
      index++;
    } else if (array[index] == '-') {
      positive = false;
      index++;
    }
    //judge whether out of range
    int result = 0, overflow = 0;
    while (index < array.length) {
      char c = array[index];
      //if not number,just end the search
      if (c < '0' || c > '9') {
        break;
      }
      int temp = c - '0';
      result = overflow;
      overflow = overflow * 10 + temp;
      //if out of range,just return
      if (result != overflow / 10) {
        return positive == true ? Integer.MAX_VALUE : Integer.MIN_VALUE;
      }
      index++;
    }
    //add symbol
    return positive == true ? overflow : 0 - overflow;
  }

11. Container With Most Water

This question is a very clever thought.We all know the bucker effect,The volume of the bucket is dominated by the smaller side.We can imagine that the length of both sides of this barrel is the same,and the length is n.The distance between the two sides is m.So the volume of the barrel is n*m.

But the both sides of this barrel maybe not be the same.So we can just use the smaller side.

I write a picture to describe the situation.We can find the that the side length of the rectangle is getting smaller and smaller.So we can use two pointers,if one pointer is smaller than another pointer,just need update the smaller one.Just like the picture i draw.If the area of the current rectangle is larger than the previous area,update the area value.

Solution

public int maxArea(int[] height) {
    //two pointer,area value
    int left = 0, right = height.length - 1, result = 0, temp = 0;
    //while thery did,t meet,just update the smaller pointer
    while (left < right) {
      temp = result;
      //count the current rectangle area
      if (height[left] < height[right]) {
        temp = height[left] * (right - left);
        left++;
      } else {
        temp = height[right] * (right - left);
        right--;
      }
      //update the larger rectangle area
      if (temp > result) {
        result = temp;
      }
    }
    return result;
  }

12. Integer to Roman

This question is opposite of 13. Roman to Integer.If you under stand that question,so you can understand this question easily.

We can finde a pattern:In Roman numerals,the number composition is the big number on the left and then decreases to the right.

  • num = 1994=MCMXCIV M = 1000, CM = 900, XC = 90 and IV = 4
  • num = 58=LVIII L = 50, V = 5, III = 3

So we can use enmu,enumerate every special roman numeral.Start subtracting from the largest Roman numeral and finally concatenate it to get the answer.

Solution

public String intToRoman(int num) {
    StringBuilder builder = new StringBuilder();
    //1 4 5 9 10 40 50 90 100 400 500 900 1000
    String[] Roman = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
    while (num > 0) {
      if (num >= 1000) {
        builder.append(Roman[12]);
        num -= 1000;
      } else if (num >= 900) {
        builder.append(Roman[11]);
        num -= 900;
      } else if (num >= 500) {
        builder.append(Roman[10]);
        num -= 500;
      } else if (num >= 400) {
        builder.append(Roman[9]);
        num -= 400;
      } else if (num >= 100) {
        builder.append(Roman[8]);
        num -= 100;
      } else if (num >= 90) {
        builder.append(Roman[7]);
        num -= 90;
      } else if (num >= 50) {
        builder.append(Roman[6]);
        num -= 50;
      } else if (num >= 40) {
        builder.append(Roman[5]);
        num -= 40;
      } else if (num >= 10) {
        builder.append(Roman[4]);
        num -= 10;
      } else if (num >= 9) {
        builder.append(Roman[3]);
        num -= 9;
      } else if (num >= 5) {
        builder.append(Roman[2]);
        num -= 5;
      } else if (num >= 4) {
        builder.append(Roman[1]);
        num -= 4;
      } else if (num >= 1) {
        builder.append(Roman[0]);
        num -= 1;
      }
    }
    return builder.toString();
  }
Last modification:October 20th, 2021 at 10:33 am