Cinte's Leetcode Record
0%

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

面试题 02.01. 移除重复节点

借助set
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        ListNode* pseudoHead = new ListNode();
        ListNode* ret = pseudoHead;
        unordered_set<int> set;
        while(head)
        {
            if(set.emplace(head->val).second)
            {
                pseudoHead->next = head;
                pseudoHead = pseudoHead->next;
            }
            head = head->next;
        }
        pseudoHead->next = nullptr;
        return ret->next;
    }
};

T(n) : O(n)

S(n) : O(n)

不用set(遍历好多次)
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        auto point = head;
        while(point)
        {
            auto pre = point;
            auto cur = point->next;
            while(cur)
            {
                if(cur->val == point->val)
                {
                    pre->next = cur->next;
                    cur = cur->next;
                }else
                {
                    pre = pre->next;
                    cur = cur->next;
                }
            }
            point = point->next;
        }
        return head;
    }
};

T(n) : O(n^2)

S(n) : O(1)

Posted on Edited on In Disqus:
Symbols count in article: 648 Reading time ≈ 1 mins.

面试题 02.06. 回文链表

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *walker = head, *runner = head;
        ListNode* pre = nullptr;
        while(runner && runner->next)
        {
            runner = runner->next->next;
            auto next = walker->next;
            walker->next = pre;
            pre = walker;
            walker = next;
        }
        if(runner)
            walker = walker->next;
        while(pre && walker && pre->val == walker->val) {
            pre = pre->next;
            walker = walker->next;
        }
        return !(pre || walker);
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 640 Reading time ≈ 1 mins.

面试题 01.09. 字符串轮转

题解中的大佬
1
2
3
4
5
6
class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        return s1.size() == s2.size() && (s1 + s1).find(s2) != -1;
    }
};

把旋转字符串前半部分补充成旋转前的，后半部分也补充成旋转前的。最后就变成了两个旋转前的拼起来，而旋转后的必然存在与其中。find表示未找到s2子串就返回-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
class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if(s1.size() != s2.size())
            return false;
        if(s1.empty())
            return s2.empty();
        for(int i = 0; i < s2.size(); ++i)
        {
            if(s2[i] == s1[0])
            {
                int j = i + 1;
                int k = 1;
                while(k < s1.size() && s2[j % s2.size()] == s1[k]) {
                    ++j;
                    ++k;
                }
                if(k == s1.size())
                    return true;
            }
        }
        return false;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 395 Reading time ≈ 1 mins.

面试题 01.06. 字符串压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string compressString(string S) {
        string ret;
        int curNum = 1;
        char curVal = S.front();
        for(int i = 1; i < S.size(); ++i)
        {
            if(S[i] != curVal)
            {
                ret.append(curVal + to_string(curNum));
                curVal = S[i];
                curNum = 1;
            }
            else
                ++curNum;
        }
        ret.append(curVal + to_string(curNum));
        return ret.size() >= S.size() ? S : ret;
    }
};

T(n) : O(n)

S(n) : O(n)

Posted on Edited on In Disqus:
Symbols count in article: 492 Reading time ≈ 1 mins.

面试题 01.03. URL化

类似剑指 Offer 05. 替换空格

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 replaceSpaces(string S, int length) {
        int spaceNum = 0;
        for(int i = 0; i < length; ++i)
            spaceNum += (S[i] == ' ' ? 1 : 0);
        int realSize = length + 2 * spaceNum;
        S.resize(realSize); // 有时候这个字符串会给出额外的空余空间，需要根据实际大小resize一下
        for(int i = length - 1, j = realSize - 1; i >= 0; --i, --j)
        {
            if(S[i] != ' ')
                S[j] = S[i];
            else
            {
                S[j] = '0';
                S[j - 1] = '2';
                S[j - 2] = '%';
                j -= 2;
            }
        }
        return S;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.5k Reading time ≈ 1 mins.

647. Palindromic Substrings

自下而上，从单个字母和相邻两个字母相同的条件出发
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int ret{ 0 };
        for(int i = 0; i < n; ++i)
            ret += helper(s, n, i, i) + helper(s, n, i, i + 1); // 奇数的情况，从单个字母向外开展 偶数的情况，从相邻2个向外开展
        return ret;
    }
