leetcode507-551

LeetCode 探索：发散你的思维

[507] 完美数

对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。

给定一个 整数 n， 如果他是完美数，返回 True，否则返回 False

解题思路：在 [1, sqrt(num)] 内从左往右迭代，依次求出num的因子，当 num % i == 0 时，num 的因子有两个：i 和 num / i，但注意当 i * i == num 时的情形，此时因子只有一个。

/*
 * @lc app=leetcode.cn id=507 lang=cpp
 *
 * [507] 完美数
 */

// @lc code=start
class Solution
{
public:

    bool checkPerfectNumber(int num)
    {
        if (num == 0)
            return false;
        int n = 0;
        for (int i = 1; i * i <= num; i++)
        {
            if (num % i == 0)
            {
                n += i;
                if (i * i != num)
                    n += num / i;
            }
        }
        return num == n;
    }

}; 
// @lc code=end

[509] 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。给定N，计算F(N)。

解题思路：递归

/*
 * @lc app=leetcode.cn id=509 lang=cpp
 *
 * [509] 斐波那契数
 */

// @lc code=start
class Solution
{
public:

    int fib(int N)
    {
        if (N == 0)
            return 0;
        if (N == 1)
            return 1;
        return fib(N - 1) + fib(N - 2);
    }

}; 
// @lc code=end

[520] 检测大写字母

给定一个单词，你需要判断单词的大写使用是否正确。

我们定义，在以下情况时，单词的大写用法是正确的：

• 全部字母都是大写，比如”USA”。
• 单词中所有字母都不是大写，比如”leetcode”。
• 如果单词不只含有一个字母，只有首字母大写， 比如 “Google”。
• 否则，我们定义这个单词没有正确使用大写字母。

解题思路：只需对大写字母进行计数即可

/*
 * @lc app=leetcode.cn id=520 lang=cpp
 *
 * [520] 检测大写字母
 */

// @lc code=start
class Solution
{
public:

    bool detectCapitalUse(string word)
    {
        int up = 0;
        int low = 0;
        for (char c : word)
        {
            if (isupper(c))
                up++;
            else
                low++;
        }
        return up == 0 || low == 0 || (up == 1 && isupper(word[0]));
    }

}; 
// @lc code=end

[521] 最长特殊序列 Ⅰ

给定两个字符串，你需要从这两个字符串中找出最长的特殊序列。最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。

子序列可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。

输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。

解题思路：当a和b相等时，此时不存在最长特殊序列，返回-1；当a和b的长度不相等时，较长字符串不可能是较短字符串的子串，因此最长特殊序列则为较长字符串本身。

/*
 * @lc app=leetcode.cn id=521 lang=cpp
 *
 * [521] 最长特殊序列 Ⅰ
 */

// @lc code=start
class Solution
{
public:

    int findLUSlength(string a, string b)
    {
        if (a == b)
            return -1;
        return max(a.length(), b.length());
    }

}; 
// @lc code=end

[530] 二叉搜索树的最小绝对差

给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。

/*
 * @lc app=leetcode.cn id=530 lang=cpp
 *
 * [530] 二叉搜索树的最小绝对差
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * }; 
 */

class Solution
{
public:

    void travel(TreeNode *root, int &pre, int &diff)
    {
        if (root == NULL)
            return;
        travel(root->left, pre, diff);
        if (pre >= 0)
            diff = min(diff, root->val - pre);
        pre = root->val;
        travel(root->right, pre, diff);
    }

    int getMinimumDifference(TreeNode *root)
    {
        int diff = INT32_MAX;
        int pre = -1;
        travel(root, pre, diff);
        return diff;
    }

}; 
// @lc code=end

[532] 数组中的K-diff数对

给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.

解题思路：利用set的元素唯一性的特性

/*
 * @lc app=leetcode.cn id=532 lang=cpp
 *
 * [532] 数组中的K-diff数对
 */

// @lc code=start
class Solution
{
public:

    int findPairs(vector<int> &nums, int k)
    {
        if (nums.size() == 0)
            return 0;
        set<pair<int, int>> sets;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 1; i++)
        {
            for (int j = i + 1; j < nums.size(); j++)
            {
                if (nums[i] + k == nums[j])
                {
                    sets.insert({nums[i], nums[j]});
                    break;
                }
            }
        }
        return sets.size();
    }

}; 
// @lc code=end

