一些数据结构的思想(1)

更新时间：2022-08-20 20:18:40

查找单链表的倒数第k个值

刚开始，我想到的是一种笨方法，先遍历单链表，计算出单链表的长度len，然后再从头遍历单链表到第len-k个节点，那么这个节点既是单链表的倒数第k个节点。不过这种算法时间复杂度挺高的，还有一种更简单的方法，就是设置两个指针，分别指向单链表的头节点，然后让其中一个指针，先走k步，之后，再让两个指针同时走，直到第一个指针走到单链表尾节点结。

Java分词

Lucene，http://www.cnblogs.com/zuoxiaolong/p/lang2.html

php分词

一个专门的库 http://www.cnblogs.com/xshang/p/3603037.html

判断一个链表是不是循环链表

算法思想：在建立循环链表时设置两个指针，头指针和尾指针，head和tail,使tail->next=head,即让尾节点指向头节点，建立的时候采用尾插入法，每次让新节点先指向尾节点的下一个节点，然后让头节点的下一个节点指向新节点，然后让新节点赋值给头节点和尾节点。

判断是否是循环链表时，也设置两个指针，慢指针和快指针，让快指针比慢指针每次移动快两次。如果快指针追赶上慢指针，则为循环链表，否则不是循环链表，如果快指针或者慢指针指向NULL，则不是循环链表。

有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。

问题：

1、如何判断一个链表是不是这类链表？ 2、如果链表为存在环，如果找到环的入口点？

一、判断链表是否存在环，办法为：

设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)。

二、找到环的入口点：

当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则 fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：

2s = s + nr

s= nr

设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。

a + x = nr

a + x = (n – 1)r +r = (n-1)r + L – a

a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。

一、将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。

二、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。

这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点

一个整型数组里除了一个或者两个或者三个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)

如果只有一个出现一次，考察到异或的性质，就是如果同一个数字和自己异或的活结果为零，那么循环遍历一遍数组，将数组中的元素全部做异或运算，那么出现两次的数字全部异或掉了，得到的结果就是只出现一次的那个数字。
如果有两个只出现一次的数字，设定为a,b。也是应用异或，但是数组元素全部异或的结果x=a^b，因为a,b是不相同的数字，因此x肯定不为0。对于x，从低位到高位开始，找到第一个bit位为1的位置设定为第m位，这个第m位的bit肯定来自a或者来自b，不可能同时a,b的第m位（从低到高位）都为1。这样，就可以根据这个第m位就可以把数组分为两个部分，一组为第m位为0，一组为第m位为1.这样，就把问题分解成了求两个数组中只出现一次的数字了。
考虑给定数组中有三个单独出现一次的数字，这个会比有两个的稍微复杂。分步分析，设定这三个数为a,b,c:

(1)将数组中的数字全部异或，得到的结果x=a^b^c，但是x不是a，b，c中的其中一个，假设x=a，那么b^c=0说明b=c，与题目给定的条件矛盾。

(2)设定f(n)可以像2中的那样，从低位开始，找到第一个bit为1的位置，f(x^a),f(x^b),f(x^c)得到的值肯定都不为0，因为x^a,x^b,x^c本身就不为0。f(x^a)^f(x^b)^f(x^c)结果不为0。因为f(x^a)^f(x^b)的结果中可能为0，也可能有两个bit为1。如果假设f(x^c)的结果bit为1的位置与f(x^a)^f(x^b)的其中一个重合，则f(x^a)^f(x^b)^f(x^c)结果中只有1个bit为1，如果不重合的话那么有3个bit位为1。

(3)这便可以推断出f(x^a)^f(x^b)^f(x^c)中至少有一个bit位为1。假设从低位到高位的第mbit位为1.那么可以得出结论x^a,x^b,x^c中有一个或者三个的第m位为1（不可能有两个，因为有两个的话，异或的结果就为0了）。

