发表于

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) 
    {
        for (int i = digits.size() - 1; i >= 0; --i)
        {
            ++digits[i];
            digits[i] %= 10;
			
            // 说明不需要在最前面加一个 “1” 了
            if (digits[i]) return digits;
        }

        // 例子： 999 + 1 = 1000
        // 首位还需加上一个1
        digits.insert(digits.begin(), 1);
        return digits;    
    }
};

总结

  • 很简单的循环判断，一开始也AC，但是代码很冗余，可读性差些，根据reference中的代码解进行修改。

References

https://leetcode-cn.com/problems/plus-one/solution/java-shu-xue-jie-ti-by-yhhzw/

发表于

题目

以下2种题解，时间均是\(O(1)\)

哈希表

额外空间: \(O(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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        auto p = head;
        set<ListNode*> hash;

        while (p)
        {
            if (!hash.count(p))
            {
                hash.insert(p);
            }
            else
            {
                return true;
            }
            p = p->next;
        }   
        
        return false;
    }
};

双指针法

额外空间：\(O(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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        if (!head || !head->next)   return false;
        ListNode* slowP = head;
        ListNode* fastP = head->next;

        while (slowP != fastP)
        {
            // CUZ fastP 快些，所以fastP/ fastP->next为null之后，就说明 无环了
            if (!fastP || !fastP->next) return false;
            
            slowP = slowP->next;
            fastP = fastP->next->next;        
        }

        return true;
    }
};

总结

  • 双指针法

    • 需要注意，初始化 fastP, slowP快慢指针的时候的判别条件。

      1
      2
      3
      if (!head || !head->next)   return false;
      ListNode* slowP = head;
      ListNode* fastP = head->next;

    • 判断是否有环 <=> 判断是否指针指向nullptr处. 判断指针是否指向nullptr处的常数项系数更小。

      注意此时的循环/条件语句的判别条件。

      1
      2
      3
      4
      5
      while (slowP != fastP)
      {
          // CUZ fastP 快些，所以fastP/ fastP->next为null之后，就说明 无环了
          if (!fastP || !fastP->next) return false;
      }

发表于

题目

官方解

1.水平扫描法

思路：

\[ LCP(S_1 ...S_n) = LCP(LCP(LCP(S_1, S_2), S_3), ...Sn) \]

求\(2\)个字符串的最长前缀一般来说是每个字符串从头比较到尾，直到不相等为止。

但假如是\(n\)个字符串之间的比较的话，为了避免每次比较从头到尾进行，可以根据如上述公式，

  • 选取一个字符串\(A\)作为前缀，长度为\(k\);

  • 若该字符串\(A\)与另一个\(B\)的前\(k\)字符串不同；

  • 则去掉一个字符串\(A\)中的末尾字符，形成新字符串\(A'\)，

  • 与串\(B\)比较直至满足前缀完全相等的情况；

  • 再将得到的最大公共前缀与串\(C,...,N\)比较，按上述循环进行，直至满足条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string s_0 = strs.size() ? strs[0] : "";

        for (auto& str: strs)
        {
            // 前缀串s_0 与 串str的前s_0.size()部分不等，则前缀串s_0去掉末尾字符
            while (str.substr(0, s_0.size()) != s_0)
            {
                s_0 = s_0.substr(0, s_0.size()-1); 
                if (s_0 == "")  return "";
            }
        }

        return s_0;
    }
};

同时可以用s_0.pop_back(); 或者 s_0.erase(s_0.size() - 1);

替换掉 s_0 = s_0.substr(0, s_0.size() - 1)

发表于 | 更新于

题目

回溯法

递归实现

额外空间：\(O(n)\)

时间：\(O(2^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
class Solution {
private:
    vector<vector<int>> sub;
public:
    void findSub(vector<int>& nums, vector<int>& tmp, const int pos)
    {
        if (pos >= nums.size())
        {
            sub.emplace_back(tmp);
            return ;
        }

        // add this element
        tmp.emplace_back(nums[pos]);
        findSub(nums, tmp, pos + 1);

        // not add this element
        tmp.pop_back();
        findSub(nums, tmp, pos + 1);
    }
    
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        vector<int> tmp{};
        findSub(nums, tmp, 0);
        return sub;
    }
};

总结

  • 使用emplace_back() 而不是 push_back()

  • 我的理解：带有条件判断的DFS

    回溯法=>递归实现=>自动调栈<=> DFS

References

push_back vs emplace_back

Examples where std::vector::emplace_back is slower than std::vector::push_back?

push_back vs emplace_back to a std::vector

发表于

题目

Leetcode官方 way

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) 
    {
        node->val = node->next->val;
        node->next = node->next->next;    
    }
};

Reference

https://leetcode-cn.com/problems/delete-node-in-a-linked-list/solution/shan-chu-lian-biao-zhong-de-jie-dian-by-leetcode/

总结

  • 提供了一个新的删除节点的思路：
    • 在不考虑末尾节点的时候！！
    • 跟下一个节点交换值之后，然后调整next指针为next->next

发表于

题目

My way

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
class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> m;

        if (s.size() < t.size())    swap(s, t);

        for (auto& it : s)
        {
            --m[it];
        }

        for (auto& it: t)
        {
            ++m[it];
        }

        for (auto& it: m)
        {
            if (it.second != 0)  return false;
        }

        return true;
    }
};
  • 利用哈希表构成一个计数器的效果。
  • 利用ctor初始化int变量默认值是0，
    • 在s里出现过，则自减1；
    • 在t里出现过，则自增1；
  • 要注意，s, t字符串的大小可能不一样。所以需要在计数前，交换一次。

官方 way

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size())   return false;

        int counter[26] = {0};

        for (size_t i = 0; i < s.size(); ++i)
        {
            ++counter[s[i] - 'a'];
            --counter[t[i] - 'a'];
        }

        for (auto& it: counter)
        {
            if (it != 0) return false;
        }

        return true;
    }
};
  • 利用一个int数组构造出一个计数器

References

https://leetcode-cn.com/problems/valid-anagram/solution/you-xiao-de-zi-mu-yi-wei-ci-by-leetcode/