力扣(LeetCode)刷題，簡單+中等題(第31期)

目錄

第1題：同構字符串

第2題：最后一塊石頭的重量

第3題：最小路徑和

第4題：鍵盤行

第5題：存在重復元素 II

第6題：兩數相加

第7題：三個數的最大乘積

第8題：等價多米諾骨牌對的數量

第9題：公平的糖果棒交換

第10題：替換后的最長重復字符

力扣(LeetCode)定期刷題，每期10道題，業務繁重的同志可以看看我分享的思路，不是最高效解決方案，只求互相提升。

第1題：同構字符串

試題要求如下：

回答（C語言）：

#define MAX_NUM 128

bool isIsomorphic(char * s, char * t){

int sLen = 0;

int tLen = 0;

int *hash1 = NULL;

int *hash2 = NULL;

sLen = strlen(s);

tLen = strlen(t);

// 特殊處理

if (sLen != tLen) {

return false;

}

// 分配空間

hash1 = malloc(sizeof(int) * MAX_NUM);

memset(hash1, 0, sizeof(int) * MAX_NUM);

hash2 = malloc(sizeof(int) * MAX_NUM);

memset(hash2, 0, sizeof(int) * MAX_NUM);

// 統計字符串出現的次數

for (int i = 0; i < sLen; i++) {

if (hash1[s[i]] == 0) {

hash1[s[i]] = t[i];

}

if (hash2[t[i]] == 0) {

hash2[t[i]] = s[i];

}

if (hash1[s[i]] != t[i] || hash2[t[i]] != s[i]) {

return false;

}

}

return true;

}

運行效率如下所示：

第2題：最后一塊石頭的重量

試題要求如下：

回答（C語言）：

int cmp(const void* _a, const void* _b){

int a = *(int*)_a;

int b = *(int*)_b;

return b-a;

}

int lastStoneWeight(int* stones, int stonesSize){

if(stonesSize <=1){

return stones[0];

}

qsort(stones,stonesSize,sizeof(int),cmp);

while(stones[1] != 0){

stones[0] = stones[0] - stones[1];

stones[1] = 0;

qsort(stones,stonesSize,sizeof(int),cmp);

}

return stones[0];

}

運行效率如下所示：

第3題：最小路徑和

試題要求如下：

回答（C語言）：

