820. 单词的压缩编码

Posted on 2020-09-15 by Longl Yang

给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

例如，如果这个列表是 [“time”, “me”, “bell”]，我们就可以将其表示为 S = “time#bell#” 和 indexes = [0, 2, 5]。

对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 “#” 结束，来恢复我们之前的单词列表。

那么成功对给定单词列表进行编码的最小字符串长度是多少呢？

示例：

输入: words = [“time”, “me”, “bell”]
输出: 10
说明: S = “time#bell#” ， indexes = [0, 2, 5] 。

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 7
每个单词都是小写字母 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/short-encoding-of-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        string ret;
        sort(words.begin(),words.end(),[&](string&a,string&b){return a.size()>b.size();});
        for (auto& s : words) {
            auto i = ret.find(s+"#", 0);
            if (i != string::npos) {
                continue;
            }
            else {
                ret.append(s);
                ret.append("#");
            }
        }
        return ret.size();
    }
};
Posted in leetcode | Leave a comment

性能测试（push_back,embrace_back,copy,move)

Posted on 2020-09-04 by Longl Yang

TL;DR (划到文章末尾）


#include<iostream>
#include<vector>
#include<ostream>
#include<Windows.h>

using namespace std;

class A {
public:
	int a;
	friend ostream& operator <<(ostream& out, A& a);
	A& operator=(int data);
	A(const A& a);
	A(int a);
	A() {}
};

A::A(int a) {
	cout << "new A with " << a << endl;
	this->a = a;
}

A::A(const A& a) {
	cout << "coping" << endl;
	this->a = a.a;
}

A& A::operator=(int data) {
	this->a = data;
	return *this;
}


ostream& operator<<(ostream& out, A& a) {
	out << a.a;
	return out;
}

int main() {

	DWORD t1, t2;
	t1 = GetTickCount();

	vector<A> arr;

	for (int i = 0; i < 10000; i++) {
		A a{ i };
		cout << "before push:" << arr.capacity() << endl;
		arr.push_back(a);
		cout << "after push:" << arr.capacity() << endl;
	}
	cout << "swap begin" << endl;
	iter_swap(arr.begin() + 1, arr.begin());
	cout << "swap end" << endl;
	for (int i = 0; i < 10; i++) {
		cout << arr[i];
	}

	t2 = GetTickCount();
	cout << endl <<  "time = " << ((t2 - t1) * 1.0 / 1000)<<"s" << endl; // seconds

	return 0;
}

结果：

after push:1
new A with 1
before push:1
coping
coping
after push:2
new A with 2
before push:2
coping
coping
coping
after push:3
new A with 3
before push:3
coping
coping
coping
coping
after push:4
new A with 4
before push:4
coping
coping
coping
coping
coping
after push:6
new A with 5
before push:6
coping
after push:6
new A with 6
before push:6
coping
coping
coping
coping
coping
coping
coping
after push:9
new A with 7
before push:9
coping
after push:9
new A with 8
before push:9
coping
after push:9
new A with 9
before push:9
coping
coping
coping
coping
coping
coping
coping
coping
coping
coping
after push:13
new A with 10
before push:13
coping
after push:13
new A with 11
before push:13
coping
after push:13
new A with 12
before push:13
coping
after push:13
new A with 13
before push:13
coping
…
after push:12138
new A with 9999
before push:12138
coping
after push:12138
swap begin
coping
swap end
1023456789
time = 14.203s

总结：
原程序所花费时间为：14.203s
把push_back改为embrace_back,其他不变，时间为：14.406s；比push_back稍慢。
把push_back(a)改为push_back(move(a))，其他不变，时间为：14.282s；仍然进行了copy
把push_back(a)改为push_back(i),其他不变，时间为：16.859s；
把push_back(a)改为push_back(i),删除A a{ i };其他不变，时间为：14.516s；
把vector arr;改为vector arr(10000);删除A a{ i };arr.push_back(a)改为arr[i] = i;其他不变，时间为9.922s；提升了30%，vector扩容太花时间了；

Posted in C++ | Tagged | Leave a comment

字符串分割

Posted on 2020-08-19 by Longl Yang

题目描述

•连续输入字符串，请按长度为8拆分每个字符串后输出到新的字符串数组；
•长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。

输入描述:

连续输入字符串(输入2次,每个字符串长度小于100)

输出描述:

输出到长度为8的新字符串数组

示例1

输入

abc
123456789

输出

abc00000
12345678
90000000
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<iomanip>
using namespace std;

int main() {

    string input;
    while (cin >> input) {
        if (input.size() <= 8) {
            cout << left << setw(8) << setfill('0') << input << endl;
            continue;
        }
        else {
            int diff = (8 - input.size() % 8) % 8;
            input.insert(input.size(), diff, '0');
            for (int i = 0; i < input.size() / 8; i++) {
                cout << string(input,i*8,8) << endl;
            }
        }
    }
    return 0;
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main() {

    char input[101] = { 0 };
    while (scanf("%s", input) != EOF) {
        int sz = strlen(input);
        if (sz <= 8) {
            printf("%s", input);
            for (int i = 0; i < 8 - sz; i++) {
                printf("%c", '0');
            }
            printf("\n");
        }
        else {
            int diff = (8 - sz % 8) % 8;
            for (int i = 0; i < sz; i++) {
                printf("%c", input[i]);
                if ((i+1) % 8 == 0 && i != 0) {
                    printf("\n");
                }
            }
            for (int i = 0; i < diff; i++) {
                printf("%c", '0');
            }
            if(diff!=0)printf("\n");
        }
    }
    return 0;
}
Posted in hwleetcode | Leave a comment

明明的随机数

Posted on 2020-08-19 by Longl Yang

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据，希望大家能正确处理)。

Input Param

n               输入随机数的个数

inputArray      n个随机整数组成的数组

Return Value

OutputArray    输出处理后的随机整数


注：测试用例保证输入参数的正确性，答题者无需验证。测试用例不止一组。 样例输入解释： 样例有两组测试 第一组是3个数字，分别是：2，2，1。 第二组是11个数字，分别是：10，20，40，32，67，40，20，89，300，400，15。

输入描述:

输入多行，先输入随机整数的个数，再输入相应个数的整数

输出描述:

返回多行，处理后的结果

示例1

输入

3
2
2
1
11
10
20
40
32
67
40
20
89
300
400
15

输出

1
2
10
15
20
32
40
67
89
300
400

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
    int count = 0;
    while (cin >> count) {
        vector<int> arr;
        for (int i = 0; i < count; i++) {
            int tmp;
            cin >> tmp;
            arr.emplace_back(tmp);
        }
        sort(arr.begin(), arr.end());
        arr.erase(unique(arr.begin(),arr.end()),arr.end());
        for (auto i : arr) {
            cout << i << endl;
        }

    }
    return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

int cmp(const void* a, const void* b) {
    return *(int*)a > *(int*)b;
}
int main() {
    int count = 0;
    while (scanf("%d", &count) != EOF) {
        int* arr = (int*)calloc(count, sizeof(int));
        for (int i = 0; i < count; i++) {
            scanf("%d", arr + i);
        }
        qsort(arr, count, sizeof(int), cmp);
        int output = -1;
        for (int i = 0; i < count; i++) {
            if (arr[i] != output) {
                output = arr[i];
                printf("%d\n", arr[i]);
            }
        }
        free(arr);
    }
}
Posted in hwleetcode | Leave a comment

计算字符个数

Posted on 2020-08-19 by Longl Yang

题目描述

写出一个程序，接受一个由字母和数字组成的字符串，和一个字符，然后输出输入字符串中含有该字符的个数。不区分大小写。

输入描述:

第一行输入一个有字母和数字以及空格组成的字符串，第二行输入一个字符。

输出描述:

输出输入字符串中含有该字符的个数。

示例1

输入

ABCDEF
A

输出

1
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int main(){
    string input;
    char c;
    getline(cin,input);
    cin>>c;
    if(c>='A'&&c<='Z'){
        c=c-'A'+'a';
    }
    int count=0;
    for(auto& it:input){
        if(it>='A'&&it<='Z'){
            it=it-'A'+'a';
        }
        if(it==c)count++;
    }
    cout<<count;    
    return 0;
}
#include<stdio.h>
#include<string.h>

int main(){
    char input[1025]={0};
    char c;
    gets(input);
    scanf("%c",&c);
    if(c>='A'&&c<='Z'){
        c=c-'A'+'a';
    }
    int size=strlen(input);
    int count=0;
    for(int i=0;i<size;i++){
        if(input[i]>='A'&&input[i]<='Z'){
            input[i]=input[i]-'A'+'a';
        }
        if(input[i]==c)count++;
    }
    printf("%d",count);
    return 0;
}
Posted in hwleetcode | Leave a comment

字符串最后一个单词的长度

Posted on 2020-08-19 by Longl Yang

题目描述

计算字符串最后一个单词的长度，单词以空格隔开。

输入描述:

一行字符串，非空，长度小于5000。

输出描述:

整数N，最后一个单词的长度。

示例1

输入

hello world

输出

5
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {

    string input;
    getline(cin, input);
    auto it = find(input.rbegin(), input.rend(), ' ');
    if (it == input.rend()) {
        cout << input.size();
        return 0;
    }
    cout << input.size()-distance(it,input.rend());
    return 0;
}
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {

    string input;
    getline(cin, input);
    auto index=input.rfind(' ');
    if (index == string::npos) {
        cout << input.size();
        return 0;
    }
    cout << input.size() - index - 1;
    return 0;
}
#include <stdio.h>
#include <string.h>

int main() {

	char input[5001] = { 0 };
	gets(input);

	int size=strlen(input);
	for (int i = size - 1; i >= 0; i--) {
		if (input[i] == ' ') {
			printf("%d", size - i - 1);
			return 0;
		}
	}
	printf("%d", size);
	return 0;
}
Posted in hwleetcode | Leave a comment

C++ memory layout(1)

Posted on 2020-08-19 by Longl Yang

TL;DR

  • 未初始化的全局变量储存在bss段
  • 未初始化的静态变量储存在bss段
  • 初始化的静态变量储存在data段（初始化为0还是在bss段）
  • 初始化的全局变量储存在data段（初始化为0还是在bss段）
  • 局部变量在程序运行时会在栈上分配空间，体现在text段里的初始化代码，所以初始化的局部变量会使的text段变大

#include<iostream>
using namespace std;

int main(){
    return 0;
}

long@DESKTOP-47UH3ST:~$ size ml
   text    data     bss     dec     hex filename
   1985     640       8    2633     a49 ml
#include<iostream>
using namespace std;

int global;

int main(){
    return 0;
}

long@DESKTOP-47UH3ST:~$ size ml
   text    data     bss     dec     hex filename
   1985     640      16    2641     a51 ml
#include<iostream>
using namespace std;

int global=0;

int main(){
    return 0;
}

long@DESKTOP-47UH3ST:~$ size ml
   text    data     bss     dec     hex filename
   1985     640      16    2641     a51 ml
#include<iostream>
using namespace std;

int global=1;

int main(){
    return 0;
}

long@DESKTOP-47UH3ST:~$ size ml
   text    data     bss     dec     hex filename
   1985     644       4    2633     a49 ml
#include<iostream>
using namespace std;

int main(){
    int local;
    return local;
}

long@DESKTOP-47UH3ST:~$ g++ ml.cpp -o ml && size ml
   text    data     bss     dec     hex filename
   1985     640       8    2633     a49 ml
#include<iostream>
using namespace std;

int main(){
    int local=0;
    return local;
}

long@DESKTOP-47UH3ST:~$ g++ ml.cpp -o ml && size ml
   text    data     bss     dec     hex filename
   2001     640       8    2649     a59 ml
#include<iostream>
using namespace std;

int main(){
    int local=1;
    return local;
}

long@DESKTOP-47UH3ST:~$ g++ ml.cpp -o ml && size ml
   text    data     bss     dec     hex filename
   2001     640       8    2649     a59 ml
#include<iostream>
using namespace std;

int main(){
    static int local;
    return local;
}

long@DESKTOP-47UH3ST:~$ g++ ml.cpp -o ml && size ml
   text    data     bss     dec     hex filename
   1985     640      16    2641     a51 ml
#include<iostream>
using namespace std;

int main(){
    static int local=0;
    return local;
}

long@DESKTOP-47UH3ST:~$ g++ ml.cpp -o ml && size ml
   text    data     bss     dec     hex filename
   1985     640      16    2641     a51 ml
#include<iostream>
using namespace std;

int main(){
    static int local=1;
    return local;
}

long@DESKTOP-47UH3ST:~$ g++ ml.cpp -o ml && size ml
   text    data     bss     dec     hex filename
   1985     644       4    2633     a49 ml
Posted in showmecode | Leave a comment

贝叶斯法则

Posted on 2020-08-17 by Longl Yang
Posted in Statistical Inference | Leave a comment

彩球抽球模型

Posted on 2020-08-17 by Longl Yang
Posted in Statistical Inference | Leave a comment

Bonferroni’s Inequality

Posted on 2020-08-17 by Longl Yang

应用场景，知道P(A),P(B)…P(N)，求不出他们的交的概率，可以用这个求出他们的交的bound。对负数也成立不过没意义。

Posted in Statistical Inference | Leave a comment