存档

‘算法’ 分类的存档

字符串翻转算法

2018年2月8日 没有评论
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;
        }
    }
}

分类: 算法 标签:

字符串字母包含算法

2018年2月8日 没有评论

给定两个分别由字母组成的字符串A和字符串B,字符串B的长度比字符串A短。请问,如何最快地判断字符串B中所有字母是否都在字符串A里?

为了简单起见,我们规定输入的字符串只包含大写英文字母,请实现函数bool StringContains(string &A, string &B)



/**
 * 穷举查找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="aafgrsdfsdfsdafsdafsefwefsdacsdfvdgdfhfgjuytnwabcde";
    string s2="absdffsdafsddafqwrwesdfrsdafsvxcvasdfc";
    cout<<StringContains(s1,s2)<<endl;
    s1="aafgrsdfsdfsdafsdafsefwefsdacsdfvdgdfhfgjuytnwabcde";
    s2="absdffsdafsddafqwrwesdfrsdafsvxcvasdfc";
    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="aafgrsdfsdfsdafsdafsefwefsdacsdfvdgdfhfgjuytnwabcde";
    s2="ab";
    cout<<StringContains3(s1,s2)<<endl;
    s1="aafgrsdfsdfsdafsdafsefwefsdacsdfvdgdfhfgjuytnwabcde";
    s2="abgfex";
    cout<<StringContains4(s1,s2)<<endl;
}



分类: 算法 标签:

最长回文串算法

2018年2月8日 没有评论
给定一个字符串,求它的最长回文子串的长度。
/**
 * @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;
} 

 

分类: 算法 标签:

吸血鬼算法 高效率版本

2014年7月12日 评论已被关闭

取自Java 编程思想 第四章 练习10

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);
  }
}

假设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);

分类: 算法 标签:

队列的循环数组实现

2013年3月6日 没有评论

queue.h

#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);


a_queue.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;
}
分类: 算法 标签: