统计词频

问题描述

写一个 bash 脚本以统计一个文本文件 words.txt 中每个单词出现的频率。

为了简单起见，你可以假设：
words.txt只包括小写字母和 ' ' 。
每个单词只由小写字母组成。
单词间由一个或多个空格字符分隔。

示例:
假设 words.txt 内容如下：
the day is sunny the the
the sunny is is
你的脚本应当输出（以词频降序排列）：
the 4
is 3
sunny 2
day 1

说明:
不要担心词频相同的单词的排序问题，每个单词出现的频率都是唯一的。
你可以使用一行 Unix pipes 实现吗？

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

思路

本题先用cat命令和管道命令|将文件内容传给awk。

在awk中我们用一个字典(?)count储存每个单词的词频，先遍历每一行(awk自身机制)的每一个字段(i<=NF)，然后用该字段本身作为key,将其value++；最后用一个for循环输出count数组中的每个元素的key(词)及其value(词频)。

最后用|管道命令传给sort命令：

-r是倒序排序，相当于DESC
-n是将字符串当作numeric数值排序
-k则指定用于排序的字段位置，后跟2指将第二位的countk作为排序的key

作者：gao-si-huang-bu
链接：https://leetcode-cn.com/problems/two-sum/solution/awksort-by-gao-si-huang-bu/

题解

cat words.txt | awk '{ for(i=1;i<=NF;i++){count[$i]++} } END { for(k in count){print k" "count[k]} }' | sort -rnk 2

分数排名

问题描述

编写一个 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();
    }
};