每天进步一点点

0%

LeetCode每日一题(updating)

发表于 更新于 分类于 阅读次数： ℃ Valine：
本文字数： 7.8k 阅读时长 ≈ 13 分钟

每日一刷，每日一结

五月每日一题

5.09 母亲节，制作m束花所需要的最少天数

这一题主要是先对题目做一个概览性的分析：

  • 1、只要花的数量小于总数，必然无返回，只要花的数量大于或等于总数，则必然有结果

  • 2、存在那么一个days，当大于days必然有连续数组满足，小于days必然不满足，是一个关于days的递增函数，我们就是要找到这个突变点

  • 关于days满不满足，这就是判断不超过days限定条件的最多长度为k的连续子数组的数量

下面给出代码分析：

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
class Solution {
public:
    bool checkDays(vector<int> bloomDay,int days,int m,int k)
    {
        //先定义花的捆数，以及每捆花初始花朵数
        int kun=0;
        int flowers=0;
        int length=bloomDay.size();
        //遍历整个数组,以不超过天数为界线，然后去找连续子数组的长度，实时更新长度与比较长度。
        for(int i=0;i<length&&kun<m;i++)
        {
            if(bloomDay[i]<=days)
            {
                flowers++;
                if(flowers==k)
                {
                    kun++;
                    flowers=0;
                }
            }
            else flowers=0;
        }
        return kun>=m;
    }
    int minDays(vector<int>& bloomDay, int m, int k) {
        int length=bloomDay.size();
        //花的数目本来就不够
        if(m*k>length) return -1;
        //找到开放天数的最大值
        int largestday=0;
        for(int i=0;i<length;i++)
        {
            if(bloomDay[i]>=largestday) largestday=bloomDay[i];
        }
        int left=1;
        int right=largestday;
        while(left<right)
        {
            int days=(left+right)/2;
            if(checkDays(bloomDay,days,m,k)) right=days;
            else left=days+1;
        }
        return left;
    }
};

05.10 二叉树的叶子的遍历：叶子相似的树

给定两棵二叉树，首先通过递归方法遍历得到叶子节点，然后比较两颗树的叶子节点是否完全一样

  • 首先定义两个vector对叶子节点进行存储
  • 然后写一个dfs进行二叉树叶子节点遍历存储
    • 1、注意通过引用进行vector的地址传递‘
    • 2、如果为空，结束标志
    • 3、否则如果左右孩子均为空，则说明为叶子，放入vector
    • 4、用dfs继续操作左右孩子
  • 判断两个vector是否相同

给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void dfs(TreeNode* root,vector<int> &temp)//一定要进行引用传递
    {
        //root为空，结束标志
        if(root==nullptr) return ;
        //左右孩子均为空，叶子标志
        if(root->left==nullptr&&root->right==nullptr) temp.push_back(root->val);
        //然后分别对左孩子，右孩子执行相同操作
        dfs(root->left,temp);
        dfs(root->right,temp);
    }
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> temp1;
        vector<int> temp2;
        dfs(root1,temp1);
        dfs(root2,temp2);
        return (temp1==temp2);
    }
};

05.11位操作，根据异或的加密结果求原码值

描述一种加密方式：pre有奇数个元素（元素为1-n），相邻两个异或操作可以得到encoded数组，现在给出encoded数组，需要求出原本的pre数组

  • 这道题目最关键的要点在于：若是知道pre第一个数字，其他的结果可以立刻求得。而pre第一个元素的获取方法比较特殊：由于，pre_all=pre_0异或pre_剩余，pre_all可以知道，pre_剩余可以知道(为encode中所有奇数位上元素的异或)。因此pre_0可以知道。
  • 然后即可通过pre_0和encode求得pre所有元素。

代码如下：

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
class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        //最关键的一点：per的除了第一个元素以外的另外偶数个两两之间操作，即为encoded的奇数项的结果；
        //异或交换定律： per全部元素的异或=   除去per[0]异或结果与per[0]异或结果
        //所以：per[0]=per全部元素异或 与除去per[0]之外元素异或（也是encoded的奇数元素下标项异或结果）
        int n=encoded.size()+1;
        //初始化除去第一个，全部
        int without_first=0;
        int all=0;
        for(int i=1;i<encoded.size();i+=2)
        {
            without_first=without_first^encoded[i];
        }
        for(int i=1;i<=n;i++)
        {
            all=all^i;
        }
        //获得目标数组
        vector<int>per;
        int per_first=without_first^all;
        per.push_back(per_first);
        for(int i=1;i<n;i++)
        {
            per.push_back(per[i-1]^encoded[i-1]);
        }
        return per;
    }
};

