Question ：1 - 100

记录我的LeetCode答题记录。说明：

• 编程语言：Java
• 每道题只记录自己做出来的“最优解”（耗时最少）。
• 每道题其他题解可能记录在本人的的项目- leetCode (opens new window)，或去官方看大家的提交记录。

Q1：两数之和 (opens new window)

public int[] twoSum(int[] nums, int target) {
		int[] result = new int[2];
		Map<Integer, Integer> map = new HashMap<>();
		for (int x = 0, len = nums.length; x < len; ++x) {
			if (map.containsKey(target-nums[x])){
				result[0] = x;
				result[1] = map.get(target-nums[x]);
				return result;
			}
			map.put(nums[x], x);
		}
		return result;
}

Q7*：整数反转Ω (opens new window)

public int reverse(int x) {
		int r = 0 , temp;
		while (x != 0){
			temp = r * 10 + x % 10;
			if (temp / 10 != r){
				return 0;
			}
			r = temp;
			x /= 10;
		}
		return r;
}

Q8*：字符串转换整数 (atoi) (opens new window)

public int myAtoi(String s) {
  if (s == null || s.length() == 0) {
    return 0;
  }

  char[] chars = s.toCharArray();
  int index = 0, result = 0, sign = 1;
  boolean hasNumber = false;
  while (index < chars.length){
    char aChar = chars[index];
    if (aChar >= '0' && aChar <= '9'){
      int temp = result * 10 + (aChar - '0');
      if (temp / 10 != result) {
        return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
      }
      result = temp;
      hasNumber = true;
    } else if (aChar == ' ' || aChar == '-' || aChar == '+'){
      // 数字中间出现特殊字符或+、-连续出现
      if (hasNumber || (aChar != ' '
                        && index != s.length() - 1
                        && (chars[index + 1] < '0' || chars[index + 1] > '9'))){
        break;
      }
      if (aChar != ' '){
        sign = aChar == '-' ? -1 : 1;
      }
    }else {
      break;
    }
    index++;
  }

  return result * sign;
}

Q9：回文数 (opens new window)

public boolean isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)){
        return false;
    }
    int revertedNumber = 0;
    while (x > revertedNumber) {
        revertedNumber = revertedNumber * 10 + x % 10;
        x /= 10;
    }
    return x == revertedNumber || x == revertedNumber / 10;
}

Q13：罗马数字转整数 (opens new window)

public int romanToInt(String s) {
  int result = 0;
  char[] chars = s.toCharArray();
  for (int i = 0, n = chars.length; i < n; i++) {
    int current = romanValueOf(chars[i]);

    if(i < n - 1 && romanValueOf(chars[i]) < romanValueOf(chars[i + 1])) {
      result -= current;
    }else {
      result += current;
    }

  }
  return result;
}

private Integer romanValueOf(Character roman) {
  switch (roman) {
    case 'I': return 1;
    case 'V': return 5;
    case 'X': return 10;
    case 'L': return 50;
    case 'C': return 100;
    case 'D': return 500;
    case 'M': return 1000;
    default: return 0;
  }
}

Q14：最长公共前缀 (opens new window)

public String longestCommonPrefix(String[] strs) {
  if( strs.length == 0){
    return "";
  }else{
    String commonPre = strs[0];
    for(String str : strs){
      while(!str.startsWith(commonPre)){
        if (commonPre.length() == 1){
          return "";
        }
        commonPre = commonPre.substring(0, commonPre.length() - 1);
      }
    }
    return commonPre;
  }
}

Q19*：删除链表的倒数第 N 个结点 (opens new window)

public ListNode removeNthFromEnd(ListNode head, int n) {
  ListNode dummy = new ListNode(0, head);
  ListNode first = head, second = dummy;
  for (int i = 0; i < n; ++i) {
    first = first.next;
  }
  while (first != null) {
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  return dummy.next;
}

Q20：有效的括号 (opens new window)

public boolean isValid(String s) {
    int n = s.length();
    if (n % 2 == 1){
        return false;
    }

    Map<Character, Character> pairs = new HashMap<Character, Character>() {{
        put(')', '(');
        put(']', '[');
        put('}', '{');
    }};
    Deque<Character> stack = new LinkedList<>();
    for (int i = 0; i < n; ++i) {
        char ch = s.charAt(i);
        if (pairs.containsKey(ch)){
            if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                return false;
            }
            stack.pop();
        } else {
           stack.push(ch);
        }
    }
    return stack.isEmpty();
}

Q21：合并两个有序链表 (opens new window)

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null){
        return list2;
    }else if (list2 == null){
        return list1;
    }else if (list1.val <= list2.val){
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    }else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

Q26：删除有序数组中的重复项 (opens new window)

public int removeDuplicates(int[] nums) {
  int newLen = 0;
  for(int x = 1, len = nums.length; x < len; ++x) {
    if(nums[newLen] != nums[x]) {
      ++newLen;
      nums[newLen] = nums[x];
    }
  }
  return newLen + 1;
}

Q28：实现strStr() (opens new window)

题目本质考的是字符串匹配问题，题目归类为简单，可直接使用String的indexOf()。这里我使用了KMP算法实现，比JDK 8的indexOf()效率高不少。

KMP算法，推荐博客：

