发表更新学习8 分钟读完 (大约1204个字)

安大考研复试题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
有一个分数序列:2/1,3/2,5/3,8/5……求出这个数列的前n项之和.
*/
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int n=0;
    float sum=0;
    float a = 1.0;
    float b = 2.0;
    cin>>n;
    if(n<1||n>40)
        return 0;
    for(int i=0; i< n;i++){
        sum = sum + b/a;
        b = a + b;
        a = b - a;
    }
    cout<<sum<<endl;
    printf("%.6f",sum);
    return 0;
}

longestWord

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
#include <vector>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp> 
using namespace std;
int main(){
    char* str = new char[1000];
    string temp_str="";

    cin.getline(str,1000);


    temp_str = str;

    vector<string> ver_temp;
    boost::split(ver_temp,temp_str,boost::is_any_of(" "),boost::token_compress_on);
    //cout<<ver_temp.size()<<endl;
    for(vector<string>::iterator it=ver_temp.begin(); it != ver_temp.end();it++){
        //cout<<*it<<endl;
        for(int i=0; i <it->length();i++){
            (*it)[i] = tolower((*it)[i]);
        }
    }
    sort(ver_temp.begin(),ver_temp.end());

    string temp="";
    //cout<<"-----\n";
    for(int i=0; i<ver_temp.size();i++){
        //cout<<ver_temp[i]<<endl;
        
        if(ver_temp[i].length()>temp.length()){
            temp = ver_temp[i];
        }
    }
    cout<<temp<<endl;
    return 0;
}

2018

1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
 *第一题是斐波那契数列，给定一个函数： 
 *F(0)=0; F(1)=1; F(n)=F(n-1)+F(n-2),n>1
 *程序输入一个整数n,输入F(n)的值。
 *
 */

#include "iostream"
using namespace std;

int fri(int n)
{
	if(n==0)
		return 0;
	else if(n == 1)
		return 1;
	else
		return fri(n-2)+fri(n-1);

}
int main()
{
	for(int i=0;i<11;i++)
		cout<<fri(i)<<endl;
	return 0;
}

2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
/*================================================================
*   创建日期：2018年07月26日
*   描    述：
*
================================================================*/

#include <iostream>
#include "cstdio"
using namespace std;
typedef int ElemType;
#define MAXSIZE 100

struct sStack{
	ElemType data[MAXSIZE];
	int top;
};
typedef struct sStack seqStack;

void initial(seqStack &s){
	s.top = -1;
}
bool empty(seqStack &s){
	if(s.top == -1)
		return true;
	else
		return false;
}

ElemType top(seqStack S){
	if(empty(S))
		return -1;
	else
		return S.data[S.top];
}

bool full(seqStack S){
	if(S.top == MAXSIZE - 1)
		return true;
	else
		return false;
}
bool push(seqStack &S,ElemType x){
	if(full(S))
		return false;
	else{
		S.top++;
		S.data[S.top] = x;
		return true;
	}
}

ElemType pop(seqStack &S){
	if(empty(S))
		return -1;
	else
		return S.data[S.top--];
}
ElemType getBottomElemType(seqStack &S){
	if(empty(S))
		return -1;
	int x = -2;
	while(!empty(S)){
		x = S.data[S.top--];
	}
	return x;
}
void print(seqStack &S){
	while(empty(S)){
		cout<<pop(S)<<" ";
	}
	cout<<endl;
}
int main()
{
    int n =0;
    ElemType temp=0;

    seqStack fuck_s;
    initial(fuck_s);
    int test[3]={0};
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>test[i];
    }
    int i = 0;

    if(empty(fuck_s))
        push(fuck_s,test[i++]);
    cout<<top(fuck_s)<<endl;
    cout<<"----------\n";
    for(int i=1;i<n;i++)
    {
        if(top(fuck_s)>test[i]){
            pop(fuck_s);
            push(fuck_s,test[i]);

            cout<<"i-->"<<i<<" "<<test[i]<<endl;
        }
        else
            push(fuck_s,test[i]);

    }
    cout<<"========\n";
	while(!empty(fuck_s)){
		cout<<pop(fuck_s)<<"\n";
	}

