Sitch's Blog
0%

发表于 分类于 Valine：

(合并区间 || 插入区间)[https://leetcode-cn.com/problems/merge-intervals]

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

题目分析

合并区间

  1. [a,b] [c,d]合并条件：b=c && a<=d 此时区间存在重复区段，可以合并
  2. 由于原区间序列是乱序，你合并了前两个，产生合并结果temp，但你不知道temp还可以和后续的什么合并，所以又需要遍历一遍，不现实。
  3. 因此我们先按区间左边界进行排序，这样temp只需要考虑是否还要合并紧挨着的下一个即可。 ### 插入区间
  4. 首先需要找到插入位置，即左边界 介于 前一个和后一个的左边界 中间。
  5. 插入之后的收尾工作 插入时会不会和前一个发生和合并？ 因为是按左边界顺序，因此往前只可能合并一个 但是不知道新区间的右边界延伸到了哪里，因此对后续区间都要检查一遍是否需要合并

题解代码

合并区间

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
class Solution {
public:
    vector<vector<int merge(vector<vector<int& intervals) 
    {
        vector<vector<int result;
        int Len=intervals.size();
        if(Len==0)
            return result;
        
        sort(intervals.begin(),intervals.end(),cmp);
        result.push_back(intervals[0]);

        int i=1;
        while(i<Len)
        {    //可连接 [1,3] [2,4]
            if(intervals[i][0]<=result.back()[1])
                if(intervals[i][1]result.back()[1])
                    result.back()[1]=intervals[i][1];
                else;
            else//不可连接 
                result.push_back(intervals[i]);
            i++;
        }

        return result;
    }

    static bool cmp(vector<int& a,vector<int& b)
    {
        return a[0]<b[0];
    }

    
};

插入区间

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
class Solution {
public:
    vector<vector<int insert(vector<vector<int& intervals, vector<int& newInterval) 
    {
        int i=0;
        int Len=intervals.size();
        bool IsInsert=false;
        vector<vector<int result;
        while(i<Len)
        {   //找到插入的位置
            if(intervals[i][1]<newInterval[0])
                i++;
            else
                break;
        }

        if(i==Len)//插在末尾之后
        {
            intervals.push_back(newInterval);
            return intervals;
        }

        for(int j=0;j<i;j++)//无需检查的项直接插入
            result.push_back(intervals[j]);

        if(intervals[i][0]<=newInterval[1])//可以合并
        {
            intervals[i][0]=min(intervals[i][0],newInterval[0]);
            intervals[i][1]=max(intervals[i][1],newInterval[1]);
            result.push_back(intervals[i]);
            i++;
        }
        else//插入 而不是合并
            result.push_back(newInterval);

        while(i<Len)
        {
            //插入项往后 每一项都要检查是否要往前合并,直到不用合并
            if(intervals[i][0]<=result.back()[1])
            {
                if(result.back()[1]<intervals[i][1])
                    result.back()[1]=intervals[i][1];
            }
            else
                break;
            
            i++;
        }
        //出来的i往后是无法合并的项
        while(i<Len)
        {
            result.push_back(intervals[i]);
            i++;
        }


        return result;




    }
};

发表于 分类于 Valine：

第K个排列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123" "132" "213" "231" "312" "321" 给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。 给定 k 的范围是[1,  n!]。

示例 1:

输入: n = 3, k = 3 输出: "213"

示例 2:

输入: n = 4, k = 9 输出: "2314"

题目分析

  1. 我一开始想到的是全排列的函数的复用，我能找到全排列难道我找不到第k个排列？但我发现全排列那里并没有按序排列，因此不可复用..

  2. 可以复用 下一个排列 的函数，毕竟一直找找到第K个就好，效率较低，没尝试。

  3. 数学计算。全排列每个位置的每个数其实是有数学特征的。比如对 1 2 3

    3.1 首位情况： 肯定先是1在首位两次，然后是2首位2次，然后是3首位两次。

    3.2 次位情况：除掉首位数字，剩下的数字在nums[]中，同样也是先nums[0]作为次位，出现 尾部排列次数 次，然后是nums[1]...依次类推。

    综上：即我们知道每位的次数情况，比如 1 2 3中，我们要找第5个排列，因为首位1在前两个， 首位2 在3 4 个，因此 第5个排列必然是首位3。 再看次位，第5个排列，除去 1 2 首位的四个，我们要找的是3首位的第一个，依次类推即可。 即我们可以直接计算出每一位应该是什么数字。然后组成result即可。

  4. 细节

    4.1 当前位 每个数字出现次数，由尾部的全排列次数决定，而全排列是n！，因此最好能预置个阶乘结果数组。

    4.2 k/fac[n-1] 向上取整得i，此时该位应该是 nums里的第i个数（下标i-1），同时对nums删除这个数。

    4.3 n==1 时，nums只剩一个数，直接连上并返回。

题解代码

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
class Solution {
public:
    string getPermutation(int n, int k) 
    {   
        //题解数组
        const vector<int fac = {0,1,2,6,24,120,720,5040,40320,362880,3628800};
        string result(n,'0');
        string nums(n,'0');
        for(int i=0;i<n;i++)
            nums[i]='1'+i;
        
        for(int i=0;n0;i++)
        {   
            int a;
            int left=0;
            if(n=2) //计算每个首位有多少个排列,跳过这些排列
            {   
                left=fac[n-1];
                a=k/left;
                if(k%left!=0)
                    a++;
                result[i]=nums[a-1];
                k-=(a-1)*left;
                nums.erase(a-1,1);
                n--;

            }
            else //只剩一个数,直接修改返回
            {
                result[i]=nums[0];
                return result;   
            }

        }
        return result;
    }
 
    
};

发表于 分类于 Valine：

旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1-2-3-4-5-NULL, k = 2 输出: 4-5-1-2-3-NULL 解释: 向右旋转 1 步: 5-1-2-3-4-NULL 向右旋转 2 步: 4-5-1-2-3-NULL

示例 2:

输入: 0-1-2-NULL, k = 4 输出: 2-0-1-NULL 解释: 向右旋转 1 步: 2-0-1-NULL 向右旋转 2 步: 1-2-0-NULL 向右旋转 3 步: 0-1-2-NULL 向右旋转 4 步: 2-0-1-NULL

题目分析

1. 直观移位——每个节点向右移动K位

遍历每个节点，都后向计算出该位置的新节点，即向左找K位，然后赋值过来。思路很简单。 （前向计算也是可以的，甚至更利于想出优化的第二步） ##### 注意细节：一个是移动出了链头，要转到链尾继续移动。 ##### 然而链表头并没有指向链尾的指针，因此怎么从链头转到链尾呢？ 一个很傻的方法是把链表数值做成vector...然后在vector中找相应的数值，然后赋给当前位置... 很傻，浪费空间时间= = ##### 2. 我们的目标是从链头转到链尾，然而链头唯一的跳转指针next又必须连着链表，所以不太好修改头指针。但是链尾的next是空的，我们是不是可以利于一下呢？ 再看前向计算，每个节点向右移动K位，找到正确位置然后赋值，问题也在于怎么从链尾转移到链头。 ##### 3. 因此我们可以把链尾连向链头，即tail-next=head，此时找位置的问题就不存在了，可以开开心心对每个节点遍历。 ##### 4. 遍历移动完想想，移完虽然AC了，但好像憨憨的？链表顺序还是原来的样子，对链尾连着链头的循环链表来讲，移完看起来只不过是head从原节点，往前走了几步，然后停了下来选了一个新位置当head。 例如 1-2-3-4-5，k=2 遍历移动==》4-5-1-2-3，即head往前走了K步，停在了4的位置，然后以4为链头往后即是新链表。 ##### 5. 因此我们不需要遍历移动每个节点，首先我们找到链尾，然后知道链尾往前K个（包括链尾本身）即是新head，找到新head时，把head前一个的next置为NULL，断开循环链表即是所需链表。 当然，我们在链尾的时候同样不能往前走，因此往前找K个即相当于往后找L-K+1个（不包括链尾）。 你可能会想既然是从链尾向后找L-K+1个，那不是相当于从最初的head过去找L-K个吗？

但是没有先遍历到链尾，把链尾链头连接起来的话，我们是没有循环链表的，即使一开始从head找出新head，我们还是得再遍历到链尾，连上链头，再把新链头和新链尾断开= = 当然直接从head开始找，可以沿途把新链尾和原链头都存储下来，然后遍历到链尾的时候，该连的连该断的断即可= =。

题解代码

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) 
    {
        ListNode* i=head;
        int L=0;
        if(head==NULL)
            return head;
        
        while(i-next!=NULL)//找链尾
        {

            i=i-next;
            L++;
        }
        L++;

        i-next=head;//首尾相连
        //缩小k
        k%=L;
        int j=0;
        //从末尾起移动L-k到达 i , i-next是新头
        k=L-k;

        while(j<k)
        {
            i=i-next;
            j++;
        }

        head=i-next;
        i-next=NULL;

       

       return head;
    }
};

