每日刷题计划Day2笔记-字符串+树

计算 a+b 并以标准格式输出总和----也就是说，从最低位开始每隔三位数加进一个逗号（千位分隔符），如果结果少于四位则不需添加。

输入格式
共一行，包含两个整数 a 和 b。

输出格式
共一行，以标准格式输出 a+b 的和。

数据范围 −106≤a,b≤106

输入样例：
-1000000 9

输出样例：
-999,991

#include 
using namespace std;

int main(){
    int a, b;
    cin>>a>>b;
    int c = a + b;
    string num = to_string(c);
    string res;
    for(int i = num.size() - 1, j=0; i>=0; i-- ){
        res = num[i] +res;
        j++;
        if( j % 3 == 0 && i && num[i-1] != '-' ) 
            res = ',' + res;
    }
    cout<< res < 
to_string()函数：把数字变为字符串。
 字符数字 - ‘0’ ：把字符变成数字。
 
循环条件是：if( j % 3 == 0 && i && num[i-1] != ‘-’ )
 每一次都是先把原字符串的当前位放进答案，然后(对于原字符串的这一位) 判断在当前答案的下一位上是否该放’,’
 三种情况：
 
 
j 是count答案的位数，每有3位，得加个′,′，即j % 3 == 0
  
如果和为负数，就不能在本来是‘-’的位置(也是num[0]的位置)写′,′，即原字符串的下一位也就是num[i - 1] != ’ ,’
  
i = 0 时整个字符串刚好结束，如果刚好是3倍，就不用再加′,′了（比如 -48 + 2）
 
 
题解参考：小张同学
 
1477. 拼写正确 
给定一个非负整数 N，你的任务是计算 N 的所有数字的总和，并以英语输出总和的每个数字。
 
输入格式
 共一行，包含一个整数 N。
 
输出格式
 共一行，用英语输出总和的每个数字，单词之间用空格隔开。
 
数据范围
 0≤N≤10100
 
 
 
输入样例： 12345
 输出样例： one five
 
 
#include 
using namespace std;
int main(){
    string n;
    cin>>n;
    
    int sum(0);
    for(int i=0; i < n.size(); i++)
        sum += n[i] - '0';
    string str = to_string(sum);
    char word[10][10] = {
         "zero", "one", "two", "three", "four",
        "five", "six", "seven", "eight", "nine",
    };
    cout << word[str[0]-'0'];
    for(int i = 1; i < str.size(); i++)
        cout << ' ' << word[str[i] - '0'];
    
    return 0;
}
 
此题先把string转化成int，再把int转化成string。怎么方便怎么来。int求和方便。string用某一位方便。
 
1478. 签到与签出 
每天第一个到机房的人负责开门，最后一个从机房离开的人负责锁门。
 
现在，给定每个人的签到与签出记录，请你找出当天开门的人以及锁门的人分别是谁。
 
输入格式
 第一行包含整数 M，表示共有 M 个人的签到签出记录。
 
接下来 M 行，每行的形式如下：
 
ID_number Sign_in_time Sign_out_time
 时间以 HH:MM:SS 形式给出，ID_number 是一个长度不超过 15 的字符串。
 
输出格式
 共一行，输出开门人和锁门人的ID_number，用一个空格隔开。
 
数据范围
 1≤M≤10,
 数据保证每个人的签到时间早于签出时间，并且不会出现两个人同时签到或同时签出的情况。
 
 
 
输入样例：
 3
 CS301111 15:30:28 17:00:10
 SC3021234 08:00:00 11:25:25
 CS301133 21:45:00 21:58:40
 输出样例：
 SC3021234 CS301133
 
 
直接想到了排序，但是这种题只要求最大值或最小值，不用排序，只需在输入时比较大小，记录下最大值或最小值即可。
 
#include
using namespace std;
int main(){
    //记录结果
    string open_id, open_time, close_id, close_time;
    int m;
    cin >> m;
    for(int i=0; i < m; i ++ ){
        string id, in_time, out_time;
        cin >> id >> in_time >> out_time;
        //更新开门的人
        if(!i || in_time < open_time){
            open_id = id;
            open_time = in_time;
        }
        //更新锁门的人
        if(!i || out_time > close_time){
            close_id = id;
            close_time = out_time;
        }
    }
    cout<< open_id << ' ' << close_id < 
这种题把第一个输入的值赋值给结果，然后与之后输入的值比较大小。用for(i=0;…) if(!i || …)形式很简洁。
 
题源：LeetCode 
14. 最长公共前缀 
编写一个函数来查找字符串数组中的最长公共前缀。
 
如果不存在公共前缀，返回空字符串 “”。
 
 
 
示例 1：
 输入：strs = [“flower”,“flow”,“flight”]
 输出：“fl”
 
 
 
 
示例 2：
 输入：strs = [“dog”,“racecar”,“car”]
 输出："" 解释：输入不存在公共前缀。
 
 
提示：
 
1 <= strs.length <= 200
 0 <= strs[i].length <= 200
 strs[i] 仅由小写英文字母组成
 
纵向扫描，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
 
class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        if (!strs.size()) {
            return "";
        }
        int length = strs[0].size();//第一个字符串的长度
        int count = strs.size();//字符串的总数量
        for (int i = 0; i < length; i++) {//遍历第一个字符串
            char c = strs[0][i];
            for (int j = 1; j < count; j++) {//遍历所有字符串
                if (i == strs[j].size() || strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};

 
复杂度分析
 
时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
 
空间复杂度：O(1)。使用的额外空间复杂度为常数。
 
102. 二叉树的层序遍历 
给你二叉树的根节点 root ，返回其节点值的层序遍历 。 （即逐层地，从左到右访问所有节点）。
 
 
 
输入：root = [3,9,20,null,null,15,7]
 输出：[[3],[9,20],[15,7]]
 
 
class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        vector > ret;
        if (!root) {
            return ret;
        }

        queue  q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();
            ret.push_back(vector  ());//vector  ()表示构造函数，每一层
            for (int i = 1; i <= currentLevelSize; i++) {
                auto node = q.front(); q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return ret;
    }
};

 
vector(向量): C++中的一种数据结构,确切的说是一个类.它相当于一个动态的数组,当程序员无法知道自己需要的数组的规模多大时,用其来解决问题可以达到最大节约空间的目的。
 
1、push_back 在数组的最后添加一个数据
 
2、pop_back 去掉数组的最后一个数据
 
3、at 得到编号位置的数据
 
4、begin 得到数组头的指针
 
5、end 得到数组的最后一个单元+1的指针
 
6、front 得到数组头的引用
 
7、back 得到数组的最后一个单元的引用
 
8、max_size 得到vector最大可以是多大
 
9、capacity 当前vector分配的大小
 
10、size 当前使用数据的大小
 
11、resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
 
12、reserve 改变当前vecotr所分配空间的大小
 
13、erase 删除指针指向的数据项
 
14、clear 清空当前的vector
 
15、rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
 
16、rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
 
17、empty 判断vector是否为空
 
18、swap 与另一个vector交换数据