c++算法笔记
2018-12-26 19:12:49 qq_23304241 阅读数 111

 1、题目描述

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

输入描述:

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

输出描述:

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

示例1

输入:hello world

输出:5

方法一:

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main()
{
	string input;
	vector<string>arr;
	while (cin >> input)
	{
		arr.push_back(input);
	}
	cout << arr[arr.size() - 1].length() << endl;
	return 0;
}

方法二:

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s;
    while(getline(cin,s)){
        int n=0,flag=1;
        for(int i=s.length()-1;i>=0;--i){//倒着计算
            if(flag && s[i]==' '){//如果末尾有空格,先清除末尾空格
                continue;
            }
            else if(s[i]!=' '){
                flag = 0;
                ++n;
            }
            else{
                break;
            }
        }
        cout << n << endl;
    }
    return 0;
}

2、题目描述

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

输入描述:

输入一个有字母和数字以及空格组成的字符串,和一个字符。

输出描述:

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

示例1 

输入:ABCDEF A  输出:1

#include<iostream>
#include<string>
#include<ctype.h>
using namespace std;
int main()
{
	string str;
	
	while (getline(cin,str))
	{
		char s;
		cin >> s;
		int count = 0;
		for (int i = 0; i < str.size(); i++)
		{
			if (tolower(s) == tolower(str[i])) //都转换成小写进行比较
				count++;
		}
		cout << count << endl;
		cin.ignore();
	}
	
	return 0;
}

3、C++中substr函数的用法

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

int main()
{
	//string str("123456abc"); string两种初始化方式均可以
	string str = "123456abc";
	string a = str.substr(6, str.size()); // substr()可以获得指定字符串
	cout << a << endl;   //输出abc
	return 0;
}

4、

题目描述

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

输入描述:

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

输出描述:

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

输入:abc
          123456789

输出:abc00000
          12345678
          90000000

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

void fuck(string str)
{
	if (str == "")       //明确分几种情况
		return;
	if (str.size() <= 8)
	{
		str.append(8 - str.size(), '0');
		cout << str << endl;
		return;
	}
	cout << str.substr(0, 8) << endl;
	fuck(str.substr(8, str.size()));//递归调用
}
int main()
{
	string str1, str2;
	cin >> str1 >> str2;
	fuck(str1);
	fuck(str2);
	return 0;
}

5、合并表并记录

题目描述

数据表记录包含表索引和数值,请对表索引相同的记录进行合并,即将相同索引的数值进行求和运算,输出按照key值升序进行输出。

输入描述

先输入键值对的个数
然后输入成对的index和value值,以空格隔开

输出描述:

输出合并后的键值对(多行)

示例1

输入

4
0 1
0 2
1 2
3 4

输出

0 3
1 2
3 4
这道题的方法有很多种,其中最关键的一点是数据结构,也就是说你打算用什么样的方式来存放表每一项的索引和键值,最容易想到的一种方法是使用结构体,这个结构体包含两项分别为索引和键值,于是整个表就是这样的一个结构体数组,这种方法很常规,但是其实有一个更为简单的小技巧,我们不需要去定义结构体,只使用普通的数组就可以完成,我们需要处理的数据有两项,一项是index索引,一项是键值value,我们可以把index用数组下标来存放,而键值用数组元素的值来存放,这样我们存放的数据在数组中是不连续的,但是不论是代码还是思路都会大大简化,代码如下

#include<iostream>
using namespace std;
int  main()
{
 int Key_Value[10000]={0},Key,Value,Number,i;
 cin>>Number;
 for(i=0;i<Number;i++)
 {
  cin>>Key>>Value;
  Key_Value[Key]+=Value;
 }
 for(i=0;i<10000;i++)
 {
  if(Key_Value[i]!=0)
   cout<<i<<"  "<<Key_Value[i]<<endl;
 }
 return 0;
}

链接:https://www.nowcoder.com/questionTerminal/de044e89123f4a7482bd2b214a685201
来源:牛客网

以上的这种方法虽然比较简单,但是中间有一个小Bug,在这里虽然可以通过所有测试,但是必须是在相同索引项最后的键值和不为0的情况下才能正确,而这里牛客的测试数据最后的输出结果的键值都是非0值,所以也通过了,但是更严谨地来应该采用一种更为常规的方法,也就是用结构体来设计算法,这样输入的每一项是一种连续存放的数据结构,相对第一种方法来说代码更复杂一点,但是更具有普适性,代码如下

