Leetcode刷题笔记

先给自己定个小目标吧,今年8月份前至少完成Leetcode Top100题目中的一半(大概),不过刷题笔记真的好花时间……今年上半年的压力真的点大啊,都在为工作做准备,也许可以换个词,为了我们的未来(希望那个她能够看到😋)。

上半年主要目标:技术、算法、健身、CET4。

进度:Leetcode刷题笔记 1(这坑怕是填不上了,还在准备面试)

目标这东西肯定就需要一个进度条了,然后发现了一个好玩的进度条项目progressed.io,本想直接用的,结果发现这项目已经归档,尴尬,只好在自己的服务器上部署了(后面改为调用API)。

1. 两数之和 easy

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

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力法

Leetcode刷题笔记 2

其实从题目意思,很容易就想到暴力法来解决,遍历数组的每一个元素x,检查数组中元素x后的所有元素的值是否与target - x相等(无需检查元素x前的元素,因为在之前的遍历中已经检查),相等则取出两者的坐标。

时间复杂度:O(n^2)
空间复杂度:O(1)

//@Date: 2020年02月15日
class Solution {
    public int[] twoSum(int[] nums, int target) {
        //遍历每个元素
        for(int i = 0;i < nums.length;i ++) {
            //遍历当前元素后的每一个元素
            for(int j = i + 1;j < nums.length;j++) {
                if(target - nums[i] == nums[j]) {
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }
}

哈希表

Leetcode刷题笔记 3

在暴力法中,数组被遍历了多次,导致每个元素x的查找时间为O(n),显然,我们可以通过hash表降低查找时间到O(1)。数组的中的每一个元素x,都对应着一个补数target - x,对数组元素建立hash表<target - x,索引>,在建立的同时进行查表,即可快速得出索引值。

时间复杂度:O(n)
空间复杂度:O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0;i < nums.length;i++) {
            //建立hash表的同时查hash表
            //如果key存在,即当前元素为 target - x
            if(map.containsKey(nums[i])) {
                return new int[] {map.get(nums[i]), i};
            }
            map.put(target - nums[i],i);
        }
        return null;
    }
}

数组法

Leetcode刷题笔记 4

建立hash表带来了时间开销,可以新建一个数组,索引为元素值x,数组存储元素x的索引。

但数组需要注意开辟连续内存空间的大小问题,相对而言,hash表适用范围更广,更有生产力。

时间复杂度:O(n)
空间复杂度:O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int max = 2047;
        int[] temp = new int[max+1];
        for(int i=0;i < nums.length;i++){
            int diff = target-nums[i];
            int pos = temp[diff&max];
            if(pos!=0){
                return new int[]{pos-1,i};
            }
            //存储元素索引
            temp[nums[i]&max] = i+1;
        }
        return null;
    }  
}

2. 两数相加 middle

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

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

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

简单加法

Leetcode刷题笔记 5

整道题而言,其实就是个简单的链表相加问题,通过遍历两个链表,将对应的节点相加,结果存储到新的链表中即可。需要注意两个点:

  1. 进位
  2. 最后一位相加后判断是否要进位

时间复杂度:O(max(m,n)),取两个链表最长值
空间复杂度:O(max(m,n)),如果有进位,则为O(max(m,n)) + 1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//@Date: 2020年02月18日
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode result = head;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int a = (l1 != null) ? l1.val : 0;
            int b = (l2 != null) ? l2.val : 0;
            int sum = a + b + carry;
            result.next = new ListNode(sum % 10);
            carry = sum / 10;
            if(l1!=null){
                l1 = l1.next;
            }
            if(l2!=null){
                l2 = l2.next;
            }
            result = result.next;
        }
        //处理最后一位的进位问题
        if (carry > 0) {
            result.next = new ListNode(carry);
        }
        return head.next;
    }
}

优化后

Leetcode刷题笔记 6

对上面的代码观察发现,反复new ListNode对象带来了大量的时间以及空间开销。

如何优化?

  1. 直接使用l1链表存储计算结果
  2. 当两个链表不等长时,处理进位后直接将长链表的余下部分接到l1链表(MAX = l2时)
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode temp = head;
        int carry = 0;
        while(true) {
            //下面两个判断处理链表不等长的情况
            if (l1 == null) {
                //getLast()函数处理进位问题
                temp.next = getLast(l2, carry);
                break;
            }
            else if (l2 == null) {
                temp.next = getLast(l1, carry);
                break;
            }
            else {
                int num = l1.val + l2.val + carry;
                temp.next = l1;
                temp = l1;
                temp.val = num % 10;
                carry = num / 10;
                l1 = l1.next;
                l2 = l2.next;
            }
        }
        return head.next;
    }
    //处理进位函数
    public ListNode getLast(ListNode nodes, int carry) {
        ListNode temp = nodes;
        if (carry > 0) {
            while(temp != null) {
                //当val<9时,无需再处理进位,直接退出循环
                if (temp.val < 9) {
                    temp.val += carry;
                    carry = 0;
                    break;
                }
                //val = 9 的情况
                temp.val = 0;
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
        }
        //处理最后一位进位
        if (carry > 0) {
            if (temp != null) {
                temp.next = new ListNode(carry);
            }        
            else {
                return new ListNode(carry);
            }
        }
        return nodes;
    }
}

4 条评论

发表评论

*

      • 文儿啊,我好想吧架子搭的差不多了,然后发现你已经把友链加好了呢,真是快呢

        • 哈哈,之前去你博客看了下就加上了,最近忙着搞报告,好几个,通信专业太多破事了啊(我们开学了😂)