//	ElemType test[10]={2,3,7};
//	ElemType temp;
//	seqStack fuck_s;
//	initial(fuck_s);
//	int i = 0;
//	int n = 0;
//	for(i = 0; i<3;i++)
//		push(fuck_s,test[i]);
//
//	//push(fuck_s,2);
//	cout<<"输入整数n: ";
//	cin>>temp;
//	while(!empty(fuck_s)){
//		if(top(fuck_s)>temp){
//			pop(fuck_s);
//			if(empty(fuck_s)){
//				push(fuck_s,temp);
//				break;
//			}
//		}
//		else{
//			push(fuck_s,temp);
//			break;
//		}
//		//cout<<pop(fuck_s)<<endl;
//	}
////	while(!empty(fuck_s)){
////		cout<<pop(fuck_s)<<"\n";
////	}
//	cout<<endl;
//	//print(fuck_s);
//	//cout<<top(fuck_s)<<endl;
	return 0;
}

3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*================================================================
*   创建日期：2018年07月27日
*   描    述：输入两个整数n，m每一次，第一个整数可以
*   		执行乘2,、减1、加1三种操作的任意一种，
*   		求n到m至少要多少次这样的操作。
*
================================================================*/


#include "iostream"
#include <cstdio>
#include <cstdlib>
using namespace std;

struct list{
    long n;
    int step;   //步数
    struct list *next;
};
int main(){
    long n,m,k;
    struct list *p,*p1,*p2,*p3,*pm;
    scanf("%ld %ld",&n,&m);

    //开辟节点,初始化
    p = (struct list *)malloc(sizeof(struct list));
    p ->n = n;
    p ->step = 1;
    p -> next = NULL;

    cout<<endl;
    //队尾节点
    pm = p;

    while(p!=NULL){

        cout<<"\n------------->\n";
        cout<<"p -> n: "<<p->n<<" p -> step: "<<p->step<<endl;
        k = p->n;
        if(k == m)
            break;

        //减操作
        p1 = (struct list*)malloc(sizeof(struct list));
        p1 -> n = k-1;
        p1 -> step = p->step+1;
        p1 -> next = NULL;
        cout<<"p1 -> n: "<<p1->n<<" p1 -> step: "<<p1->step<<endl;
        //入队尾
        pm -> next = p1;

        //加操作
        p2 = (struct list*)malloc(sizeof(struct list));
        p2 -> n = k + 1;
        p2 -> step = p->step +1;
        p2 -> next = NULL;
        p1 -> next = p2;    //入队，此时队尾为p2
        cout<<"p1 -> n: "<<p2->n<<" p1 -> step: "<<p2->step<<endl;

        //乘操作
        p3 = (struct list*)malloc(sizeof(struct list));
        p3 -> n = k * 2;
        p3 -> step = p -> step +1;
        p3 -> next = NULL;

        cout<<"p3 -> n: "<<p3->n<<" p3 -> step: "<<p3->step<<endl;
        p2 -> next = p3;
        pm = p3;    //此时队尾为p3

        p1 = p;
        p = p -> next;//此时p指向p后面的节点
//        cout<<p->n<<" "<<p->step<<endl;
        free(p1);   //释放原来的p节点

    }

    printf("%d\n",p->step -1);
    return 0;

}

2017

1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
1.输入10个正整数（有奇数也有偶数），要求输出其中的每个奇数，并输出奇数个数与奇数之和。
例如：输入：11,4,3,2,7,6,8,5,10,9
      输出：11 3 7 5 9
      NUM=5
      SUM=35
*/
#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int a[10]={0};
    int l_num = 0;
    int l_sum = 0;
    int n;
    for(int i=0;i<10;i++){
        cin>>n;
        if(n%2!=0){
            a[l_num++]=n;
            l_sum+=n;
        }
    }

    for(int i =0; a[i]!=0;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    cout<<"NUM="<<l_num<<endl;
    cout<<"SUM="<<l_sum<<endl;


    return 0;
}

2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
找出1000之内的所有完数，并输出完数和它的所有因子（一个数恰好等于他的因子之后，称为完数，例如：6=1+2+3）
*/
#include <iostream>
#include <cmath>
using namespace std;

int getGongyin(int num){
    //cout<<sqrt(num)<<endl;
    int sum=0;
    for(int i = num-1; i>0; i-- )
    {
        if(num % i == 0 )
        {
            //cout<<i<<" ";
            sum+=i;
        }
    }
    if(sum==num){
        cout<<num<<" "<<sum<<endl; 
        for(int i = num-1;i>0;i--){
            if(num%i==0)
                cout<<i<<" ";
        }
        cout<<endl;
    }
}
int main(){
    int n;
    cin>>n;
    for(int i =1; i <1000;i++)
        getGongyin(i);

    
}