• https://www.cnblogs.com/yjiyjige/p/3263858.html
• https://www.cnblogs.com/dusf/p/kmp.html（基于上一篇博客补充修改）

public int strStr(String haystack, String needle){
  
  char[] tsChars = haystack.toCharArray();
  char[] psChars = needle.toCharArray();

  // 主串、模式串的index
  int i = 0, j = 0;
  // KMP核心算法
  int[] next = getNext(needle);

  while (i < haystack.length() && j < needle.length()){
    // 当j为-1时，要移动的是i，j也要归0
    if (j == -1 || tsChars[i] == psChars[j]) {
      i++;
      j++;
    }
    // j回到指定位置，同时i不需要回溯
    else{
      j = next[j];
    }
  }

  return j == needle.length() ? i-j : -1;
}

/**
* 模next[j] = k，表示当T[i] != P[j]时，模式串j指针的下一个位置。
*/
private int[] getNext(String ps) {

  if (ps.length() == 0){
    return new int[0];
  }

  char[] p = ps.toCharArray();
  int[] next = new int[p.length];

  next[0] = -1;

  int j = 0, k = -1;

  while (j < p.length - 1) {

    if (k == -1 || p[j] == p[k]) {
      // 优化next[++j] = ++k; 跳过t[j] == t[next[j]]的情况，
      if (p[++j] == p[++k]) {
        next[j] = next[k];
      } else {
        next[j] = k;
      }
    } else {
      k = next[k];
    }
  
  }

  return next;
}

Q36*：有效的数独 (opens new window)

public boolean isValidSudoku(char[][] board) {
  int[][] rows = new int[9][9];
  int[][] columns = new int[9][9];
  int[][][] subBoxes = new int[3][3][9];
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      char c = board[i][j];
      if (c != '.') {
        int index = c - '0' - 1;
        rows[i][index]++;
        columns[j][index]++;
        subBoxes[i/3][j/3][index]++;
        if (rows[i][index] > 1 || columns[j][index] > 1 || subBoxes[i / 3][j / 3][index] > 1) {
          return false;
        }
      }
    }
  }
  return true;
}

Q38*：外观数列 (opens new window)

public String countAndSay(int n) {
  String say = "1";
  while(--n > 0) {
    int num = 1;
    char[] chars = say.toCharArray();
    StringBuilder countSay = new StringBuilder();
    // 索引改为从1开始
    for(int i = 1; i < say.length(); ++i) {
      if(chars[i] == chars[i-1]) {
        ++num;
      }else {
        countSay.append(num).append(chars[i-1]);
        num = 1;
      }
    }
    // 此处转换为字符串，需要添加最后一个字符的统计
    say = countSay.append(num).append(chars[say.length()-1]).toString();
  }
  return say;
}

Q48*：旋转图像 (opens new window)

/**
 * 原地旋转，四项循环具体推导过程可参考官方解答。
 * 还有其他原地旋转的解法如下，源码可参见仓库。
 * 1. 先以对角线（右斜）为轴翻转，再以x轴为轴翻转得到结果。
 * 2. 对矩阵进行转置，即行变成列（以对角线（左斜）为轴翻转），再以y轴为轴翻转得到结果。
 */
public void rotate(int[][] matrix) {
	int n = matrix.length;
	for (int i = 0; i < n / 2 ; ++i) {
		for (int j = 0; j < (n + 1) / 2; ++j) {
			// 四项循环
			int temp = matrix[i][j];
			matrix[i][j] = matrix[n - j - 1][i];
			matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
			matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
			matrix[j][n - i - 1] = temp;
		}
	}
}

Q53：最大子数组和 (opens new window)

public int maxSubArray2(int[] nums) {
    int res = nums[0], sum = 0;
    for (int num : nums) {
        sum = Math.max(num, sum + num);
        res = Math.max(res, sum);
    }
    return res;
}

Q66：加一 (opens new window)

public int[] plusOne(int[] digits){
   for (int i = digits.length - 1; i >= 0; --i){
      if (digits[i] != 9){
         digits[i]++;
         return digits;
      }
      digits[i] = 0;
   }
   int[] result = new int[digits.length + 1];
   result[0] = 1;
   return result;
}

Q70*：爬楼梯 (opens new window)

/**
* m4(0ms, 45tc): 动态规划，滚动数组
* Tn = O(n)，Sn = O(1)
*/
public int climbStairs4(int n) {
  int first = 0, second = 0, third = 1;
  for (int i = 1; i <= n; i++) {
    first = second;
    second = third;
    third = first + second;
  }
  return third;
}

/**
* m6(0ms, 45tc): 通项公式, Binet's Formula
* Tn = O(logn)，Sn = O(1)
*/
public int climbStairs6(int n) {
  double sqrt5 = Math.sqrt(5);
  double result = (Math.pow((1 + sqrt5)/2, n + 1) - Math.pow((1 - sqrt5)/2, n + 1)) / sqrt5;
  return (int)result;
}

Q94：二叉树的中序遍历 (opens new window)

/**
* 递归版
*/
public List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> list = new ArrayList<>();
  inorder(root, list);
  return list;
}

private void inorder(TreeNode root, List<Integer> list) {
  if (root == null) {
    return;
  }

  inorder(root.left, list);
  list.add(root.val);
  inorder(root.right, list);
}