題目一：

給定一整型數組，從中找到兩個數以使得他們的加和等于給定的數。

其中，時間復雜度要求O(n)

函數原型：

（1）Python語言：

class Solution:

# @return a tuple, (index1, index2)

def twoSum(self, num, target):

#your code

（2）C語言：

int *twoSum(int numbers[], int n, int target) {

?

}

返回值：整型數組中兩個數的下標index1，index2（其中，index1<index2）

測試用例：

Input:?numbers={2, 7, 11, 15}, target=9

Output:?index1=1, index2=2

Input:?numbers={0,0,3,2,8,9,7,8,9,7}, target=0

Output:?index1=1, index2=2

c語言版：

新學了一個叫map的東東，聽說是個容器，用于hash對應。

?

#include <stdio.h> #include<map> using namespace std; int re[2]; int *twoSum(int numbers[], int n, int target) {map<int, int> m;int r, l = n;while (l--) {r = m[target - numbers[l]];//沒有對應的值則為0if (r != 0){ //有對應的值表示當前的數和r位置的數是結果re[0] = l + 1;re[1] = r + 1;break;}m[numbers[l]] = l;}return re; }int main(){int n=4;int numbers[]={2, 7, 11, 15};int target=13;int *result;result=twoSum(numbers,n,target);printf("index1=%d,index2=%d\n",result[0],result[1]);return 0; }

?

python版（有問題）：

# -*- coding: utf-8 -*-class Solution:# @return a tuple, (index1, index2)def twoSum(self, num, target):index = range(len(num)) #下標d=dict(zip(num,index)) #原列表與下標對應起來，形成字典find=0print 'd=',dfor n in num:# print 'n=',n# print 'target-n=',target-nif ((target-n) in d.keys())and(d[target-n]!=d[n]):index1=d[n]+1index2=d[target-n]+1print''find=1breakif find==0:print"there is no results"else:return (index1,index2)if __name__=="__main__":num=[1,0,5,0,8]print numtarget=0S=Solution()result=S.twoSum(num,target)print("index1=",result[0],"index2=",result[1])

原諒我放了一個有問題的代碼，本來覺得用字典很是方便，不過它不允許存在鍵值相同的元素，如果遇到num=[2,3,3,3,5],target=6這種情況怎么辦呢？

對了，剛開始還把列表初始化用成了{}，還以為列表是無序的，錯怪了它。

題目二：

給定一個字符串S，找到S中最長的回文字串。假設S的長度小于1000，并且只存在一個最長回文字串。

補充：回文字串就是字符串正序和逆序是完全相同。

要求：時間復雜度不超過O(n^2),有能力考慮O(nlogn)或者O(n)算法

函數原型：

返回值：最長回文字串的起始地址，并將其打印出來

C語言：char *longestPalindrome(char *s) {

?

}

Python語言：

class Solution:

# @return a string

def longestPalindrome(self, s):

測試用例：

Input:?str = ‘eabcbadf’

Output:?‘abcba’

?

#include <stdio.h>
#include <cstring>
?
int p[2005];//對應以每個字符為中心的回文串的長度的一半，人家叫半徑好吧
char str[2005];
int min(int a,int b){
?? ?if(a<b)
?? ??? ?return a;
?? ?else
?? ??? ?return b;
}
char *longestPalindrome(char *s) {
??? int len = strlen(s), k = 1, i, num;
??? str[0] = '$';
??? for (i = 0; i < len; ++i){
??????? str[k++] = s[i];
??????? str[k++] = '#';
??? }
??? str[k - 1] = '@';
??? //以上是加工原字符串，將每個字符用'#'隔開，以保證‘aa’這種也可以被處理
?? ?p[0] = 0;
??? int maxRight = 1, maxCenter = 1;
?? ?//maxCenter是已處理的字符串的最大回文串的中心位置，maxRight是該回文串的最右位置，記錄最右位置的意義就在于每個字符只需要被計算一遍，不走回頭路，才能將效率提高到O(n)
??? int re=0;//re的含義后面揭曉
??? for (i = 1; i < k; ++i){
??????? if(maxRight > i)//如果現在的位置被包括在到目前為止最大的回文串，可以找到與它對稱的那個點作為參考，還挺聰明的
??????????? p[i] = min(maxRight - i + 1, p[(maxCenter<<1) - i]);
??????? else
??????????? p[i] = 1;
??????? while(str[i - p[i]] == str[i + p[i]])//然后往兩邊擴展
??????????? ++p[i];
??????? if(i + p[i] - 1 > maxRight){//如果擴展的超過了原來的最大回文串的位置，就再往后面挪動
??????????? maxRight = i + p[i] - 1;
??????????? maxCenter = i;
??????? }
??????? if(p[i] > p[re])//以re為中心的回文串最長
??????????? re = i;
??????? else if(p[i] == p[re] && str[i] != '#')
??????????? re = i;
??? }
??? k = 0;
??? num = p[re];//num是最大回文串的半徑
??? re -= (num - 1);//re變身為最大回文串起始位置
??? num = (num << 1) - 1;//num變身為最大回文串結束位置
??? for(i = 0; i < num; ++i) {//這里真的是從0開始嗎？！！！
??????? if(str[re] != '#')
??????? str[k++] = str[re];
??????? ++re;
??? }
??? str[k] = 0;//將最大回文串存放到str里，并以0結尾
??? return str;
}
?
int main() {
??? char originalStr[2005], *result;
??? gets(originalStr);
??? result = longestPalindrome(originalStr);
??? printf("%s\n", result);
??? return 0;
}

?

?

我可以說這個題已經遠遠超出了我的智力范圍了嗎，一個點一個點的給我講都是打了二十多個哈欠才勉強有點懂了，更別說自己看代碼了。

至于什么是動態規劃，原來這個算法是Manacher算法，好吧，恕我無知。隨便找個人家的帖子都比我說的清楚很多，先記錄一個吧：

http://blog.csdn.net/pi9nc/article/details/9251455

?

轉載于:https://www.cnblogs.com/myblog-lyc/p/4324419.html

總結

以上是生活随笔為你收集整理的小题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。