# 力扣题解

两数之和

// 暴力解法
// sizeof会造成溢出访问数组的问题，size则没有问题
class Solution {
 public:
     vector<int> twoSum(vector<int>& nums, int target) {
         int l = nums.size();
         int o1,o2;
         int flag=0;
         for(int i=0; i<l; i++){
             for(int j=i+1; j<l; j++){
                 if(nums[i]+nums[j]==target){
                     o1=i;
                     o2=j;
                     flag = 1;
                     break;
                 }
             }
             if(flag==1){
                 break;
             }
         }
         return {o1,o2};
     }
 };

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

整数反转

// 溢出检测问题比较多，看有没有可以精简的地方
double o = 0;
int m, flag=0;

if (x < 0) {
    if(x<=-pow(2,31)){
        return 0;
    }
    x = -x;
    flag = 1;
}
while (1) {
    m = x % 10;
    o = o * 10 + m;
    x /= 10;
    if (x==0)
    {
        break;
    }
}
if (o>=pow(2,31)){
    return 0;
}
if (flag == 1) {
    return -o;
}
else {
    return o;
}

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

回文数

// 采用生成反转数的方法进行判断
 while (x>=0)
 {
     double r = 0;
     int y = x, yy;
     while (y > 0) {
         yy = y % 10;
         r = r * 10 + yy;
         y /= 10;
     }
     if (x == r) {
         return true;
     }
     else
     {
         return false;
     }
 }
 return false;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

罗马数字转整数

// 程序没啥问题，就是执行太慢
map<string, int> Roma = {
    {"I",1},{"IV",4},{"V",5},{"IX",9},{"X",10},{"XL",40},{"L",50},
    {"XC",90},{"C",100},{"CD",400},{"D",500},{"CM",900},{"M",1000}
    };
 int o = 0;
 for (int i = 0; i < s.length(); i++) {
     string s1 = s.substr(i, 2);
     if (Roma.find(s1) != Roma.end()) {
         // 找到双字符
         i += 1;
     }
     else{
         // 单字符
         s1 = s.substr(i, 1);
     }
     o += Roma.at(s1);
 }
 return o;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

最长公共前缀

class Solution {
    public:
    string longestCommonPrefix(vector<string>& strs) {
        int num=0,flag=0;
        if(strs.size()>=1){
            for(int i=0;i<strs[0].size();i++){
                string cp = strs[0].substr(0,i+1);
                for(int j=1;j<strs.size();j++){
                    if (strs[j].substr(0, i + 1) != cp){
                        num = i;
                        flag=1;
                        break;
                     }
                 }
                 if(flag==1){
                     break;
                 }
             }
             if(flag==1){
                 return strs[0].substr(0,num);
             }else{
                 return strs[0];  // 两个字符串完全按相同或只有一个字符串时
             }
         }
         else{
             return "";   // 传入字符串为空时
         }
     }
 };

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 isValid(string s) {
        string ss;
        map<string, string> mk = {
            {"{", "}"}, {"[", "]"}, {"(", ")"}
        };
        for (int i = 0; i < s.size(); i++) {
            if (s.substr(i, 1) == "{" || s.substr(i, 1) == "(" || s.substr(i, 1) == "[") {
                ss.append(s.substr(i, 1));
            }
            else if (ss.size() != 0 && s.substr(i, 1) == mk.at(ss.substr(ss.size() - 1, 1))) {
                ss.erase(ss.size() - 1, 1);
            }
            else {
                return false;
            }
        }
        if (ss.size() == 0) {
            return true;
        }
        else {
            return 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

合并两个有序链表

// 官方解法，不开心
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* ll = new ListNode(0);
        ListNode* l3 = ll;
        while(l1 != NULL && l2 != NULL){
            if(l1->val < l2->val){
                l3->next = l1;
                l1 = l1->next;
            }else{
                l3->next = l2;
                l2 = l2->next;
            }
            l3 = l3->next;
        }
        l3->next = l1!=NULL ? l1:l2;
        return ll->next;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

删除排序数组中的重复项

// 还是官方的解法，跟vector没半毛钱关系，我佛了
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0){return 0;}
        int n = 0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=nums[n]){
                n++;
                nums[n] = nums[i];
            }
        }
        return n+1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

移除元素

