#ifndef XINWEI_ROTATESTRING_H_
#define XINWEI_ROTATESTRING_H_
#include <iostream>
using namespace std;
void ReverseString(char *s,int from , int to){
char temp;
while (from <to){
temp=*(s+from);
*(s+from)=*(s+to);
*(s+to)=temp;
from++;
to--;
}
}
void LeftShiftOne(char* s,int n){
char temp=s[0];
int i=0;
while (i<n-1){
s[i]=s[i+1];
i++;
}
s[n-1]=temp;
}
/**
* (X^TY^T)^T=YX
* n字符串长度，m旋转前m位
*/
void LeftRotateString(char* s,int n,int m){
ReverseString(s,0,m-1);
ReverseString(s,m,n-1);
ReverseString(s,0,n-1);
}
void LeftRotateString2(char* s,int n,int m){
while (m--){
LeftShiftOne(s,n);
}
}
void RightRotateString(char* s,int n,int m){
ReverseString(s,0,n-m-1);
ReverseString(s,n-m,n-1);
ReverseString(s,0,n-1);
}
void ReverseWords(char* s){
ReverseString(s,0,strlen(s)-1);
int x=0;
for (int j = 0; j <strlen(s) ; ++j) {
if(s[j]==' '){
ReverseString(s,x,j-1);
x=j+1;
}
}
}
#endif
算法
字符串字母包含算法
给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数
bool StringContains(string &A, string &B)
// Created by Lv,Xinwei on 2018/2/5.
/**
* 穷举查找O(nm)
* @param A
* @param B
* @return
*/
bool StringContains(string &A, string &B) {
typedef string::const_iterator it;
int num=0;
for (it i = B.begin(); i < B.end(); i++) {
for (it j = A.begin(); j < A.end(); j++) {
if (*i == *j) {
num++;
break;
}
}
}
return num==B.length();
}
int cmp(const void* a,const void* b){
return ( *(char*)a - *(char*)b );
}
/**
* 排序查找O(nlogN+mlogM+m)
* @param A
* @param B
* @return
*/
bool StringContains2(string &A, string &B) {
sort(A.begin(),A.end());
sort(B.begin(),B.end());
typedef string::const_iterator it;
it j=A.begin();
for (it i = B.begin(); i < B.end(); i++) {
for (; j < A.end(); ) {
if (*i == *j) {
break;
}
j++;
}
if(j==A.end()){
return false;
}
}
return true;
}
/**
* 使用map O(n+m)
* @param A
* @param B
* @return
*/
bool StringContains3(string &A, string &B) {
map<int,char> bulk;
typedef string::const_iterator it;
for (it i = A.begin(); i<A.end() ; i++) {
bulk.insert(pair<char,int>(*i,1));
}
for (it i = B.begin(); i<B.end() ; i++) {
if(bulk.find(*i)==bulk.end()){
return false;
}
}
return true;
}
/**
* 使用位计算 O(n+m)
* @param A
* @param B
* @return
*/
bool StringContains4(string &A, string &B) {
int bit_counter=0;
typedef string::const_iterator it;
for (it i = A.begin(); i <A.end() ; i++) {
bit_counter|=1<<((*i)-'a');
}
for (it i = B.begin(); i <B.end() ; i++) {
if((bit_counter&(1<<((*i)-'a')))==0){
return false;
}
}
return true;
}
void testStringContain(){
string s1="aafgrsdf fsefvdgdfhfg";
string s2="absdff afsvxcvasdfc";
cout<<StringContains(s1,s2)<<endl;
s1="aafgrsdfsdfscde";
s2="absdffsdafsddafqwdfc";
cout<<StringContains2(s1,s2)<<endl;
cout<<s1<<endl;
map<char,int> bulk;
typedef map<char,int>::const_iterator it;
pair<char,int> data('s',11);
bulk.insert(data);
data={'s',100};
pair<it,bool> temp=bulk.insert(data);
cout <<temp.second<<endl;
it iii=temp.first;
cout <<iii->first<<iii->second<<endl;
s1="aafsdfsdawefscde";
s2="ab";
cout<<StringContains3(s1,s2)<<endl;
s1="aafgrsdefwfgjuytnwabcde";
s2="abgfex";
cout<<StringContains4(s1,s2)<<endl;
}
#endif //THEARTOFPROGRAMING_STRINGCONTAIN_H
最长回文串算法
给定一个字符串，求它的最长回文子串的长度。
/**
* @param s
* @param n
* @return
*/
bool IsPalindrome(const char *s, int n){
if(s== NULL||n<1){
return false;
}
for (int i = 0; i < n/2; ++i) {
if(s[i]!=s[n-i-1]){
return false;
}
}
return true;
}/**
* 穷举法遍历所有长度 O(n^3)
* @param s
* @param n
* @return
*/
int LongestPalindrome(const char *s, int n){
if(s== nullptr||n<1){
return 0;
}
int longest=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=n-i;j++){
if(IsPalindrome(s+j,i)){
longest=longest<i?i:longest;
}
}
}
return longest;
}
/**
* 找中心点向外扩散 O(n^2)
* @param s
* @param n
* @return
*/
int LongestPalindrome2(const char *s, int n){
if(s== nullptr||n<1){
return 0;
}
int longest=0;//长度
//i是中心点下标
for (int i = 0; i <n ; ++i) {
//j是长度
//奇数串
for (int j = 0;(i-j)>=0&&(i+j)<n; ++j) {
if(s[i-j]!=s[i+j]){
break;
}
int c=j*2+1;
longest=longest<c?c:longest;
}
for (int j = 0;(i-j)>=0&&(i+j+1)<n; ++j) {
if(s[i-j]!=s[i+j+1]){
break;
}
int c=j*2+2;
longest=longest<c?c:longest;
}
}
return longest;
}
/**
* Manacher算法 O(n)
* @param s
* @param n
* @return
*/
int LongestPalindrome3(const char *s, int n){
if(s== nullptr||n<1){
return 0;
}
char str[n*2+4];
int j=0;
str[j++]='$';
str[j++]='#';
for (int i = 0; i < n; ++i) {
//使回文串长度变成偶数
str[j++]=*(s+i);
str[j++]='#';
}
str[j]='\0';
int p[j-1];//保存以下标为中心点的最长回文串长度
memset(p,0, sizeof(p));
int mx=0;//回文串最右边界
int idx=0;//回文串中心点
int longest=0;//最长子串
for(int i=1;i<j-1;i++){
p[i]=mx>i?min(mx-i,p[2*idx-i]):1;//2*idx-i 与i关于idx对称,如果p[2*idx-i]比mx-i长则说明p[i]>=p[2*idx-i] 短的话 p[i]=p[2*idx-i]
while(str[i-p[i]]==str[i+p[i]]){
p[i]++; //继续求p[i]的最长回文串
}
longest=p[i]>longest?p[i]:longest;
if(p[i]+i>mx){
mx=p[i]+i;
idx=i;
}
}
return longest-1;
}
吸血鬼算法 高效率版本
取自Java 编程思想 第四章 练习10
[java]
import java.util.Arrays;
/**
* 吸血鬼数字,高效率版本.
* 一个4位数字，可以拆分2个2位数数字的乘积,顺序不限。
* 比如 1395 =15 * 93
*
* @author
*/
public class Vampire {
public static void main(String[] arg) {
String[] ar_str1, ar_str2;
int sum = 0;
int from;
int to;
int i_val;
int count = 0;
// 双重循环穷举
for (int i = 10; i < 100; i++) {
// j=i+1避免重复
from = Math.max(1000 / i, i + 1);
to = Math.min(10000 / i, 100);
for (int j = from; j < to; j++) {
i_val = i * j;
//
if (i_val % 100 == 0 || (i_val – i – j) % 9 != 0) {
continue;
}
count++;
ar_str1 = String.valueOf(i_val).split("");
ar_str2 = (String.valueOf(i) + String.valueOf(j)).split("");
Arrays.sort(ar_str1);
Arrays.sort(ar_str2);
if (Arrays.equals(ar_str1, ar_str2)) {// 排序后比较,为真则找到一组
sum++;
System.out.println("第" + sum + "组: " + i + "*" + j + "=" + i_val);
}
}
}
System.out.println("共找到" + sum + "组吸血鬼数");
System.out.println(count);
}
}
[/java]
假设val = 1000a + 100b + 10c + d, 因为满足val = x * y, 则有x = 10a + b, y = 10c + d
则val – x – y = 990a + 99b + 9c = 9 * (110a + 11b + c), 所以val – x – y能被9整除。
所以满足该条件的数字必定能被9整除，所以可以直接过滤其他数字。
我准许做一下
x*y = val = 1000a + 100b + 10c + d;
我们假设
x = 10a + b, y = 10c + d
则
x*y-x-y
= val – x-y
= (1000a + 100b + 10c + d) – (10a+b) – (10c +d) = 990a + 99b + 9c
= 9 * (110a + 11b + c);
队列的循环数组实现
queue.h
[c]
#include <stdlib.h>
#define QUEUE_TYPE int
void delete(void);
void insert(QUEUE_TYPE value);
QUEUE_TYPE first(void);
int is_empty(void);
int is_full(void);
void create_queue(size_t size);
void destory_queue(void);
[/c]
a_queue.c
[c]
/*
**队列的循环数组实现
*/
#include "queue.h"
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#define QUEUE_SIZE 100
#define ARRAY_SIZE QUEUE_SIZE
static QUEUE_TYPE queue[ARRAY_SIZE];
static front =1;
static rear=0;
void create_queue(size_t size){
}
void destroy_queue(void){
}
void insert(QUEUE_TYPE value){
assert(!is_full());
rear=(rear+1)%ARRAY_SIZE;
queue[rear]=value;
}
void delete(void){
assert(!is_empty());
front=(front+1)%ARRAY_SIZE;
}
QUEUE_TYPE first(void){
assert(!is_empty());
return queue[front];
}
int is_empty(void){
return (front+1)%ARRAY_SIZE==rear;
}
int is_full(void){
return (rear+2)%ARRAY_SIZE==front;
}
void p(void){
int i=0;
int m;
if(rear<front)
rear+=ARRAY_SIZE;
for(i=front;i<rear+1;i++){
m=i;
if(i>=ARRAY_SIZE)
m=i-ARRAY_SIZE;
printf("%dn",queue[m]);
}
}
int main(void){
int j=1;
for(;j<ARRAY_SIZE;j++)
insert(j);
delete();
insert(100);
p();
return 0;
}
[/c]