LeetCode-hot100题解—Day1

原题链接：力扣热题-HOT100

题解的顺序和题目的顺序一致，那么接下来就开始刷题之旅吧

力扣hot100题解 1-8

• • 1.两数之和
  • 2.两数相加
  • 3.无重复字符的最长子串
  • 4.寻找两个正序数组的中位数
  • 5.最长回文子串
  • 6.Z字形变换
  • 7.整数反转
  • 8.字符串转换整数（atoi）

    1.两数之和

    思路1：暴力枚举法

    暴力枚举法很简单，遍历nums数组的每一个元素，找到和target-nums[i]相同的元素即可。

    时间复杂度：需要使用到两层for循环，所以时间复杂度为O(n^2)。

    代码实现：

    class Solution {
        public int[] twoSum(int[] nums, int target) {
            for(int i=0;i
               for(int j=i+1;j
                   if(nums[j]==target-nums[i]){
                       return new int[] {i,j};
                   }   
               } 
            }
            return null;
        }
    }
    
        public int[] twoSum(int[] nums, int target) {
            Map
                int tar = target-nums[i];
                if(tab.containsKey(tar)){
                    return new int[] {i,tab.get(tar)};
                }else{
                    tab.put(nums[i],i);
                }
            }
             return null;
        }
    }
    
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode head = new ListNode(-1);
            ListNode tail = head;
            int sum;
            int carry = 0;
            while(l1 != null || l2 != null){
                int n = l1 == null ? 0 : l1.val;
                int m = l2 == null ? 0 : l2.val;
                sum = n + m + carry;
                carry = sum / 10;
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
                l1 = l1 != null ? l1.next : null;
                l2 = l2 != null ? l2.next : null;
            }
            if(carry != 0){
                tail.next = new ListNode(carry);
            }
            return head.next;
        }
    };
    
        public int lengthOfLongestSubstring(String s) {
            HashMap
                return 0;
            }
            int max=0;
            int left=0;
            for(int i = 0;i
                if(map.containsKey(s.charAt(i))){
                    left = Math.max(left,map.get(s.charAt(i))+1);
                }
                map.put(s.charAt(i),i);
                max=Math.max(max,i-left+1);
            }
            return max;
        }
    }
    
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            //将nums1设置为长度较小的数组，方便代码的编写
            if(nums1.lengthnums2.length){
                int[] temp = nums1;
                nums1 = nums2;
                nums2 = temp;
            }
            
            int m = nums1.length;
            int n = nums2.length;
            //计算分割线左边元素的数量
            int totalleft = (m+n+1)/2;
            
            //二分法查找nums1部分的分割线
            int left = 0;
            int right = m;
            while(left
                //这是对于(left+right)/2的特殊处理方式，防止发生整型溢出
                //同时使用二分法时，如果出现left=i，则这里需要+1，否则不需要
                int i = left+(right-left+1)/2;
                int j = totalleft - i;
                if(nums1[i-1]  nums2[j]){
                    right = i - 1;
                }else{
                    left = i;
                }
            }
            int i = left;
            int j = totalleft - i;
            //最后得到两个数组分割线左右两边元素的最大值的最小值
            //为了防止出现分割线左右两边没有元素的极端情况加上判断
            int nums1LeftMax = i ==0 ? Integer.MIN_VALUE : nums1[i-1];
            int nums1RightMin = i ==m ? Integer.MAX_VALUE : nums1[i];
            int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j-1];
            int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
            //计算中位数的值
            if(((m+n) % 2) == 1){
                return Math.max(nums1LeftMax,nums2LeftMax);
            }else{
                return (double) ((Math.max(nums1LeftMax,nums2LeftMax) + Math.min(nums1RightMin,nums2RightMin))) / 2;
            }
        }
    }
    
    	while(left
    		if(charArry[left] != charArry[right]){
    			return false;
    		}
    		left++;
    		right--;
    	}
    	return true;
    }
    
        public String longestPalindrome(String s) {
            int len = s.length();
            if(len
                return s;
            }
            int maxLen = 1;
            int begin = 0;
            //初始化二维数组
            boolean[][] dp = new boolean[len][len];
            for(int i=0;i
                dp[i][i] = true;
            }
            char[] charArray = s.toCharArray();
            for(int j=1;j
                for(int i=0;i
                    if(charArray[i] != charArray[j]){
                        dp[i][j]=false;
                    }else{
                        if(j-i
                            dp[i][j]=true;
                        }else{
                            dp[i][j] = dp[i+1][j-1];
                        }
                    }
                    if(dp[i][j] && j-i+1  maxLen){
                        maxLen = j-i+1;
                        begin = i;
                    }
                }
            }
            return s.substring(begin,begin+maxLen);
        }
    }
    
        public String convert(String s, int numRows) {
            if (numRows == 1) {
                return s;
            }
            ArrayList
                rows.add("");
            }
            boolean down = false;
            for (int i = 0, row = 0; i