LeetCode刷题答案

比眉伴天荒 2022-04-24 09:46 299阅读 0赞

**目录**

3. 无重复字符的最长子串

4. 寻找两个有序数组的中位数

5. 最长的回文子串

6.Z 字形变换

8. 字符串转换整数 (atoi)

9. 回文数

11. 盛最多水的容器

12. 整数转罗马数字

13. 罗马数字转整数

14. 最长公共前缀

15. 三数之和

16. 最接近的三数之和

18. 四数之和

20. 有效的括号

21. 合并两个有序链表

26. 删除排序数组中的重复项

27. 移除元素

28. 实现 strStr()

35. 搜索插入位置

38. 报数

53. 最大子序和

持续更新中.........

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

###  [3. 无重复字符的最长子串][3.] ###

package cn.zh.t3;
    
    /**
     * 无重复字符最长子串
     */
    public class Test3 {
        public static int lengthOfLongestSubstring(String s) {
            int l = 0;
            int r = 0;
            int[] temp = new int[128];
            int maxlen = 0;
            while(l<s.length()){
                if(r<s.length() && temp[s.charAt(r)] == 0){
    
                    temp[s.charAt(r)]++;
    
                    r++;
                }else{
                    maxlen = Math.max(maxlen,r-l);
    
                    temp[s.charAt(l)]--;
                    l++;
                }
    
            }
            return maxlen;
    
        }
        public static void main(String[] args) {
            String string ="abcabcbb";
            System.out.println(lengthOfLongestSubstring(string));
    //        int[] a = new int[344];
    //        System.out.println(string.charAt(4));
    //        for(int i = 0 ;i<string.length();i++){
    //            System.out.println(a[string.charAt(i)]);
    //
    //        }
    
        }
    }

### [4. 寻找两个有序数组的中位数][4.] ###

package cn.zh.t3;
    
    /**
     * 最长回文子串
     */
    public class Test4 {
        public static void main(String[] args) {
            String s = "a";
    
            System.out.println(longestPalindrome(s));
        }
        public static  String longestPalindrome(String s) {
            int max = 0;
            int len = s.length();
            String test=null;
            String ans = null;
            for (int i = 0; i < len/2;i++){
                for (int j = i+1;j < len;j++){
                    test = s.substring(i,j);
                    if (fun(test) && (test.length()>max)){
                        max = test.length();
                        ans = s.substring(i,j);
                    }
                }
            }
            return  ans;
    
        }
        public static boolean fun(String s){
    
            int len = s.length();
    
                if (s.charAt(0) != s.charAt(len - 1)) {//判断首字符和尾字符是否相等
                    return false;
                 }
            return true;//首位相等
        }
    
    
    }

### 5. 最长的回文子串 ###

