算法题（一）

本文最后更新于：2021年3月11日 晚上

概览：LeetCode刷题。

697 数组的度

标签：哈希表，最值，计数。

给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

1
2
>输入：[1, 2, 2, 3, 1]
>输出：2

解释：
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.

1
2
>输入：[1,2,2,3,1,4,2]
>输出：6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/degree-of-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的本能思路就是使用map进行计数，然后双重循环来找到对应的最短连续子数组。

果不其然，这种操作超出时间限制。

点击查看/关闭初始思路代码 
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
    #include <iostream>
    #include <vector>
    #include <map>
    #include <algorithm>
    using namespace std;

~~~c++
/*
思路：先找到数组的度，即出现频数最大的那个数
找寻频率最大：map映射可以，遍历vector，将所有值插入计数找到出现频率最大的数的次数degree。
找寻最小数组：以一定的度提取一个小数组，找到其的gegree是否与要找的相同，度的范围为 degree到数组长度，
*/

int findMaxDegree(vector<int>& nums) {
    map<int, int> maps;
    for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++) {
        pair<map<int, int>::iterator, bool> pairs = maps.insert(make_pair(*it, 1));
        if (pairs.second == false) {
            //如果插入失败
            maps[*it]++;//计数+1
        }
    }

    //找到最大的value
    int max = 0;
    map<int, int>::iterator maxit;
    for (map<int, int>::iterator mit = maps.begin(); mit != maps.end(); mit++) {
        if (mit->second > max) {
            max = mit->second;
            maxit = mit;
        }
    }
    return max;
}

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {

        int maxDegree = findMaxDegree(nums);

        //确定连续的子序列中是否
        if (maxDegree == 1) return 1;
        else {
            //找到拥有相同大小的度的最短连续子数组，返回其长度
            for (int i = maxDegree; i <= nums.size(); i++) {	//i表示每次要找的子串长度
                //从maxDegree开始，往后找，然后+1往后找 
                for (int j = 0; j < nums.size()-i+1; j++) {

                    //构造vector
                    vector<int> subVector;
                    subVector.clear();
                    for (int k = 0; k < i; k++) {
                        subVector.push_back(nums[j+k]);
                    }
                    //找到当前子序列之中的度
                    int subDegree = findMaxDegree(subVector);
                    if (subDegree == maxDegree)
                        return subVector.size();
                }
            }
        }
    }
};

int main() {

    vector<int> v = { 1,2,2,3,1,4,2 };

    Solution s;
    cout<<"值："<<s.findShortestSubArray(v);

    return 0;
}

~~~

大神思路

链接：https://leetcode-cn.com/problems/degree-of-an-array/solution/xiang-xi-fen-xi-ti-yi-yu-si-lu-jian-ji-d-nvdy/

1.先求原数组的度，即统计各个元素的出现次数，使用哈希表（unordered_map）来进行计数。
2.求与原数组相同度的最短子数组，那么这个子数组也应当有n个重复的元素。

所以，要求的最短子数组应当是由出现次数最多的元素 其第一次和最后一次的位置来进行确定。

而当出现次数最多的元素不止一个时，都要对其进行处理，找到它们中最小的。

unordered_map底层是哈希表，它的查找速度比较快。

点击查看/关闭代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, int> left, right, counter;//第一次出现，最后一次出现，出现次数
        int degree = 0;//度
        for (int i = 0; i < nums.size(); i++) {
            if (left.count(nums[i]) == 0) {//若没有这个元素
                left[nums[i]] = i;//插入元素及其位置
            }
            right[nums[i]] = i;//map的数组插入方式可以覆盖
            counter[nums[i]]++;//计数
            degree = max(degree,counter[nums[i]]);
        }

        int res = nums.size();	//长度
        for (auto& kv : counter) {
            if (kv.second == degree) {//若出现次数等于度
                //选择最小的那个长度
                res = min(res,right[kv.first]-left[kv.first]+1);
            }
        }
        return res;
    }
};

1438 绝对差不超过限制的最长连续子数组

标签：

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

输入：nums = [8,2,4,7], limit = 4
输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此，满足题意的最长子数组的长度为 2 。

输入：nums = [10,1,2,4,7,2], limit = 5
输出：4
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。