发表于 分类于 Valine：

有效数字

验证给定的字符串是否可以解释为十进制数字。

例如:

"0" = true " 0.1 " = true "abc" = false "1 a" = false "2e10" = true " -90e3   " = true " 1e" = false "e3" = false " 6e-1" = true " 99e2.5 " = false "53.5e93" = true " --6 " = false "-+3" = false "95a54e53" = false

说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。这里给出一份可能存在于有效十进制数字中的字符列表：

数字 0-9 指数 - "e" 正/负号 - "+"/"-" 小数点 - "." 当然，在输入中，这些字符的上下文也很重要。

题目分析

  1. 这题我感觉是一种代码实现问题，考查考虑问题是否全面？ 没有什么特别的算法思想，想清楚判定数字的流程，然后一路判断下来即可。但是要实现你原计划的流程，还是要好好打理一下自己的代码。

  2. 字符特征 ： 2.1 可能包含”0~9“，”e“，”.“，“+”，“-”，” “。 2.2 ”e” 允许出现的次数？还要考虑“e”后是否允许出现”." ， ”+“，”-“？是否允许作为开头结尾？前面是否一定要有数字？ 2.3 “." 允许出现的次数？ ”." 后是否允许出现 “e" , "+ " ,"- "？是否允许作为开头结尾 ？前面是否一定要有数字？ 2.4 ”+“ ，”-“，最多出现两次，一次在幂，一次在指数，且一定位于其他符号之前，且不能作为结尾 2.5 ”0~9“ ，”0“是否允许在幂 或者 指数 或者 小数部分 的首部，是否允许”0“结尾的小数部分。 2.6 ” “，只能作为开头结尾。 2.7 整个数，必须要有数字出现。

  3. 判断流程 3.1 数前空格清除 3.2 首位判断+ - 号，然后进入幂部分/整数部分 3.3 正常判断数字，遇到 ”." 进入小数部分，“e” 进入指数部分，其余false。 3.4.1 小数部分，标记小数点已经用过，不能再出现，其余照常。 3.4.2 指数部分，检查e前是否有数字，”+“ ”-“可以再用，重置”+-“的标志位，小数点不能用了，小数点标志位置false，当然e也不能再用了。继续照常检查数字。 3.5 检查到” “，” “只能作为末尾出现，因此直接跳出主体循环，进入尾部判断环节。 3.6 数的结尾检查，不能是”e", "+ " "-" ，但可以是“ . ”。 3.7尾部清洗，一路检查是否是“ ”，遇到个不是的则false。 3.8 检查全部通过，但它也要有数字才可能是数！return HasNum；

