双指针算法()

双指针算法

大致格式如下:

for(int i = 0; i < n; i++){
	while(j < i && check(i, j)) j++;
	
	//每道题目的具体逻辑 
}

核心思想:

for(int i = 0; i < n; i++){
	for(int j = 0; j < n; j++){
		//O(n^2)的复杂度		
	}
}
将上述朴素算法优化到O(n); 

例题
输入一个字符串,把其中的输出出来。
输入:
输出:

每一个单词
abc def ghi
abc
def
ghi
#include <bits/stdc++.h>

using namespace std;

int main(){
	char str[1000];
	
	gets(str);
	int len = strlen(str);
	for(int i = 0; i < len; i++){
		int j = i;
		while(j < len && str[j] != ' ') j++;
		
		//这道题的具体逻辑
		for(int k = i; k < j; k++){
			cout << str[k];
		} 
		cout << endl;
		i = j;
		
	}
	
	return 0;
}

————————

双指针算法

大致格式如下:

for(int i = 0; i < n; i++){
	while(j < i && check(i, j)) j++;
	
	//每道题目的具体逻辑 
}

核心思想:

for(int i = 0; i < n; i++){
	for(int j = 0; j < n; j++){
		//O(n^2)的复杂度		
	}
}
将上述朴素算法优化到O(n); 

例题
输入一个字符串,把其中的输出出来。
输入:
输出:

每一个单词
abc def ghi
abc
def
ghi
#include <bits/stdc++.h>

using namespace std;

int main(){
	char str[1000];
	
	gets(str);
	int len = strlen(str);
	for(int i = 0; i < len; i++){
		int j = i;
		while(j < len && str[j] != ' ') j++;
		
		//这道题的具体逻辑
		for(int k = i; k < j; k++){
			cout << str[k];
		} 
		cout << endl;
		i = j;
		
	}
	
	return 0;
}