输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3

1 <= nums.length <= 10^5

1 <= nums[i] <= 10^9

0 <= limit <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

字节教育一面 三十六进制数相加

标签：数组下标，字符串处理

36进制由0-9，a-z，共36个字符表示，最小为’0’, ‘0’、’9’对应十进制的09，‘a’、’z’对应十进制的1035

例如：

‘1b’ 换算成10进制等于 1 * 36^1 + 11 * 36^0 = 36 + 11 = 47

要求按照加法规则计算出任意两个36进制正整数的和

如：按照加法规则，计算’1b’ + ‘2x’ = ‘48’

点击查看/关闭代码 
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
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string allchar = "0123456789abcdefghijkLmnopqrstuvwxyz";

string add36(string first, string second) {

    //计算长度，找到短的那段，然后翻转字符串，相加
    //使得段的字符串为 first，长的为second
    int firstlen = first.size();
    int secondlen = second.size();

    int len = 0;

    if (firstlen <= secondlen) {
        len = firstlen;
    }
    else {
        len = secondlen;
        string temp = first;
        first = second;
        second = temp;
    }

    //翻转字符串
    reverse(first.begin(),first.end());
    reverse(second.begin(),second.end());

    string result = "";
    int A, B, C = 0;//c为进位

    for (int i = 0; i < len; i++) {
        //读取两个字母位置
        A = allchar.find(first[i]);
        B = allchar.find(second[i]);

        //与进位相加,对 36求除数和余数
        result.push_back(allchar[(A+B+C)%36]);
        C = allchar.find(allchar[(A+B+C)/36]);
    }

    //之后对于较长的字符串，逐步插入
    for (int i = len; i < second.size(); i++) {
        B = allchar.find(second[i]);
        result.push_back(allchar[(B + C) % 36]);
        C = allchar.find(allchar[(B + C) / 36]);
    }

    //若最后的进位不是0，则也要添加
    if (C != 0) {
        result.push_back(allchar[C]);
    }

    //最后字符串进行翻转
    reverse(result.begin(),result.end());

    return result;
}

int main() {


    string a, b;
    cin >> a;
    cin >> b;

    string result = add36(a, b);

    cout << a << " + " << b << " = " << result << endl;

    return 0;
}

1 两数之和

标签：哈希表，便利

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：暴力遍历

同一个数字不能够使用两遍，且可以按照任意顺序返回答案。
则只需要遍历即可，大循环从第一个元素开始，小循环，从大循环的下一个开始，找到位置就停止

时间复杂度 O(n^2) 。

点击查看/关闭代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i+1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return {i,j};
                }
            }
        }
        return {};
    }
};

思路2：使用哈希表

哈希表的查找非常的迅捷，可在O(1)的时间内完成，不再需要像上面那样循环遍历查找。

建立哈希表，值——索引的映射关系。

循环遍历nums，然后查找哈希表内是否有target - nums[i]这个数据，若有返回两个数的索引，若没有，将当前元素插入哈希表。

对于重复的元素，若是恰好是最终结果，那么第二个重复的数据不会插入到哈希表中就停止了，如果不是最终结果，只需要保留一个即可。

点击查看/关闭代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;	//unordered_map底层是哈希表

        for (int i = 0; i < nums.size(); i++) {
            if (hashtable.count(target - nums[i]) > 0) {//count计数，或者使用find，未找到元素就指向end()
                return { hashtable[target - nums[i]],i };
            }
            else {
                hashtable.insert(make_pair(nums[i],i));
            }
        }
        return {};
    }
};

2 两数相加

标签：链表

相似：三十六进制数相加

2021/03/03

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