题解代码

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
83
84
85
86
87
88
89
class Solution {
public:
    bool isNumber(string s) 
    {   //0开头结尾 true
        //多个e  false
        //e左右两边要有数 
        //指数不能为小数
        int i=0;
        bool UsedSign=false;
        bool UsedCom=false;
        bool UsedExp=false;
        bool HasNum=false;
        //首部空格清除
        while(i<s.size())
        {
            if(s[i]!=' ')
                break;
            i++;
        }

        //首位判断符号位
        if(i<s.size() && (s[i]=='+' || s[i]=='-') )//符号
        {
            UsedSign=true;
            i++;
        }



        //主体判断
        for(;i<s.size();i++)
        {
            if(s[i]='0' && s[i]<='9')
            {   
                HasNum=true;
                continue;
            }
            else if(s[i]=='+' || s[i]=='-')//主要用来判断指数的符号
            {
                if(UsedSign==false && s[i-1]=='e')
                {
                    UsedSign=true;
                    continue;
                }
                else
                    return false;
            }
            else if(s[i]=='.')//小数点
            {
                if(UsedCom==false)
                {
                    UsedCom=true;
                    continue;
                }
                else
                    return false;
            }
            else if(s[i]=='e')//指数符号
            {
                if(UsedExp==false && HasNum==true) //e前需有数字
                {
                    UsedExp=true;
                    UsedSign=false;//重置符号状态位,指数也可以带符号
                    UsedCom=true;//指数不能是小数
                    continue;
                    
                }
                else
                    return false;
            }
            else if(s[i]==' ') //尾部空格
                break;
            else
                return false;
        }

        if(s[i-1]=='e' ||s[i-1]=='+' || s[i-1]=='-')//e + -结尾 不行
            return false;

        while(i<s.size())//尾部空格清除
        {
            if(s[i]!=' ')
                return false;
            i++;
        }

        return HasNum;
    }
};

