本文为记录自己学习算法的过程

[9]回文数

描述：给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

  • 例如，121 是回文数，而 123 不是

示例1

1
2
输入：x = 121
输出：true

示例2

1
2
3
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例3

1
2
3
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数

提示

  • $-2^{31} <= x <= 2^{31} - 1 $

题解：

方法一

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {//数字小于0不可能是回文数，直接返回false
            return false;
        }
        string s = to_string(x);//将x转化成字符串
        string s1 = s;//接受字符串s，便于后面比对
        reverse(s.begin(), s.end());//翻转字符串
        return s1 == s;//判断翻转前后是否相等
    }
};

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPalindrome(int x) {

        if (x < 0) {//数字小于0直接返回false
            return false;
        }
        int t = x;//记录x便于比对
        double cur = 0;//每次翻转取余更新的数字
        while (x) {
            cur = cur * 10 + x % 10;//取出来的数字乘以10加上x取余得到的数字
            x /= 10;
        }
        return t == cur;
    }
};

LeetCode题解

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:
    bool isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }
};
作者：LeetCode-Solution

解释：

对x整数进行判断，小于0就直接返回false。接下来就是操作大于0的数字了。为了不全部进行翻转，我们其实只要翻转一半即可。假如对数字 12321 进行翻转，由于是奇数个数字，翻转时只要翻转到出现的数字比原来的大就代表翻转了一半。这种意思就是第一次翻转得到的数字是 1232 和 1 ，此时 1<1232 ，继续翻转，得到 12<123 ，继续翻转，123>12，此时翻转结束，由于奇数的数字，最终的那个数字不需要进行比较，所以我们便可以将翻转得到的数字（假设x）x/10，判断与剩下的数字（上述是12）是否相等。对于偶数位个的数字 1221 ，此时只需要直接对数字翻转得到了的数字判断相等即可。

  • 注：翻转结束的条件是原始数字小于等于翻转之后的数字（原始数字在翻转的时候发生了改变的）

[13]罗马数字转整数

描述：罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX +V+II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

1
2
输入: s = "III"
输出: 3

示例 2:

1
2
输入: s = "IV"
输出: 4

示例 3:

1
2
输入: s = "IX"
输出: 9

示例 4:

1
2
3
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

1
2
3
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

  • 1 <= s.length <= 15
  • s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
  • 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
  • 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
  • IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
  • 关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。

题解：

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:
    int romanToInt(string s) {
        int num = 0;
        int length = s.length();//获取s字符串的长度
        for (int i = 0; i < length; i++) {
            //比较当前这个字符和下一个字符的大小，小的就减去当前这个
            //就好比'IV'是-1+5=4  
            if (getnum(s[i]) < getnum(s[i + 1]) && i + 1 < length) {
                num -= getnum(s[i]);  //减去这个字符对应的数字
            } else {
                num += getnum(s[i]);  //加上这个字符对应的数字
            }
        }
        return num;
    }

    //获取字符对应的数字
    int getnum(char x) {
        switch (x) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }
};

解释：

这题我拿到手的思路就是将每个字符转化成数字，但是看了题目的要求发现会存在需要进行减法的操作就好比 IV 是 4 运算的过程就是 -1 + +5 = 4 。所以一开始的思路不能完全执行了。考虑到这我就想着直接进行两层的for循环进行遍历不就可以控制后面的字符与前面的字符进行比较了，但是发现如果这个时间复杂度将会变得十分的高，所以肯定不可以这样做，后面思考下发现可以直接一层循环就可以了呀。接下来就是主要的思路了。

思路：

首先我们需要实现一个函数来将字符转化成数字，任何一层for循环直接比较第 i 个字符和第 i+1 个字符就可以了（这里最需要注意的就是需要判断 i+1 个字符有没有越界了，所以上述加了个 i+1<length ）。通过比较存在在前面的字符小于后面的字符说明当前这个字符需要执行的计算是减法，一次遍历执行完所有的字符就可以了。

LeetCode题解

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 {
private:
    unordered_map<char, int> symbolValues = {
        {'I', 1},
        {'V', 5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000},
    };

public:
    int romanToInt(string s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int value = symbolValues[s[i]];
            if (i < n - 1 && value < symbolValues[s[i + 1]]) {
                ans -= value;
            } else {
                ans += value;
            }
        }
        return ans;
    }
};
作者：LeetCode-Solution

可以看出思路还是一致的

[14]最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

