分数排名

问题描述

编写一个 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() 将返回二叉搜索树中的下一个最小的数。

示例：

二叉搜索树迭代器.png

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

分数到小数

作者: ireneliu
时间: 2019-07-29
分类: 数组
评论

分数到小数

问题描述

给定两个整数，分别表示分数的分子 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;
    }
};

逆波兰表达式求值

作者: ireneliu
时间: 2019-07-27
分类: 栈
评论

逆波兰表达式求值

问题描述

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

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

说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 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();
    }
};

乘积最大子序列

作者: ireneliu
时间: 2019-07-27
分类: 数组
1 条评论

乘积最大子序列

问题描述

给定一个整数数组 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]为开始的所有子序列的乘积。当子序列的乘积大于最大值时，令最大值等于子序列的乘积即可。

乘积最大子序列.png

题解

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

ireneliu 发布的文章

分数排名

分数排名

问题描述

思路

题解

二叉搜索树迭代器

二叉搜索树迭代器

问题描述

思路

题解

分数到小数

分数到小数

问题描述

思路

题解

逆波兰表达式求值

逆波兰表达式求值

问题描述

思路

题解

乘积最大子序列

乘积最大子序列

问题描述

思路

题解

最新文章

最近回复

分类

归档

其它