点击查看/关闭代码 
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* result = new ListNode();//默认构造一个单链表

        //非空链表至少可以相加一次，借此来初始化

        int val = (l1->val + l2->val) % 10;//结果
        int C = (l1->val + l2->val) / 10;  //进位

        result->val = val;
        l1 = l1->next;
        l2 = l2->next;

        ListNode * result1 = result;//暂存头节点

        //之后逐个相加
        while(l1 != nullptr && l2 != nullptr){
            val = (l1->val + l2->val + C) % 10;
            C = (l1->val + l2->val + C) / 10;
            l1 = l1->next;
            l2 = l2->next;

            //插入结果的单链表，尾插法
            result->next = new ListNode(val);
            result = result->next;//指向下一个节点
        }

        //当某一端结束
        while(l1 != nullptr){
            val = (l1->val + C) % 10;
            C = (l1->val + C) / 10;
            l1 = l1->next;

            //插入结果的单链表，尾插法
            result->next = new ListNode(val);
            result = result->next;//指向下一个节点
        }

        while(l2 != nullptr){
            val = (l2->val + C) % 10;
            C = (l2->val + C) / 10;
            l2 = l2->next;

            //插入结果的单链表，尾插法
            result->next = new ListNode(val);
            result = result->next;//指向下一个节点
        }

        //以及进位不为零的时候
        if(C != 0){
            //插入结果的单链表，尾插法
            result->next = new ListNode(C);
            result = result->next;//指向下一个节点
        }

        //返回即可
        return result1;
    }
};

其他：

  • result->next = new ListNode(val);习惯这种写法，来简化。
  • 对于没有头节点的链表，也可以尝试第一个节点值置为无意义的数，然后最后返回头节点的下一个return result->next。

3 无重复字符的最长子串

标签：字符串，滑动窗口

2021/03/03

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

思路1：滑动窗口

对于字符串abcabcbb

先abc
–> abca | len=3
–> 截去重复的字母，bca | len = 3
–> bcab –> cab | len=3
–> cabc –> abc |len=3
–> abcb –> cb | len=2
–> cbb –> b | len=1
–> 结束

即当不满足时，将队列左边的元素移除即可（滑动窗口）。一直维持这样的序列，获取序列的最大长度。

用哪个数据结构存储逐个字符？
要求：1.可以查出重复 2.保存时原序，并且方便裁剪，截取

点击查看/关闭代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = 0;//长度
        string sub="";//子串
        for (int i = 0; i < s.size(); i++) {

            int find_result = sub.find(s[i]);
            if (find_result == sub.npos) {//没找到，则插入， npos string特殊的一个变量
                sub.push_back(s[i]);
            }
            else {
                //找到了，说明出现了重复元素，清除对应位置上的子串
                sub.replace(0,find_result+1,"");//将从首字符串到重复位置的那个字符串替换为“”.
                //然后添加那个字符
                sub.push_back(s[i]);
            }
            len = max(len, int(sub.size()));//记录最大长度
        }
        return len;
    }
};

4 寻找两个正序数组的中位数

标签：

2021/03/04

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

输入：nums1 = [], nums2 = [1]
输出：1.00000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：合并数组 o(m+n)

点击查看/关闭初始思路代码 
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
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        vector<int> result;

        int size1 = nums1.size();
        int size2 = nums2.size();
        result.reserve(size1+size2);//预留空间

        int i=0, j=0;

        while (i<size1 && j<size2) {
            if (nums1[i] > nums2[j]) {
                result.push_back(nums2[j]);
                j++;
            }
            else {
                result.push_back(nums1[i]);
                i++;
            }
        }

        //某一方长度耗尽
        while (i < size1) {
            result.push_back(nums1[i]);
            i++;
        }

        while (j < size2) {
            result.push_back(nums2[j]);
            j++;
        }

        int size = result.size();

        if (size == 0) return 0.0;
        else if (size % 2 == 1) return result[size/2]/1.0;
        else return (result[size / 2 - 1] + result[size / 2])/2.0;
    }
};

思路2：

5 最长回文子串

2021/03/05

给你一个字符串 s，找到 s 中最长的回文子串。

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

输入：s = “a”
输出：”a”

输入：s = “ac”
输出：”a”

https://leetcode-cn.com/problems/longest-palindromic-substring/

思路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
class Solution {
public:
	string longestPalindrome(string s) {
		//substr(pos,n);可以返回从pos开始的长度为n的子串
		int len = s.size();

		int beginpos = 0;	//开始位置
		int maxsublen = 1;		//子串长度

		for (int i = 0; i < len; i++) {
			for (int j = i+1; j < len; j++) {
				string str = s.substr(i, j - i + 1);
				if (j-i+1 > maxsublen && str == string(str.rbegin(),str.rend())) {//若是回文串
					beginpos = i;
					maxsublen = j - i + 1;
				}
			}
		}
		return s.substr(beginpos, maxsublen);
	}
};