// 跟上一题一样的思路，两个游标
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = 0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=val){
                nums[n] = nums[i];
                n++;
            }
        }
        return n;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

实现strStr()

// 调用函数
class Solution {
public:
    int strStr(string haystack, string needle) {
        int x = haystack.find(needle);
        return x;
    }
};

1
2
3
4
5
6
7
8

// 一般的解法
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) { return 0; }
        int i = 0;
        while (haystack[i] != '\0') {
            if (haystack[i] == needle[0]) {
                int j = 0;
                while (needle[j] != '\0') {
                    char ss1 = haystack[i + j];
                    char ss2 = needle[j];
                    if (haystack[i + j] == needle[j]) { j++; }
                    else { break; }
                }
                if(j==needle.size()){return i;}
            }
            if (haystack.size() - i < needle.size()) { return -1; }
            i++;
        }
        return -1;
    }
};

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:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        if(target>nums[n-1])return n;
        for(int i=0;i<n;i++){
            if(nums[i]>=target){
                return i;
            }
        }
        return 0;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

报数

// 题目不太好理解
// 用递归或许会简单一些
// 这道题主要还是题目不好理解

#include <stdio.h>
#include <string>
#include <iostream>

using namespace std;

string solution(int n) {
    string s = "1";
    string s1 = "";
    if (n == 1)return s;
    for (int i = 1; i < n; i++) {
        int count = 1;
        for (int j = 0; j < s.size(); j++) {
            if (s[j + 1] == '\0') {
                s1.append(to_string(count));
                s1.append(s.substr(j, 1));
                break;
            } else if (s[j + 1] == s[j]) {
                count++;
            } else {
                s1.append(to_string(count));
                s1.append(s.substr(j, 1));
                count = 1;
            }
        }
        s = s1;
        s1.clear();
    }
    return s;
}


int main() {
    int n = 0;
    printf("Input a number:");
    scanf("%d", &n);
    cout << solution(n) << endl;
    return 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

最后一个单词长度

// 用的从后往前检测的方法能快一点
// 主要还是在于空格的检测

#include <stdio.h>
#include <string>
#include <iostream>

using namespace std;

int solution(string s) {
    if (s == "")return 0;
    int l = s.size();
    int n = 0;
    for (int i = 0; i < l; ++i) {
        if (s[l - i - 1] == ' ' && n == 0) {
            continue;
        } else if (s[l - i - 1] == ' ' && n != 0) {
            break;
        }
        n++;
    }
    return n;
}


int main() {
    string s = "a bc";
    cout << solution(s) << endl;
    return 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

加一

// 出题人不让用转换成数字的方法做，故意把调试数据放的很长
// 主要问题在于进位

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        int l = digits.size();
        digits[l - 1] += 1;
        int flag = 0; // 进位标志
        while (l) {
            digits[l - 1] += flag;
            flag = 0;
            if (digits[l - 1] == 10) {
                if (l - 1 == 0) {
                    digits[0] = 0;
                    digits.insert(digits.begin(), 1);
                    break;
                }
                flag = 1;
                digits[l - 1] = 0;
            }
            l--;
        }
        return digits;
    }
};


int main() {
    Solution s;
    vector<int> vec = {9, 9, 9, 9};
    vec = s.plusOne(vec);
    for (int i = 0; i < vec.size(); ++i) {
        cout << vec[i];
    }
    return 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

二进制求和

// 转数字做法容易溢出
// 主要问题还是string的使用

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    string addBinary(string a, string b) {
        string o = "";
        int la = a.size(), lb = b.size();
        int flag = 0;
        while (la + lb) {
            int ia = 0, ib = 0;
            if (la){
                ia = stoi(a.substr(la - 1, 1));
                la--;
            }
            if (lb){
                ib = stoi(b.substr(lb - 1, 1));
                lb--;
            }
            o.insert(0, to_string((ia + ib + flag) % 2));
            flag = (ia + ib + flag) / 2;
        }
        if (flag)o.insert(0, "1");
        return o;
    }
};