发表于 分类于 Valine：

文本左右对齐

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

单词是指由非空格字符组成的字符序列。 每个单词的长度大于 0，小于等于 maxWidth。 输入单词数组 words 至少包含一个单词。 示例:

输入: words = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth = 16 输出: [    "This    is    an",    "example  of text",    "justification.  "] 示例 2:

输入: words = ["What","must","be","acknowledgment","shall","be"] maxWidth = 16 输出: [   "What   must   be",   "acknowledgment  ",   "shall be        "] 解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be",   因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。 示例 3:

输入: words = ["Science","is","what","we","understand","well","enough","to","explain",   "to","a","computer.","Art","is","everything","else","we","do"] maxWidth = 20 输出: [   "Science  is  what we", "understand      well",   "enough to explain to",   "a  computer.  Art is",   "everything  else  we",   "do                  "]

题目分析

  1. 也是没有突出思路的困难题....考验代码实现细节的功底。 #### 进入每行一轮的循环：
  2. 计算每行能最多放多少个单词，贪心尝试，能放多少放多少= = 2.1 注意每个单词后面要留个位置给空格 2.2 同时记得保存个末行标志位，以便后续末行特殊处理 2.3 这里用到了两个指针，一个指向起始单词，一个探索结束单词
  3. 计算每行的所需空格数，用vector存储每空应该有多少个空格，注意空格多了先在左边填，因此可以实现类似个抽屉原理，先把能平均分的部分分了，然后多的从前往后填。 3.1 注意最后一个单词后面没有空格，计算每空空格数时可以先排除它，前面的空格全分完了，在vector后面push_back(0)即可 3.2 注意该行一个单词的时候需要特殊处理，把所有空格都填在vector[0]即可。
  4. 末行特殊处理，末行单词间空格数固定为1，最后一个单词之后的空格数为所有剩余空格。
  5. 循环填入单词，填一个单词+vector[i]数量的空格。
  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
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
class Solution {
public:
    vector<string fullJustify(vector<string& words, int maxWidth) 
    {
        vector<string  result;
        int wordsFlag=0;//处理到的最远的单词
        int StartFlag=0;
        int SpaceNum=0;
        int wordsNum=0;//每行单词数
        int CurrentLength=0;
        bool isLast=false;
        vector<int spaces;//存储每行每处的空格数
        while(wordsFlag<words.size())//行循环
        {   
            StartFlag=wordsFlag;
            wordsNum=0;
            CurrentLength=0;
            while(CurrentLength<maxWidth)//判断一行最多能放几个单词
            {   
                CurrentLength+=words[wordsFlag].size();
                
                if(CurrentLength+wordsNummaxWidth)//超过了 退掉最后一次
                {
                    CurrentLength-=words[wordsFlag].size();
                    // wordsFlag--; wordsFlag 停在下一行第一个
                    break;
                }
                wordsNum++;
                wordsFlag++;

                //末行判定
                if(wordsFlag=words.size())
                {
                    isLast=true;
                    break;
                }
            }

            //计算所需空格数
            SpaceNum=maxWidth-CurrentLength;
            
            if(wordsNum1)//1判断，wordsNum-1=0时不能当除数
            {
                 spaces= vector<int(wordsNum-1,SpaceNum/(wordsNum-1));//space有wordsNum-1处，每处平均有SpaceNum/(wordsNum-1)个
					for (int j = 0; j < SpaceNum%(wordsNum-1); ++j)//多的从前往后填，填多少是多少，保证左边的空格大于等于右边的
                        spaces[j] += 1;
                spaces.push_back(0);//最后一个数不要空格
            }
            else
                spaces= vector<int(1,SpaceNum);

            //末行处理
            if(isLast==true && wordsNum1)
            {
                int j= 0;
                for (; j <wordsNum-1; j++)
                    spaces[j]=1;//末行每处空都只有一个空格，最后是剩余空格，也是服了= =
                spaces[j]=SpaceNum-(wordsNum-1);//剩余空格
            }
                    
            string temp;
            int j=0;
            while(StartFlag<wordsFlag)
            {   
                //填充单词
                temp+=words[StartFlag];//填词
                //填充空格
                for(int i=0;i<spaces[j];i++)//填空格
                    temp.push_back(' ');
                StartFlag++;
                j++;
            }

            result.push_back(temp);

        }

        return result;
    }
};