(4)证明，x^a,x^b,x^c中只有一个第m-bit位为1.假设他们的第m位都为1，那么x的第m位为0，但是x=a^b^c其第m位肯定为1，所以假设不成立。那么相反，假设x的第m位为1，a,b,c的第m位都为0，也不成立，因为x=a^b^c。所以综上所述x^a,x^b,x^c中只有一个第m位为1。那么这个问题就好办了。根据这个第m位找到第一个只出现一次的数字。

将给定的英文字符串进行反转

双指针，一个在最前面，一个在最后面，然后调换内容。

例如： I love programming。得到的结果是：.gnimmargorp evol I。下面给出核心代码：

#include<stdio.h>  
#include<string.h>  
  
void swap_string(char *p_start, char *p_end) {  
    char temp;  
    while(p_start <= p_end) {  
        temp = *p_start;  
        *p_start = *p_end;  
        *p_end = temp;  
        p_start++;  
        p_end--;  
    }  
}  
  
void main() {  
    char str[] = "I love programming.";  
    swap_string(str, str + strlen(str) - 1);  
    printf("%s\n", str);  
}

给定一个字符串，例如：" test ** "，要求出去字母之外其他多余的字符

这也需要设定两个指针，一个慢指针和一个快指针，如果快指针指到的是字母，则赋值给慢指针，否则快指针继续前进，核心代码如下：

#include<stdio.h>  
#include<string.h>  
  
void trim_word(char *word) {  
    char *p_slow = word;  
    char *p_fast = word;  
    while(*p_fast) {  
        if(!(*p_fast >= 'a' && *p_fast <= 'z') && !(*p_fast >= 'A' && *p_fast <= 'Z')) {  
            p_fast++;  
        } else {  
            *p_slow++ = *p_fast++;  
        }  
    }  
    *p_slow = '\0';  
}  
void main() {  
    char word[] = "   test **   ";  
    trim_word(word);  
    printf("%s\n", word);  
}

给定一个字符串，例如："abccba"，判断它是否是回文

可以应用数组解决，但是数组的索引速度没有指针的移动速度快，所以设定两个指针，一个指向字符串开始，一个指向字符串结尾，同步移动。核心代码如下：

#include<stdio.h>  
#include<string.h>  
  
int is_palindrome(char *str) {  
    char *p_start = str;  
    char *p_end = str + strlen(word) - 1;  
    while(p_start < p_end) {  
        if(*p_start != *p_end) {  
            return 0;  
        }  
        p_start++;  
        p_end--;  
    }  
    return 1;  
}  
void main() {  
    char string[] = "abccba";  
    if(is_palindrome(string)) {  
        printf("string is palindrome.\n");  
    } else {  
        printf("string is not palindrome.\n");  
    }  
}

给定一个有序数组，然后给定一个数字m，在数组中找出两个数，使得这两个数的和与m相等

#include<stdio.h>    
#include<stdlib.h>   
  
void FindTwoNumbers(int a[], int n, int dest)  {    
    int *e, *f;    
    e = a;    
    f = a + n - 1;    
    int sum;    
    sum = *e + *f;    
    while(sum != dest && e < f)    
    {    
        if(sum < dest) {    
            sum = sum - *e + *(++e);   
        } else {     
            sum = sum - *f + *(--f);  
        }  
    }    
    if(sum == dest) {    
        printf("%d=%d+%d\n",dest,*e,*f);  
    } else {  
        printf("not find\n");  
    }  
}    
  
void main()    
{     
    int num[] = {1, 2, 4, 7, 11, 15};    
    int temp = 9;    
    FindTwoNumbers(num, sizeof(num)/sizeof(int), temp);    
}

字符串移位问题

就是字符串移位问题，这个也用到的双指针，假设给定字符串“abcdefg”，让字符串向左移动三位,得到的结果是：“defgabc”,这个怎么做呢，首先找到分界点，将字符串分为两部分，很自然的分界点应该和移动位数有关，故将字符串分为:abc,defg两部分，先分别将两部分翻转成：cbagfed，然后再将整个字符串翻转：defgabc。