package cn.zh.t3;
    
    public class Test5 {
        public static String longestPalindrome1(String s) {
            if (s == null || s.length() == 0) {
                return s;
            }
            String res = "";
            boolean[][] dp = new boolean[s.length()][s.length()];
            int max = 0;
            for (int j = 0; j < s.length(); j++) {
                for (int i = 0; i <= j; i++) {
                    dp[i][j] = s.charAt(i) == s.charAt(j) && ((j - i <= 2) || dp[i + 1][j - 1]);
                    if (dp[i][j]) {
                        if (j - i + 1 > max) {
                            max = j - i + 1;
                            res = s.substring(i,j + 1);
                        }
                    }
                }
            }
            return res;
        }
        //------------------------------------------
        public static String res = "";
        public static String longestPalindrome2(String s) {
    
            if (s == null || s.length() == 0) {
                return s;
            }
            for (int i = 0; i < s.length(); i++) {
                helper(s,i,i);
                helper(s,i,i + 1);
            }
            return res;
        }
        public static void helper(String s,int left,int right) {
            while (left > 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
    
            String cur = s.substring(left + 1,right);
    
    
            if (cur.length() > res.length()) {
                res = cur;
            }
        }
    
        public static void main(String[] args) {
            String s = "babad";
            System.out.println(longestPalindrome2(s));
        }
    }

### 6.[Z 字形变换][Z] ###

package cn.zh.t3;
    
    public class Test6 {
        public static String convert(String s, int numRows) {
    
            if (numRows == 1) return s;
    
            StringBuilder ret = new StringBuilder();
            int n = s.length();
            int cycleLen = 2 * numRows - 2;
    
            for (int i = 0; i < numRows; i++) {
                for (int j = 0; j + i < n; j += cycleLen) {
                    ret.append(s.charAt(j + i));
                    if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                        ret.append(s.charAt(j + cycleLen - i));
                }
            }
    
            return ret.toString();
        }
    
        public static void main(String[] args) {
            String string = "LEETCODEISHIRING";
            int numRows = 3;
            System.out.println(convert(string,numRows));
        }
    
    }

### [8. 字符串转换整数 (atoi)][8. _ _atoi] ###

package cn.zh.t3;
    
    /**
     * 1.首先去除字符串左右空格,不符合条件的直接return 0;
     * 2.sign是符号位,start指针指向第一个数字的位置,如果第一位为数字,则sign=1,start=0,否则firstChar接收字符串第一个字符,若为“+”、“-”,sign分别赋值1、-1,start自增1,
     * 3.从字符串第一个为数字的位置开始遍历,res为无符号结果,如果res大于Integer最大值且sign=1,输出Integer的最大值,反之输出Integer最小值,如果遍历到不为数字的字符,则直接返回res*sign;
     * 4.如果遍历时该字符串未超范围,且无非数字字符,则返回res * sign;
     *
     */
    public class Test8 {
        public static int myAtoi(String str) {
            //1.首先去除字符串左右空格,不符合条件的直接return 0;
            str=str.trim();
            if (str == null || str.length() == 0) {
                return 0;
    
            }
            int sign = 1;
            if(str.charAt(0) == '-'){
                sign = -1;
                str = str.substring(1);
    
            }else if(str.charAt(0) == '+'){
                sign = 1;
                str= str.substring(1);
            }
            long ans = 0;
            for(int i = 0; i<str.length();i++) {
                char val = str.charAt(i);
                if(!Character.isDigit(val))
                    break;
                ans = ans*10 + (val - '0');
                if (ans*sign<Integer.MIN_VALUE) return Integer.MIN_VALUE;
                if(ans*sign>Integer.MAX_VALUE) return Integer.MAX_VALUE;
    
            }
            return (int)ans*sign;
    
        }
    
        public static void main(String[] args) {
            String string = "123 4 ee ";
    
            System.out.println(myAtoi(string));
    
    
        }
    }

###  [9. 回文数][9.] ###

package cn.zh.t3;
    
    public class Test9 {
        public static boolean isPalindrome(int x) {
            int k = x;
            int y = 0;
            if (x<0){
             return false;
            }
            while (x!=0){
             y=y*10+x%10;
             x/=10;
            }
            if (k == y) {
                return true;
    
            }else{
                return false;
            }
        }
    
        public static void main(String[] args) {
            System.out.println(isPalindrome(12321));
        }
    }

### [11. 盛最多水的容器][11.] ###

package cn.zh.t3;
    
    public class Test11 {
        public static int maxArea(int[] height) {
            int res = 0;
            int l = 0, r = height.length - 1;
            while (l < r) {
                res = Math.max(res,Math.min(height[l],height[r])*(r - l));
                if (height[l] < height[r]) {
                    l++;
    
                }else r--;
            }
            return res;
        }
    
        public static void main(String[] args) {
            int[] height = {1,8,6,2,5,4,8,3,7};
            System.out.println(maxArea(height));
        }
    }

### [12. 整数转罗马数字][12.] ###

package cn.zh.t3;
    
    public class Test12 {
        public static String intToRoman(int num) {
            int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
            String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < values.length; i++) {
                while (num >= values[i]) {
                    num -= values[i];
                    sb.append(strs[i]);
                }
            }
            return sb.toString();
        }
    
        public static void main(String[] args) {
            System.out.println(intToRoman(4));
        }
    }

