Day7-学习内容：
1.python菜鸟教程-100例
例17：统计一行字符中英文字母、空格、数字和其它字符的个数。
例18:求s=a+aa+aaa+aaaa+aa...a的值。
例19:找出1000以内的所有完数。
2.剑指Offer
面试题6:从尾到头打印链表
面试题20:表示数值的字符串
3.Leetcode
例1:求逆波兰表示式的值
例2:使用插入排序排序一个链表
4.2017年校招真题-合唱团
1.python菜鸟教程-100例
例17：输入一行字符，分别统计出其中英文字母、空格、数字和其它字符的个数。
解析：1.使用python内建函数 input()输入字符串需要使用单/双引号
2.判断字符是否为英文、空格、数字的函数：isalpha(),isspace(),isdigit()
3.if elif else用法
4.len()函数返回字符串的实际长度，没有结束符的概念，python使用引号('或")来创建字符串
参考：https://blog.csdn.net/lb_1024/article/details/54410269
https://www.cnblogs.com/shengulong/p/7906582.html(python中+=与+的区别)
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
232 # -*- coding: UTF-8 -*- 3 4 import string 5 6 str=raw_input('请输入字符串：') 7 letter=0 8 space=0 9 digit=0 10 other=0 11 i=0 12 while(i<len(str)): 13 c=str[i] 14 i+=1 15 if(c.isalpha()): 16 letter+=1 17 elif(c.isspace()): 18 space+=1 19 elif(c.isdigit()): 20 digit+=1 21 else: 22 other+=1; 23 print("{} has {} letters,{} spaces,{} digits and {}other".format(str,letter, space,digit,other))
例18:求s=a+aa+aaa+aaaa+aa...a的值，其中a是一个数字。例如2+22+222+2222+22222(此时共有5个数相加)，几个数相加由键盘控制。
解析：1.reduce() 函数会对参数序列中元素进行累积。
2.Sn = reduce(lambda x,y : x + y,Sn)使用lambda匿名函数对列表求和
代码：
方法1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16#!/usr/bin/python # -*- coding: UTF-8 -*- number=input("请输入数字:") time=input("相加次数:") sum=0 cur=0 for i in range(time): cur=cur+number*(10**i) sum+=cur if(i!=time-1): print("{}+".format(cur)), else: print("{}".format(cur)) print("={}".format(sum)) ~
方法2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15#!/usr/bin/python # -*- coding: UTF-8 -*- Tn = 0 Sn = [] n = int(raw_input('n = ')) a = int(raw_input('a = ')) for count in range(n): Tn = Tn + a a = a * 10 Sn.append(Tn) print Tn Sn = reduce(lambda x,y : x + y,Sn) print "计算和为：",Sn
例19:一个数如果恰好等于它的因子之和，这个数就称为"完数"。例如6=1＋2＋3.编程找出1000以内的所有完数。
解析：1.python print 和 sys.stdout.write()区别：当我们使用print(obj)在console上打印对象的时候，实质上调用的是sys.stdout.write(obj+'n')，print在打印时会自动加个换行符，即sys.stdout.write(obj）打印对象不会换行，而print打印后会默认换行，也可使用在print后加一个逗号，使其不换行。
参考：https://blog.csdn.net/u011244839/article/details/79932148
2.正确理解此题中的完数（能被整除且相加等于其本身）而非质数（相乘等于其本身），因子都表示该因子能被其整除。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19#!/usr/bin/python # -*- coding: UTF-8 -*- number=[] for i in range(2,1001): prime=[] n=-1 s=i for j in range(1,i): if(i%j==0): n+=1 s-=j prime.append(j) if(s==0): print("current number:{}".format(i)) print("factor:{}".format(prime)) number.append(i) print("all number ={}".format(number))
2.剑指Offer
面试题6:从尾到头打印链表
题目描述：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
方法1:递归（已调试通过！）
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution { public: vector<int> value; vector<int> printListFromTailToHead(ListNode* head) { ListNode* p=head; if(p){ if(p->next){ printListFromTailToHead(p->next); } value.push_back(p->val); } return value; } };
方法2:栈的迭代（已调试通过！）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector<int> value; stack<ListNode*> stack; ListNode* p=head; while(p){ stack.push(p); p=p->next; } while(!stack.empty()){ p=stack.top(); value.push_back(p->val); stack.pop(); } return value; } };
方法3:利用数组翻转，先利用数组存储链表中的值，再对数组进行翻转就不会造成对原有链表的修改了。（已调试通过！）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector<int> value; ListNode* p=head; while(p){ value.push_back(p->val); p=p->next; } //reverse(value.begin(),value.end()); 利用C++自带的翻转函数实现 int temp; int i=0; int j=value.size()-1; while(i<j){ temp=value[j]; value[j]=value[i]; value[i]=temp; ++i; --j; } return value; } };
面试题20:表示数值的字符串
题目描述：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路：表示数值的字符串遵循模式A[.[B]][e|EC]或者.B[e|EC]，其中A表示整数部分，B表示小数部分，C表示指数部分，A和C都是可能以“+”或者“-”开头的0～9的数位串，B也是0～9的数位串但前面不能有正负号。
代码：（已调试通过！）
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
28class Solution { public: bool isNumeric(char* string) { bool sign=false,decimal=false,hasE=false; //标记符号、小数点、e是否出现过 for(int i=0;i<strlen(string);i++){ if(string[i]=='e'||string[i]=='E'){ if(i==strlen(string)-1) return false; //e后面必须有数字 if(hasE) return false; //e不能出现两次 hasE=true; } else if(string[i]=='+'||string[i]=='-'){ if(sign&&string[i-1]!='e'&&string[i-1]!='E') return false; //第二次出现必须在e后面 if(!sign&&i>0&&string[i-1]!='e'&&string[i-1]!='E') return false; //第一次出现且不是在字符开头，也必须出现在e后面- sign=true; } else if(string[i]=='.'){ if(hasE||decimal) return false; //只能出现一次且不能出现在e后面 decimal=true; } else if(string[i]<'0'||string[i]>'9'){ //不合法字符 return false; } } return true; } };
3.Leetcode
例1:求逆波兰表示式的值
题目描述：
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are+,-,*,/. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
解析：1.逆波兰式（后缀表达式）
参考：https://blog.csdn.net/linraise/article/details/20459751
2.C++中auto原理是根据后面的值来自己推测前面的类型是什么，作用是为了简化变量初始化。
参考：https://blog.csdn.net/lwgkzl/article/details/82110068
3.C++字符串流stringstream
参考：https://blog.csdn.net/shs1992shs/article/details/83051298
代码：
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
36class Solution { public: int evalRPN(vector<string> &tokens) { stack<int> numbers; for(auto token : tokens){ if(token=="+"||token=="-"||token=="*"||token=="/"){ int res,a,b; b=numbers.top(); numbers.pop(); a=numbers.top(); numbers.pop(); if(token=="+"){ res=a+b; } else if(token=="-"){ res=a-b; } else if(token=="*"){ res=a*b; } else{ res=a/b; } numbers.push(res); } else{ stringstream ss; ss<<token; int temp; ss>>temp; numbers.push(temp); } } return numbers.top(); } };
注意：1.代码中加减乘除要用双引号“”不能用单引号
2.auto 函数的写法
3.stringstream的用法，方向不能颠倒
例2:使用插入排序排序一个链表
题目描述：Sort a linked list using insertion sort.
思路：插入排序就是不断向一个已经排序的列表中(此处为代码中的sortedList)添加新的节点，并且保证添加节点后的列表仍然有序，每次需先在已排序的链表中找到要插入的节点位置。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution { public: ListNode *insertionSortList(ListNode *head) { if(head==nullptr||head->next==nullptr){ return head; } ListNode sortList(0); ListNode *cur=head; while(cur){ ListNode *next=cur->next; ListNode *sortnode=&sortList; //已排序的链表头指针 while(sortnode->next!=nullptr&&sortnode->next->val<cur->val){ sortnode=sortnode->next; } //找到插入位置 cur->next=sortnode->next; sortnode->next=cur; cur=next; //插入指针 } return sortList.next; } };
4.2017年校招真题-合唱团
题目描述：有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
输入描述:
1
2
3每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。 输出描述:
1输出一行表示最大的乘积。
示例1
输入
1
2
3
4
5
63 7 4 7 2 50 输出 49
思路：
采用动态规划（理由：1.求解的是最优化问题；2.可以分解为最优子结构），dp_max[i][j]，dp_min[i][j]分别表示以第i个人位结尾，选择j个人的最大乘积和最小乘积。
代码：
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#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ int n; while (cin >> n){ vector<int> a(n); for (int i = 0; i < n; i++){ cin >> a[i]; } int k, d; cin >> k >> d; vector<vector<long long>> dp_max(n, vector<long long>(k + 1, 0)); vector<vector<long long>> dp_min(n, vector<long long>(k + 1, 0)); for (int i = 0; i < n; i++){ dp_max[i][1] = a[i]; dp_min[i][1] = a[i]; } for (int i = 0; i < n; i++){ for (int j = 2; j <= k; j++){ for (int m = max(0, i - d); m <= i - 1; m++){ dp_max[i][j] = max(dp_max[i][j], max(dp_max[m][j - 1] * a[i], dp_min[m][j - 1] * a[i])); dp_min[i][j] = min(dp_min[i][j], min(dp_min[m][j - 1] * a[i], dp_max[m][j - 1] * a[i])); } } } long long max_value = dp_max[k - 1][k]; for (int i = k; i < n; i++){ max_value = max(max_value, dp_max[i][k]); } cout << max_value << endl; } return 0; }
最后
以上就是冷艳火最近收集整理的关于编程之旅-Day7Day7-学习内容：的全部内容，更多相关编程之旅-Day7Day7-学习内容内容请搜索靠谱客的其他文章。
发表评论 取消回复