lalaorya/leetcode-onepiece

Record my own solution and ideas in the process of brushing LeetCode

leetcode-onepiece's Issues

[leetcode]2. 两数相加

• 两数之和

这道题其实就是两条链表相加，思路很简单，构造新的链表，注意进位即可，注意细节即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res=new ListNode(0);
        ListNode cur=res;
        int carry=0;
        while(l1!=null||l2!=null){
            int d1= l1==null?0:l1.val;
            int d2= l2==null?0:l2.val;
            int sum=d1+d2+carry;
            
            carry=sum>=10?1:0;
            
            cur.next=new ListNode(sum%10);
            cur=cur.next;
            if(l1!=null)    l1=l1.next;
            if(l2!=null)    l2=l2.next;
            
        }
        // 最后一个进位没计算
        if(carry == 1){
            cur.next = new ListNode(1);
        }
        
        return res.next;

    }
}

[leetcode]4. 寻找两个正序数组的中位数

mark

[leetcode]1. 两数之和

• 两数之和

这道题主要考察了hash容器的使用，通过hash容器，我们可以以O(1)的代价查找某元素，远远优于O(n)的暴力遍历

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

    }
}

也可以写的更简洁一些，把两个for循环合成一个

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        
        for(int i=0;i<nums.length;i++){
            int t=target-nums[i];
            if(map.containsKey(t)){
                return new int[]{i,map.get(t)};
            }
            // 因为是后put，所以不会出现一个元素被计算两次的情况
            map.put(nums[i],i);
        }
        
        return new int[]{-1,-1};

    }
}

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

• 无重复字符的最长子串

这道题其实就是求给定字符串的子串最大长度，这个子串的字符笔试是无重复的。注意：子串必须是连续的，子序列可以不是连续的

这道题有两种解法：滑动窗口和map

解法一：滑动窗口

通过set对当前子串去重，滑动窗口的最大长度即是最终结果

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res=0;
        HashSet<Character> set=new HashSet<>();
        // 滑动窗口解法
        int left=0;
        int right=0;
        char[] chars=s.toCharArray();
        
        while(right<chars.length){
            if(set.add(chars[right])){
                right++;
                res=Math.max(res,set.size());
            }else{
                // 删除至可以添加right处元素
                set.remove(chars[left]);
                left++;
            }
            
        }
        return res;

    }
}

解法二：map

使用map缓存每个字符及其对应位置，相同字符时根据删除最近字符的下标确定窗口大小

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res=0;
        HashMap<Character,Integer> map=new HashMap<>();
        // -1是当字符串字符均不相同的情况
        int left=-1;
        char[] data=s.toCharArray();
        for(int i=0;i<data.length;i++){
            
            if(map.containsKey(data[i])){
                // 最近相同字符的下标，要删掉其前面的
                left=Math.max(left,map.get(data[i]));
            }
            res=Math.max(res,i-left);
            // 包含了覆盖的情况
            map.put(data[i],i);
            
            
        }
        return res;

    }
}