Sakamoto

leetcode

发布于 2020-08-24 评论

1. 两数之和#

执行用时：12 ms
内存消耗：8.3 MB

vector<int> twoSum(vector<int> &num, int target) {
    unordered_map<int, int> numMap;

    int i = 0;
    for (; i < num.size(); i++) {
        numMap[num[i]] = i;
    }

    for (i = 0; i < num.size(); i++) {
        if (numMap.find(target - num[i]) != numMap.end() && numMap[target - num[i]] != i) {
            return {i, numMap[target - num[i]]};
        }
    }

    return {};
}

9. 回文数#

执行用时：12 ms
内存消耗：6.1 MB

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        } else {
            std::string a = std::to_string(x);

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

            while (i < j) {
                if (a[i++] != a[j--]) {
                    return false;
                }
            }

            return true;
        }
    }
};

13. 罗马数字转整数#

这题回来要优化

执行用时：40 ms
内存消耗：7.9 MB

int romanToInt(string s) {
    unordered_map<char, int> roma = {
        {'I', 1}, {'V', 5}, {'X', 10},
        {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}
    };

    int ans = 0;

    int i;
    for (i = s.size() - 1; i >= 1; i--) {
        if (roma[s[i]] > roma[s[i - 1]]) {
            ans += roma[s[i]] - roma[s[i - 1]];
            i--;
        } else {
            ans += roma[s[i]];
        }
    }

    if (i == 0) ans += roma[s[0]];

    return ans;
}

14. 最长公共前缀#

执行用时：0 ms
内存消耗：6.7 MB

string longestCommonPrefix(vector<string>& strs) {
    string res = "";

    if (strs.empty()) return res;

    for (int j = 0; j < strs[0].length(); j++) {
        for (int i = 1; i < strs.size(); i++) {
            if (strs[i][j] != strs[i - 1][j] || j > strs[i - 1].size() || j > strs[i].size()) {
                return res;
            }
        }

        res.push_back(strs[0][j]);
    }

    return res;
}

20. 有效的括号#

太菜了，没找准约束条件改了好几次。。。

大致就是利用栈先进后出的特性模拟下对称性

执行用时：0 ms
内存消耗：6.3 MB

bool isValid(string s) {
    int start = 0, end = s.size();
    if (end == 0) return true;
    if (end & 1 == 1) return false;

    stack<char> bracks;
    char ch;
    while (start != end) {
        ch = s.at(start);
        start++;
        switch (ch) {
            case '{':
            case '[':
            case '(':
                bracks.push(ch);
                break;

            case ')':
                if (!bracks.empty() && bracks.top() == '(') {
                    bracks.pop();
                } else {
                    return false;
                }
                break;

            case ']':
                if (!bracks.empty() && bracks.top() == '[') {
                    bracks.pop();
                } else {
                    return false;
                }
                    break;

            case '}':
                if (!bracks.empty() && bracks.top() == '{') {
                    bracks.pop();
                } else {
                    return false;
                }
                break;

            default:
                break;
        }
    }

    if (!bracks.empty()) return false;

    return true;
    }

21. 合并两个有序链表#

算是用空间换时间了

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode *nl = new ListNode(-1);
    ListNode *start = nl;
    while (l1 != nullptr && l2 != nullptr) {
        if (l1 -> val < l2 -> val) {
            start -> next = l1;
            l1 = l1 -> next;
        } else {
            start -> next = l2;
            l2 = l2 -> next;
        }

        start = start -> next;
    }

    if (l1 != nullptr) {
        start -> next = l1;
    } else {
        start -> next = l2;
    }

    return nl -> next;
}

26. 删除排序数组中的重复项#

执行用时：12 ms
内存消耗：7.5 MB

int removeDuplicates(vector<int>& nums) {
    int resize = 1, biao = 0;
    int len = nums.size();

    if (len == 0) return 0;
    if (len == 1) return 1;

    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] == nums[biao]) {
            continue;
        }
        else {
            nums[resize] = nums[i];
            resize++;
            biao = i;
        }
    }
    return resize;
}

35. 搜索插入位置#

二分查找

执行用时：8 ms
内存消耗：6.5 MB

