分数排名

问题描述

编写一个 SQL 查询来实现分数排名。如果两个分数相同，则两个分数排名（Rank）相同。请注意，平分后的下一个名次应该是下一个连续的整数值。换句话说，名次之间不应该有“间隔”。

+----+-------+
| Id | Score |
+----+-------+
| 1  | 3.50  |
| 2  | 3.65  |
| 3  | 4.00  |
| 4  | 3.85  |
| 5  | 4.00  |
| 6  | 3.65  |
+----+-------+

例如，根据上述给定的 Scores 表，你的查询应该返回（按分数从高到低排列）：

+-------+------+
| Score | Rank |
+-------+------+
| 4.00  | 1    |
| 4.00  | 1    |
| 3.85  | 2    |
| 3.65  | 3    |
| 3.65  | 3    |
| 3.50  | 4    |
+-------+------+

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rank-scores

思路

对于a表中的每一个分数score，找出b表中有多少个大于或等于该分数的不同的分数，然后按降序排列

题解

select 
    a.Score as score , 
    (select count(distinct b.Score) from Scores b where b.Score >=a.Score) as rank
from Scores a order by Score DESC;

作者：zazalumonster
链接：https://leetcode-cn.com/problems/two-sum/solution/mysqlbi-jiao-hao-li-jie-de-yi-chong-xie-fa-by-zaza/

二叉搜索树迭代器

问题描述

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：

BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
 
提示：
next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search-tree-iterator

思路

复杂度没满足要求...

• 因为二叉树是搜索二叉树，所以中序遍历的顺序即为从小到大的顺序。
• 设置一个全局变量的指针，指向下一个最小的数。
• 对于bool hasNEXT（）这一函数，当指针指向vec最后一个元素的下一个时，才return false，否则返回true即可。

题解

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class BSTIterator {
private:
    vector<int> vec;
    int location;
public:
    void inorder(TreeNode *node){
        if(node == nullptr){
            return ;
        }
        inorder(node->left);
        vec.push_back(node->val);
        inorder(node->right);
    }
    BSTIterator(TreeNode* root) {
        inorder(root);
        location=0;
    }

    /** @return the next smallest number */
    int next() {
        if(location<vec.size()){
            return vec[location++];
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        if(location>=vec.size()){
            return false;
        } else return true;
    }
};

分数到小数

问题描述

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

示例 1:
输入: numerator = 1, denominator = 2
输出: "0.5"

示例 2:
输入: numerator = 2, denominator = 1
输出: "2"

示例 3:
输入: numerator = 2, denominator = 3
输出: "0.(6)"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fraction-to-recurring-decimal

思路

在小数部分如果出现两次除数相同的情况即说明是循环小数.
来源：https://leetcode-cn.com/problems/fraction-to-recurring-decimal/solution/li-yong-hashbiao-ding-wei-xun-huan-by-just_coding/

题解

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        string ret;
        if (denominator == 0) return ret;
        if (numerator == 0) return "0";
        long long num = numerator;
        long long denom = denominator;

        if (num < 0 && denom > 0 || num > 0 && denom < 0) {
            ret += "-";
        }
        num = abs(num);
        denom = abs(denom);

        ret += to_string(num / denom);
        num = num % denom;

        if (num != 0) {
            ret += ".";
        }
        map<long long, int> table;
        int index = 0;
        while (num != 0 && table.find(num) == table.end()) {
            table[num] = index++;
            num *= 10;
            ret += to_string(num / denom);
            num %= denom;
        }
        if (table.find(num) != table.end()) {
            ret += "()";
            int cur = ret.size() - 2;
            while (index-- > table[num]) {
                swap(ret[cur], ret[cur - 1]);
                --cur;
            }
        }
        return ret;
    }
};

逆波兰表达式求值

问题描述

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9

示例 2：
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6

示例 3：
输入: ["10", "6", "9", "3", "+", "-11", "", "/", "", "17", "+", "5", "+"]
输出: 22
解释:
((10 (6 / ((9 + 3) -11))) + 17) + 5
= ((10 (6 / (12 -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation

思路

本题的意思为，根据后缀表达式求值。

• 如果是数字就入栈
• 如果是运算符号的话，就弹出栈顶两个元素，并根据运算符做相应的运算
• 将运算结果入栈
• 最后栈内的唯一元素即为最终的结果

题解

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        stack<int> tmp;
        int n = tokens.size();
        for (int i = 0; i < n; i++) {
            if (tokens[i] == "+") {
                int tmp2 = tmp.top();
                tmp.pop();
                int tmp1 = tmp.top();
                tmp.pop();
                int sum = tmp1 + tmp2;
                tmp.push(sum);
            } else if (tokens[i] == "*") {
                int tmp2 = tmp.top();
                tmp.pop();
                int tmp1 = tmp.top();
                tmp.pop();
                int sum = tmp1 * tmp2;
                tmp.push(sum);
            } else if (tokens[i] == "-") {
                int tmp2 = tmp.top();
                tmp.pop();
                int tmp1 = tmp.top();
                tmp.pop();
                int sum = tmp1 - tmp2;
                tmp.push(sum);
            } else if (tokens[i] == "/") {
                int tmp2 = tmp.top();
                tmp.pop();
                int tmp1 = tmp.top();
                tmp.pop();
                int sum = tmp1 / tmp2;
                tmp.push(sum);
            } else {
                tmp.push(stoi(tokens[i]));
            }
        }
        return tmp.top();
    }
};

乘积最大子序列

问题描述

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray

思路

• 首先对特殊情况，num.size()==0||num.size()==1进行处理。如果nums为空，返回0；如果只有一个数，返回那个唯一的数即可。
• 当num.size()>=2时，初始化max=-∞，i从2开始，递增到n结束，j从i开始，递增到n结束。如此循环可以得出以nums[i]为开始的所有子序列的乘积。当子序列的乘积大于最大值时，令最大值等于子序列的乘积即可。

题解

class Solution {
public:
    int maxProduct(vector<int> &nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        else if(n==1){
            return nums[0];
        }
        int max = INT_MIN;
        int tmp;
        for (int i  = 0; i < n; i++) {
            tmp=1;
            for (int j =i; j < n; j++) {
                tmp = nums[j] * tmp;
                if (max < tmp) {
                    max = tmp;
                }
            }
        }
        return max;
    }
};