1
2
3
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string longestCommonPrefix(vector <string> &strs) {
        string s = "";//初始化字符串s，需要被返回的字符串
        int minLength = strs[0].length();
        for (int i = 0; i < strs.size(); i++) {//找到最小的字符串的长度
            if (strs[i].length() < minLength) {
                minLength = strs[i].length();
            }
        }
        //外层循环遍历，控制每个字符串遍历的最长距离
        for (int i = 0; i < minLength; i++) {
            char str = strs[0][i];//接收第一个字符串的第i个字符
            for (int j = 0; j < strs.size(); j++) {//遍历每个字符串
                if (strs[j][i] != str) {//一旦有一个字符串的第i个字符与第一个字符串的第i个字符不相等就直接返回s终止遍历
                    return s;//说明此时已经找到最长的公共前缀
                }
            }
            s += strs[0][i];//一次循环的第i个字符都相等，s加上这个字符
        }
        return s;
    }
};

解释：

这道题目给的就是一些类的字符串，然后判断这些字符串中的公共最长字符前缀。最主要的特色是这里指定的是前缀，所以在判断的时候还是比较简单的，接下来就是描述思路了。

思路：

首先我们需要判断出最短的那个字符串出来(不过也可以考虑直接在后面比较的时候一起判断)，然后就是根据这个最短的字符串的长度进行遍历（因为我们需要返回的是公共最长前缀，所以不可能超过最短的那个字符串长度），外层循环控制遍历所有的字符串的第i个元素，内层 for 循环遍历每个字符串。为了判断每个字符串的第 i 个元素是否都是一样的，所以我们需要定义一个 str 来记录第一个字符串的第 i 个元素，在第二层 for 循环里面来判断当前这个字符串的第 i 个字符是否与 str 相等，不相等就可以直接返回字符串 s。当第 i 个字符串都相等就将其加入字符串 s 中，如果都遍历完了，最后就可以直接返回字符串 s。

LeetCode题解

方法一：横向扫描

用 $LCP(S_1…S_n)$ 表示字符串 $S_1…S_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
class Solution {
public:
    string longestCommonPrefix(vector <string> &strs) {
        if (!strs.size()) {
            return "";
        }
        string prefix = strs[0];
        int count = strs.size();
        for (int i = 1; i < count; ++i) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (!prefix.size()) {
                break;
            }
        }
        return prefix;
    }

    string longestCommonPrefix(const string &str1, const string &str2) {
        int length = min(str1.size(), str2.size());
        int index = 0;
        while (index < length && str1[index] == str2[index]) {
            ++index;
        }
        return str1.substr(0, index);
    }
};
作者：LeetCode-Solution

方法二：纵向扫描

