LeetCode001~010

╰半橙微兮° 2022-05-16 10:06 219阅读 0赞

**实验平台**：[LeetCode][]  
**代码地址**：[my github][]

--------------------

## LeetCode001：两数之和 ##

### 题目描述： ###

![这里写图片描述][70]

### 示例： ###

![这里写图片描述][70 1]

### 运行结果： ###

![这里写图片描述][70 2]

### 代码： ###

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

--------------------

## LeetCode002：两数相加 ##

### 题目描述： ###

![这里写图片描述][70 3]

### 示例： ###

![这里写图片描述][70 4]

### 运行结果： ###

![这里写图片描述][70 5]

### 代码： ###

/** * 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) {
            if (l1 == null || l2 == null) {
                return l1 == null ? l2 : l1;
            }
            int sum = l1.val + l2.val;
            ListNode node = new ListNode(sum % 10);
            node.next = addTwoNumbers(l1.next, l2.next);
            if (sum >= 10) {
                node.next = addTwoNumbers(new ListNode(sum / 10), node.next);
            }
            return node;
        }
    }

--------------------

## LeetCode003：无重复字符的最长子串 ##

### 题目描述： ###

![这里写图片描述][70 6]

### 示例： ###

![这里写图片描述][70 7]

### 运行结果： ###

![这里写图片描述][70 8]

### 代码： ###

class Solution {
        public int lengthOfLongestSubstring(String s) {
            int result = 0, start = 0, end = 0;
            int sLen = s.length();
            HashMap<Character, Integer> map = new HashMap<>();// key存字符，value存字符所在的位置
            while (start < sLen && end < sLen) {
                if (map.containsKey(s.charAt(end))) {
                    start = Math.max(map.get(s.charAt(end)) + 1, start);// 考虑到回文等情况
                }
                map.put(s.charAt(end), end);
                result = Math.max(result, end - start + 1);
                end++;
            }
            return result;
        }
    }

--------------------

## LeetCode004：两个排序数组的中位数(时间复杂度要求没达到，为O（n）) ##

### 题目描述： ###

![这里写图片描述][70 9]

### 示例： ###

![这里写图片描述][70 10]

### 运行结果： ###

![这里写图片描述][70 11]

### 代码： ###

class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int length = nums1.length + nums2.length;
            int[] array = new int[length];
            int i = 0, j = 0, k = 0;
            while (i < nums1.length && j < nums2.length) {
                if (nums1[i] <= nums2[j]) {
                    array[k++] = nums1[i++];
                } else {
                    array[k++] = nums2[j++];
                }
            }
            while (i < nums1.length) {
                array[k++] = nums1[i++];
            }
            while (j < nums2.length) {
                array[k++] = nums2[j++];
            }
            int middle = length / 2;
            if ((length & 1) == 0) {
                return (array[middle - 1] + array[middle]) / 2.0;
            } else {
                return array[middle];
            }
        }
    }

--------------------

## LeetCode005：最长回文子串 ##

### 题目描述： ###

![这里写图片描述][70 12]

### 示例： ###

![这里写图片描述][70 13]

### 运行结果： ###

![这里写图片描述][70 14]

### 代码： ###

class Solution {
        public String longestPalindrome(String s) {
            int beginIndex = 0, endIndes = 0;
            for (int i = 0; i < s.length(); i++) {
                int len = Math.max(getLength(i, i, s), getLength(i, i + 1, s));
                if (len >= endIndes - beginIndex + 1) {
                    beginIndex = i - (len - 1) / 2;
                    endIndes = i + len / 2 + 1;
                }
            }
            return s.substring(beginIndex, endIndes);
        }
    
        public int getLength(int left, int right, String s) {
            int l = left, r = right;
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                l--;
                r++;
            }
            return r - l - 1;
        }
    }

--------------------

## LeetCode006： Z字形变换 ##

### 题目描述： ###

![这里写图片描述][70 15]

### 示例： ###

![这里写图片描述][70 16]

### 运行结果： ###

![这里写图片描述][70 17]

### 代码： ###

class Solution {
        public String convert(String s, int numRows) {
            if (numRows <= 1) {
                return s;
            }
            StringBuilder sb = new StringBuilder();
            int margin = 2 * numRows - 2;
            int strLen = s.length();
            for (int i = 0; i < numRows; i++) { // 行数
                for (int j = 0; i + j * margin < strLen; j++) {
                    sb.append(s.charAt(i + j * margin));
                    if (i > 0 && i < numRows - 1 && (j + 1) * margin - i < strLen) {
       // 当行数在0和(numRows-1)之间时
                        sb.append(s.charAt((j + 1) * margin - i));
                    }
                }
            }
            return sb.toString();
        }
    }

--------------------

## LeetCode007：反转整数 ##

### 题目描述： ###

给定一个 32 位有符号整数，将整数中的数字进行反转。

### 示例： ###

![这里写图片描述][70 18]

### 运行结果： ###

![这里写图片描述][70 19]

### 代码： ###

class Solution { 
        public int reverse(int x) {
            int absNum = Math.abs(x);
            long result = 0;
            while (absNum > 0) {
                result = result * 10 + absNum % 10;
                absNum /= 10;
            }
            if ((x > 0 && result > Integer.MAX_VALUE) || (x < 0 && result * -1 < Integer.MIN_VALUE)) {
                return 0;
            } else if (x > 0) {
                return (int) result;
            } else {
                return (int) (-1 * result);
            }
        }
    }

--------------------

## LeetCode008：字符串转整数 (atoi) ##

### 题目描述： ###

![这里写图片描述][70 20]

### 示例： ###

![这里写图片描述][70 21]

### 运行结果： ###

![这里写图片描述][70 22]

### 代码： ###

class Solution { 
        public int myAtoi(String str) {
            str = str.trim(); // 去除首尾空格
            int strLen = str.length();
            int flag = 1;// flag取值为1、-1，代表符号
            int index = 0;
            long res = 0;
            if (strLen == 0) {
                return 0;
            }
            char beginChar = str.charAt(0);
            if (beginChar != '+' && beginChar != '-' && (beginChar < '0' || beginChar > '9')) {
                return 0;
            } else if (beginChar == '+') {
                index += 1;
            } else if (beginChar == '-') {
                flag = -1;
                index += 1;
            }
            for (int i = index; i < strLen; i++) {
                char curChar = str.charAt(i);
                if (curChar >= '0' && curChar <= '9') {
                    res = res * 10 + curChar - 48;
                    if (flag > 0 && res > Integer.MAX_VALUE) {
                        return Integer.MAX_VALUE;
                    } else if (flag < 0 && flag * res < Integer.MIN_VALUE) {
                        return Integer.MIN_VALUE;
                    }
                } else {
                    return (int) (flag * res);
                }
            }
            return (int) (flag * res);
        }
    }

--------------------

## LeetCode009：回文数 ##

### 题目描述： ###

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

### 示例： ###

![这里写图片描述][70 23]

### 运行结果： ###

![这里写图片描述][70 24]

### 代码： ###

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

--------------------

## LeetCode0010：正则表达式匹配 ##

### 题目描述： ###

![这里写图片描述][70 25]

### 示例： ###

![这里写图片描述][70 26]

### 运行结果： ###

![这里写图片描述][70 27]

### 代码： ###

class Solution {
        public boolean isMatch(String s, String p) {
            if (s == null || p == null) {
                return false;
            } else if (s.length() == 0 && p.length() == 0) {
                return true;
            } else {
                char[] sArray = s.toCharArray();
                char[] pArray = p.toCharArray();
                return isMatchCore(sArray, pArray, 0, 0);
            }
        }
    
        public boolean isMatchCore(char[] s, char[] p, int sIndex, int pIndex) {
            if (sIndex == s.length && pIndex == p.length) {
                return true;
            }
            if (sIndex != s.length && pIndex >= p.length) {
                return false;
            }
            if (pIndex + 1 < p.length && p[pIndex + 1] == '*') {
                if (sIndex < s.length && (s[sIndex] == p[pIndex] || p[pIndex] == '.')) {
                    return isMatchCore(s, p, sIndex + 1, pIndex) || isMatchCore(s, p, sIndex, pIndex + 2);
                } else {
                    return isMatchCore(s, p, sIndex, pIndex + 2);
                }
            } else if (sIndex < s.length && pIndex < p.length && (s[sIndex] == p[pIndex] || p[pIndex] == '.')) {
                return isMatchCore(s, p, ++sIndex, ++pIndex);
            }
            return false;
        }
    }

[LeetCode]: https://leetcode-cn.com/problemset/all/
[my github]: https://github.com/TimePickerWang/LeetCode
[70]: /images/20220516/19d1e032e28a4ead863774c844f43eb6.png
[70 1]: /images/20220516/b812ff42cbba4510bfbeef5104f42c13.png
[70 2]: /images/20220516/6305c317ad4b4849b1c3707b6a1d1195.png
[70 3]: /images/20220516/03550e06bba748faae8792b7795d6b66.png
[70 4]: /images/20220516/019833e0f5d6459886fb06f3a02a878b.png
[70 5]: /images/20220516/68f73f12a6bf4824b1c97fe638131454.png
[70 6]: /images/20220516/40879ef15e3a4ae799eff4357f6dddb7.png
[70 7]: /images/20220516/e8e35f165c8e49a889723550e04e7a3b.png
[70 8]: /images/20220516/429cd386c8f440a9b3f2e84153a82989.png
[70 9]: /images/20220516/0a1817cbe41e40b2a7f57cf0ab751a6a.png
[70 10]: /images/20220516/d946349cf2b041feb2b312a862858f16.png
[70 11]: /images/20220516/74aef1c30cdf4f15b680fe0bb81eb00c.png
[70 12]: /images/20220516/3a74e421acd74587b4950d61f55248ed.png
[70 13]: /images/20220516/a72032915af84022b0fd9251f48856f3.png
[70 14]: /images/20220516/51978331879b4c6486bc978ab300cdfb.png
[70 15]: /images/20220516/1c261052a3c74d3eb5842d5ff90ca97d.png
[70 16]: /images/20220516/e34aa4ba5df9466e82ba094333319537.png
[70 17]: /images/20220516/23f4184d69ec48588bea2e5e6fa56e9d.png
[70 18]: /images/20220516/82bad31ee09240b5bd91fb9257cb24cd.png
[70 19]: /images/20220516/1ae7c0c470a349f1870c0958abc1e030.png
[70 20]: /images/20220516/2cbea39d7104422580f7f76a0b4c8451.png
[70 21]: /images/20220516/720455b46a85467785bee5ddad8e7674.png
[70 22]: /images/20220516/e26208279acf4362bb086b9c6d6fe18e.png
[70 23]: /images/20220516/ff352b5af4db486b9e022c7c2d1a48f7.png
[70 24]: /images/20220516/859f4c4baf074d8d81e3424d83644ee6.png
[70 25]: /images/20220516/20271a5f44744affb5d17d952abf33a2.png
[70 26]: /images/20220516/efca7378b9514d77bbe2dd137808ac89.png
[70 27]: /images/20220516/cf9effd747f442b0be555bb0966d0e19.png