Blog of Aspirer – 第5页 – 收集生活点滴，留下美好回忆！

1. 两数之和

Posted on 2022-06-15 by aspirer

题目链接：https://leetcode.cn/problems/two-sum/

还是只会暴力搜索法，其实也能想到要用空间换时间，但是不知道用啥数据结构比较合适。。。。

仔细想想，就是要把一个数字存到一个能快速搜索的数据结构里，比如target=7，遍历nums{2,3,4}的过程中，遍历到3的时候要能快速找到另外一个数据结构中的数字4，这么看来也就hash table里的key比较合适，正好也能用value保存key对应的数组下标。

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 {};
    }
*/

/* 官方hash table搜索法
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> ht;
        for (int i = 0; i < nums.size(); i++) {
            auto it = ht.find(target - nums[i]);
            if (it != ht.end()) {
                return {it->second, i};
            } else {
                ht[nums[i]] = i;
            }
        }
        return {};
    }
*/

    // 官方hash table解法稍微变化了下，更容易理解一点，但是时间复杂度稍微高一些
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> ht;
        for (int i = 0; i < nums.size(); i++) {     // 先把数组的数字都丢入hash table
            ht[nums[i]] = i;
        }
        for (int i = 0; i < nums.size(); i++) {     // 遍历数组，同时搜索hash table
            auto it = ht.find(target - nums[i]);
            if (it != ht.end() && it->second != i) {    // 找到跟当前数字nums[i]匹配的另一个目标数字，并且不是当前数字自己
                return {i, it->second};
            }
        }
        return {};
    }

};

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 {};

}

/* 官方hash table搜索法

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> ht;

for (int i = 0; i < nums.size(); i++) {

auto it = ht.find(target - nums[i]);

if (it != ht.end()) {

return {it->second, i};

} else {

ht[nums[i]] = i;

}

return {};

}

// 官方hash table解法稍微变化了下，更容易理解一点，但是时间复杂度稍微高一些

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> ht;

for (int i = 0; i < nums.size(); i++) { // 先把数组的数字都丢入hash table

ht[nums[i]] = i;

}

for (int i = 0; i < nums.size(); i++) { // 遍历数组，同时搜索hash table

auto it = ht.find(target - nums[i]);

if (it != ht.end() && it->second != i) { // 找到跟当前数字nums[i]匹配的另一个目标数字，并且不是当前数字自己

return {i, it->second};

}

return {};

}

};

技术

19. 删除链表的倒数第 N 个结点

Posted on 2022-06-14 by aspirer

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

这道题目，内存占用会比较多，空间复杂度比较高，不过还好vector里保存的都是指针，没看官方题解，省得记不住，还是自己的思路比较容易记忆。

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        vector<ListNode*> ln;  // store all nodes to vector
        ListNode* p = head;
        while (p) {
            ln.push_back(p);
            p = p->next;
        }
        if (n == 1 && ln.size() > 1) {  // remove the last node
            ln[ln.size() - 2]->next = nullptr;
            return head;
        } else if (n == ln.size()) {  // remove the first node
            return head->next;
        }
        ln[ln.size() - n - 1]->next = ln[ln.size() - n + 1];  // remove the middle node
        return head;
    }
};

/**

* 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* removeNthFromEnd(ListNode* head, int n) {

vector<ListNode*> ln; // store all nodes to vector

ListNode* p = head;

while (p) {

ln.push_back(p);

p = p->next;

}

if (n == 1 && ln.size() > 1) { // remove the last node

ln[ln.size() - 2]->next = nullptr;

return head;

} else if (n == ln.size()) { // remove the first node

return head->next;

}

ln[ln.size() - n - 1]->next = ln[ln.size() - n + 1]; // remove the middle node

return head;

}

};

技术

11. 盛最多水的容器

Posted on 2022-06-13 by aspirer

题目链接：https://leetcode.cn/problems/container-with-most-water/

这道题，也是只能想到最笨的方法，两层循环，复杂度最高，所以提交之后就提示运行超时。。。。

等我研究官方题解再来更新吧。。。

已更新，官方的双指针法，关键是移动左右两边哪个X轴坐标，这里选的是Y轴低的，这样才有可能补偿X轴（也就是底边）减少1导致的面积缩小问题：

class Solution {
public:
/*  暴力搜索法
    int maxArea(vector<int>& height) {
        int area = 0;
        for (int i = 0; i < height.size(); i++) {
            for (int j = i + 1; j < height.size(); j++) {
                int newarea = (j - i) * min(height[i], height[j]);
                area = max(area, newarea);
            }
        }
        return area;
    }
*/
    int maxArea(vector<int>& height) {
        int area = 0;
        int i = 0, j = height.size() - 1;
        while (i < j) {
            area = max(area, (j - i) * min(height[i], height[j]));
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return area;
    }
};