方法和我的类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string longestCommonPrefix(vector <string> &strs) {
        if (!strs.size()) {
            return "";
        }
        int length = strs[0].size();
        int count = strs.size();
        for (int i = 0; i < length; ++i) {
            char c = strs[0][i];
            for (int j = 1; j < count; ++j) {
                if (i == strs[j].size() || strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};
作者：LeetCode-Solution

方法三：分治

注意到 LCP 的计算满足结合律，有以下结论：

其中$LCP(S_1…S_n)$是字符串$S_1…S_n$ 的最长公共前缀，$1<k<n$。

基于上述结论，可以使用分治法得到字符串数组中的最长公共前缀。对于问题$LCP(S_i…S_j)$，可以分解成两个子问题$LCP(S_i…S_mid)$与$LCP(S_mid+1…S_j)$其中 $mid=\frac{i+j}{2}$ 。对两个子问题分别求解，然后对两个子问题的解计算最长公共前缀，即为原问题的解。

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
class Solution {
public:
    string longestCommonPrefix(vector <string> &strs) {
        if (!strs.size()) {
            return "";
        } else {
            return longestCommonPrefix(strs, 0, strs.size() - 1);
        }
    }

    string longestCommonPrefix(const vector <string> &strs, int start, int end) {
        if (start == end) {
            return strs[start];
        } else {
            int mid = (start + end) / 2;
            string lcpLeft = longestCommonPrefix(strs, start, mid);
            string lcpRight = longestCommonPrefix(strs, mid + 1, end);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    string commonPrefix(const string &lcpLeft, const string &lcpRight) {
        int minLength = min(lcpLeft.size(), lcpRight.size());
        for (int i = 0; i < minLength; ++i) {
            if (lcpLeft[i] != lcpRight[i]) {
                return lcpLeft.substr(0, i);
            }
        }
        return lcpLeft.substr(0, minLength);
    }
};
作者：LeetCode-Solution

方法四：二分查找

显然，最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。用 minLength 表示字符串数组中的最短字符串的长度，则可以在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值 mid ，判断每个字符串的长度为 mid 的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于 mid，如果不相同则最长公共前缀的长度一定小于 mid ，通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。

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
class Solution {
public:
    string longestCommonPrefix(vector <string> &strs) {
        if (!strs.size()) {
            return "";
        }
        int minLength = min_element(strs.begin(), strs.end(),
                                    [](const string &s, const string &t) { return s.size() < t.size(); })->size();
        int low = 0, high = minLength;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (isCommonPrefix(strs, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return strs[0].substr(0, low);
    }

    bool isCommonPrefix(const vector <string> &strs, int length) {
        string str0 = strs[0].substr(0, length);
        int count = strs.size();
        for (int i = 1; i < count; ++i) {
            string str = strs[i];
            for (int j = 0; j < length; ++j) {
                if (str0[j] != str[j]) {
                    return false;
                }
            }
        }
        return true;
    }
};
作者：LeetCode-Solution

[20]有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。

    示例 1：

1
2
输入：s = "()"
输出：true

示例 2：

1
2
输入：s = "()[]{}"
输出：true

示例 3：

1
2
输入：s = "(]"
输出：false

示例 4：

1
2
输入：s = "([)]"
输出：false

示例 5：

1
2
输入：s = "{[]}"
输出：true

提示：

  • $1 <= s.length <= 10^4$
  • s 仅由括号 '()[]{}' 组成

题解：

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
class Solution {
public:
    bool isValid(string s) {
        if (s.length() <= 1) {//字符串长度小于等于1，一定不合法
            return false;
        }
        stack<char> st;
        for (int i = 0; i < s.length(); i++) {
            if (st.empty() && checkright(s[i])) {//栈不为空并且此时是右括号直接返回false
                return false;
            }
            if (checkleft(s[i])) {//左括号入栈
                st.push(s[i]);
            }
            if (!st.empty() && checkright(s[i])) {//栈不为空并且是右括号
                if (check(st.top(), s[i])) {//栈顶元素和当前括号匹配
                    st.pop();//出栈
                } else {//括号不匹配，返回false
                    return false;
                }
            }
        }
        if (!st.empty()) {
            return false;
        }
        return true;
    }

    //判断左括号
    bool checkleft(char str) {
        if (str == '{' || str == '[' || str == '(') {
            return true;
        }
        return false;
    }

    //判断右括号
    bool checkright(char str) {
        if (str == '}' || str == ']' || str == ')') {
            return true;
        }
        return false;
    }

    //判断左右括号是否匹配
    bool check(char left, char right) {
        if (left == '{' && right == '}') {
            return true;
        }
        if (left == '[' && right == ']') {
            return true;
        }
        if (left == '(' && right == ')') {
            return true;
        }
        return false;
    }
};

思路：

这道题主要考察的就是栈的基本性质和括号的匹配规则吧。只要对左括号和右括号的匹配了解，利用栈的基本操作就可以实现了。接下里就是基本的思路。

首先判断字符串长度，如果长度小于等于1那肯定不合法，直接返回 false 。任何判断是左括号就入栈，是右括号就判断当前这个括号是否与栈顶元素匹配，匹配就出栈，不匹配就可以直接返回 false 了。不过在这里需要注意的是需要判断栈是否为空，只有在栈不为空的情况下才能取栈顶元素，否则会有问题。

LeetCode题解

方法一：栈

判断括号的有效性可以使用「栈」这一数据结构来解决。

我们遍历给定的字符串 ss。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。

当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 ss 无效，返回 False。为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。

在遍历结束后，如果栈中没有左括号，说明我们将字符串 ss 中的所有左括号闭合，返回 True，否则返回 False。

注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 False，省去后续的遍历判断过程。

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:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
                {')', '('},
                {']', '['},
                {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            } else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};
作者：LeetCode-Solution

主要的不同就是利用了哈希表存储了每一种括号

[21]合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

合并两个有序链表

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

1
2
输入：l1 = [], l2 = []
输出：[]

示例 3：

1
2
输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *preHead = new ListNode(-1);

        ListNode *prev = preHead;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {//l1节点的值小于l2的节点的值
                prev->next = l1;//接上l1
                l1 = l1->next;//l1向后移动
            } else {
                prev->next = l2;//接上l2
                l2 = l2->next;//l2向后移动
            }
            prev = prev->next;//指向这个链表的后一个位置，也就是需要返回的链表的最后一个位置
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev->next = l1 == nullptr ? l2 : l1;

        return preHead->next;//返回头节点的后一个
    }
};

思路：

这题主要就是将两个有序非递减链表链表进行合并，所以我们需要将两个链表的每一个元素进行比较，由于比较特殊的是两个链表的元素是非递减的，所以我们需要利用这个特点将两个链表遍历一遍就可以将两个链表进行合并就可以了，下面描述的就是主要的思路。

我们可以建立一个头节点（后面只需要返回头节点的下一个元素就可以），然后同时遍历list1和list2，每次都判断比较当前指向的元素的大小，将小的元素接到 prev 链表后面，需要注意的是，我们需要每次将 prev 指针向后移动，否则就只会接上一个元素。操作完之后由于可能会有某个链表先遍历完了，另一个链表还没有遍历完，我们只需要将剩下的链表接到 prev 后面就可以了（一定只会有有一个链表可能没有遍历完，while判断是只要一个遍历完就出循环）。

LeetCode题解类似就不做介绍了

[26]删除有序数组中的重复项

给你一个升序排列 的数组nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持一致。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么nums 的前k个元素应该保存最终结果。

将最终结果插入 nums 的前 k个位置后返回k 。

不要使用额外的空间，你必须在 原地 修改输入数组并在使用 O(1) 额外空间的条件下完成。

判题标准:

系统会用下面的代码来测试你的题解:

1
2
3
4
5
6
7
8
9
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

  • $0 <= nums.length <= 3 * 10^4$
  • $-10^4 <= nums[i] <= 10^4$
  • nums 已按 升序 排列

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 1) {//nums数组长度小于等于1
            return nums.size();
        }
        int index = 0;//返回的k值
        int i = 1;//指向需要判断的元素
        while (i < nums.size()) {
            if (nums[i] > nums[index]) {//当前指向的元素大于index下标的元素怒
                nums[index + 1] = nums[i];//交换index下标前一个元素
                i++;//向后移动
                index++;//需要返回的长度对应的下标加1
            } else {//否则，只需要移动i指针
                i++;
            }
        }
        return index + 1;//因为是长度所以是下标加1
    }
};

思路：

这题主要就是给你一个数组，然后判断返回数组中不重复的元素，一开始拿到题目那肯定就是直接两层循环来交换元素将不重复的元素放到前面，但是由于本题的特殊性有序，所以我们可以有另外一种想法，直接一层 while 就可以将数组中的元素换位。

主要的思路就是先判断数组的长度，如果小于等于 1，那么就一定不重复，直接返回数组的长度。如果不是长度不是`1，那么我们就可以定义一个 i 指针来判断元素是否重复，定义一个 index 来记录当前不重复的元素到某个位置截至。遍历数组，利用数组是递增有序的特点，我们不需要考虑数组里面的元素是否相等，只要判断 i 指针指向的元素是否大于 index 指针指向的元素，如果大于就将 index 指向的下一个元素的值设置成 i 指针指向的值，i 指针向后移动和 index 指针向后移动。将 index 指针后一个赋值的意思就是我们发现了一个新的可以返回的元素，所以我们需要将其放到前面去，不交换是因为后面的元素我们完全不需要保留，所以直接赋值。如果小于等于 index 指向的元素的值，我们就直接移动i指针就可以了。

LeetCode题解

方法一：双指针

这道题目的要求是：对给定的有序数组 nums 删除重复元素，在删除重复元素之后，每个元素只出现一次，并返回新的长度，上述操作必须通过原地修改数组的方法，使用 O(1) 的空间复杂度完成。

由于给定的数组 nums 是有序的，因此对于任意 i<j，如果nums[i]=nums[j]，则对任意 i≤k≤j，必有 nums[i]=nums[k]=nums[j] ，即相等的元素在数组中的下标一定是连续的。利用数组有序的特点，可以通过双指针的方法删除重复元素。

如果数组 nums 的长度为 0，则数组不包含任何元素，因此返回 0。

当数组 nums 的长度大于 0 时，数组中至少包含一个元素，在删除重复元素之后也至少剩下一个元素，因此 nums[0] 保持原状即可，从下标 1 开始删除重复元素。

定义两个指针 fast 和 slow 分别为快指针和慢指针，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标 1。

假设数组 nums 的长度为 n。将快指针 fast 依次遍历从 1 到 n−1 的每个位置，对于每个位置，如果 nums[fast]≠nums[fast−1]，说明 nums[fast] 和之前的元素都不同，因此将 nums[fast] 的值复制到 nums[slow] ，然后将 slow 的值加 1，即指向下一个位置。

遍历结束之后，从 nums[0] 到 nums[slow−1] 的每个元素都不相同且包含原数组中的每个不同的元素，因此新的长度即为 slow，返回 slow 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};
作者：LeetCode-Solution

思路和我的基本一致，就不作介绍了

总结

  在这一周的学习过程中，主要的就是对数组，链表，字符串进行操作。考察的主要就是交换元素，判断元素，数字的反转（这是我认为学习到了一个完全的新的知识），同时在这次的学习过程中，发现了一点就是需要发现题目的特点，有时候利用题目的特点，可以大大提高我们算法的效率，总的来说，这个星期的学习也算是对算法的一个基本学习吧，让自己对算法有着更好的了解。