查找单链表的倒数第k个值 刚开始，我想到的是一种笨方法，
查找单链表的倒数第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
#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
#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
#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
#include
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
#include
#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 ) {
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
#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
#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://blog.csdn.net/zzran/article/details/8456721
参考：http://blog.csdn.net/zzran/article/details/8108787
![[编程题] LeetCode上的Dynamic Programming(动态规划)类型的题目](https://img1.php1.cn/3cd4a/24cea/42f/ab7ad6031d31eee4.jpeg)
京公网安备 11010802041100号