private:
    int helper(string& s, int n, int i, int j)
    {
        int ret{ 0 };
        while(i >= 0 && j < n && s[i--] == s[j++])
            ++ret;
        return ret;
    }
};
dp
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 countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int ret = s.size();
        for(int i = 0; i < s.size(); ++i)
            dp[i][i] = true; // 单个字母的base
        for(int i = 0; i < s.size() - 1; ++i)
        {
            // 这里不能dp[i+1][i]，因为判断时候总是i<j，所以得保持顺序
            dp[i][i + 1] = s[i] == s[i + 1]; // 相邻两个字母相同的base
            ret += dp[i][i + 1] ? 1 : 0;
        }
        // 注意，由于每次的dp是基于长度缩小的区间，所以需要根据长度大小来遍历，从较短的长度遍历到较长的长度。
        for(int len = 3; len <= s.size(); ++len)
        {
            for(int i = 0, j = i + len - 1; j < s.size(); ++i, ++j)
            {
                dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
                ret += dp[i][j] ? 1 : 0;
            }
        }
        return ret;
    }
};
dpReview
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i = 0; i < n; ++i)
            dp[i][i] = true;
        int ret = n;
        for(int i = 0; i < n - 1; ++i)
            if(dp[i][i + 1] = s[i] == s[i + 1])
                ++ret;
        for(int i = n - 1; i >= 0; --i)
            for(int j = i + 2; j < n; ++j)
                if(dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1])
                    ++ret;
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 550 Reading time ≈ 1 mins.

面试题 01.01. 判定字符是否唯一

排序
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool isUnique(string astr) {
        sort(astr.begin(), astr.end());
        for(int i = 1; i < astr.size(); ++i)
            if(astr[i] == astr[i - 1])
                return false;
        return true;
    }
};
位运算

由题意，可能这个字符串所有字母是a~z之间，本来想到用一个26大小的数组来记录。但是可以通过一个26位的二进制中的每个位是否为1来表示这个位对应的字母是否出现过，由此就可以呃不用其他的数据结构 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isUnique(string astr) {
        int a = 0;
        for(auto& ch : astr)
        {
            int i = ch - 'a';
            if(a & (1 << i)) // 如果a这个位为1，那么结果为1，表示重复了
                return false;
            else
                a |= 1 << i; // 记录这个位
        }
        return true;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

621. Task Scheduler

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 leastInterval(vector<char>& tasks, int n) {
        int maxFreqNum = 0;
        int maxVal = 0;
        int taskCount[26]{ 0 };
        for(auto& task : tasks)
        {
            ++taskCount[task - 'A'];
            if(maxVal == taskCount[task - 'A'])
                ++maxFreqNum;
            if(taskCount[task - 'A'] > maxVal)
            {
                maxFreqNum = 1;
                maxVal = taskCount[task - 'A'];
            }
        }
        int leftSpace = (maxVal - 1) * (n - maxFreqNum + 1);
        int leftTasks = tasks.size() - maxFreqNum * maxVal;
        int idle = max(0, leftSpace - leftTasks);
        return idle + tasks.size();
    }
};

首先对于AAABBCC的情况，先获得出现最多的任务

然后假设n=2

1
A??A??A

先放A，然后把中间空余的用其他的来填满，因为其他的如果有多个，那么只需要依次填入到每个间隔中去就可以了，例如

1
AB?AB?A

依旧可以保证他们的间隔符合要求。

如果有多个出现最多次数的任务，比如AAABBBC，n=2那就

1
A??A??A->AB?AB?AB

把AB视为一个整体X

1
X?X?X

此时就转化为一个XXXC,n=1的问题

由此我们可以先计算出出现最多的任务的出现次数maxVal，和出现最多的任务同时有几个maxFreqNum。

可以计算得到把这些任务放置后，空余的空间就是

leftSpace = (maxVal - 1) * (n - maxFreqNum + 1)

剩余的任务就是leftTasks = tasks.size() - maxFreqNum * maxVal

然后把其他的元素排放进空余的空间中去，如果空余的空间足够。那么需要填充idle空间就是

leftSpace - leftTasks，如果空余的空间不够了,那么上面算式结果是负，那么idle的空间是0，然后将剩余的任务填充进入之前每个分块的末尾即可。所以使用

1
max(0, leftSpace - leftTasks)

例如

AAABBBCC,n=1。放完最高频率后是

1
ABABAB

那么下一步只需要

1
ABCABCAB

如果maxFreqNum > n

例如AAABBBCCCDD,n = 1

只需要这样排

1
ABCABCABC->ABCDABCDABC

因为maxFreqNum > n可以保证符合要求

排列后由于n - maxFreqNum + 1是负数，所以剩余空间是负数，最终idle还是0，所以结果不变。

所有情况下的结果都是任务数和需要填充的idle数

Posted on Edited on In Disqus:
Symbols count in article: 695 Reading time ≈ 1 mins.

617. Merge Two Binary Trees

递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1)
            return root2;
        if(!root2)
            return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};
还有迭代

用队列可以记录2个对应的节点进行操作