int minPathSum(int** grid, int gridSize, int* gridColSize) {

int rows = gridSize, columns = gridColSize[0];

if (rows == 0 || columns == 0) {

return 0;

}

int dp[rows][columns];

dp[0][0] = grid[0][0];

for (int i = 1; i < rows; i++) {

dp[i][0] = dp[i - 1][0] + grid[i][0];

}

for (int j = 1; j < columns; j++) {

dp[0][j] = dp[0][j - 1] + grid[0][j];

}

for (int i = 1; i < rows; i++) {

for (int j = 1; j < columns; j++) {

dp[i][j] = fmin(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

}

}

return dp[rows - 1][columns - 1];

}

運行效率如下所示：

第4題：鍵盤行

試題要求如下：

解題思路：

1、先在 a 空間中，將3行鍵盤的下標分別記為1，2，3；

2、遍歷數組，如果不在同一行就退出；

3、如果是正常退出的，將單詞記錄。

回答（C語言）：

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

char ** findWords(char ** words, int wordsSize, int* returnSize){

*returnSize=0;

char **res=(char**)malloc(sizeof(char*)*wordsSize);

char *a=(char*)calloc(59,sizeof(char));

for(int i=0;i<58;i++){

if(i=='Q'-65||i=='W'-65||i=='E'-65||i=='R'-65||i=='T'-65||i=='Y'-65||i=='U'-65||i=='I'-65||i=='O'-65||i=='P'-65||i=='q'-65||i=='w'-65||i=='e'-65||i=='r'-65||i=='t'-65||i=='y'-65||i=='u'-65||i=='i'-65||i=='o'-65||i=='p'-65)

a[i]=1;

else if(i=='A'-65||i=='S'-65||i=='D'-65||i=='F'-65||i=='G'-65||i=='H'-65||i=='J'-65||i=='K'-65||i=='L'-65||i=='a'-65||i=='s'-65||i=='d'-65||i=='f'-65||i=='g'-65||i=='h'-65||i=='j'-65||i=='k'-65||i=='l'-65)

a[i]=2;

else

a[i]=3;

}

int i,j;

for(i=0;i

for(j=1;j

char t=a[words[i][0]-65];

if(t!=a[words[i][j]-65])

break;

}

if(j==strlen(words[i])){

res[*returnSize]=(char*)calloc(strlen(words[i])+1,1);

strcpy(res[*returnSize],words[i]);

(*returnSize)++;

}

}

return res;

}

運行效率如下所示：

第5題：存在重復元素 II

試題要求如下：

回答（C語言）：

bool containsNearbyDuplicate(int* nums, int numsSize, int k){

if(numsSize==0)

return false;

int mark[numsSize];//Hash表

memset(mark,-1,sizeof(int)*numsSize);

for(int i = 0, tmp = 0; i < numsSize; i++)

{

tmp=nums[i]%numsSize;//Hash函數

if(tmp<0)//轉換為正數

tmp+=(numsSize-1);

if(mark[tmp]==-1)//沒有存數

mark[tmp]=i;//存下數組下標

else//已經存數

{

while(nums[mark[tmp]]!=nums[i])//發生沖突

{

tmp++;tmp%=numsSize;

if(mark[tmp]==-1)//沒有存數

mark[tmp]=i;//存下數組下標

}

//已經存過該數

if(i!=mark[tmp])

if(i-mark[tmp]<=k)//求差值

return true;

else

mark[tmp]=i;

}

}

return false;

}

運行效率如下所示：

第6題：兩數相加

試題要求如下：

回答（C語言）：

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){

struct ListNode* pre = (struct ListNode*)malloc(sizeof(struct ListNode));

pre->val = 0;

pre->next = NULL;

struct ListNode* cur = pre;

int carry = 0;

int sum = 0;

while(l1 != NULL || l2 != NULL){

int x = (l1 == NULL) ? 0:l1->val;

int y = (l2 == NULL) ? 0:l2->val;

sum = x + y + carry;

carry = sum / 10;

struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));

p->val = sum % 10;

p->next = NULL;

cur->next = p;

cur = cur->next;

if(l1 != NULL){

l1 = l1->next;

}

if(l2 != NULL){

l2 = l2->next;

}

}

if(carry == 1){

struct ListNode* ca = (struct ListNode*)malloc(sizeof(struct ListNode));

ca->val = carry;

ca->next = NULL;

cur->next = ca;

}

return pre->next;

}

運行效率如下所示：

第7題：三個數的最大乘積

試題要求如下：

解題思路：

假設若使用排序法。

如果數組中全是非負數，則排序后最大的三個數相乘即為最大乘積；如果全是非正數，則最大的三個數相乘同樣也為最大乘積。

如果數組中有正數有負數，則最大乘積既可能是三個最大正數的乘積，也可能是兩個最小負數（即絕對值最大）與最大正數的乘積。

所以，根據此規律，使用線性掃描法實現。

回答（C語言）：

int maximumProduct(int* nums, int numsSize) {

// 最小的和第二小的

int min1 = INT_MAX, min2 = INT_MAX;

// 最大的、第二大的和第三大的

int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;

for (int i = 0; i < numsSize; i++) {

int x = nums[i];

if (x < min1) {

min2 = min1;

min1 = x;

} else if (x < min2) {

min2 = x;

}

if (x > max1) {

max3 = max2;

max2 = max1;

max1 = x;

} else if (x > max2) {

max3 = max2;

max2 = x;

} else if (x > max3) {

max3 = x;

}

}

return fmax(min1 * min2 * max1, max1 * max2 * max3);

}