int main() {

    string s = "babad";
    string s1 = "asdfghjkllkjhgfdsa";
    string s2 = "cddb";
    string s3 = "a";
    string s4 = "ac";
    string s5 = "anugnxshgonmqydttcvmtsoaprxnhpmpovdolbidqiyqubirkvhwppcdyeouvgedccipsvnobrccbndzjdbgxkzdbcjsjjovnhpnbkurxqfupiprpbiwqdnwaqvjbqoaqzkqgdxkfczdkznqxvupdmnyiidqpnbvgjraszbvvztpapxmomnghfaywkzlrupvjpcvascgvstqmvuveiiixjmdofdwyvhgkydrnfuojhzulhobyhtsxmcovwmamjwljioevhafdlpjpmqstguqhrhvsdvinphejfbdvrvabthpyyphyqharjvzriosrdnwmaxtgriivdqlmugtagvsoylqfwhjpmjxcysfujdvcqovxabjdbvyvembfpahvyoybdhweikcgnzrdqlzusgoobysfmlzifwjzlazuepimhbgkrfimmemhayxeqxynewcnynmgyjcwrpqnayvxoebgyjusppfpsfeonfwnbsdonucaipoafavmlrrlplnnbsaghbawooabsjndqnvruuwvllpvvhuepmqtprgktnwxmflmmbifbbsfthbeafseqrgwnwjxkkcqgbucwusjdipxuekanzwimuizqynaxrvicyzjhulqjshtsqswehnozehmbsdmacciflcgsrlyhjukpvosptmsjfteoimtewkrivdllqiotvtrubgkfcacvgqzxjmhmmqlikrtfrurltgtcreafcgisjpvasiwmhcofqkcteudgjoqqmtucnwcocsoiqtfuoazxdayricnmwcg";

    Solution so;
    cout << so.longestPalindrome(s) << endl;
    cout << so.longestPalindrome(s1) << endl;
    cout << so.longestPalindrome(s2) << endl;
    cout << so.longestPalindrome(s3) << endl;
    cout << so.longestPalindrome(s4) << endl;
    cout << so.longestPalindrome(s5) << endl;

    return 0;
}
  • 不出所料，时间超限。

思路2：动态规划

参考题解：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/

「状态转移方程」是原始问题的不同规模的子问题的联系。即大问题的最优解如何由小问题的最优解得到。

回文有一个特性，去除首尾字符后仍然是回文（回文长度>= 2）。

则当前这个字符串是否是回文取决于

  1. 首尾字符是否相同
  2. 去除首位字符的子串是否是回文。

状态转移方程：s[i..j] == (s[i] == s[j] && s[i+1 .. j-1])。

  • s[i..j]表示从i到j下标所组成的字符串。

  • s[i+1 .. j-1] 是 s[i .. j]的子问题。

整体思路：

  • 若s[i] != s[j] 则s[i .. j]不是回文

  • 若s[i] == s[j] 则s[i .. j]就看s[i+1 .. j-1]是不是回文

  • 边界条件：s[i+1 .. j-1]不再构成区间的时候 (j-1) - (i+1) + 1 < 2时 –>j-i < 3时

    • 若只剩下一个字符，则一定是回文
    • 若为空，也一定是回文。
    • 即j-i<3时，无论如何都是回文。

所以需要一个二维数组来记录s[i..j]是不是回文，在循环遍历中要小心顺序。

eg: babad这个字符串，顺序是ba、bab、baba、babad。

  • baba查询时，分别查询下标(i,j)–>(0,3)、(1,3)、(2,3)三个子串是不是回文
  • j从1开始至4结束，i从0开始，至j结束。
纵j|横i 0 1 2 3
1|a ba不是
2|b (0,2) bab是 (1,2)ab不是
3|a (0,3)baba不是 (1,3)aba是 (2,3)ba不是
4|d (0,4)babad不是 (1,4)abad不是 。。 。。

图源上述思路的链接。