### [13. 罗马数字转整数][13.] ###

package cn.zh.t3;
    
    import java.util.HashMap;
    import java.util.Map;
    
    public class Test13 {
        public static int romanToInt(String s) {
            Map<String,Integer> map = new  HashMap<String,Integer>();
            map.put("I", 1);
            map.put("IV", 4);
            map.put("V", 5);
            map.put("IX", 9);
            map.put("X", 10);
            map.put("XL", 40);
            map.put("L", 50);
            map.put("XC", 90);
            map.put("C", 100);
            map.put("CD", 400);
            map.put("D", 500);
            map.put("CM", 900);
            map.put("M", 1000);
    
            int ans = 0;
            for(int i = 0;i < s.length();) {
                if(i + 1 < s.length() && map.containsKey(s.substring(i, i+2))) {
                    ans += map.get(s.substring(i, i+2));
                    i += 2;
                } else {
                    ans += map.get(s.substring(i, i+1));
                    i ++;
                }
            }
            return ans;
    
    
        }
    
        public static void main(String[] args) {
            String s = "MCMXCIV";
            System.out.println(romanToInt(s));
    
        }
    }

### [14. 最长公共前缀][14.] ###

package cn.zh.t3;
    
    public class Test14 {
        public static String longestCommonPrefix(String[] strs) {
            if(strs == null || strs.length == 0) return "";
            String res = strs[0];
            for (int i = 0; i < strs.length; i++) {
    
                while (strs[i].indexOf(res) != 0 ){
                    res = res.substring(0,res.length() - 1);
                }
            }
            return res;
        }
    
        public static void main(String[] args) {
            String[] strs=  {"flower","flow","flight"};
            String s = longestCommonPrefix(strs);
            System.out.println(s);
        }
    }

### [15. 三数之和][15.] ###

package cn.zh.t3;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Test15 {
        public static List<List<Integer>> threeSum1(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
    
            Arrays.sort(nums);
            for (int i = 0; i < nums.length-2; i++) {
                if (i > 0 && nums[i] == nums[i - 1]) continue;//去重
                int low = i + 1, high = nums.length - 1, sum = 0 - nums[i];
                while (low < high) {
                    if (nums[low] + nums[high] == sum) {
                        res.add(Arrays.asList(nums[i],nums[low],nums[high]));
                        while (low < high && nums[low] == nums[low + 1]) low++;//去重
                        while (low < high && nums[high] == nums[high - 1]) high--;//去重
                        low++;
                        high--;
    
                    } else if (nums[low] + nums[high] <sum) {
                        low++;
                    } else {
                        high--;
                    }
                }
            }
            return res;
        }
    
    
        public static List<List<Integer>> threeSum2(int[] nums) {
            List<List<Integer>> ans = new ArrayList();
            int len = nums.length;
            if(nums == null || len < 3) return ans;
            Arrays.sort(nums); // 排序
            for (int i = 0; i < len ; i++) {
                if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
                if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
                int L = i+1;
                int R = len-1;
                while(L < R){
                    int sum = nums[i] + nums[L] + nums[R];
                    if(sum == 0){
                        ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                        while (L<R && nums[L] == nums[L+1]) L++; // 去重
                        while (L<R && nums[R] == nums[R-1]) R--; // 去重
                        L++;
                        R--;
                    }
                    else if (sum < 0) L++;
                    else if (sum > 0) R--;
                }
            }
            return ans;
        }
    
        public static void main(String[] args) {
            int[] nums = {-1, 0, 1, 2, -1, -4};
            System.out.println(threeSum2(nums));
        }
    }

###  [16. 最接近的三数之和][16.] ###