#include<iostream>
using namespace std;
struct Key_Value_Pair
{
    int index;
    int value;
};
int main()
{
    Key_Value_Pair Part[1000];
    int Key_Value_Pairs_Num,i,j,k;
    cin>>Key_Value_Pairs_Num;
    for(i=0;i<Key_Value_Pairs_Num;i++)
        cin>>Part[i].index>>Part[i].value;
    for(i=0;i<Key_Value_Pairs_Num;i++)
    {
        for(j=i+1;j<Key_Value_Pairs_Num;j++)
        {
            if(Part[i].index==Part[j].index)
            {
                Part[i].value+=Part[j].value;//对第二键值求和,累加在第一次出现的键值项上,下一步进行重复索引的删除操作
                for(k=j;k<Key_Value_Pairs_Num-1;k++)
                    Part[k]=Part[k+1];
                j--;
                Key_Value_Pairs_Num--;
            }
        }
    }
    //下面进行排序操作
    Key_Value_Pair Temp;//定义一个结构体,作为交换操作的中间值
    for(i=0;i<Key_Value_Pairs_Num-1;i++)
    {
        for(j=0;j<Key_Value_Pairs_Num-1-i;j++)
        {
            if(Part[j].index>Part[j+1].index)
            {
                Temp=Part[j];
                Part[j]=Part[j+1];
                Part[j+1]=Temp;
            }
        }
    }
    for(i=0;i<Key_Value_Pairs_Num;i++)
        cout<<Part[i].index<<" "<<Part[i].value<<endl;
    return 0;
}

6、以下代码是把一个字符串倒序,如“abcd”倒序后变为“dcba”。

方法一:

int main()
{
    char *src = "hello,world";
    int len = strlen(src);
    char *dest = (char *)malloc(len + 1); //要为\0分配一个空间
    char *d = dest;
    char *s = &src[len - 1]; //指向最后一个字符
    while ( len-- != 0 )
        *d++ = *s--;
    *d = 0; //尾部要加\0
    printf("%s\n", dest);
    free(dest);// 使用完,应当释放空间,以免造成内存汇泄露
    return 0;
}

方法二:

int main()
{
    char str[] = "hello,world";
    int len = strlen(str);
    char t;
    for (int i = 0; i < len; i++)
    {
        t = str[i];
        str[i] = str[len - i - 1]; 
        str[len - i - 1] = t;      
    }
    printf("%s", str);
    return 0;
}

7、实现函数 ToLowerCase(),该函数接收一个字符串参数 str,并将该字符串中的大写字母转换成小写字母,之后返回新的字符串。

class Solution {
public:
    string toLowerCase(string str) {
        for(auto &c:str){     //对字符串str中的每个字符
                c = tolower(c);
        }
        return str;
    }
};

8、汉诺塔用递归实现

#include <stdio.h>

void hanoi(int n, char A, char B, char C)
{
	if(n==1){
		printf("%c -> %c\n",A,C);
	}
	else{
		hanoi(n-1,A,C,B);
		printf("%c -> %c\n",A,C);
		hanoi(n-1,B,A,C);
	}

}
int main(){
	hanoi(3,'A','B','C');
}

9、求数组最大值

#include <stdio.h>

