leetcode_01_part
liduoan.efls Engineer
  2020-04-26 13:50:58 2020-04-26 13:50   2020-05-02 00:21:38    2.8k 字  12 分钟  

2020.04.26

23. 合并K个排序链表

难度困难610

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

正常对两个链表排序

下图是我以前写的基本算法训练

然后递归就是了，所以最差版本就是下面了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	//这里就是标准的两个链表进行有序化为一个链表
    ListNode* sortLists(ListNode* l1,ListNode * l2)
    {
        ListNode * head = new ListNode(0);
        ListNode * pre = head;
        while(l1!=NULL&&l2!=NULL)
        {
            if(l1->val > l2->val){
                pre->next=l2;
                pre=l2;
                l2=l2->next;
            }
            else{
                pre->next=l1;
                pre=l1;
                l1=l1->next;
            }
        }
        if(l1==NULL){
            pre->next=l2;
        }
        else{
            pre->next=l1;
        }
        return head->next;
    }


    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //这里如果输入为空
        if(lists.size()==0)
            return NULL;
        
        ListNode* res=lists[0];
        for(int i=1;i<lists.size();i++){
            res = sortLists(res, lists[i]);
        }
        return res;
    }
};

很明显的做法不是吗？

然而有更好的做法，

优化-1

分治合并

复习下分治算法：

把一个难以解决的问题分解成规模较小的相似问题，分而治之。

子问题要求分割到最小最小！

那么我们分析下 可以看成 合并两个最链表 这两个链表又可以分成四个小链表，以此类推….

好的，那么我们大致思路为： 先把链表分割 然后从最小链表开始合并 自底向上，逐渐到最顶层。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	//核心合并两个链表
    ListNode* sortLists(ListNode* l1,ListNode * l2)
    {
        ListNode * head = new ListNode(0);
        ListNode * pre = head;
        while(l1!=NULL&&l2!=NULL)
        {
            if(l1->val > l2->val){
                pre->next=l2;
                pre=l2;
                l2=l2->next;
            }
            else{
                pre->next=l1;
                pre=l1;
                l1=l1->next;
            }
        }
        if(l1==NULL){
            pre->next=l2;
        }
        else{
            pre->next=l1;
        }
        return head->next;
    }
	//分割的函数 在内部存在合并  分治法要求在最小子问题出
    //再向顶前进
    ListNode * spitList(vector<ListNode*>& lists,int left,int right){
        if(left==right)
            return lists[left];
        if(left>right)
            return NULL;
        int mid = (left+right)/2;
        return sortLists(spitList(lists,left,mid),spitList(lists,mid+1,right));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0)
            return NULL;
        return spitList(lists,0,lists.size()-1);
    }
};

还有一种利用优先队列的方法。这里就不说了。【还是太菜

2020.04.28

I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

1
2
3
4
5
6
7
8
示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

分析：

知识点： 异或 按位与运算

首先我们先回忆一下 异或运算( ^ ) 和按位与运算( & )的规则

异或：相同为0 不同为1

按位与：有0为0 全1为1

异或和加法

异或和按位与

附上两篇关于异或和按位与的文章

具体说说这个

我们首先知道，如何解决下面这个问题

如果除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？

可以全体异或，最终得到的值就是这个数字。仔细体会下异或就明白了。相同为0

而0任意异或都为其本身。

那么我们这里有两个不同的数字。可以分割成两个上述的问题。那么关键在于如何准确分割？

首先我们全体异或 得到的是最终两个不同数字的异或值。那么我们拿取这个异或值的某一个不为0的位。把这个位和这两个数字按位与，最终得到的是分割开的。

比如说： 最终异或： 0111 而 两个不一样的数字 1和6 其位为：0001 0110

那么我们利用最终异或的最后一个1来进行判断 就是0001 依次和

0001 0110 相互按位与 前者是1 后者是0 所以就分开啦。这样我们就可以分成两组来全异或。

所以代码就顺势写出来了。

理一遍思路

1、全部异或得到两个不同数字的异或值

2、取这个异或值的不为0的最低位

3、重新遍历 依次按位与分割

4、分割的途中对每一个异或 得到最终解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int ret=0;
        for(int n: nums){
            ret ^=n;
        }
        int div = 1;
        //把我们异或的最终结果 拿出不为0的位出来
        while((div&ret)==0)  //有0为0 全1为1
        {
            div<<=1;
        }
        int a = 0;
        int b = 0;
        for(int n:nums){
            if(div&n){
                a^=n;
            }
            else{
                b^=n;
            }
        }
        return vector<int>{a,b};


    }
};

2020.04.29

1095. 山脉数组中查找目标值

（这是一个 交互式问题 ）

给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。

如果不存在这样的下标 index，就请返回 -1。

何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：

首先，A.length >= 3

其次，在 0 < i < A.length - 1 条件下，存在 i 使得：

A[0] < A[1] < … A[i-1] < A[i]
A[i] > A[i+1] > … > A[A.length - 1]

你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：

MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始）
MountainArray.length() - 会返回该数组的长度

注意：

对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。

为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：https://leetcode-cn.com/playground/RKhe3ave，请注意这 不是一个正确答案。

示例 1：

输入：array = [1,2,3,4,5,3,1], target = 3
输出：2
解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。
示例 2：

输入：array = [0,1,2,4,2,1], target = 3
输出：-1
解释：3 在数组中没有出现，返回 -1。

提示：

3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9
通过次数10,429提交次数28,914

分析：

很明显，这应该是我们先进行二分，在进行两个二分最终得到最终答案

注意到，二分算法的时间复杂度是O(log n)

下面是二分查找的一个详细的博文:

二分查找

1. 分析二分查找代码时，不要出现 else，全部展开成 else if 方便理解。

2. 注意「搜索区间」和 while 的终止条件，如果存在漏掉的元素，记得在最后检查。

3. 如需要搜索左右边界，只要在 nums[mid] == target 时做修改即可。搜索右侧时需要减一。

就算遇到其他的二分查找变形，运用这几点技巧，也能保证你写出正确的代码。LeetCode Explore 中有二分查找的专项练习，其中提供了三种不同的代码模板，现在你再去看看，很容易就知道这几个模板的实现原理了。

下面说下具体想法：

首先我们二分查找到整个山脉数组的最大值——利用二分查找

我们得到这个最大值的时候，就可以把这个山脉数组分割成两个数组

一个是递增数组 一个是递减数组

我们依次在两个数组中进行二分查找

emmm基础前备知识已经有了，那么代码就来了

代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int l = 0; int r = mountainArr.length()-1;
        while(l<r){//这里确定《= 意味着是在空区间的时候出循环
            //我想找出最大值，最好是
            int mid = ( l+ r)/2;
            //如果我取等 会在这里卡住
            if(mountainArr.get(mid)>mountainArr.get(mid+1)){
                r=mid;
            }else{
                l = mid +1;
            }
        }
        int div = l;
        int xl=mountainArr.get(l);
        if(xl<mountainArr.get(l+1)){
            div=l+1;
        }
        if(mountainArr.get(div-1)>xl){
            div = div -1;
        }
        //获得峰值
        //开始两个二分
        int res =  getTheValue(target,mountainArr,0,div);
        if(res != -1){
            return res;
        }
        res = getOtherValue(target,mountainArr,div+1,mountainArr.length()-1);
        if(res != -1){
            return res;
        }
        return -1;



    }
	//这里是递增二分查找
    int getTheValue(int target, MountainArray &mountainArr,int left, int right){
            
            while(left<=right){//注意
                int mid = (left+right)/2;
                int value = mountainArr.get(mid);
                if(value==target)
                    return mid;
                else if(value>target){
                    right = mid -1;
                }
                else if(value<target){
                    left = mid +1;
                }
            }
            return -1;
    }
    //这里是递减二分查找
    int getOtherValue(int target, MountainArray &mountainArr,int left, int right){
            
            while(left<=right){
                int mid = (left+right)/2;
                int value = mountainArr.get(mid);
                if(value==target)
                    return mid;
                else if(value>target){
                    left = mid + 1;
                }
                else if(value<target){
                    right = mid - 1;
                }
            }
            return -1;
    }
};

2020.04.30

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

这道题目 亮点在于找到是否循环

我们知道会有以下三种可能。

  1. 最终会得到 11。
  2. 最终会进入循环。
  3. 值会越来越大，最后接近无穷大。

最后一种不会出现，因为 在全部拆解平方和之后，会把数字下降。

所以就是看循环啦。怎么判断进入循环呢？

利用快慢指针！！

快的比慢的每次多走一步。

记住反正如果是1的话，最后快指针会停下来。慢指针会追上来。

而循环的话，快指针总会追上慢指针的，只是时间的问题而已。

这里的环是数值的环形链。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    //得到各个数平方和
    int getNext(int n){
        int sum = 0;
        while(n){
            int t = n%10;
            t*=t;
            sum+=t;
            n=n/10;
        }
        return sum; 
    }
	
    bool isHappy(int n) {
        int slow = n;
        int fast = n;
        //开始移动
        do{
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }while(slow != fast);
        return slow == 1;
    }
};
  • 本文标题：leetcode_01_part
  • 本文作者：liduoan.efls
  • 创建时间：2020-04-26 13:50:58
  • 本文链接：2020/04/26/Leetcode_每日一题/leetcode-01-week/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
  1. 1. 2020.04.26
    1. 1.1. 23. 合并K个排序链表
      1. 1.1.1. 优化-1
  2. 2. 2020.04.28
    1. 2.0.1. I. 数组中数字出现的次数
  • 3. 2020.04.29
    1. 3.0.1. 1095. 山脉数组中查找目标值
      1. 3.0.1.1. 二分查找
      2. 3.0.1.2. 代码如下
  • 4. 2020.04.30
    1. 4.0.1. 202. 快乐数
      1. 4.0.1.1. 利用快慢指针！！