leetcode336. Palindrome Pairs 372. Super Pow

336. Palindrome Pairs

题目大意

给你n个字符串，选出任意两个不同的字符串i和j，其拼接后是否为回文子串，返回所有可能的小标组合。

思路一

直接遍历所有可能的组合，并判断是否为回文子串，其时间复杂度为O（k*n^2） 代码如下：

/** 值得注意的是，在c语言中不能进行应用的传递，所以在返回多个参数的时候，就只能进行指针传递 另外，在进行realloc的时候，只能对指针的一维进行扩展！！！ */ //is palindrome pair? bool is_ok(char *s1, int len1, char *s2, int len2){ char tmp[len1+len2]; for(int i=0; i<len1; i++) tmp[i] = s1[i]; for(int i=0; i<len2; i++) tmp[len1+i] = s2[i]; int l = 0, r = len1+len2-1; while(l < r){ if(tmp[l] != tmp[r]) return false; l++, r--; } return true; } int** palindromePairs(char** words, int wordsSize, int** columnSizes, int* returnSize) { *returnSize = 0; (*columnSizes) = (int*)malloc(sizeof(int)); int *first,*second;// to record the pairs first = malloc(sizeof(int)); second = malloc(sizeof(int)); for(int i=0; i<wordsSize; i++){ for(int j=0; j<wordsSize; j++){ if(i == j)continue; if(is_ok(words[i], strlen(words[i]), words[j], strlen(words[j]))){ //update the pairs (*returnSize) ++; (*columnSizes) = (int *) realloc(*columnSizes, sizeof(int) * (*returnSize)); (*columnSizes)[(*returnSize)-1] = 2; first = realloc(first, sizeof(int) * (*returnSize)); second = realloc(second, sizeof(int) * (*returnSize)); first[(*returnSize)-1] = i; second[(*returnSize)-1] = j; } } } int **ret; ret = malloc(sizeof(int *)*(*returnSize)); for(int i=0; i<(*returnSize); i++){ ret[i] = malloc(sizeof(int) * 2); ret[i][0] = first[i]; ret[i][1] = second[i]; } return ret; }

思路二

其实第一种方法过于暴力，谁都可以想到，我以为一定挂了，但是毕竟是c，速度还可以，没有挂掉 第二种方法是使用hash的方法。可以使用一个字典来记录下每个字符串的下标和字符的关系，对于每个字符串做如下处理： 1. 将每个字符串依次分隔为left和right两个部分 2. 对于每个分隔，作如下处理 + 如果left是回文子串，那么查询right的逆串是否存在于字典当中，如果存在，将当前下标和right逆串的下标作为一组返回 + 如果right是回文子串，那么查询left的逆串是否存在于字典当中，如果存在，将left逆串的小标和当前下标作为一组返回 该方法的时间复杂度为O(k*n*(字典查询时间))。 由于在c中好像并没有字典，所以，暂时也就没去实现这个方法。

---

372. Super Pow

题目大意

计算a^b mod(1337)，其中a是一个正整数，b是一个很大的正整数，以数组的形式给出。

思路

最开始我想到的是费马定理，想将a^b分解为a^(（bi*(10^i)）%1337)mod(1337)的计算，但是没有注意到1337并不是一个素数，所以不可以使用费马定理。 由于(a*b)%k = (a%k)*(b%k)%k，所以按照上面的思想，一次计算b的每一位mod1337的答案，然后乘起来并模上1337即可。

int superPow(int a, int* b, int bSize) { int ans = 1; int ji = a%1337;//use it to record a^(10^k)mod(1337) for(int i=bSize-1; i>=0; i--){ //calculate the ith palce int tmp = 1; for(int j=0; j<b[i]; j++){ tmp *= ji; tmp %= 1337;} ans *= tmp; ans %= 1337; //update the record tmp = 1; for(int j=0; j<10; j++){ tmp *= ji; tmp %= 1337;} ji = tmp; } return ans; }