输入两个字符串，从第一字符串中删除第二个字符串中所有的字符

例如，输入”They are students.”和"aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”。这个题的思路其实也可以用双指针来完成。首先我们还得设定一个hash表，来记录在第二个字符串中有哪些字母出现。当hash值等于1的时候表示在第二个字符串，也就是要除去的字符串中出现，等于0的时候表示不出现。然后遍历第一个字符串，设定两个指针，一个p_slow, 一个p_fast，如果某个单词的hash值为1，说明要从原始字符串中除去这个单词，那么p_fast++。这个讲解起来有点不清晰，直接给出代码吧。

#include<stdio.h>  
#include<stdlib.h>  
#include<string.h>  
  
void trim_string(char *string, char *trim_str) {  
    int hash[256] = {0};  
    int len_trim = strlen(trim_str);  
    char *p_slow = string;  
    char *p_fast = string;  
    int i;  
    for(i = 0; i < len_trim; i++) {  
        hash[trim_str[i]]++;  
    }  
    while(*p_fast) {  
        if(hash[*p_fast] > 0) {  
            p_fast++;  
        } else {  
            *p_slow++ = *p_fast++;  
        }  
    }  
    *p_slow = '\0';  
}  
  
void main() {  
    char string[] = "They are students.";  
    char trim[] = "aeiou";  
    trim_string(string, trim);  
    printf("%s\n", string);  
}

在O（n）时间内删除字符串中重复的字符，不使用Hash

位图，bitmap：

#include<stdio.h>  
#include<string.h>  
  
void remove_duplicate(char *str) {// assume all characters are little   
    char *p_slow = str;  
    char *p_fast = str;  
    int flag = 0;  
    int value;  
    int bits;  
    while(*p_fast) {  
        value = 1;  
        bits = *p_fast - 'a';  
        value = (value << bits);  
        if((flag & value) == value) {  
            p_fast++;  
        } else {  
            *p_slow++ = *p_fast++;  
            flag |= value;  
        }  
    }  
    *p_slow = '\0';  
}  
  
void main() {  
    char str[] = "abcddbcdefghijm";  
    remove_duplicate(str);  
    printf("%s\n", str);  
    getchar();  
}

反转句子中单词的顺序，忽略标点符号的处理

反转句子中单词的顺序，即把一个英文句子的单词顺序倒转，忽略标点符号的处理,例如： I love linux programming. 操作之后结果： .programming linux love I。也需要设定双指针，这个情况和题目1有相似之处，但是又不完全的相同，需要在反转的过程中做一些判断，下面给出代码：

#include<stdio.h>  
#include<string.h>  
void swap_block(char *start, char *end) {  
    char temp;  
    while(start < end) {  
        temp = *start;  
        *start = *end;  
        *end = temp;  
        start++;   
        end--;  
    }  
}  
  
void reverse_sentence(char *str) {  
    char *p_slow = NULL;  
    char *p_fast = NULL;  
    swap_block(str, str + strlen(str) - 1);  
    p_slow = str;  
    p_fast = str;  
    while(*p_fast) {  
        if((*p_fast >= 'a' && *p_fast <= 'z') || (*p_fast >= 'A' && *p_fast <= 'Z')) {  
            p_fast++;  
        } else {  
            swap_block(p_slow, p_fast - 1);  
            while(!(*p_fast >= 'a' && *p_fast <= 'z') && !(*p_fast >= 'A' && *p_fast <= 'Z')) {  
                p_fast++;//跳过多余的空格  
            }  
            p_slow = p_fast;  
        }  
    }  
}  
  
void main() {  
    char str[] = "I love linux programming.";  
    reverse_sentence(str);  
    printf("%s\n", str);  
    getchar();  
}

本文转自我爱物联网博客园博客，原文链接：http://www.cnblogs.com/yydcdut/p/3873341.html如需转载请自行联系原作者

一些数据结构的思想(1)

相关阅读

推荐文章