概述
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中+=与+的区别)
代码:
2 # -*- 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:
#!/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:
#!/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.正确理解此题中的完数(能被整除且相加等于其本身)而非质数(相乘等于其本身),因子都表示该因子能被其整除。
代码:
#!/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:递归(已调试通过!)
class 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:栈的迭代(已调试通过!)
class 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:利用数组翻转,先利用数组存储链表中的值,再对数组进行翻转就不会造成对原有链表的修改了。(已调试通过!)
class 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的数位串但前面不能有正负号。
代码:(已调试通过!)
class 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
代码:
class 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)添加新的节点,并且保证添加节点后的列表仍然有序,每次需先在已排序的链表中找到要插入的节点位置。
代码:
class 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 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50),表示学生的个数,接下来的一行,包含 n 个整数,按顺序表示每个学生的能力值 ai(-50 <= ai <= 50)。接下来的一行包含两个整数,k 和 d (1 <= k <= 10, 1 <= d <= 50)。
输出描述:
输出一行表示最大的乘积。
示例1
输入
3
7 4 7
2 50
输出
49
思路:
采用动态规划(理由:1.求解的是最优化问题;2.可以分解为最优子结构),dp_max[i][j],dp_min[i][j]分别表示以第i个人位结尾,选择j个人的最大乘积和最小乘积。
代码:
#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-学习内容:所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复