int main() {
    Solution s;
    string a = "1";
    string b = "11";
    string o = s.addBinary(a, b);
    cout << o;
    return 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

删除排序链表中的重复元素

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        int num=0;
        ListNode *t = head,*p;
        p = t;
        while(t != NULL){
            if(t->val == num){
                p->next = t->next;
            }else{
                num = t->val;
                p = t;
            }
            if(t->next == NULL){
                break;
            }
            t = t->next;
        }
        return 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

合并两个有序数组


#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
        nums1.erase(nums1.begin() + m, nums1.end());
        int i = 0, j = 0;
        while (m != 0) {
            if (j == n)break;
            if (nums2[j] < nums1[i]) {
                nums1.insert(nums1.begin() + i, nums2[j]);
                j++;
            } else if (nums2[j] >= nums1[nums1.size() - 1]) {
                nums1.insert(nums1.end(), nums2[j]);
                j++;
            } else {
                i++;
            }
        }
        if (m == 0) {
            nums1 = nums2;
        }
    }
};


int main() {
    Solution s;
    vector<int> n1{1, 2, 3, 4, 4, 8, 0, 0};
    vector<int> n2{0, 3, 5};
    int m = 6, n = 3;
    s.merge(n1, m, n2, n);
    for (int i = 0; i < n1.size(); ++i) {
        cout << n1[i];
    }
    cout << endl;
    return 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

杨辉三角

// 少见的顺利

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> dd;
        for (int i = 0; i < numRows; ++i) {
            vector<int> d;
            for (int j = 0; j <= i; ++j) {
                if (j == i) {
                    d.push_back(1);
                    dd.push_back(d);
                } else if (j == 0) {
                    d.push_back(1);
                } else {
                    d.push_back(dd[i - 1][j - 1] + dd[i - 1][j]);
                }
            }
        }
        return dd;
    }
};


int main() {
    Solution s;
    int n = 7;
    vector<vector<int>> d;
    d = s.generate(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            cout << d[i][j]<<" ";
        }
        cout << endl;
    }
    return 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

字符串中的第一个唯一字符

// 时间太长

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int firstUniqChar(string s) {
        int l = s.size();
        string s1 = "";
        vector<int> vec;
        // 统计字符串
        for (int i = 0; i < l; ++i) {
            int k = s1.find(s.substr(i,1));
            if(k==-1){
                s1.append(s.substr(i,1));
                vec.push_back(1);
            }else{
                vec[k]+=1;
            }
        }
        // 找首个出现次数为1的
        for (int j = 0; j < vec.size(); ++j) {
            if(vec[j]==1){
                return s.find(s1.substr(j,1));
            }
        }
        return -1;
    }
};


