题目连接：https://leetcode-cn.com/problems/add-two-numbers/
提示：超出时间限制就是不管结果如何。但是运行效率太低了

查找maven jar包地址：https://mvnrepository.com/
题目更新记录：
2019年12月5日： 更新6-9题题解

1、给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
   int[] end = new int[2];
        int k = nums.length;
        for (int i = 0; i< k; i++){
            int m = i+1;
          for(; m < k; ){
                int n = nums[i];
                int x = nums[m];
                if (nums[i] + nums[m] == target){
                    end[0] = i;
                    end[1] = m;
                    return end;
                }
                m++;
            }
        }
        return nums;
        
    }
}

2、给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//    class ListNode {
//        int val;
//        ListNode next;
//
//        ListNode(int x) {
//            val = x;
//        }
//    }
         ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) {
                p = p.next;
            }
            if (q != null) {
                q = q.next;
            }
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }

3、给定一个字符串，请你找出其中 不含有重复字符的最长子串 的长度。

自己低效的解题结果

class Solution {
    public int lengthOfLongestSubstring(String s) {
         int length = 0;
        if (null == s) {
            return 0;
        } else if (s.length() == 1) {
            return 1;
        } else {
            while (s.length() != 0 && s.length() > length) {
                length = getLegth(s, length);
                if (s.length() != 1) {
                    s = s.substring(1, s.length());
                } else {
                    break;
                }
            }
        }
        return length;
    }
    private static int getLegth(String ss, int length) {
        String[] strs = ss.split("");
        Map<String, String> map = new HashMap<>(strs.length);
        int temp = map.size();
        for (String s : strs) {
            map.put(s, s);
            if (map.size() == temp) {
                if (map.size() > length) {
                    length = map.size();
                }
                map = new HashMap<>();
                map.put(s, s);
            }
            temp = map.size();
            if (temp == strs.length){
                length = temp;
            }
        }
        return length;
    }
}

参考答案

class Solution {
    public int lengthOfLongestSubstring(String s) {
         if (s == null || s.length() == 0) {
            return 0;
        }
        int[] tmp = new int[256];
        int maxlen = 0;
        int l = 0;
        int r = 0;
        while (l < s.length()) {
            if (r < s.length() && tmp[s.charAt(r)] == 0) {
                tmp[s.charAt(r++)] = 1;
            } else {
                maxlen = maxlen > (r - l) ? maxlen : (r - l);

                tmp[s.charAt(l++)] = 0;

            }
        }
        return maxlen;

    }
}

4 求中位数

题目描述：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
    if (nums1 == null) {
            return getValue(nums2);
        }
        if (nums2 == null) {
            return getValue(nums1);
        }

        int n = nums1.length;
        int m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
        return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
    }

    private  int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
        if (len1 > len2) {
            return getKth(nums2, start2, end2, nums1, start1, end1, k);
        }
        if (len1 == 0) {
            return nums2[start2 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }
        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        } else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

    private  double getValue(int[] nums) {
        int length = nums.length;
        if (length % 2 == 0) {
            return ((double) nums[length - 1] + nums[length]) / 2;
        }
        return nums[length / 2];
    }
}

5、给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000

样例：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

解答：

class Solution {
    public String longestPalindrome(String str) {
        if (str == null || str.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < str.length(); i++) {
            // 获取类似 aba这种回文最大长度
            int len1 = expandAroundCenter(str, i, i);
            // 获取类似 abba这种回文最大长度
            int len2 = expandAroundCenter(str, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                // 从当前坐标
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return str.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;
    }
}

6、将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
解释：

L   C   I   R
E T O E S I I G
E   D   H   N

示例 2:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

题解： 主要的思路是判断规律，重点要用到 flag 思想，用于标志什么时候应该需要换行

class Solution {
    public String convert(String s, int numRows) {
         if(numRows < 2) {
            return s;
        }
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        // 此处算出来有多少行
        for(int i = 0; i < numRows; i++) {
            rows.add(new StringBuilder());
        }
        int i = 0, flag = -1;
        // 用flag标志来进行判断应该放到哪个数组中
        for(char c : s.toCharArray()) {
            rows.get(i).append(c);
            if(i == 0 || i == numRows -1) {
                flag = - flag;
            }
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows) {
            res.append(row);
        }
        return res.toString();
    }
}

7、整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
如果反转后越界，则返回0；

解题：

    public int reverse(int x) {
       // 如果是正数，那么标志就是true
        boolean mark = true;
        // 如果是负数，修改标志位并且去除符号;先将数值转换为long避免修改符号时出错
        long xValue = x;
        if (xValue < 0) {
            mark = false;
            xValue = 0 - xValue;
        }
        // 转换成String
        String str = Long.toString(xValue);
        StringBuilder builder = new StringBuilder(str);

        // 反转
        String string = builder.reverse().toString();
        long result = Long.parseLong(string);
        
        // 如果是负数，更改符号
        if (!mark) {
            result = 0 - result;
        }
        // 判断是否越界
        if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
            return 0;
        }
        return (int) result;
    }
}

8、字符串转换整数

描述：给定一个字符串，从第一个非空字符开始判断，如果是非数字且非“+”“-”符号，直接返回0.
如果数据超过整数最大位数，对应返回最大整数值或最小整数值

题解：

class Solution {
    public int myAtoi(String str) {
           if (null == str) {
            return 0;
        }
        String x = str.trim();
        if (null == x) {
            return 0;
        }
        // 去除多余空格
        boolean flag = true;
        // 如果是正数，那么标志就是true  并且去除首位
        char[] chars = x.toCharArray();
        StringBuilder stringBuilder = new StringBuilder("0");
        boolean flagZero = true;
        for (int i = 0; i < chars.length; i++) {
            if (i == 0) {
                if ('+' == chars[i]) {
                    continue;
                }
                if ('-' == chars[i]) {
                    flag = false;
                    continue;
                }
            }
            // 如果是数字
            if (Character.isDigit(chars[i])) {
                if (flagZero && '0' == chars[i]) {
                    continue;
                }
                flagZero = false;
                stringBuilder.append(chars[i]);
            } else {
                break;
            }
        }


        if (stringBuilder.length() > String.valueOf(Integer.MIN_VALUE).length()) {
            return flag ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }

        long result = Long.parseLong(stringBuilder.toString());
        if (!flag) {
            result = 0 - result;
        }
        // 判断是否越界
        if (result > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (result < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        return (int) result;
    }
}

9、判断是否为回文

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

class Solution {
    public boolean isPalindrome(int x) {
        // 小于0 ，肯定不是回文
        if (x < 0){
            return false;
        }
        // 小于10 大于0 肯定是回文
        if (x < 10){
            return  true;
        }
        // 其他正整数转换一下
        StringBuilder stringBuilder = new StringBuilder(String.valueOf(x));
        StringBuilder reverse = stringBuilder.reverse();
        Long longValue = Long.parseLong(reverse.toString());
        if (longValue == x){
            return true;
        }
        return false;
    }
}