美文网首页
2020-02-14 刷题 2(字符串)

2020-02-14 刷题 2(字符串)

作者: nowherespyfly | 来源:发表于2020-02-14 12:39 被阅读0次

38 外观数列

简单粗暴,效果也不太好

time: 18.22%, memory: 5.05%
class Solution {
public:
    string countAndSay(int n) {
        string cur_array = "1";
        while(--n){
            string tmp = "";
            char c = cur_array[0];
            int cnt = 1;
            for(int i = 1; i < cur_array.size(); i++){
                if(cur_array[i] == c){
                    cnt++;
                }
                else{
                    tmp = tmp + to_string(cnt);
                    tmp = tmp + c;
                    c = cur_array[i];
                    cnt = 1;
                }
            } 
            tmp = tmp + to_string(cnt);
            tmp = tmp + c;
            cur_array = tmp;
        }
        return cur_array;
    }
};

14 最长公共子前缀

还是最简单的做法,以第一个字符串作为初始前缀,逐个比较得到公共子前缀。做了一步优化,先选出最短的字符串作为初始前缀,然后再比较,能从20ms优化到16ms。如果能先根据字符串长度做一下排序,可能会更快。
代码:

time: 7.31%, memory: 5.02%
class Solution {
public:
    string get_prefix(string s1, string s2){
        int i = 0, j = 0;
        string prefix = "";
        while(i < s1.size() && j < s2.size() && s1[i] == s2[j]){
            prefix = prefix + s1[i];
            i++;
            j++;
        }
        return prefix;
    }
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0) return "";
        int min_len = strs[0].size(), idx = 0;
        for(int i = 1; i < strs.size(); i++){
            if(strs[i].size() < min_len) {
                min_len = strs[i].size();
                idx = i;
            }
        }
        string pre = strs[idx];
        for(int i = 0; i < strs.size(); i++){
            if(i == idx) continue;
            pre = get_prefix(pre, strs[i]);
            if(pre == "") break;
        }
        return pre;
    }
};

相关文章

  • 2020-02-14 刷题 2(字符串)

    38 外观数列 简单粗暴,效果也不太好 14 最长公共子前缀 还是最简单的做法,以第一个字符串作为初始前缀,逐个比...

  • Leetcode刷题总结(2):字符串问题

    38 题意 这道题的题面很有趣:生成一个这样的序列:1:"1"2:"11"(1个1)3:"21"(2个1)4:"1...

  • Manacher's Algorithm 的理解

    在 leetcode 刷题刷到求字符串的最长回文字串,而马拉车算法(Manacher's Algorithm), ...

  • java刷题-2

    总结 多线程控制并发顺序问题,线程之间通信问题AtomicIntegerlock wait + notifyAll...

  • PTA刷题总结-Part 3 数据结构与算法

    PTA刷题总结-Part 1 基础部分PTA刷题总结-Part 2 模拟与数学问题PTA刷题总结-Part 3 数...

  • PTA刷题总结-Part 2 模拟与数学问题

    PTA刷题总结-Part 1 基础部分PTA刷题总结-Part 2 模拟与数学问题PTA刷题总结-Part 3 数...

  • leecode刷题(16)-- 字符串转换整数

    leecode刷题(16)-- 字符串转换整数 字符串转换整数 描述: 请你来实现一个 atoi 函数,使其能将字...

  • 2021-03-03

    SQL刷题 1:向学生表里添加数据 2:简单的查询 引申内容:正则 ^匹配输入字符串的开始位置。如果设置了 Reg...

  • leecode刷题(11)-- 反转字符串

    leecode刷题(11)-- 反转字符串 反转字符串 描述: 编写一个函数,其作用是将输入的字符串反转过来。 示...

  • 刷题刷题

    时间紧迫,任务繁重,又有疫情影响,搞的人心惶惶,一时间复习得不安宁,又舍不得摆烂。 在焦灼、惶恐的情绪中,紧张急迫...

网友评论

      本文标题:2020-02-14 刷题 2(字符串)

      本文链接:https://www.haomeiwen.com/subject/ahedfhtx.html