leetcode top 100 questions - day 1: 1, 2, 3, 4

0. Always say

It's time to pick up your studies that have been neglected for so long. Today is 2022-05-18. Brush at least two questions every day. I've written the first few times and directly abbreviated them.

1. 1. Sum of two numbers

1. Title Description

2. Topic analysis

Traverse to find two numbers with mapping relationship, so you can directly use the Map hash table. Note: the first parameter of HashMap is key and the second parameter is value.

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

2. 2. Add two numbers

1. Title Description

2. Topic analysis

Linked list calculation addition, consider the carry problem and pointer transformation problem.
Carry: store with an int variable and update the value with the result of dividing 10 by the sum value. Finally, note that there may be another value after traversal.
Pointer transformation problem: after each addition, the pointer of two addends should be moved back; Use a waste header pointer (the value of new is meaningless) to record the position of the header pointer, and then use a pointer to point down to enter the loop body; Note: if the pointer to the list is not null, it is used to judge whether the pointer to the list is null. Otherwise, it is used to judge whether the pointer to the list is null.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head=new ListNode(0);
        ListNode cur=head;
        int jin=0;
        while(l1!=null||l2!=null){
            int a1=(l1==null)?0:l1.val;
            int a2=(l2==null)?0:l2.val;
            int a=a1+a2+jin;
            cur.next=new ListNode(a%10);           
            cur=cur.next;
            jin=a/10;
            if(l1!=null)
                l1=l1.next;
            if(l2!=null)
            l2=l2.next;
        }
        if(jin!=0){
            cur.next=new ListNode(jin);
        }
        return head.next;
    }
}

3. 3. Longest substring without duplicate characters

1. Title Description

2. Topic analysis

You can think of a mapping table or set to determine whether it is repeated. Here, the mapping table Map is selected because the record length (or length) is required.

Record length: since the substring is continuous, the length can be recorded at the starting position of the record. Therefore, maintain a left recording starting point and a max recording maximum. Since the previous character cannot be removed from the map, the relationship between the position of the character and left can be judged.

Note: length calculation method; Empty string.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0)return 0;
        Map<Character,Integer> res=new HashMap<>();
        int left=0;
        int max=0;
        for(int i=0;i<s.length();i++){
            if(res.containsKey(s.charAt(i))){
                int tmp=res.get(s.charAt(i))+1;
                max=max>(i-left)?max:(i-left);
                left=tmp>left?tmp:left;               
            }
            res.put(s.charAt(i),i);
            max=max>(i-left+1)?max:(i-left+1);
        }
        return max;
    }
}

4. 4. Find the median of two positively ordered arrays

1. Title Description

2. Topic analysis

Time complexity requires log + positive order array: use binary search for query.

Calculation of the median of odd and even numbers: the median of even numbers is the average of the two numbers, so it can be calculated uniformly: find the average of the two numbers (length + 1 divided by 2) and (length + 2 divided by 2).

The code is in the solution of the problem. I comb it with my own ideas:

Convert it into the number with the smallest K, and compare the k/2 number between the two arrays A and B. If A is small, the first k/2 number of A is not, so remove this part and find A new number with the smallest (k-k/2) of A and B until k=1 or an array is empty.
If the length of the array is less than k/2, point directly to the end.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //Combine even and odd numbers. If it is an odd number, it will find the same k twice.
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  //Note that * 0.5 is not divided by 2
}
    
    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;
        //Let the length of len1 be less than len2, so as to ensure that if there is an empty array, it must be 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));
        }
    }
}
Author: windliang
 Link: https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.

Tags: Algorithm leetcode

Posted by php3ch0 on Thu, 19 May 2022 01:06:23 +0300