class Solution {

public:

/* 暴力搜索法

int maxArea(vector<int>& height) {

int area = 0;

for (int i = 0; i < height.size(); i++) {

for (int j = i + 1; j < height.size(); j++) {

int newarea = (j - i) * min(height[i], height[j]);

area = max(area, newarea);

}

return area;

}

int maxArea(vector<int>& height) {

int area = 0;

int i = 0, j = height.size() - 1;

while (i < j) {

area = max(area, (j - i) * min(height[i], height[j]));

if (height[i] < height[j]) {

i++;

} else {

j--;

}

return area;

}

};

技术

20. 有效的括号

Posted on 2022-06-13 by aspirer

题目链接：https://leetcode.cn/problems/valid-parentheses/submissions/

这道题也没做出来，因为没有想到用栈来保存括号的对应关系，而是想着用递归判断子串是否是左右匹配的括号。看了官方题解才想明白，汗！！！

class Solution {
public:
    bool isValid(string s) {
        if (s.length() % 2 == 1) {
            return false;
        }

        unordered_map<char, char> mp = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };

        stack<char> st;
        for (int i = 0; i < s.length(); i++) {
            char c = s[i];
            if (mp.count(c)) {   // 'c' is a close bracket character
                if (st.empty() || st.top() != mp[c]) {  // if stack top can not match the new character, means can not close the bracket
                    return false;
                } else {    // close the bracket, pop it
                    st.pop();
                }
            } else {    // 'c' is a new open bracket character, push it
                st.push(c);
            }
        }

        return st.empty();
    }
};

class Solution {

public:

bool isValid(string s) {

if (s.length() % 2 == 1) {

return false;

}

unordered_map<char, char> mp = {

{')', '('},

{']', '['},

{'}', '{'}

};

stack<char> st;

for (int i = 0; i < s.length(); i++) {

char c = s[i];

if (mp.count(c)) { // 'c' is a close bracket character

if (st.empty() || st.top() != mp[c]) { // if stack top can not match the new character, means can not close the bracket

return false;

} else { // close the bracket, pop it

st.pop();

}

} else { // 'c' is a new open bracket character, push it

st.push(c);

}

return st.empty();

}

};

技术

5. 最长回文子串

Posted on 2022-06-09 by aspirer

题目链接：https://leetcode.cn/problems/longest-palindromic-substring/

下面这个解法理论上应该是正确的，暴力搜索法，但是实际上提交上去就会提示执行超时，因为真的是太费时间了。

等我研究下官方题解里面的高级算法再来重写一个吧，汗!!!

感觉自己就是个渣渣。。。。。。。。

ps. 已更新了中心扩展法实现。

class Solution {
public:
    /* 暴力搜索法，时间复杂度太高，提交会提示运行超时！
    bool isPalindrome(string sub) {
        int i = 0, j = sub.length() - 1;
        while (i < j) {
            if (sub[i++] != sub[j--]) {
                return false;
            }
        }
        return true;
    }

    string longestPalindrome(string s) {
        int i, j;
        int start = 0, end = 0;
        for (i = 0; i < s.length(); i++) {
            for (j = s.length() - 1; j > i; j--) {
                string substr = s.substr(i, j - i + 1);
                if (isPalindrome(substr)) {
                    if (j - i > end - start) {
                        start = i;
                        end = j;
                        break;
                    }
                }
            }
        }

        return s.substr(start, end - start + 1);
    }
    */

