栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode笔记01

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode笔记01

  1. 两数之和(Easy)
问题:

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]
思路:

这道题想要解出来很简单, 循环暴力破解就行, 但是想要使算法复杂度小, 就要去换个方法了, 这里使用哈希表(HashMap)这个数据结构, 特点是键不可重复。

我们遍历数组的时候, 将target - nums[i]当作key(这样只需要看后面有没有等于这个key的, 有的话我们就可以直接找到, 不用像之前那样那两个数的和取进行对比, 相当于拿着答案去找有没有), 将索引i作为value存入map, 下次进入循环时, 先看map里的keys有没有num[i], 有的话直接返回结果。

示例:
public int[] twoSum(int[] nums, int target) {
    int[] indexs = new int[2];
    HashMap map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (map.containsKey(num)) {
            indexs[0] = map.get(num);
            indexs[1] = i;
            return indexs;
        }
        map.put(target - num, i);
    }
    return indexs;
}
2. 两数相加(Medium) 问题:

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例 1:

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

示例 2:

输入:l1 = [0], l2 = [0]
输出:[0]

示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]
思路:

这道题是一道中等难度的题, 思路并不是很难, 就是中间有一些细节需要注意:

  1. 使用临时变量来保存参数, 方便操作
  2. 由于最后要返回头节点, 所以对于我们要返回的result也进行"备份"(这里的备份并不是真正的备份, 如果p = result, 其实p和result是一样的, 他们指向同一个地址), 后面队p操作不管到了那个next, reslut都还是头节点
  3. 两数相加可能会大于10, 大于10就要取余, 并且把多出来的进给下一位
  4. 当两个链表都遍历完时, 也不能忘记查看是否有进位, 有进位需要把进位给到下个节点再结束
示例:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode p1 = l1, p2 = l2;
    ListNode result = new ListNode(0);
    ListNode p = result;
    int extra = 0;
    while (p1 != null || p2 != null || extra > 0) {
        int val = extra;
        if (p1 != null) {
            val += p1.val;
            p1 = p1.next;
        }
        if (p2 != null) {
            val += p2.val;
            p2 = p2.next;
        }
        p.next = new ListNode(val % 10);
        extra = val / 10;
        p = p.next;
    }
    return result.next;
}
3. 无重复字符的最长字串(Medium) 问题:

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,
"pwke" 是一个子序列,不是子串。
思路:

这是一个典型的滑动窗口问题, 我推荐大家去看labuladong大佬的文章, 讲的十分清晰, 我就简单复述一下:

使用左右双指针, 右指针先滑动, 当条件达到window need shrink时, 左指针开始滑动, 当达到目标结果时, 保存结果, 以便最后进行对比, 找出最优结果。

int left = 0, right = 0;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

单就这道题而言, 右指针不断滑动增大窗口, 当发现重复值后, 左指针滑动缩小窗口, 期间将窗口内没有重复值的结果不断记录更新其最大值。

示例:
// 这里先给一个比较清晰的示例
public int lengthOfLongestSubstring(String s) {
    if (s.length() <= 1) {
        return s.length();
    }
    HashMap window = new HashMap<>();
    int res = 0;
    int left = 0, right = 0;
    while (right < s.length()) {
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        right++;
        while (window.get(c) > 1) {
            char d = s.charAt(left);
            window.replace(d, window.get(d) - 1);
            left++;
        }
        res = res > right - left ? res : right - left;
    }
    return res;
}
// 再来一个刷记录的

public int lengthOfLongestSubstring(String s) {
    if (s.length() <= 1) {
        return s.length();
    }
    int res = 0;
    int low = 0;
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        for (int j = low; j < i; j++) {
            if (chars[i] == chars[j]) {
                low = j + 1;
                break;
            }
        }
        res = res > (i - low + 1) ? res : (i - low + 1);
    }
    return res;
}
4. 寻找两个正序数组的中位数(Hard) 问题:

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
思路:

对于一道Hard题而言, 我的思路属实不值一提, 这里给大家简述一下力扣评论区一位大佬的思路, 感谢Wait想念大佬:

  1. 对于两个数组而言, 我们分别找第 (m+n+1) / 2 个, 和 (m+n+2) / 2 个, 然后求其平均值即可, 这对奇偶数均适用。
  2. 定义一个函数, 这个函数的目的就是找到第K位元素, 函数的具体实现思路如下:
  3. 对于边界值而言, 如果起始值大于等于数组长度, 说明此数组已经没有我们要找的数了, 看作是空数组, 直接在另一个数组中找到第k位数进行返回, 而如果k=1, 说明两个数组的起始位置的数最小的那个就是我们要的(为什么是最小的呢? 两个数那个最小, 那个就是第一个嘛)。
  4. 对于一般情况来说, 我们对两个数组都去找第k/2位元素, 但是如果有一个数组没有k/2个元素, 那么说明这个数组目前是影响不到结果的, 直接对另一个数组进行剪枝(减去k/2个元素, 也就是使数组的起始位置加k/2), 并递归进入下一轮寻找; 如果都有第k/2个元素, 那么比较两个数组的第k/2个元素的大小, 对小的数组剪枝(因为第k/2个元素小的数组的前k/2个元素是肯定比中位数小的), 并继续递归。
  5. 每次剪枝完进入下一次的时候, 此时的数组已经减去了k/2个比中位数小的元素, 那么现在我们要找的就不是第K个元素了, 而是第k-k/2个元素
示例:
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    int left = (m + n + 1) / 2;
    int right = (m + n + 2) / 2;
    return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2;
}

// 找到第K个元素
public double findKth(int[] nums1, int i, int[] nums2, int j, int k) {
    
    if (i >= nums1.length) {
        return nums2[j + k - 1];
    }
    if (j >= nums2.length) {
        return nums1[i + k - 1];
    }

    
    if (k == 1) {
        return Math.min(nums1[i], nums2[j]);
    }

    
    int midNum1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
    int midNum2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;

    
    if (midNum1 < midNum2) {
        return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
    } else {
        return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
    }
}

我的个人主页: www.ayu.link
本文连接: [┏ (゜ω゜)=☞]

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/980948.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号