int main() {
    Solution s;
    string s1 = "abbacd";
    cout << s.firstUniqChar(s1) << endl;
    return 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

// 比之前快一点，但还是很慢
class Solution {
public:
    int firstUniqChar(string s) {
        int l = s.size();
        string s1 = "";
        vector<int> vec;
        vector<int> vec_ad;
        // 统计字符串
        for (int i = 0; i < l; ++i) {
            int k = s1.find(s.substr(i,1));
            if(k==-1){
                s1.append(s.substr(i,1));
                vec.push_back(1);
                vec_ad.push_back(i);
            }else{
                vec[k]+=1;
            }
        }
        // 找首个出现次数为1的
        for (int j = 0; j < vec.size(); ++j) {
            if(vec[j]==1){
                return vec_ad[j];
            }
        }
        return -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:
    int firstUniqChar(string s) {
        vector<int> vec(26,0);
        // 统计字符
        for (auto i:s) {
            vec[i-'a']+=1;
        }
        // 返回首个出现次数为1的位置
        for (int j = 0; j < s.size(); ++j) {
            if (vec[s[j]-'a']==1){
                return j;
            }
        }
        return -1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

相同的树

// 递归NB，写不来
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (p == NULL && q == NULL) {
            return true;
        } else if (p != NULL && q != NULL && p->val == q->val) {
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        } else {
            return false;
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

移除链表元素

// 常规解法
// 主要问题在于链表头部元素的处理
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *p, *q;
        p = head;
        if (p == nullptr)return head;  // 空链表
        while (p != nullptr) {
            if (p->val != val) {  // 链表从非删除元素开始
                head = p;
                break;
            }
            p = p->next;
        }
        if (p == nullptr) {  // 链表元素全部都是要删除的
            head = nullptr;
            return head;
        }
        // 删除链表后部指定元素
        q = p;
        while (p != nullptr) {
            if (p->val == val) {
                q->next = p->next;
            } else {
                q = p;
            }
            p = p->next;
        }
        return 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

// 评论区解法，思路：在链表头部插入元素，让原链表的头部元素编程一般元素
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *h = new ListNode(-1);
        ListNode *p, *q;
        if (head == nullptr)return head;
        h->next = head;
        p = h, q = h;
        head = p->next;
        while (p != nullptr) {
            if (p->val == val) {
                q->next = p->next;
            } else {
                q = p;
            }
            p = p->next;
        }
        return h->next;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

反转链表

// 太慢，太大
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *p = head;
        if(p==NULL)return head;
        vector<int> v;
        while(p!=NULL){
            v.insert(v.begin(),p->val);
            p = p->next;
        }
        ListNode *t = new ListNode(0);
        head = t;
        for(int i:v){
            ListNode *q = new ListNode(i);
            t->next = q;
            t = q;
        }
        return head->next;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

删除链表中的节点

class Solution {
public:
    void deleteNode(ListNode* node) {
        *(node) = *(node->next);
    }
};

1
2
3
4
5
6

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

1
2
3
4
5
6
7

最大连续1的个数

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int> &nums) {
        int t = 0, l = 0;
        for (int i:nums) {
            if (i == 1) {
                t++;
                l = t > l ? t : l;
            } else {
                t = 0;
            }
        }
        return l;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最小栈

// 力扣编程及测试文件

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {}

    stack<int> s1;  // main stack
    stack<int> s2;  // assist stack

    void push(int x) {
        s1.push(x);
        if (s2.empty() || x <= s2.top()) {
            s2.push(x);
        }
    }

    void pop() {
        if (!s1.empty()) {
            if (s1.top() == s2.top())s2.pop();
            s1.pop();
        }
    }

    int top() {
        return s1.top();
    }

    int getMin() {
        return s2.top();
    }
};


int main() {
    MinStack *obj = new MinStack();
    obj->push(2);
    obj->push(0);
    obj->push(-1);
    obj->push(-3);
    obj->push(2);
    obj->pop();
    cout << obj->top() << endl;
    cout << obj->getMin() << endl;

    return 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

excel表列名称

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    string convertToTitle(int n) {
        string s1 = "", s2;
        while (n) {
            switch (n % 26) {
                case 0:
                    s2 = "Z";
                    n -= 26;
                    break;
                default:
                    s2 = (char) (n % 26 + 64);
            }
            n /= 26;
            s1.insert(0, s2);
        }
        return s1;
    }
};


int main() {
    Solution so;
    cout << so.convertToTitle(0) << endl;    // 空
    cout << so.convertToTitle(28) << endl;   // AB
    cout << so.convertToTitle(701) << endl;  // ZY
    cout << so.convertToTitle(26 * 26) << endl;  // YZ
    return 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

同构字符串

// map解法有些慢
// cpp hash_map非标准库中的库，使用有些问题

#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;


class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, char> m1, m2;
        for (int i = 0; i < s.size(); ++i) {
            m1.insert(pair<char, char>(s[i], t[i]));
            m2.insert(pair<char, char>(t[i], s[i]));
        }
        for (int j = 0; j < s.size(); ++j) {
            if (m1.at(s[j]) != t[j] || m2.at(t[j])!=s[j])
                return false;
        }
        return true;
    }
};


int main() {
    Solution so;
    cout << so.isIsomorphic("egg", "add") << endl;
    cout << so.isIsomorphic("paper", "title") << endl;
    cout << so.isIsomorphic("add", "aaa") << endl;
    return 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

// 本地测试能通过，力扣上面使用hash_map会有问题
// hash_map思想一样，就是速度会变快一点
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        __gnu_cxx::hash_map<int, char> map1,map2;
        for (int i = 0; i < s.size(); ++i) {
            map1[s[i] - 96] = t[i];
            map2[t[i] - 96] = s[i];
        }
        for (int j = 0; j < s.size(); ++j) {
            if (map1[s[j] - 96] != t[j] || map2[t[j] - 96] != s[j])
                return false;
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

存在重复元素

// 直接用map即可
class Solution {
public:
    bool containsDuplicate(vector<int> &nums) {
        map<int, int> hashMap;
        for (int i = 0; i < nums.size(); ++i) {
            hashMap[nums[i]] += 1;
            if (hashMap[nums[i]] > 1)
                return true;
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

// unordered_map做法
// 速度有提升

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool containsDuplicate(vector<int> &nums) {
        unordered_map<int, int> hashMap;
        for (int i = 0; i < nums.size(); ++i) {
            hashMap[nums[i]] += 1;
            if (hashMap[nums[i]] > 1)
                return true;
        }
        return false;
    }
};


int main() {
    Solution so;
    vector<int> vec1 = {1, 2, 3, 4, 5, 6, 1};
    cout << so.containsDuplicate(vec1) << endl;
    return 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

存在重复元素II

// 此题描述有误
// 思路：HashMap中存储的是该元素最近一次出现的位置
class Solution {
public:
    bool containsNearbyDuplicate(vector<int> &nums, int k) {
        unordered_map<int, int> hashMap;
        for (int i = 0; i < nums.size(); ++i) {
            if (hashMap.count(nums[i]) != 0 && i - hashMap[nums[i]] <= k) {
                return true;
            } else {
                hashMap[nums[i]] = i;
            }
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

有效的字母异位词

// 不想用map了，用了vector，思想是一样的
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size())return false;
        vector<int> vec(26, 0);
        for (int i = 0; i < s.size(); ++i) {
            vec[s[i] - 97]++;
            vec[t[i] - 97]--;
        }
        for (int j = 0; j < 26; ++j) {
            if (vec[j] != 0)return false;
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

各位相加

// 递归，需要注意递归用法
// 评论里有些数学解法比较有意思
class Solution {
public:
    int addDigits(int num) {
        string s = to_string(num);
        int out = 0;
        for (int i = 0; i < s.size(); ++i) {
            out += s[i] - 48;
        }
        if(out<10){
            return out;
        }
        return addDigits(out);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

丑数

// 跟评论区解法一致，也没看到别的解法
class Solution {
public:
    bool isUgly(int num) {
        if (num == 0)return false;
        while (num % 2 == 0) {
            num /= 2;
        }
        while (num % 3 == 0) {
            num /= 3;
        }
        while (num % 5 == 0) {
            num /= 5;
        }
        return num == 1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

缺失数字

// 要注意定义flag大小的问题
// 排序算法也想过，不过速度不会快
class Solution {
public:
    int missingNumber(vector<int> &nums) {
        int n = nums.size();
        vector<int> flag(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            flag[nums[i]] = 1;
        }
        int j = 0;
        while (flag[j]) {
            j++;
        }
        return j;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 评论区看到一个加法的算法，是一个很好的思路
// 不过力扣的执行用时也太迷了，明明这个应该更快
class Solution {
public:
    int missingNumber(vector<int> &nums) {
        int n = nums.size();
        int sub = 0;
        for (int i = 0; i < n; ++i) {
            sub += nums[i];
        }
        return (1 + n) * n / 2 - sub;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

单词规律

// 不想用双map，但没成功
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        vector<string> vec;
        // 分割string
        while (str.find(" ") != -1) {
            int n = str.find(" ");
            vec.push_back(str.substr(0, n));
            str = str.substr(n + 1);
        }
        vec.push_back(str);

        map<char, string> m1;
        map<string, char> m2;
        if (pattern.size() == vec.size()) {
            for (int i = 0; i < pattern.size(); ++i) {
                m1.insert(pair<char, string>(pattern[i], vec[i]));
                m2.insert(pair<string, char>(vec[i], pattern[i]));
            }
            for (int j = 0; j < pattern.size(); ++j) {
                if(m1[pattern[j]]!=vec[j] || m2[vec[j]]!=pattern[j]){
                    return false;
                }
            }
            return true;
        }
        return 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
29
30

区域和检索——数组不可变

// 二维向量太麻烦了，想到了一个取巧的方法，可惜评论区已经有了
#include <iostream>
#include <vector>

using namespace std;

class NumArray {
public:
    NumArray(vector<int> &nums) {
        int add = 0;
        sum.push_back(add);
        for (int i = 0; i < nums.size(); ++i) {
            add+=nums[i];
            sum.push_back(add);
        }
    }

    int sumRange(int i, int j) {
        return sum[j+1]-sum[i];
    }

private:
    vector<int>sum;
};


int main() {
    vector<int> vec{-2, 0, 3, -5, 2, -1};
    NumArray *na = new NumArray(vec);
    cout << na->sumRange(0, 2) << endl;
    cout << na->sumRange(2, 5) << endl;
    cout << na->sumRange(0, 5) << endl;
    return 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

3的幂

// 循环的方法
class Solution {
public:
    bool isPowerOfThree(int n) {
        bool flag = false;
        while (n) {
            if (n == 1) {
                flag = true;
                break;
            } else if (n % 3 != 0) {
                break;
            }
            n /= 3;
        }
        return flag;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 递归方法，速度更快
class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n==1){
            return true;
        }else if(n==0 || n%3!=0){
            return false;
        }
        return isPowerOfThree(n/3);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12

反转字符串

// 可以通过，但似乎不是个好的解法
class Solution {
public:
    void reverseString(vector<char> &s) {
        for (int i = 0; i < s.size() / 2; ++i) {
            swap(s[i], s[s.size() - i - 1]);
        }
    }
};

1
2
3
4
5
6
7
8
9

两个数组的交集

// 还是hash方法比较快
class Solution {
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        unordered_map<int, int> ins;
        vector<int> out;
        for (int i = 0; i < nums1.size(); ++i) {
            ins[nums1[i]] = 1;
        }
        for (int j = 0; j < nums2.size(); ++j) {
            if (ins[nums2[j]] == 1) {
                ins[nums2[j]] = 2;
                out.push_back(nums2[j]);
            }
        }
        return out;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

赎金信

// hash能做，但是麻烦，在一直字符种类上限的情况下，vector更省事
// 就是可能会浪费点内存
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> vec(26, 0);
        if (ransomNote.size() > magazine.size())return false;
        for (int i = 0; i < magazine.size(); ++i) {
            if (i < ransomNote.size()) {
                vec[(int) (ransomNote[i]) - 97]--;
            }
            vec[(int) (magazine[i]) - 97]++;
        }
        for (int j = 0; j < vec.size(); ++j) {
            if (vec[j] < 0)return false;
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

字符串中的第一个唯一字符（同19题）

找不同

// 偷懒失败，不让用vector，unordered_map
// 我咋就没想到直接用ASCII码计算，明明vecotr也是用的ASCII
class Solution {
public:
    char findTheDifference(string s, string t) {
        int s_sum=0,t_sum=0;
        for (int i = 0; i < t.size(); ++i) {
            if (i < s.size()) {
                s_sum+=(int)(s[i]);
            }
            t_sum+=(int)(t[i]);
        }
        return (char)(t_sum-s_sum);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Fizz Buzz

//Em...好像没啥特别的
class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> vec;
        for (int i = 1; i <= n; ++i) {
            string s = "";
            if (i % 3 != 0&& i % 5 != 0){
                s = to_string(i);
            } else{
                if (i % 3 == 0) { s += "Fizz"; }
                if (i % 5 == 0) { s += "Buzz"; }
            }
            vec.push_back(s);
        }
        return vec;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

字符串中的单词数

// 采用检测空格的方法
// 评论区没看到什么清奇的解法
class Solution {
public:
    int countSegments(string s) {
        int n = 0;
        if (s.size() != 0){
            if(s[0]!=' '){
                n++;
            }
            for (int i = 0; i < s.size(); ++i) {
                if (int(s[i]) == 32 && int(s[i+1]) > 32) {
                    n++;
                }
            }
        }

        return n;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

找到字符串中所有字母的异位词

// 第一时间想到ASCII相加的方法，但不合适
// 评论区有window的解法，但是没接触过，感觉不太能用得到，所以没看
// 最后用了比较笨的向量方法，哈希会有点问题
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> vec;
        if (s.size() < p.size())return vec;
        vector<int> upp(26, 0), ups(26, 0);
        for (int i = 0; i < p.size(); ++i) {
            upp[p[i] - 97]++;
            ups[s[i]-97]++;
        }
        for (int j = 0; j <= s.size() - p.size(); ++j) {
            if (j) {
                ups[s[j - 1]-97]--;
                ups[s[j + p.size() - 1]-97]++;
            }
            if (upp == ups) {
                vec.push_back(j);
            }
        }
        return vec;
    }
};

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:
    int arrangeCoins(int n) {
        int i=1;
        while (n>=i){
            n-=i;
            i++;
        }
        return i-1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12

// 数学解法，解个方程就行
// 深深感受到年龄增长智力下降
// 力扣后台用的什么沙雕系统，动不动就溢出要改成(sqrt(2)*sqrt(n+0.125)-0.5)/1;
class Solution {
public:
    int arrangeCoins(int n) {
        return (sqrt(8*n+1)-1)/2;
    }
};

1
2
3
4
5
6
7
8
9

压缩字符串

// 当年（其实就是去年）华为笔试做过类似的
// 感觉写的稍微有些麻烦
class Solution {
public:
    int compress(vector<char> &chars) {
        vector<char> cc;
        if (chars.size() == 0) {
            return 0;
        }
        char c = chars[0];
        int t = 1;
        for (int i = 1; i < chars.size(); ++i) {
            if (chars[i] == c) {
                t++;
            } else {
                cc.push_back(c);
                if(t > 1) {
                    string s = to_string(t);
                    for (int j = 0; j < s.size(); ++j) {
                        cc.push_back(s[j]);
                    }
                }
                c = chars[i];
                t = 1;
            }
        }
        cc.push_back(c);
        if(t > 1) {
            string s = to_string(t);
            for (int j = 0; j < s.size(); ++j) {
                cc.push_back(s[j]);
            }
        }
        chars = cc;
        return cc.size();
    }
};

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

汉明距离

// 意外的简单，想想这道题有没有其他玩法
class Solution {
public:
    int hammingDistance(int x, int y) {
        int d = 0;
        while(true){
            if(x==0 && y==0){
                break;
            }
            if((x%2)!=(y%2)){
                d++;
            }
            x/=2;
            y/=2;
        }
        return d;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// 用位操作符
// 速度提升
class Solution {
public:
    int hammingDistance(int x, int y) {
        int a = x ^y;
        int b = 0;
        while (a) {
            b += a % 2;
            a /= 2;
        }
        return b;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

最大连续1的个数（同24）

键盘行

// map的方法太麻烦，懒得打
// 用字符的方法，会牺牲速度
class Solution {
public:
    vector<string> findWords(vector<string> &words) {
        vector<string> out;
        string s1 = "qwertyuiopQWERTYUIOP";
        string s2 = "asdfghjklASDFGHJKL";
        string s3 = "zxcvbnmZXCVBNM";
        for (int i = 0; i < words.size(); i++) {
            int a1 = 0, a2 = 0, a3 = 0;
            for (int j = 0; j < words[i].size(); j++) {
                char ss = words[i][j];
                if (s1.find(words[i][j]) != -1)a1++;
                if (s2.find(words[i][j]) != -1)a2++;
                if (s3.find(words[i][j]) != -1)a3++;
            }
            if(a1==words[i].size()||a2==words[i].size()||a3==words[i].size()){
                out.insert(out.end(), words[i]);
            }
        }
        return out;
    }
};

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:
    string convertToBase7(int num) {
        string s1,s2;
        if (num < 0) {
            num = -num;
            s1="-";
        }else if(num==0){
            return "0";
        }
        while (num) {
            s2.insert(0, to_string(num % 7));
            num /= 7;
        }
        return s1+s2;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// 稍微改了一下就莫名变快
class Solution {
public:
    string convertToBase7(int num) {
        string s1,s2;
        if (num < 0) {
            num = -num;
            s1="-";
        }else if(num==0){
            return "0";
        }
        while (num) {
            s2 = to_string(num % 7)+s2;
            num /= 7;
        }
        return s1+s2;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

检测大写字母
反转字符转II
学生出勤记录I
反转字符串中的单词III
N叉树的最大深度
数组拆分I
重塑矩阵
分糖果
最短无序连续子数组
种花问题
三个数的最大乘积
二叉树的层平均值
机器人能否返回原点
最长连续递增序列
交替位二进制数
字少是其他数字两倍的最大数
寻找比目标字母大的最小字母
宝石与石头
字母大小写全排列
旋转字符串

← Tomcat笔记文件系统 →