int searchInsert(vector<int>& nums, int target) {
    int start = 0, end = nums.size() - 1, mid;

    if (nums.size() == 0) return 0;

    while (start <= end) {
        mid = (end + start) >> 1;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }

    }
    return start;
}

58. 最后一个单词的长度#

执行用时：0 ms
内存消耗：6.5 MB

int lengthOfLastWord(string s) {
    if (s.empty()) return 0;

    // 清除末尾的空格
    s.erase(0,s.find_first_not_of(" "));
    s.erase(s.find_last_not_of(" ") + 1);

    // 切换到第一个字母上
    auto sptr = s.rbegin();
    if (*sptr == ' ') sptr++;

    int len = 0;

    // 在开头或空格前结束函数
    for (; sptr != s.rend(); sptr++) {
        if (*sptr == ' ') break;
        else len++;
    }

    return len;
}

66. 加一#

执行用时：4 ms
内存消耗：8.9 MB

vector<int> plusOne(vector<int>& digits) {
    int len = digits.size() - 1;
    digits[len] += 1;

    if (digits[len] != 10) {
        return digits;
    } else {
        for (int i = len; i >= 1; i--) {
            if (digits[i] == 10) {
                digits[i] -= 10;
                digits[i - 1] += 1;
            }
        }

        if (digits[0] == 10) {
            digits[0] -= 10;
            digits.insert(digits.begin(), 1);
        }
    }
    return digits;
}

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

执行用时：83 ms
内存消耗：17.7 MB

ListNode* deleteDuplicates(ListNode* head) {
    if (head == NULL) return head;

    int tmpNum = head -> val;

    ListNode *tmp = head;
    while (tmp -> next != NULL) {
        if (tmpNum == tmp -> next -> val) {
            tmp -> next = tmp -> next -> next;
        } else {
            tmpNum = tmp -> next -> val;
            tmp = tmp -> next;
        }
    }

    return head;
}

100. 相同的树#

树这玩意递归就完事了

执行用时 4 ms
内存消耗：9.9 MB

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;

    if (p == nullptr || q == nullptr) return false;
    if (p -> val != q -> val) return false;

    return isSameTree(p -> left, q -> left) && isSameTree(p -> right, q-> right);
}

101. 对称二叉树#

和上一题差不多，同时比较左右就可以了

执行用时：4 ms
内存消耗：12.4 MB

bool isSymmetric(TreeNode* root) {
    if (!root) return true;

    return isSym(root, root);
}

bool isSym(TreeNode *l, TreeNode *r) {
    if (!l && !r) return true;

    if (l == NULL || r == NULL) return false;
    if (l -> val != r -> val) return false;

    return isSym(l -> left, r -> right) && isSym(l -> right, r -> left);
}

118. 杨辉三角#

执行用时：0 ms
内存消耗：6.6 MB

vector<vector<int>> generate(int numRows) {
    if (numRows == 0) return {};

    vector<vector<int> > ans(numRows, vector<int>(0));
    int layers = 1;

    for (int i = 1; i <= numRows; i++) {
        ans[i - 1].resize(i);
    }

    while (layers <= numRows) {
        for (int i = 0; i < layers; i++) {
            if (i == 0 || i == layers - 1) {
                ans[layers - 1][i] = 1;
            } else {
                ans[layers - 1][i] += ans[layers - 2][i] + ans[layers - 2][i - 1];
            }
        }

        layers++;
    }

    return ans;
}

459. 重复的子字符串#

执行用时：56 ms
内存消耗：17.7 MB

bool repeatedSubstringPattern(string s) {
    int len = s.size();
    if (len <= 1) return false;

    bool flag = false;
    for (int gaps = 1; gaps <= len / 2; gaps ++) {
        if (len % gaps != 0) continue;

        string basic = s.substr(0, gaps);
        for (int i = gaps; i < len; i += gaps) {
            string p = s.substr(i, gaps);

            if (p != basic) {
                break;
            } else if (p == basic && (i + gaps) != len) {
                continue;
            } else {
                flag = true;
            }
        }
    }
    return flag;
}

1480. 一维数组的动态和#

执行用时：4 ms
内存消耗：8.7 MB

vector<int> runningSum(vector<int>& nums) {
    for (int i = 1; i < nums.size(); i++) {
            nums[i] += nums[i - 1];
    }

    return nums;
}