package cn.zh.t3;
    
    import java.util.Arrays;
    
    public class Test16 {
        public static int threeSumClosest(int[] nums, int target) {
            int res = nums[0] + nums[1] + nums[nums.length - 1];
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) {
                int start = i + 1, end = nums.length - 1;
                while (start < end) {
                    int sum = nums[i] + nums[start] + nums[end];
                    if (sum > target) {
                        end--;
    
                    } else start++;
                    if (Math.abs(sum - target)<Math.abs(res - target)) {
                        res = sum;
                    }
                }
            }
            return res;
        }
    
        public static void main(String[] args) {
            int[] nums = {-1,2,1,-4};
            System.out.println(threeSumClosest(nums,1));
        }
    }

###    [18. 四数之和][18.] ###

package cn.zh.t3;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Test18 {
        public static List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> res = new ArrayList<>();
            if (nums.length < 4) return res;
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 3; i++) {
                if (i > 0 && nums[i] == nums[i-1]) continue;
                for (int j = i + 1; j < nums.length -2; j++) {
                    if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                    int low = j + 1, high = nums.length - 1;
                    while (low < high) {
                        int sum = nums[i] + nums[j] + nums[low] + nums[high];
                        if (sum == target) {
                            res.add(Arrays.asList(nums[i],nums[j],nums[low],nums[high]));
                            while (low < high && nums[low] == nums[low + 1]) low++;
                            while (low < high && nums[high] == nums[high - 1]) high--;
                            low++;
                            high--;
                        } else if (sum < target) {
                            low++;
                        } else high--;
                    }
                }
            }
            return res;
        }
    
        public static void main(String[] args) {
            int[] a = {1,0,-1,0,-2,2};
            System.out.println(fourSum(a,0));
    
        }
    }

###  [20. 有效的括号][20.] ###

package cn.zh.t3;
    
    import java.util.Stack;
    
    public class Test20 {
        public static boolean isValid(String s) {
            if (s == null || s.length() == 0) return true;
            Stack<Character> stack = new Stack<>();
            for (Character ch : s.toCharArray()) {
                if (ch == '(') {
                    stack.push(')');
                } else if (ch == '[') {
                    stack.push(']');
    
                } else if (ch == '{') {
                    stack.push('}');
                } else {
                    if (stack.isEmpty() || stack.pop() != ch) {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    
        public static void main(String[] args) {
            String s = "()[]{}";
            boolean valid = isValid(s);
            System.out.println(valid);
        }
    }

### [21. 合并两个有序链表][21.] ###

package cn.zh.t3;
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x ){
            val = x;
        }
    }
     public class Test21 {
    
        public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(0);
            ListNode cur = dummy;
            while(l1 != null || l2 != null) {
                if (l1.val<l2.val) {
                    cur.next = new ListNode(l1.val);
                    l1 = l1.next;
                } else {
                    cur.next = new ListNode(l2.val);
                    l2 = l2.next;
                }
                cur = cur.next;
            }
            if (l1!= null) {
                cur.next = l1;
    
            } else {
                cur.next = l2;
            }
            return dummy.next;
        }
    
         public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
             if (l1 == null) {
                 return l2;
             }
             if(l2 == null) {
                 return l1;
             }
             if (l1.val < l2.val) {
                 l1.next = mergeTwoLists2(l1.next, l2);
                 return l1;
             } else {
                 l2.next = mergeTwoLists2(l1, l2.next);
                 return l2;
             }
    
         }
    
        
    }

### [26. 删除排序数组中的重复项][26.] ###

package cn.zh.t3;
    
    public class Test26 {
        public static int removeDuplicates(int[] nums) {
            if (nums == null || nums.length == 0){
                return 0;
            }
            int count = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i - 1] != nums[i]) {
                    nums[count++] = nums[i];
                }
            }
            return count;
        }
    
        public static void main(String[] args) {
            int[] nums = {0,0,1,1,1,2,2,3,3,4};
            System.out.println(removeDuplicates(nums));
    
        }
    }

### [27. 移除元素][27.] ###

