查找單鏈表的倒數第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)
(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://blog.csdn.net/zzran/article/details/8456721
參考：http://blog.csdn.net/zzran/article/details/8108787
一、排序算法1、有簡單排序（包括冒泡排序、插入排序、選擇排序）2、快速排序，很常見的3、堆排序，4、歸並排序，最穩定的，即沒有太差的情況二、搜索算法最基礎的有二分搜索算法，最常見的搜索算法，前提是序列已經有序還有深度優先和廣度有限搜索；及使用剪枝，A*，hash表等方法對其進行優化。三、當然，對於基本數據結構，棧，隊列，樹。都有一些基本的操作例如，棧的pop，push，隊列的取隊頭，如隊；以及這些數據結構的具體實現，使用連續的存儲空間（數組），還是使用鏈表，兩種具體存儲方法下操作方式的具體實現也不一樣。還有樹的操作，如先序遍歷，中序遍歷，後續遍歷。當然，這些只是一些基本的針對數據結構的算法。而基本算法的思想應該有：1、回溯2、遞歸3、貪心4、動態規劃5、分治有些數據結構教材沒有涉及基礎算法，lz可以另外找一些基礎算法書看一下。有興趣的可以上oj做題，呵呵。算法真的要學起來那是挺費勁。
所謂的基本算法應該是指：
一、排序算法
1、有簡單排序（包括冒泡排序、插入排序、選擇排序）
2、快速排序，很常見的
3、堆排序，
4、歸並排序，最穩定的，即沒有太差的情況
二、搜索算法
最基礎的有二分搜索算法，最常見的搜索算法，前提是序列已經有序
還有深度優先和廣度有限搜索；及使用剪枝，A*，hash表等方法對其進行優化。
三、當然，對於基本數據結構，棧，隊列，樹。都有一些基本的操作
例如，棧的pop，push，隊列的取隊頭，如隊；以及這些數據結構的具體實現，使用連續的存儲空間（數組），還是使用鏈表，兩種具體存儲方法下操作方式的具體實現也不一樣。
還有樹的操作，如先序遍歷，中序遍歷，後續遍歷。
當然，這些只是一些基本的針對數據結構的算法。
而基本算法的思想應該有：
1、回溯
2、遞歸
3、貪心
4、動態規劃
5、分治
有些數據結構教材沒有涉及基礎算法，lz可以另外找一些基礎算法書看一下。有興趣的可以上oj做題，呵呵。算法真的要學起來那是挺費勁。