05.13停留在原地的方案数目（动态规划大法）

给定步数step，给定移动数组长度len;每次可以选择不动，向左移动一次，向右移动一次，原地保持不动。求最终回到原点的方案数目

  • 刚接触到这道题目，自己感觉应该是动态规划，但是没有想到状态转移方程怎么去写，其实对于这类题目，状态转移方程是比较容易定义的。dp数组定义dp[i] [j] 表示在i步操作到达 j位置的方案数，有了这个定义就可以往下面去一步步推理了。
  • dp[i] [j]中首先将能到达位置范围缩小一下：j的最大值是选择len和step中较小的那一个 int maxcolumm=min( len-1,steps ) 所以dp的定义 vector<vector>dp( steps+1,vector( maxcolumn+1,0];
  • 然后就是初始条件和状态转移矩阵的定义：A：都可以为原地保持不动操作；B：向右走得到；C：向左走得到。
  • 然后就是初始条件

这里给出代码

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
class Solution {
public:
    const int MODULO = 1000000007;

    int numWays(int steps, int arrLen) {
        //能够到达最远的下标数字。len太大了，步数没那么多也是白瞎。
        int maxColumn = min(arrLen - 1, steps);
        vector<vector<int>> dp(steps + 1, vector<int>(maxColumn + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j <= maxColumn; j++) {
                //首先，都可以是原地不动而来。
                dp[i][j] = dp[i - 1][j];
                //j>0，它可以除了原地不动，也可以是从左边向右移动
                if (j - 1 >= 0) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MODULO;
                }
                //j不是最右边下标，那么它除了原地不动和右边移动，也可以是从右边向左边而来
                if (j + 1 <= maxColumn) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MODULO;
                }
            }
        }
        return dp[steps][0];
    }
};

