算法成长之路leetcode1-4

二分查找分治算法字符串滑动窗口

Word count: 1.4kReading time: 8 min

 2019/11/05   Share

1.Two Sum

desc

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

solution

s.eg1.

//24 ms	38 MB s.O(n^2) k.O(1)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result =new int[2];
        for(int i = 0;i<nums.length-1;i++){
            for(int j = i+1;j<nums.length;j++){
                if(nums[i]+nums[j] == target){
                    result[0] = i;
                    result[1] = j;
                    return new int[]{i,j};
                }
            }
        }
        return new int[0];
    }
}

eg2.

// 3 ms	37.2 MB s.O(n) k.O(n)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> cache = new HashMap();
        for(int i = 0;i<nums.length;i++){
            if(cache.get(nums[i]) != null){
                return new int[]{cache.get(nums[i]),i};
            }
            cache.put(target-nums[i],i);
        }
        return new int[0];
    }
}

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

solution

eg1.

// 2 ms	44.7 MB
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
         int carry = 0; // 进位
         ListNode head = new ListNode(0);
         ListNode cur = head; // 一定要用两个链表，不能用一个操作
       while(l1 != null ||l2 != null|| carry != 0){ // lastSum当最后一位刚好进1的时候，需要在循环
           
            int l1v =  l1 == null?0:l1.val;
            int l2v =  l2 == null?0:l2.val;
            int temp =l1v+l2v+carry;
            ListNode node;
            if(temp>=10){
               node = new ListNode(temp-10);
               lastSum = 1;
            }else{
               node = new ListNode(temp);
               lastSum = 0;
            }
           
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
         
            cur.next = node;
            cur = node;
        }
        return head.next;
    }
}

3.Longest Substring Without Repeating Characters

desc

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

solution

eg1.

//2 ms 24.05% 36.9 MB 95.35%
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> strSet = new HashSet();
        int maxLen = 0;
        if(s != null && s.length() >0){
            char ss[] = s.toCharArray(); //利用toCharArray方法转换
		    for (int i = 0; i < ss.length-1; i++) {
                strSet.add(ss[i]);
                for(int j = i+1; j<ss.length; j++){
                    int oL = strSet.size();
                    strSet.add(ss[j]);
                    int cL = strSet.size();
                    if(oL != cL){ // 不相等时记下个数
                        if(cL > maxLen){
                            maxLen = cL;
                        }
                    }else{ // 相等时 跳出此次循环 清空set
                           strSet.clear();
                           break;
                    }
                 }
             }
            if(maxLen == 0){ // 全相等时
                maxLen = 1;
            }
        }
        return maxLen;
    }
}

eg2.

// 2 ms	37.3 MB
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        char[] chars = s.toCharArray();
        int leftIndex = 0;//记录最左边相等时的值，然后向右滑动窗口
        for (int j = 0; j < chars.length; j++) {
          for (int innerIndex = leftIndex; innerIndex < j; innerIndex++) {
            if (chars[innerIndex] == chars[j]) {
              maxLength = Math.max(maxLength, j - leftIndex);
              leftIndex = innerIndex + 1;
              break;
            }
          }
        }
        return Math.max(chars.length - leftIndex, maxLength);
        }
}

4.Median of Two Sorted Arrays

desc

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1
2
3

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:

1
2
3

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

solution

eg1.

// 20 ms  10.07%
// 2.2 MB 99.84%
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int maxL = 0;
        if (nums1.length >= nums2.length) {
            maxL = nums1.length;
        } else {
            maxL = nums2.length;
        }
        List<Integer> newList = new ArrayList(maxL);
        for (int i = 0; i < maxL; i++) {
            if (i < nums1.length) {
                newList.add(nums1[i]);
            }
            if (i < nums2.length) {
                newList.add(nums2[i]);
            }
        }

        int size = newList.size();
        int index = size / 2;
        newList.sort(Comparator.comparing(Integer::valueOf));
        if (size % 2 == 0) {
            return (newList.get(index) + newList.get(index - 1)) / 2d;
        } else {
            return newList.get(index);
        }
    }
}

eg2.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;
        double res = 0.0;
        if (n <= 0) {
            return res;
        }
        if ((n & 1) == 0) {
            res = (findKth(nums1, nums2, 0, 0, n / 2) + findKth(nums1, nums2, 0, 0, n / 2 + 1)) / 2.0;
        }
        else {
            res = findKth(nums1, nums2, 0, 0, n / 2 + 1);
        }
        return res;
    }
    private int findKth(int[] nums1, int[] nums2, int start1, int start2, int k) {
        if (start1 >= nums1.length) {
            return nums2[start2 + k - 1];
        }
        if (start2 >= nums2.length) {
            return nums1[start1 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }
        int left = start1 + k / 2 - 1 >= nums1.length ? Integer.MAX_VALUE : nums1[start1 + k / 2 - 1];
        int right = start2 + k / 2 - 1 >= nums2.length ? Integer.MAX_VALUE : nums2[start2 + k / 2 - 1];
        if (left < right) {
            return findKth(nums1, nums2, start1 + k / 2, start2, k - k / 2);
        }
        return findKth(nums1, nums2, start1, start2 + k / 2, k - k / 2);
    }
}

eg3.

// 二分查找、分治算法
class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        //m:A数组的长度
        int m = A.length;
        //n:B数组的长度

        int n = B.length;
        //如果A的长度大于B
        if (m > n) { // to ensure m<=n
            //交换AB数组，确保m<=n
            int[] temp = A; A = B; B = temp;
            int tmp = m; m = n; n = tmp;
        }
        //设置两个指针，iMin为头指针，IMAX为尾指针，halfLen为中位数指针
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        //如果头指针走向不大于尾指针，进行循环
        while (iMin <= iMax) {
            //i为中位数
            int i = (iMin + iMax) / 2;
            //j为
            int j = halfLen - i;
            if (i < iMax && B[j - 1] > A[i]){
                iMin = i + 1; // i is too small
            }
            else if (i > iMin && A[i - 1] > B[j]) {
                iMax = i - 1; // i is too big
            }
            else { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i - 1]; }
                else { maxLeft = Math.max(A[i - 1], B[j - 1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; }

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.min(B[j], A[i]); }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0d;
    }
}

Author：John Doe

原文链接：https://removeif.github.io/2019/11/05/algorithm/%E7%AE%97%E6%B3%95%E6%88%90%E9%95%BF%E4%B9%8B%E8%B7%AFleetcode1-4/

发表日期：November 5th 2019, 6:18:47 pm

更新日期：February 2nd 2020, 10:00:25 am

Next Post

马拉松-2019西昌最美赛道邛海马拉松
Previous Post

替代web-cookie存储方案实现



缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是archer根目录）执行以下命令：
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置：

jsonContent:
  meta: false
  pages: false
  posts:
    title: true
    date: true
    path: true
    text: false
    raw: false
    content: false
    slug: false
    updated: false
    comments: false
    link: false
    permalink: false
    excerpt: false
    categories: true
    tags: true

算法成长之路leetcode1-4

1.Two Sum

desc

solution

s.eg1.

eg2.

2.Add Two Numbers

des

solution

eg1.

3.Longest Substring Without Repeating Characters

desc

solution

eg1.

eg2.

4.Median of Two Sorted Arrays

desc

solution

eg1.

eg2.

eg3.