package cn.zh.t3;
    
    public class Test27 {
        public static  int removeElement(int[] nums, int val) {
            if (nums == null || nums.length == 0)
                return 0;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != val){
                    nums[count++] = nums[i];
                }
            }
            return count;
        }
    
        public static void main(String[] args) {
          int[] nums = {0,1,2,2,3,0,4,2};
            System.out.println(removeElement(nums,2));
        }
    }

### [28. 实现 strStr()][28. _ strStr] ###

package cn.zh.t3;
    
    public class Test28 {
        public static int strStr(String haystack, String needle) {
            if (needle == null)
                return 0;
            for (int i = 0;i <= haystack.length()-needle.length(); i++) {
                if (haystack.substring(i,i+needle.length()).equals(needle))
                    return i;
            }
            return -1;
        }
    
        public static void main(String[] args) {
            String h = "hello";
            String n = "ll";
            System.out.println(strStr(h,n));
        }
    }

### [35. 搜索插入位置][35.] ###

package cn.zh.t3;
    
    public class Test35 {
        public static int searchInsert(int[] nums, int target) {
            int left = 0;
            int right = nums.length-1;
            while(left <= right) {
                int mid = (left + right)/2;
                if (nums[mid] == target) {
                    return mid;
                }else if(nums[mid] < target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
            return left;
        }
    
        public static void main(String[] args) {
            int nums[] = {1, 2, 4, 5, 7,8, 9};
            int target = 3;
            System.out.println(searchInsert(nums,target));
        }
    
    }

###  [38. 报数][38.] ###

package cn.zh.t3;
    
    public class Test38 {
        public static String countAndSay(int n) {
            int i = 1;
            String res = "1";
            while (i < n) {
                int count = 0;
                StringBuilder sb = new StringBuilder();
                char c = res.charAt(0);
                for (int j = 0; j < res.length(); j++) {
                    if (j != res.length() && res.charAt(j) == c) {
                        count++;
                    } else {
                        sb.append(count);
                        sb.append(c);
                        if (j != res.length()) {
                            count = 1;
                            c = res.charAt(j);
                        }
                    }
                }
                res = sb.toString();
                i++;
            }
            return res;
        }
    
        public static void main(String[] args) {
            String s = countAndSay(2);
            System.out.println(s);
        }
    }

### [53. 最大子序和][53.] ###

package cn.zh.t3;
    
    public class Test53 {
    
        public static int maxSubArray(int[] nums) {
            int maxSum = nums[0];
            int thisSum = 0;
            for(int num: nums) {
                if(thisSum > 0) {
                    thisSum += num;
                } else {
                    thisSum = num;
                }
                maxSum = Math.max(maxSum, thisSum);
            }
            return maxSum;
    
        }
    
        public static void main(String[] args) {
    
            int[] n = {-2,1,-1,4,};
            System.out.println(maxSubArray(n));
        }
    }

### 持续更新中......... ###

[3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[4.]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[Z]: https://leetcode-cn.com/problems/zigzag-conversion/
[8. _ _atoi]: https://leetcode-cn.com/problems/string-to-integer-atoi/
[9.]: https://leetcode-cn.com/problems/palindrome-number/
[11.]: https://leetcode-cn.com/problems/container-with-most-water/
[12.]: https://leetcode-cn.com/problems/integer-to-roman/
[13.]: https://leetcode-cn.com/problems/roman-to-integer/
[14.]: https://leetcode-cn.com/problems/longest-common-prefix/
[15.]: https://leetcode-cn.com/problems/3sum/
[16.]: https://leetcode-cn.com/problems/3sum-closest/
[18.]: https://leetcode-cn.com/problems/4sum/
[20.]: https://leetcode-cn.com/problems/valid-parentheses/
[21.]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[26.]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
[27.]: https://leetcode-cn.com/problems/remove-element/
[28. _ strStr]: https://leetcode-cn.com/problems/implement-strstr/
[35.]: https://leetcode-cn.com/problems/search-insert-position/
[38.]: https://leetcode-cn.com/problems/count-and-say/
[53.]: https://leetcode-cn.com/problems/maximum-subarray/