05.14整数转罗马数字（类似一种贪心算法）

  • 这题的关键思路在于能够把罗马数字的所有子序列找出来

  • 所有子序列：

    1
    2
    son_nums[]={1000,900,500,400,100,90,50,40,10,9,5,4,1};
    string son_str[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

  • 然后通过数组的遍历便可以得到

    如果num大于某一个元素，那么就在结果中加上其对应的罗马数字，并且自身减去这个元素，直至不大于这个元素的时候才切换到下一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string intToRoman(int num) {
        //所有子数
        int son_nums[]={1000,900,500,400,100,90,50,40,10,9,5,4,1};
        //所有字数对应的罗马字符
        string son_str[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        string ans;
        //从大到小，如果大于当前，就减去，并且加上一个罗马字符，直至不大于当前，才切换到下一个，直至为零
        for(int i=0;i<13;i++)
        {
            while(num>=son_nums[i])
            {
                num=num-son_nums[i];
                ans+=son_str[i];
            }
        }
        return ans;

    }
};

05.15罗马数字转整数

本题与5.14整数转罗马数字是一类题目，结题思路也基本一致，属于字符串的基本操作，包括字符串选择性擦除，字符串取子串等。

  • 首先，定义所有的子罗马数字情况，从大到小排列，以及这些罗马文字对应的阿拉伯数字
  • 然后通过遍历取解决，遍历的关键在于判断当前字符串s的头部串是否有罗马数组当前i对应的字符串相同。相同就将ans加上对应的阿拉伯数字，然后通过erase进行剔除当前罗马字符串

实践复杂度为O（n），执行超过了100%，内存方面多了两个数组，以及申请了一个temp串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int romanToInt(string s) {
        string son_str[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int son_num[]={1000,900,500,400,100,90,50,40,10,9,5,4,1};
        int ans=0;
        for(int i=0;i<13;i++)
        {
            string temp=s.substr(0,son_str[i].size());
            while(temp==son_str[i])
            {
                ans+=son_num[i];
                s=s.erase(0,son_str[i].size());
                temp=s.substr(0,son_str[i].size());
            }
        }
        return ans;
    }
};

05.20前K个高频单词

给定一个非空单词列表，返回前K个出现次数最多的单词，返回单词出现频率由高到低，相同频率按字母顺序排序

  • 通过使用map,可以统计次数，由于map是按照键进行排序，我们需要对value进行排序。所以引入vector<pair<string,int>>进行对map进行copy，然后通过sort和cmp进行排序，这是本题最为关键的地方。
  • 巧用pair<string,int>。复习map中的first和second不带括号，为啥不带括号，你用ListNode和TreeNode的思维来考虑就可以了，说白了，也就是一种类似于结构体的东西。
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
class Solution {
public:
    static bool cmp(pair<string,int> wordlist1,pair<string,int> wordlist2)
    {
        //注意长度相等的排序
        if(wordlist1.second==wordlist2.second)
        {
            return wordlist1.first<wordlist2.first;
        }
        return wordlist1.second>wordlist2.second;
    }
    vector<string> topKFrequent(vector<string>& words, int k) {
        //引入map，同时，根据map的值进行排序
        map<string,int>wordlist;
        for(auto c:words)
        {
            wordlist[c]++;
        }
        //引入vector<pair<stirng,int>>,执行sort
        vector<pair<string,int>> PairMap;
        for(auto c:wordlist)
        {
            PairMap.push_back(pair<string,int>(c.first,c.second));
        }
        sort(PairMap.begin(),PairMap.end(),cmp);
        vector<string> ans;
        for(int i=0;i<k;i++)
        {
            ans.push_back(PairMap[i].first);
        }
        return ans;
    }
};

05.21不相交的线(动态规划-三叶姐姐教你如何做人)

 刷题的最高境界就是像三叶这样的大佬，能够将本题立刻联想到动态规划系列经典题目最长递增子序列。此题满足动态规划类型的特征：

  1. 两个数组（字符串）类型，然后是求最值。dp数组dp[i] [j]也比较容易理解，表示前一个数组的前i个元素，和后一个数组前j个元素所能连线的最大值。
  2. 动态规划最关键的状态转移：首先dp数组初始化均为0,然后就是第如果末尾相同，直接连在一起，那肯定是都不连的最大值加一；如果末尾不相同，那肯定是取二者退一个中较大的那个。

 动态规划的特征：动态规划就是一种典型的穷举思想，这是计算机最擅长的事情，而且你要求最值，那我就从最初状态的最值，通过题目条件一步步的去靠近你那个最终状态的最值，靠近的法则就是准确地描述状态转移方程。

 动态规划要素：状态矩阵，初始化，状态转移循环矩阵，状态转移条件，最终值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        const int lengtha=text1.size();
        const int lengthb=text2.size();
        //状态转移矩阵，一般求最大值初始化为0，求最小值初始化为取不到结果的最大值
        vector<vector<int>>dp(lengtha+1,vector<int>(lengthb+1,0));
        //穷举过程，状态转移矩阵。
        for(int i=1;i<=lengtha;i++)
        {
            for(int j=1;j<=lengthb;j++)
            {
                //这是一个自底向上的方法
                if(text1[i-1]==text2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[lengtha][lengthb];
    }
};

**05.26栈栈栈栈栈：反转每对括号间的子串

括号是成对出现的，你要反转没两个括号间的字符串，这题方法比较直接，就是遇到左括号将临时字符串入栈，然后将临时字符串清空。遇到字符就把字符加进来，知道遇到了又括号，此时就要翻转临时字符串，同时将栈顶部的元素加上反转后的临时字符串，然后将栈顶部元素pop出去。

总结起来就是：定义一个临时栈和字符串，遇到左括号就全部入栈，并清空，非括号创建字符串，右括号翻转然后将栈顶串加到子串。

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:
    string reverseParentheses(string s) {
        //巧用栈，遇到左括号就入栈
        string temp;
        stack<string> st;
       for(auto &c:s)
       {
           if(c=='('){
               st.push(temp);
               temp="";
           } 
           else if(c==')') {
               reverse(temp.begin(),temp.end());
               //注意加的顺序，栈顶元素在前
               temp=st.top()+temp;
               st.pop();
           }
           else{
               temp+=c;
           }
       }
       return temp;
    }
};

本文标题:LeetCode每日一题(updating)

文章作者:Decaprio Lee

发布时间:2021年05月09日 - 10:05

最后更新:2021年05月29日 - 16:05

原始链接:http://yoursite.com/2021/05/09/033Leetcode%E6%AF%8F%E6%97%A5%E4%B8%80%E9%A2%98/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

赞赏一杯咖啡
-------------------本文结束 感谢您的阅读-------------------