運行效率如下所示：

第8題：等價多米諾骨牌對的數量

試題要求如下：

回答（C語言）：

int numEquivDominoPairs(int** dominoes, int dominoesSize, int* dominoesColSize) {

int num[100];

memset(num, 0, sizeof(num));

int ret = 0;

for (int i = 0; i < dominoesSize; i++) {

int val = dominoes[i][0] < dominoes[i][1] ? dominoes[i][0] * 10 + dominoes[i][1] : dominoes[i][1] * 10 + dominoes[i][0];

ret += num[val];

num[val]++;

}

return ret;

}

運行效率如下所示：

第9題：公平的糖果棒交換

試題要求如下：

解題思路：

假設數組 A 和 B 的元素之和分別為 sumA 和 sumB，待交換的元素分別為 x 和 y，則按照題目的要求必然存在以下等式成立：sumA - x + y = sumB + x - y

將等式 sumA - x + y = sumB + x - y 進一步簡化，可得 x = (sumA - sumB) / 2 + y，即在數組 A 中必須存在一個值為 (sumA - sumB) / 2 + y 的元素。

此時，這個問題就簡化為：在數組中查找一個元素的值等于目標值 target 了。

回答（C語言）：

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int cmp(const void *a, const void *b) {

return *(int *)a - *(int *)b;

}

int* fairCandySwap(int* A, int ASize, int* B, int BSize, int* returnSize){

*returnSize = 0;

int *res = (int *)malloc(2 * sizeof(int));

/* 判斷是否動態內存是否申請成功*/

if (res == NULL) {

return NULL;

}

*returnSize = 2;

int sumA = 0, sumB = 0, diff = 0;

/* 求數組 A 和 B 的和*/

for (int i = 0; i < ASize; ++i) {

sumA += A[i];

}

for (int j = 0; j < BSize; ++j) {

sumB += B[j];

}

diff = sumA - sumB;

/* 排序，為后面進行二分查找做準備 */

qsort(A, ASize, sizeof(int), cmp);

for (int k = 0; k < BSize; ++k) {

/* 二分查找的目標元素 */

int target = diff / 2 + B[k];

int l = 0, r = ASize - 1;

/* 二分查找 */

while (l <= r) {

int m = l + (r - l)/2;

if (A[m] > target) {

r = m - 1;

} else if (A[m] < target) {

l = m + 1;

/* 查找到目標元素，對數組元素賦值并返回 */

} else {

res[0] = target;

res[1] = B[k];

return res;

}

}

}

return NULL;

}

運行效率如下所示：

第10題：替換后的最長重復字符

試題要求如下：

解題思路：

1、定義一個長度為 26 的整型數組（字符串僅包含大寫英文字母），用于模擬哈希表（記錄重復字母出現次數）；

2、分別定義兩個指針（字符下標），用于遍歷字符串，兩個指針組成的區間構成一個滑動窗口，當它們之間的間距大于字母當前出現最大頻次加上 k 時，代表替換 k 次仍不能使得這個窗口之間的字母全是相同，此時需要將向右移動（縮小窗口的大小），同時將頻次遞減（增大了左邊界）；否則 r 向右移動增大窗口。

回答（C語言）：

int characterReplacement(char * s, int k){

int maxCnt = 0;

int l = 0, r = 0; // 滑動窗口[l, r)

int freq[26] = {0}; // 記錄重復字符出現頻次

int lenS = strlen(s);

while (r < lenS) {

freq[s[r] - 'A']++; // 計算當前字符出現頻次

maxCnt = fmax(maxCnt, freq[s[r++] - 'A']); // 計算當前字符出現的最大頻次

if (r - l > maxCnt + k) { // 滑動窗口大小大于字母最大頻次加上能替換的次數

freq[s[l++] - 'A']--; // l 右移動減少滑動窗口大小，同時頻次減減

}

}

return r - l;

}

運行效率如下所示：

HTTP 數據結構 匯編語言

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。