    // 中心扩展法，仔细研究一下感觉原理还是比较容易理解的，
    // 就是分两种情况，奇数和偶数长度的子串，分别尝试向两边扩展，直到不是回文串就结束这个中心点的扩展
    pair<int, int> expandCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        return {left + 1, right - 1};
    }

    string longestPalindrome(string s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            auto [left1, right1] = expandCenter(s, i, i);
            auto [left2, right2] = expandCenter(s, i, i + 1);
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};

class Solution {

public:

/* 暴力搜索法，时间复杂度太高，提交会提示运行超时！

bool isPalindrome(string sub) {

int i = 0, j = sub.length() - 1;

while (i < j) {

if (sub[i++] != sub[j--]) {

return false;

}

return true;

}

string longestPalindrome(string s) {

int i, j;

int start = 0, end = 0;

for (i = 0; i < s.length(); i++) {

for (j = s.length() - 1; j > i; j--) {

string substr = s.substr(i, j - i + 1);

if (isPalindrome(substr)) {

if (j - i > end - start) {

start = i;

end = j;

break;

}

return s.substr(start, end - start + 1);

}

// 中心扩展法，仔细研究一下感觉原理还是比较容易理解的，

// 就是分两种情况，奇数和偶数长度的子串，分别尝试向两边扩展，直到不是回文串就结束这个中心点的扩展

pair<int, int> expandCenter(const string& s, int left, int right) {

while (left >= 0 && right < s.length() && s[left] == s[right]) {

left--;

right++;

}

return {left + 1, right - 1};

}

string longestPalindrome(string s) {

int start = 0, end = 0;

for (int i = 0; i < s.length(); i++) {

auto [left1, right1] = expandCenter(s, i, i);

auto [left2, right2] = expandCenter(s, i, i + 1);

if (right1 - left1 > end - start) {

start = left1;

end = right1;

}

if (right2 - left2 > end - start) {

start = left2;

end = right2;

}

return s.substr(start, end - start + 1);

}

};

技术

8. 字符串转换整数 (atoi)

Posted on 2022-06-09 by aspirer

题目链接：https://leetcode.cn/problems/string-to-integer-atoi/

class Solution {
public:
    int myAtoi(string s) {
        if (s == "") {
            return 0;
        }

        bool start = false;
        bool negative = false;
        long res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ' ') {
                if (!start) {
                    continue;
                } else {
                    break;
                }
                
            }
            if (s[i] == '-' || s[i] == '+') {
                if (!start) {
                    if (s[i] == '-') {
                        negative = true;
                    }
                    start = true;
                    continue;
                } else {
                    break;
                }
            }
            if (s[i] >= '0' && s[i] <= '9') {
                if (!start) {
                    start = true;
                }
                res = res * 10 + (s[i] - '0');
                if (res >= 1l<<31) {
                    res = (1l<<31);
                    break;
                }
                continue;
            } else {
                break;
            }

        }
        if (negative) {
            res = -res;
        }
        if (res <= -(1l<<31) - 1) {
            res = -(1l<<31) - 1;
        }
        if (res >= ((1l<<31) - 1)) {
            res = ((1l<<31) - 1);
        }
        return (int)res;
    }
};

class Solution {

public:

int myAtoi(string s) {

if (s == "") {

return 0;

}

bool start = false;

bool negative = false;

long res = 0;

for (int i = 0; i < s.length(); i++) {

if (s[i] == ' ') {

if (!start) {

continue;

} else {

break;

}

if (s[i] == '-' || s[i] == '+') {

if (!start) {

if (s[i] == '-') {

negative = true;

}

start = true;

continue;

} else {

break;

}

if (s[i] >= '0' && s[i] <= '9') {

if (!start) {

start = true;

}

res = res * 10 + (s[i] - '0');

if (res >= 1l<<31) {

res = (1l<<31);

break;

}

continue;

} else {

break;

}

if (negative) {

res = -res;

}

if (res <= -(1l<<31) - 1) {

res = -(1l<<31) - 1;

}

if (res >= ((1l<<31) - 1)) {

res = ((1l<<31) - 1);

}

return (int)res;

}

};

技术

21. 合并两个有序链表

Posted on 2022-06-08 by aspirer

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/

刚开始思路有点乱，搞了快一个小时还是有错误，原因是我想把list1的node遍历一遍，按大小插入到list2，同时list2也要跟着一起遍历，这样就很难控制两个链表遍历的顺序和位置。

后来折腾很久都合并不好，就重头考虑了一把，感觉只需要把两个链表中比较小的那个node放到merged链表里就行了，谁的node被移动了，就跳到下一个node继续跟另一个链表的node比较大小，没有被移动到链表node位置不变，继续用来下一次比较，这样一来就简单多了，就是单链表的尾部插入操作了。

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1 && !list2) {     // two empty lists
            return nullptr;
        } else if (!list1) {        // list1 is empty
            return list2;
        } else if (!list2) {        // list2 is empty
            return list1;
        }

        ListNode* head = nullptr;   // for returning merged list
        ListNode* p = nullptr;      // for adding new node
        ListNode* move = nullptr;   // for moving node from list1 or list2
        while (list1 && list2) {
            if (list1->val < list2->val) {  // move the small node
                move = list1;
                list1 = list1->next;
            } else {
                move = list2;
                list2 = list2->next;
            }

            if (head == nullptr) {  // first node
                head = move;
                p = head;
            } else {                // add the move node to merged list
                p->next = move;
                p = p->next;
            }
        }

        // move the residual nodes
        move = list1 ? list1 : list2;
        p->next = move;
        return head;
    }
};

/**

* 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* mergeTwoLists(ListNode* list1, ListNode* list2) {

if (!list1 && !list2) { // two empty lists

return nullptr;

} else if (!list1) { // list1 is empty

return list2;

} else if (!list2) { // list2 is empty

return list1;

}

ListNode* head = nullptr; // for returning merged list

ListNode* p = nullptr; // for adding new node

ListNode* move = nullptr; // for moving node from list1 or list2

while (list1 && list2) {

if (list1->val < list2->val) { // move the small node

move = list1;

list1 = list1->next;

} else {

move = list2;

list2 = list2->next;

}

if (head == nullptr) { // first node

head = move;

p = head;

} else { // add the move node to merged list

p->next = move;

p = p->next;

}

// move the residual nodes

move = list1 ? list1 : list2;

p->next = move;

return head;

}

};

技术

14. 最长公共前缀

Posted on 2022-06-07 by aspirer

题目链接：https://leetcode.cn/problems/longest-common-prefix/

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int len = strs[0].length();
        auto iter = strs.begin();
        // get the length of shortest string
        for (; iter != strs.end(); iter++) {
            if (len > (*iter).length()) {
                len = (*iter).length();
            }
        }

        int strpos = 0;     // for walk through the string
        int vpos = 0;       // for walk through the vector
        int vlen = strs.size();
        bool stop = false;  // find a different char between strings
        for(; strpos < len; strpos++) {
            vpos = 0;
            char s = strs[vpos][strpos];
            for (; vpos < vlen; vpos++) {
                if (s != strs[vpos][strpos]) {
                    stop = true;
                    break;
                }
            }
            if (stop) {
                break;
            }
        }

        // append to new string base on the longest substring position
        string prefix;
        prefix.append(strs[0], 0, strpos);
        return prefix;
    }
};

class Solution {

public:

string longestCommonPrefix(vector<string>& strs) {

int len = strs[0].length();

auto iter = strs.begin();

// get the length of shortest string

for (; iter != strs.end(); iter++) {

if (len > (*iter).length()) {

len = (*iter).length();

}

int strpos = 0; // for walk through the string

int vpos = 0; // for walk through the vector

int vlen = strs.size();

bool stop = false; // find a different char between strings

for(; strpos < len; strpos++) {

vpos = 0;

char s = strs[vpos][strpos];

for (; vpos < vlen; vpos++) {

if (s != strs[vpos][strpos]) {

stop = true;

break;

}

if (stop) {

break;

}

// append to new string base on the longest substring position

string prefix;

prefix.append(strs[0], 0, strpos);

return prefix;

}

};

技术

7. 整数反转

Posted on 2022-06-07 by aspirer

题目链接：https://leetcode.cn/problems/reverse-integer/

这个题目关键点在于反转后的数字是否越界（超出int型范围），而且还不能用long型来判断是否越界（不能存储64位整型），这个判断条件我不了解，没有推导出来（(rev < INT_MIN / 10 || rev > INT_MAX / 10)），所以最后提交之后用例有几个没通过。下面这个是看了官方题解写出来的。

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        int digit = 0;
        while (x != 0) {
            if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
                return 0;
            }
            digit = x % 10;
            x = x / 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
};

class Solution {

public:

int reverse(int x) {

int rev = 0;

int digit = 0;

while (x != 0) {

if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {

return 0;

}

digit = x % 10;

x = x / 10;

rev = rev * 10 + digit;

}

return rev;

}

};

我原来的思路（错误代码，输入x=1534236469时用例执行失败）：

ps. 为啥要先转换成字符串之后再转回整数，主要是想尝试不同的解法（这道题跟之前回文数判断的题目有点类似，之前用了取模、除10得到最后一位数字的方法，这次想尝试另外的解法：http://aspirer.wang/?p=1585）

class Solution {
public:
    int reverse(int x) {
        if (x == 0) {
            return 0;
        }

        char str[16] = {0};
        char rev[16] = {0};
        char* p = str;
        snprintf(str, 16, "%d", x);
        int len = strlen(str);
        if (x < 0) {
            int i = 0;
            rev[i] = '-';
            i++;
            while (len > 1) {
                rev[i] = str[len - 1];
                len--;
                i++;
            }
            return atoi(rev);
        } else {
            int i = 0;
            while (len > 0) {
                rev[i] = str[len - 1];
                len--;
                i++;
            }
            return atoi(rev);
        }
    }
};

class Solution {

public:

int reverse(int x) {

if (x == 0) {

return 0;

}

char str[16] = {0};

char rev[16] = {0};

char* p = str;

snprintf(str, 16, "%d", x);

int len = strlen(str);

if (x < 0) {

int i = 0;

rev[i] = '-';

i++;

while (len > 1) {

rev[i] = str[len - 1];

len--;

i++;

}

return atoi(rev);

} else {

int i = 0;

while (len > 0) {

rev[i] = str[len - 1];

len--;

i++;

}

return atoi(rev);

}

};

技术

450. 删除二叉搜索树中的节点

Posted on 2022-06-06 by aspirer

题目链接：https://leetcode.cn/problems/delete-node-in-a-bst/

这个题目自己没做出来，看的官方题解，最后一步successor找到之后再删除最后返回新的root这段没怎么看明白。

/**
 * 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* deleteNode(TreeNode* root, int key) {
        if (!root) {
            return nullptr;
        }

        if (root->val > key) {
            root->left = deleteNode(root->left, key);
            return root;
        }

        if (root->val < key) {
            root->right = deleteNode(root->right, key);
            return root;
        }

        if (root->val == key) {
            if (!root->left && !root->right) {
                return nullptr;
            }
            
            if (!root->left) {
                return root->right;
            }

            if (!root->right) {
                return root->left;
            }

            TreeNode* successor = root->right;
            while (successor->left) {
                successor = successor->left;
            }
            root->right = deleteNode(root->right, successor->val);
            root->val = successor->val;
            return root;
        }
        return root;
    }
};

/**

* 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* deleteNode(TreeNode* root, int key) {

if (!root) {

return nullptr;

}

if (root->val > key) {

root->left = deleteNode(root->left, key);

return root;

}

if (root->val < key) {

root->right = deleteNode(root->right, key);

return root;

}

if (root->val == key) {

if (!root->left && !root->right) {

return nullptr;

}

if (!root->left) {

return root->right;

}

if (!root->right) {

return root->left;

}

TreeNode* successor = root->right;

while (successor->left) {

successor = successor->left;

}

root->right = deleteNode(root->right, successor->val);

root->val = successor->val;

return root;

}

return root;

}

};