int findMax(int arr[], int n){
	int max = arr[0];
	int i;
	for (i=1;i<n;i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	return max;
}
int main(){
	int arr[10] = {8,2,3,4,6,5,1,10,9,7};
	int m= findMax(arr,10);
	printf("m = %d\n", m);

	return 0;
}

用递归实现

#include <stdio.h>

int findMax(int arr[], int L, int R){
	if(L == R){
		return arr[L];
	}
	else{
		int a = arr[L];
		int b = findMax(arr, L+1, R);
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
}
int main(){
	int arr[10] = {8,2,3,4,6,5,1,10,9,7};
	int m= findMax(arr,0,9);
	printf("m = %d\n", m);

	return 0;
}

 

2018-04-03 21:29:23 Uupton 阅读数 236

二分查找也称折半查找(Binary Search)

1、目的:给定一个数组和一个目标值,返回该目标值在数组中第一次出现位置的下标。

2、限制:(1)该数组必须满足顺序存储结构。(2)必须按关键字大小有序排列。

3、原理:每次取数组正中间的值与目标值比较,若相等则返回该中间值的下标,若目标值大于中间的值则取中间值的后半部分作为一个新的数组(保留原下标)重复第一步的操作,若目标值小于中间的值则取该中间值的前半部分的作为一个新的数组(保留原下标)重复第一步的操作。

例子:给定数组num[10]={1,2,3,4,5,6,7,8,9,10};目标值target为3

第一步:取数组中间的值,中间下标mid = (0+9)/2 = 4,num[mid] = 5; 因为3<5 ,取5的前半部分作为一个新的数组,即{1,2,3,4},该数组保留原来的下标值

第二步:重复第一步,中间下标mid =(0+3)/2 = 1,num[1] = 2;因为3>2,取2的后半部分作为一个新的数组,即{3,4},该数组保留原来的下标值

第三步:重复第一步,中间下标mid =(2+3)/2 = 2,num[2] = 3;因为3 =3,所以返回值为2;

代码实现

int binarySearch(int num[],int low,int high ,int key)
{
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (num[mid] == key) return mid;
		else if (num[mid] > key) high = mid - 1;
		else low = mid + 1;
	}
	return -1;
}

至此,我们已经完成了二分查找的一般情况下的解决方法,但是我们还要考虑一种情况:当数组存在重复元素的时候就会导致答案可能出错,因为我们要查找的是第一次出现的位置。

例如:num[5] = {1,2,2,2,3};target = 2 ;采用上面的方法得出的是下标2,而我们需要的答案是小标1.

所以对上面的代码进行改进如下,若目标值小于或等于中间的值则继续对前一部分进行操作

int binarySearch(int num[], int low, int high, int key)
{
	int mid = (low + high) / 2;
	while (low < high)
	{
		if (num[mid] >= key) high = mid;
		else if (num[mid] < key) low = mid + 1;
		mid = (low + high) / 2;
	}
	return num[mid] == key ? mid : -1;
}


2018-08-03 00:40:17 weixin_37986381 阅读数 66

一、算法概述

  1. 算法部分主要头文件<algorithm>,<numeric>,<functional>:<algorithm>是所有STL头文件中最大的一个,常用功能范围有比较、交换、查找、遍历操作、复制、修改、反转、排序、合并;<numeric>体积很小,只包括几个在序列上面进行简单数学运算的模板函数,包括加法和乘法在序列上的一些操作;<functional>中定义了一些模板类,用以声明函数对象。

  2. 算法分类:操作对象,直接改变容器的内容,将原容器的内容复制一份,修改其副本,然后传回该附本。非可辨序列算法:指不直接修改其所操作的容器内容的算法(计数算法、搜索算法、比较算法);可变序列算法:指可以修改他们所操作的内容的算法(删除算法、修改算法、排序算法)

  3. 算法中的函数对象和谓词:

  4. 函数对象--》重载函数调用操作符的类,其对象常称为函数对象,即他们是行为类似函数的对象,一个类对象,表现出一个函数的特征,就是通过“对象名+(参数列表)”方式使用一个类对象,如果没有上下文,完全可以把它看作一个函数对待。这是通过重载类的operator()来实现的。“在标准库中的很对算法都可以使用函数对象或者函数来作为自定回调行为。---实现了数据类型和算法的分离

分清楚STL算法返回的值是迭代器还是谓词(函数对象)是stl算法入门的重要点

预定义函数对象:标准模板库STL提前定义了很多预定义函数对象, #include <functional>必须包含;

  1. 谓词--》一元函数对象,函数参数1个;二元函数参数对象,函数参数2个。一元谓词:函数参数一个,函数返回值是bool类型,可以作为一个判断式;谓词可以是一个仿函数,也可以是一个回调函数;二元位置,函数参数2个,函数返回值是bool类型。

 

5.函数适配器

二、STL常用的算法

  1. for_each()
  2. for_each():用指定函数一次对指定范围内所有元素进行迭代访问,该函数不得修改序列中的元素。for_each()的第三个参数,函数对象做函数参数,函数对象做返回值。
    #include <iostream>
    
    using namespace std;
    
    #include "string"
    #include "set"
    #include <vector>
    #include <list>
    #include <algorithm>
    #include "functional"
    
    void printV(vector<int> &v)
    {
    	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    	{
    		cout << *it << "\t";
    	}
    }
    void showElem(int &n)
    {
    	cout << n << "\t";
    }
    class CMyShow
    {
    
    public :
    	CMyShow()
    	{
    		num = 0;
    	}
    	void operator()(int &n)
    	{
    		cout << n << "\t";
    		num++;
    	}
    	void printV()
    	{
    		cout << num << endl;
    	}
    private :
    	int num;
    };
    void main41()
    {
    	vector<int> v1;
    	v1.push_back(1);
    	v1.push_back(3);
    	v1.push_back(5);
    	printV(v1);
    	cout << endl;
    	for_each(v1.begin(), v1.end(), showElem);
    	cout << endl;
    	CMyShow mya;
    	CMyShow my1=for_each(v1.begin(), v1.end(), mya);
    	cout << endl;
    	my1.printV();//my1和mya是两个不同的对象
    	mya.printV();
    }
    
    void main()
    {
    	main41();
    	cout << endl;
    	system("pause");
    }

     

  3. transform():与for_each类似,遍历所有元素,但可对容器的元素进行修改。他可以把一个容器的呀U尿素,通过op,变换到另一个容器中(同一个容器中);也可以把两个容器的元素,通过op,变换到另一个容器中。
    #include <iostream>
    
    using namespace std;
    
    #include "string"
    #include "set"
    #include <vector>
    #include <list>
    #include <algorithm>
    #include "functional"
    #include "iterator"
    void printV(vector<int> &v)
    {
    	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    	{
    		cout << *it << "\t";
    	}
    }
    void printList(list<int> &v)
    {
    	for (list<int>::iterator it = v.begin(); it != v.end(); it++)
    	{
    		cout << *it << "\t";
    	}
    }
    
    int increase(int i)
    {
    	return i + 100;
    }
    
    void main42()
    {
    	vector<int> v1;
    	v1.push_back(1);
    	v1.push_back(3);
    	v1.push_back(5);
    	printV(v1);
    	cout << endl;
    	//使用回调函数
    	transform(v1.begin(), v1.end(), v1.begin(), increase);
    	printV(v1);
    	cout << endl;
    	
    	//使用预定义的函数对象
    	transform(v1.begin(), v1.end(), v1.begin(), negate<int>());
    	printV(v1);
    	cout << endl;
    
    	//使用函数适配器
    	list<int> mylist;
    	mylist.resize(v1.size());
    	transform(v1.begin(), v1.end(), mylist.begin(),bind2nd(multiplies<int>(),10));
    	printList(mylist);
    	cout << endl;
    
    	//把运算结果直接输出到屏幕
    	transform(v1.begin(), v1.end(), ostream_iterator<int>(cout, "\t"), negate<int>());
    
    }
    void main()
    {
    	main42();
    	cout << endl;
    	system("pause");
    }

     

  4.   for_each与transform的区别   一般情况下,for_each所使用的函数对象,参数是引用,没有返回值;tranform所使用的函数对象,参数一般不使用引用,而且还有返回值;
  5.  
  6.    
2019-03-03 09:36:02 qq_23304241 阅读数 36

1、输入一个链表,输出该链表中倒数第k个结点

此题我们可以先定义两个指针,p和q。让p和q都指向头结点。在定义一个i,i的初始值为0。然后进入一个for循环,直到p走到链表结尾,每次i++。当i < k 的我们让p走,q不走。当i >= k 的时候我们让p和q同时走一步。当p走到结尾的时候,那么q走的值就是倒数k的位置,我们返回这个值就好了。
 

class Solution{
public:
	ListNode * FindKthToTail(ListNode * pListHead, unsigned int k)
	{
		ListNode * p = pListHead;
		ListNode * q = pListHead;
		int i = 0;
		for (; p != NULL; i++)
		{
			if (i >= k)
			{
				q = q->next;
			}
			p = p->next;
		}
		return i > k ? NULL : q;
	}
};

2、判断字符串是否为回文

#include <iostream>
#include <string>
using namespace std;
int main()
{
	int i, j,l;
	string str;
	int flag = 1;
	while (cin >> str)
	{
		l = str.length();
	
		for (i = 0, j = l - 1; i <= j; i++, j--)
		{
			if (str[i] != str[j])
			{
				flag = 0;
				break;
			}
		}
		if (flag)
		{
			cout<<"YES"<< endl;
		}
		else
		{
			cout << "NO" << endl;
		}
		flag = true;
	}
	return 0;
}

 

2017-12-07 20:15:38 weifenglin1997 阅读数 157

对于一个P进制的数字,若要转化为Q进制,则需要两部:

第一步:

将P进制的数字转化为10进制

y=a1*p(n-1)+a2*p(n-2)+....+an-1p+an

如何实现?

 int x,p;
	int y=0,pro=1;//p表示进制
	while(x!=0){
		y=y+(x%10)*pro;
		x=x/10;
		pro=p*pro;
	}
//将 十进制转换为q进制,除基取余法;
/*例如11转换为2进制
首先11%2=5  余1
5%2=2  余1
2%2=1  余0
1%2=0  余1
所以十一的二进制为  1011 
*/ 
int z[40],num=0;
do{
z[num++]=y%q;
y=y/q;

}while(y!=0);//当商不为0时循环 

例题 PAT1022

时间限制
100 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
CHEN, Yue

输入两个非负10进制整数A和B(<=230-1),输出A+B的D (1 < D <= 10)进制数。

输入格式:

输入在一行中依次给出3个整数A、B和D。

输出格式:

输出A+B的D进制数。

输入样例:
123 456 8
输出样例:
1103

#include <stdio.h>
#include<iostream>
#include <string.h>
#include<stdlib.h>
using namespace std;
//进制转换

int main(){
	int a,b,y,q;
	scanf("%d%d%d",&a,&b,&q);
	y=a+b;
	int z[40],num=0;
	do{
		z[num++]=y%q;
		y=y/q;
		
	}while(y!=0);//当商不为0时循环 
	for(int i=num-1;i>=0;i--){
		cout<<z[i];
	}
	return 0;
}



算法笔记:递归(c++实现)

阅读数 160

递归定义递归定义是一种直接或者间接引用自身的定义方法。递归包括两部分:基础部分(直接形式列举)递归部分(给出方法)如斐波那契数列的递归定义{f0=0,f1=1{f(n)=f(n-1)+f(n-2)n&gt;1递归算法使用递归定义的算法如longFib(longn){  if(n&lt;=1)returnn;  elsereturn(Fib(n-2)+Fib(n-...

博文 来自: qq_41068877

c++算法刷题笔记

阅读数 20

c++算法刷题笔记字符串处理字符串处理1.对于从键盘接受HelloWorld这样存在空格的输入,不可以使用cin,可以使用形如stringch;getline(cin,ch);来接受一行字符串2.将string类转换成char[]时,可以使用strcpy(ch,str.c_str());,需要包含头文件#include&amp;amp;amp;amp;lt;string.h&amp;amp;amp;amp;gt;...

博文 来自: qq_36478773

数据结构与算法C++版(笔记)

阅读数 524

跳跃链表:跳跃链表主要是为了解决单链表和双链表查找复杂的问题提出的。其时间复杂度为O(lgn),主要的操作时查找和插入:一、查找目的:在跳跃表中查找一个元素x 在跳跃表中查找一个元素x,按照如下几个步骤进行:i)从最上层的链(Sh)的开头开始ii)假设当前位置为p,它向右指向的节点为q(p与q不一定相邻),且q的值为y。将y与x作比较(1)x=y 输出查询成功及相关信息(2)x

博文 来自: aixueVC

算法笔记C/C++之基本数据类型

阅读数 92

猫宁要努力成为一只程序猿呀。下面是学习《算法笔记》记下的笔记。

博文 来自: qq_38256633

算法笔记(C++描述)——KMP算法

阅读数 10

概述以发现者名字字母命名的KMP算法,是一种比BF算法(最朴素的串匹配算法)更高效的模式串匹配蛮力算法。预备概念1.主串:即将在其中进行匹配子串查找的长字符串。2.模式串:用来在主串中作为匹配时的参照模板的短字符串。3.模式串匹配算法:用来在主串中找到一个与模式串完全相同的子串的算法,找到即匹配成功,反之匹配失败。4.BF算法:一种普通的模式串算法,时间效率为O...

博文 来自: weixin_40861847
没有更多推荐了,返回首页