3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
由键盘输入一行仅由英文字母及空格组成的字符，编程实现（相邻单词之间用一个空格或多个空格隔开）
   （1）输出每个单词及其长度
   （2）输出最长的单词
例如：输入：I am a boy
      输出：I     1
            am   2
            a     1
            boy   3
            The longest word is:boy
*/
#include <iostream>
#include <cstdio>

using namespace std;
int main(){
    char a[1000];
    char b[30];

    int i,j,m=0,n=0;    //m记录最长的单词长度，j保存临时的单词长度，n记录最长单词的最后一位
    printf("请输入字符:");
    gets(a);

    //注：输入时最后要加空格
    //若临时单词长度大于m记录的单词长度，则将当前的单词长度赋给m，并记录当前单词的最后一位。
    for(i=0,j=0; a[i]!='\0';i++){
        if(a[i] != ' ')
        {
            j++;
            cout<<"i==> "<<i<<" j==> "<<j<<endl;
        }
        else if(j>m){
            cout<<"i--> "<<i<<" j--> "<<j<<" m-->"<<m<<endl;
            m=j;
            n=i;
            j=0;
        }
    }
    printf("最长的单词是：\n");
    for(i=0;i<m;i++)
        putchar(a[i+n-m]);
    return 0;
}

2016

1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int main(){
    int a[10];

    for(int i = 0; i<10;i++)
        cin>>a[i];

    for(int i =0 ; i<10;i++){
        if(a[i]>=90)
            cout<<"A"<<endl;
        else if(a[i]>=80)
            cout<<"B"<<endl;
        else if(a[i]>=70)
            cout<<"C"<<endl;
        else if(a[i]>=60)
            cout<<"D"<<endl;
        else
            cout<<"E"<<endl;
    }
}

2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int main()
{
    int a[10];
    int sum=0;
    float aver=0;
    int count=0;
    for(int i =0;i<10;i++)
        cin>>a[i];

    for(int i =0;i<10;i++){
        if(a[i]%2==0){
            sum+=a[i];
            cout<<a[i]<<" ";
            count++;
        }
    }
    cout<<endl;
    cout<<"AVE="<<sum*1.0/count<<endl;
}

3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
int main()
{
    int a[3][4]={0};

    for(int i=0; i<3;i++)
        for(int j=0;j<4;j++)
            cin>>a[i][j];

    int MAX = 0;
    int row,col;
    for(int i =0;i<3;i++){
        for(int j =0; j<4;j++){
//            cout<<a[i][j]<<" ";
            if(a[i][j]>MAX){
                MAX = a[i][j];
                row = i;
                col = j;
            }
        }
//        cout<<endl;
    }
    cout<<MAX<<" "<<row+1<<" "<<col+1<<endl;
    return 0;
}

2013

1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
#include <math.h>
using namespace std;
int main()
{
    long double a,b;

    /*
        e+002表示10的2次方。科学计数法，用e表示10，
        加号表示正整数次方， 减号，
        表示负整数次方，
        这里就是等于 123.456
    */
    double sum = 0;
    double temp = 0;
    for(int i = 0; ;i++){
        temp = pow(-1,i+1)*(1.0/(2*i-1));
        if(fabs(temp)<1e-5){
            cout<<fabs(temp)<<endl;
            break;
        }
        else{
            sum+=temp;
        }
    }
    cout<<sum<<endl;
//    printf("%lf\n",123.456e-2);
//    scanf("%le %lf",&a,&b);
//    printf("%.4lf\n",a+b);
    return 0;
}