点击查看/关闭代码 
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
class Solution {
public:
    string longestPalindrome(string s) {

        int len = s.size();

        int beginpos = 0;	//开始位置
        int maxlen = 1;		//长度

        //bool dp[len][len] = { 0 };不能这样用，老生常谈的问题。
        //二维数组，初始化了初始长度为10，元素都是vector<int>(len)的vector
        vector<vector<int> >dp(len,vector<int>(len));

        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;//长为1的一定是回文
        }

        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (s[i] != s[j]) {
                    dp[i][j] == 0;
                }
                else {//s[i] == s[j]
                    if (j - i < 3) {	//即(j-1)-(i+1)+1 < 2，到达边界
                        dp[i][j] = 1;
                    }
                    else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                if (dp[i][j] == 1 && (j - i + 1 > maxlen)) {
                    maxlen = j - i + 1;
                    beginpos = i;
                }
            }
        }

        return s.substr(beginpos, maxlen);
    }
};
  • 时间复杂度O(n^2)
  • 空间复杂度O(n^2)。

思路3：中心扩散法

遍历每一个索引，以这个索引为中心，利用回文串的中心对称特点，向两端扩散。

当然要分奇数串偶数串的情况：

  • 奇数串：以一个字符为中心；
  • 偶数串：以两个字符之间的空隙为中心。

中心扩散时这两种情况都应该考虑到。

可以使用一个函数来设置不同的参数达到这样的效果。

点击查看/关闭代码 
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 Solution2 {
private:
    string findcenter(string s, int left,int right) {

        int i = left;
        int j = right;

        while (i >= 0 && j < s.size()) {
            if (s[i] == s[j]) {
                i--;
                j++;
            }
            else break;
        }
        return s.substr(i+1,j-i-1);//注意这里
    }

public:
    string longestPalindrome(string s) {

        string substr = string(1,s[0]);
        int maxlen = 1;

        for (int i = 0; i < s.size()-1; i++) {
            string str1 = findcenter(s,i,i);//奇数
            string str2 = findcenter(s,i,i+1);//偶数

            if (str1.size() < str2.size()) {
                str1 = str2;
            }
            if (maxlen < str1.size()) {
                substr = str1;
                maxlen = substr.size();
            }
        }

        return substr;
    }
};
  • 时间复杂度O(n^2)。
  • 空间复杂度O(1)。

234 回文链表

标签：快慢指针

2020/03/08

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list/

思路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
class Solution {
public:
    bool isPalindrome(ListNode* head) {

        //压栈
        stack<int> sta;
        ListNode * tail = head;
        while (tail != nullptr) {
            sta.push(tail->val);
            tail = tail->next;
        }

        int len = sta.size();

        for (int i = 0; i < len / 2; i++) {
            int temp = sta.top();

            if (head->val == temp) {
                sta.pop();
                head = head->next;
            }
            else {
                return false;
            }

        }
        return true;
    }
};

思路2：递归

首先看一段如何逆序输出单链表的代码：

1
2
3
4
5
6
void PrintListReverse(ListNode *next) {
	if (next == nullptr)
		return;
	PrintListReverse(next->next);
	cout << next->val << " ";
}

这段代码太秀了：

点击查看/关闭代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        temp = head;
        return check(head);
    }

private:
    ListNode *temp;
    bool check(ListNode* head) {
        if (head == nullptr)
            return true;
        bool res = check(head->next) && (temp->val == head->val);
        temp = temp->next;
        return res;
    }
};

链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/di-gui-zhan-deng-3chong-jie-jue-fang-shi-zui-hao-d/

思路3：快慢指针

快指针与慢指针向后推进，然后翻转链表 进行对比。

  • 由于链表分奇数链表和偶数链表，长度不同，需要对比的区域也不相同，需做特殊处理。
  • 翻转链表时由于结构体的限制，需要巧用头插法。