[538] 把二叉搜索树转换为累加树

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

解题思路：由BST的特性可知，右子树的值大于根节点的值，因此需要用到反序中序遍历，即先遍历右子树，后遍历根节点，最后遍历左子树，从右边开始累加起来，最后回溯的时候赋值。

/*
 * @lc app=leetcode.cn id=538 lang=cpp
 *
 * [538] 把二叉搜索树转换为累加树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * }; 
 */

class Solution
{
public:

    int sum = 0;

    //递归方法：反序中序遍历，即先遍历右子树，再遍历根节点，最后遍历左子树
    TreeNode *convertBST(TreeNode *root)
    {
        if (root == NULL)
            return root;
        convertBST(root->right);
        sum += root->val;
        root->val = sum;
        convertBST(root->left);
        return root;
    }

    //迭代方法：使用栈来对树进行回溯
    TreeNode *convertBST(TreeNode *root)
    {
        if (root == NULL)
            return root;
        stack<TreeNode *> st;
        TreeNode *node = root;
        while (!st.empty() || node != NULL)
        {
            while (node != NULL)
            {
                st.push(node);
                node = node->right;
            }
            node = st.top();
            st.pop();
            sum += node->val;
            node->val = sum;
            node = node->left;
        }
        return root;
    }

}; 
// @lc code=end

[541] 反转字符串 II

给定一个字符串和一个整数 k，你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。如果剩余少于 k 个字符，则将剩余的所有全部反转。如果有小于 2k 但大于或等于 k 个字符，则反转前 k 个字符，并将剩余的字符保持原样。

解题思路：只需要记录需要反转的子串的下标即可

/*
 * @lc app=leetcode.cn id=541 lang=cpp
 *
 * [541] 反转字符串 II
 */

// @lc code=start
class Solution
{
public:

    string reverseStr(string s, int k)
    {
        for (int i = 0; i * 2 * k < s.length(); i++)
        {
            int start = i * 2 * k;
            int temp = (i + 1) * 2 * k;
            int end = (temp + start) / 2;
            if (end > s.length())
                end = s.length();
            reverse(s.begin() + start, s.begin() + end);
        }
        return s;
    }

}; 
// @lc code=end

[543] 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

解题思路：任意一条路径可以被写成两个箭头（不同方向），每个箭头代表一条从某些点向下遍历到孩子节点的路径。假设我们知道对于每个节点最长箭头距离分别为 L, R，那么最优路径经过 L + R + 1 个节点。
按照常用方法计算一个节点的深度：max(depth of node.left, depth of node.right) + 1。在计算的同时，经过这个节点的路径长度为 1 + (depth of node.left) + (depth of node.right) 。搜索每个节点并记录这些路径经过的点数最大值count，期望长度是 count - 1。

/*
 * @lc app=leetcode.cn id=543 lang=cpp
 *
 * [543] 二叉树的直径
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * }; 
 */

class Solution
{
public:

    int dia = 0;

    int travel(TreeNode *node)
    {
        if (node == NULL)
            return 0;
        int L = travel(node->left);
        int R = travel(node->right);
        dia = max(dia, L + R + 1);
        return 1 + max(L, R);
    }

    int diameterOfBinaryTree(TreeNode *root)
    {
        if (root == NULL)
            return 0;
        travel(root);
        return dia - 1;
    }

}; 
// @lc code=end

[551] 学生出勤记录 I

给定一个字符串来代表一个学生的出勤记录，这个记录仅包含以下三个字符：

• ‘A’ : Absent，缺勤
• ‘L’ : Late，迟到
• ‘P’ : Present，到场
• 如果一个学生的出勤记录中不超过一个’A’(缺勤)并且不超过两个连续的’L’(迟到), 那么这个学生会被奖赏。

你需要根据这个学生的出勤记录判断他是否会被奖赏。

解题思路：首先记录A的数量，其次记录连续的L的数量，当遇到连续的L但其数量小于等于2时，将其置为0重新计数

/*
 * @lc app=leetcode.cn id=551 lang=cpp
 *
 * [551] 学生出勤记录 I
 */

// @lc code=start
class Solution
{
public:

    bool checkRecord(string s)
    {
        int A = 0;
        int L = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == 'A')
                A++;
            if (s[i] == 'L')
                L++;
            else if (L <= 2)
                L = 0;
        }
        return A <= 1 && L <= 2;
    }

}; 
// @lc code=end