2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
int main()
{
    int a[3][3]={{3,4,-1},{2,1,3},{1,2,1}};
    int i,j;
    for(i = 0; i<3;i++)
    {
        for(j=0;j<3;j++){
            if(i>j){
                a[i][j] += a[j][i];
                a[j][i] = 0;
            }
        }
    }

    for(i =0;i<3;i++){
        for(j=0;j<3;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }


}

3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
using namespace std;

void quickSort(int a[],int left,int right){
    int i,j,t,temp;
    if(left>right)
        return;

    temp = a[left];
    i = left;
    j = right;
    while(i!=j){

        while(a[j]>= temp && i<j)
            j--;
        while(a[i]<=temp&& i<j)
            i++;

        if(i<j){
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    a[left] = a[i];
    a[i] = temp;

    quickSort(a,left,i-1);
    quickSort(a,i+1,right);
    return;
}
int main()
{
    int b[100];
    int N=0;
    int k=0;
    cout<<"输入整数n：";
    cin>>N;
    cout<<"输入整数k:";
    cin>>k;

    cout<<"输入数组：";
    for(int i=0;i<N;i++)
        cin>>b[i];

    quickSort(b,0,N-1);
    for(int i =0;i<N;i++){
        cout<<b[i]<<" ";
    }
    cout<<endl;
    for(int i = 0;i<k;i++)
    {
        cout<<b[i]<<" "<<b[N-i-1]<<endl;
    }
    cout<<endl;
    return 0;
}

发表更新学习3 分钟读完 (大约463个字)

插入排序

1.算法

插入排序由N-1趟排序组成。对于P = 1 趟到 P = N - 1趟，插入排序保证从位置0到位置P上的元素为已排序状态。插入排序利用了这样的事实：位置0到位置 P - 1上的元素是已排过序的。
下表表达了一般的方法。在第P趟，我们将位置P上的元素想做移动到它在前P+1个元素中的正确位置上。下面的程序实现了该想法。第2行到第5行实现数据移动而没有明显使用交换。位置P上的元素存于Tmp，而(在位置P之前)所有更大的元素都被向右移动一个位置。然后Tmp被置于正确的位置上。这种方法与实现二叉堆时所用到的技巧相同。

初始 34 8 64 51 32 21 移动的位置
在p=1之后 8 34 64 51 32 21 1
在p=2之后 8 34 64 51 32 21 0
在p=3之后 8 34 51 64 32 21 1
在p=4之后 8 32 54 51 64 21 3
在p=5之后 8 21 32 34 51 64 4 
1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertionSort(ElementType A[], int N)
{
    int j, P;
    
    ElementType Tmp;
    for( P = 1; P < N; P++)                         //1
    {
        Tmp = A[P];                                 //2
        for( j = P; j > 0 && A[ j-1 ] > Tmp; j--)   //3
            A[j] = A[j-1];                          //4
        A[j] = Tmp;                                 //5
    }
}

2.插入排序的分析

由于嵌套循环的每一个都花费N次迭代，因此插入排序为O(N2)，而且这个界是精确的，因为以反序输入可以达到该界。精确计算指出对于P的每一个值，第4行的测试最多执行P+1次。对所有的P求和，得到总数为
SUM = 2 + 3 + 4 + ... + N = O(N<sup>2</sup>)
另一方面，如果输入数据已排序，那么运行时间为O(N)，因为内层for循环的检测是立即判定不成立而终止。事实上，如果输入几乎被排序，那么插入排序将运行得很快。

发表更新学习几秒读完 (大约107个字)

Longest Substring Without Repeating Characters

题目链接: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;

int length(string s) {
	vector<int> dict(256,-1);
	int maxLen = 0, start = -1;
	for(int i = 0; i != s.length(); i++) {
		if(dict[s[i]] > start)
			start = dict[s[i]];
		dict[s[i]] = i;
		maxLen = max(maxLen, i -start);
	}
	return maxLen;
}

int main()
{
	cout<<length("abcabcbb")<<endl;
}

Output: 3

个人理解
dict 记录当前字符出现的位置
start 记录当前字符出现的上一次位置
参考自https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1737

关注我

链接

分类

最新文章

标签

BFS3
DFS3
Java面经1
algorithm4
android1
bfs2
c++9
dfs7
dp1
dpLearning13
java1
jvm9
ordered-map1
python8
spring6
sql3
tools16
二分查找1
二叉树13
位运算10
傻屌题1
分治2
分治算法2
动态规划6
双指针7
哈希1
哈希表2
回溯5
堆2
堆排序1
多线程1
字符串5
总结1
找规律2
指针1
排序9
数字1
数据库1
数组9
最短路径1
查找2
栈9
树12
测试6
测试知识1
滑动窗口1
自动机1
计算机基础2
计算机网络1
计算机网络基础1
论文阅读10
设计1
贪心算法3
较难13
递归6
链表14
队列1
需要review8
面试记录1
×