点击查看/关闭代码 
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
class Solution {
public:
    bool isPalindrome(ListNode* head) {

        if (head == nullptr || head->next == nullptr)
            return true;

        ListNode * slow = head;
        ListNode * fast = head;

        //快指针的移动
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        //奇数链表时，只取除中轴之外需要对比的部分
        if (fast != nullptr) {
            slow = slow->next;
        }

        //翻转后半部分链表
        ListNode * rehalf = reverse(slow,fast);

        //进行对比
        while (rehalf != nullptr) {
            if (head->val == rehalf->val) {
                head = head->next;
                rehalf = rehalf->next;
            }
            else {
                return false;
            }
        }
        return true;

    }
private:
    ListNode *temp = nullptr;//临时,每次保存头部信息
    ListNode* reverse(ListNode* head, ListNode* end) {

        temp = nullptr;//每次清空

        if (head == end)//若只有一个元素
            return head;

        while (head != nullptr) {//传入的是后半部分的字符串，结束标志就是Nullptr
            ListNode *re = new ListNode(head->val);
            re->next = temp;
            temp = re;

            head = head->next;
        }

        //由于leetcode的链表结构限制
        //头插法不方便
        //逻辑：使用一个temp来保存上一次链表保存的结果，然后使得新建的节点next指向temp，这样就完成了头插法

        return temp;
    }
};

232 用两个栈实现队列

2021/03/11

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

普通思路

栈对于一个序列可以有翻转的功能，123经过入栈出栈之后就变成了321，同样再翻转一次也就可回复原位。

点击查看/关闭代码 
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
class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        if (sta_post.empty() == true) {
            //后栈为空，直接入后栈
            sta_post.push(x);
        }
        else {
            //后栈不空时，先逐个倒入前栈
            while(!sta_post.empty()) {
                sta_pre.push(sta_post.top());
                sta_post.pop();
            }
            //新元素入前栈
            sta_pre.push(x);
            //前栈全部压入后栈
            while (!sta_pre.empty()) {
                sta_post.push(sta_pre.top());
                sta_pre.pop();
            }
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int element = sta_post.top();
        sta_post.pop();
        return element;
    }

    /** Get the front element. */
    int peek() {
        return sta_post.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return sta_post.empty();
    }

private:
    stack<int> sta_pre;
    stack<int> sta_post;
};

优化思路

每次pop、push均是一个元素。每一个栈均可暂存这个元素。

所以对于push这个操作，无需像上述那样，每次翻转post栈的数据。

仅在需要用到的时候再将pre栈内的数据导入，其他情况均将数据暂存pre栈

  • pop时，且post栈为空
  • peek时，且post栈为空
点击查看/关闭代码 
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
class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        sta_pre.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if (sta_post.empty()) {
            pre2post();
        }

        int element = sta_post.top();
        sta_post.pop();
        return element;
    }

    /** Get the front element. */
    int peek() {
        //这时需将pre栈移动
        if (sta_post.empty()) {
            pre2post();
        }
        return sta_post.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return sta_post.empty() && sta_pre.empty();
    }

private:
    stack<int> sta_pre;
    stack<int> sta_post;
    void pre2post() {//元素移动
        while (!sta_pre.empty()) {
            sta_post.push(sta_pre.top());
            sta_pre.pop();
        }
    }
};

225 用两个队列实现栈

2021/03/11

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-stack-using-queues
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

为了保证后进先出，只能进行交替操作。

若first队列为空，则压栈入该队列，为了保证下一个元素在这个元素之前，下一个元素压入second队列，并将fiest队列的元素依次出队，排列在其后，这样便保证了后进先出。

即一个队列(用于像栈一样)和一个辅助队列(帮助数据颠倒)。

点击查看/关闭代码 
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
class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        if (que_first.empty()) {
            que_first.push(x);

            while (!que_second.empty()) {
                que_first.push(que_second.front());
                que_second.pop();
            }
        }
        else if (que_second.empty()) {
            que_second.push(x);

            while (!que_first.empty()) {
                que_second.push(que_first.front());
                que_first.pop();
            }
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int temp = 0;
        if (!que_first.empty()) {
            temp = que_first.front();
            que_first.pop();
        }
        else if (!que_second.empty()) {
            temp = que_second.front();
            que_second.pop();
        }
        return temp;
    }

    /** Get the top element. */
    int top() {
        int temp = 0;
        if (!que_first.empty()) {
            temp = que_first.front();
        }
        else if (!que_second.empty()) {
            temp = que_second.front();
        }
        return temp;
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que_first.empty() && que_second.empty();
    }

private:
    queue<int> que_first;
    queue<int> que_second;
};
算法
LeetCode

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！