1、字符串中獲取最長無重復字符子串。
要在字符串中找到最長的無重復字符的子串，可以使用滑動窗口技術。滑動窗口通過兩個指針來表示當前窗口的起始和結束位置，并且維護一個哈希表來記錄字符及其最后出現的位置，以此來確保字符不重復。
以下是用C語言實現的代碼：
#include <stdio.h>
#include <string.h>
?
#define MAX_CHARS 256
?
int longestUniqueSubsttr(char *str) {int n = strlen(str);int current_len = 1; ?// 當前子串的長度int max_len = 1; ? ? ?// 結果int prev_index; ? ? ? //前一個索引
?int *visited = (int *)malloc(sizeof(int) * MAX_CHARS);
?for (int i = 0; i < MAX_CHARS; i++) {visited[i] = -1;}
?visited[(int)str[0]] = 0;
?for (int i = 1; i < n; i++) {prev_index = visited[(int)str[i]];
?if (prev_index == -1 || i - current_len > prev_index) {current_len++;} else {if (current_len > max_len) {max_len = current_len;}current_len = i - prev_index;}
?visited[(int)str[i]] = i;}
?if (current_len > max_len) {max_len = current_len;}
?free(visited);
?return max_len;
}
?
int main() {char str[] = "abcabcbb";printf("最長無重復字符子串的長度是 %d\n", longestUniqueSubsttr(str));return 0;
}
解釋：
-
初始化：
-
visited數組用于存儲每個字符的最后出現位置，大小為MAX_CHARS（ASCII 字符集）。 -
初始化
visited數組為 -1，表示所有字符初始時都未出現過。
-
-
遍歷字符串：
-
對于每個字符，檢查它是否在當前窗口內已出現。
-
使用
prev_index保存字符上次出現的位置。 -
如果字符未出現或者不在當前窗口內，當前窗口長度
current_len加 1。 -
如果字符在當前窗口內已出現，更新最大長度
max_len，并重置current_len為當前窗口的新長度。
-
-
更新哈希表：
-
更新當前字符在
visited中的位置。
-
-
返回結果：
-
返回最長無重復字符子串的長度。
-
這個算法的時間復雜度是 O(n)，因為每個字符在最壞情況下也只會被訪問兩次（一次被加入窗口，一次被移出窗口），空間復雜度是 O(1)，因為 visited 數組的大小是固定的。
2、求給定數組中出現頻率最高的前n個數。
為了找到給定數組中出現頻率最高的前n個數，我們需要以下步驟：
-
統計每個元素的出現次數：使用一個哈希表（可以用C語言中的結構體數組來實現）。
-
將元素及其出現次數存儲在一個結構體數組中。
-
對結構體數組按出現次數進行排序。
-
輸出前n個頻率最高的元素。
下面是完整的C語言實現代碼：
#include <stdio.h>
#include <stdlib.h>
?
typedef struct {int value;int count;
} ElementCount;
?
int compare(const void *a, const void *b) {ElementCount *elemA = (ElementCount *)a;ElementCount *elemB = (ElementCount *)b;return elemB->count - elemA->count;
}
?
void findTopNFrequent(int arr[], int size, int n) {ElementCount *elementCounts = malloc(size * sizeof(ElementCount));int distinctElements = 0;
?// 初始化元素計數器for (int i = 0; i < size; i++) {elementCounts[i].value = 0;elementCounts[i].count = 0;}
?// 統計每個元素的出現次數for (int i = 0; i < size; i++) {int found = 0;for (int j = 0; j < distinctElements; j++) {if (elementCounts[j].value == arr[i]) {elementCounts[j].count++;found = 1;break;}}if (!found) {elementCounts[distinctElements].value = arr[i];elementCounts[distinctElements].count = 1;distinctElements++;}}
?//按照出現次數降序排序元素qsort(elementCounts, distinctElements, sizeof(ElementCount), compare);
?// 打印前n個元素for (int i = 0; i < n && i < distinctElements; i++) {printf("Element: %d, Count: %d\n", elementCounts[i].value, elementCounts[i].count);}
?free(elementCounts);
}
?
int main() {int arr[] = {1, 3, 1, 3, 2, 1, 4, 5, 2, 3, 3, 4, 5, 4, 4, 4, 5};int size = sizeof(arr) / sizeof(arr[0]);int n = 3;
?findTopNFrequent(arr, size, n);
?return 0;
}
解釋：
-
定義結構體
ElementCount：-
value存儲數組元素的值。 -
count存儲該元素的出現次數。
-
-
統計每個元素的出現次數：
-
遍歷數組
arr，如果elementCounts中已存在該元素，則增加其count。 -
如果不存在，則將該元素及其
count初始化為1，并記錄到elementCounts中。
-
-
排序：
-
使用
qsort對elementCounts數組按count從大到小排序。
-
-
輸出前n個頻率最高的元素：
-
遍歷排序后的
elementCounts，輸出前n個元素。
-
-
釋放內存：
-
釋放動態分配的內存
elementCounts。
-
通過這種方法，我們可以有效地找到數組中出現頻率最高的前n個數。
3、100只駱駝，100筐土豆，大駱駝背3筐，中駱駝背2筐，2只小駱駝背1筐，問有多少種組合，思路？
要解決這個問題，我們需要計算所有可能的組合方式，使得100只駱駝總共能運送100筐土豆。我們可以通過設立不同的變量表示不同類型駱駝的數量，然后利用這些變量設立方程來解決問題。具體思路如下：
變量定義
-
( x ) 表示大駱駝的數量（每只大駱駝可以背3筐土豆）。
-
( y ) 表示中駱駝的數量（每只中駱駝可以背2筐土豆）。
-
( z ) 表示小駱駝的數量（每2只小駱駝可以背1筐土豆，所以一只小駱駝相當于0.5筐）。
設立方程
我們有以下兩個約束條件：
-
駱駝總數為100只： [ x + y + z = 100 ]
-
背的土豆總數為100筐： [ 3x + 2y + 0.5z = 100 ]
解方程
從第一個方程我們可以得到： [ z = 100 - x - y ]
將 ( z ) 代入第二個方程： [ 3x + 2y + 0.5(100 - x - y) = 100 ]
解簡化這個方程： [ 3x + 2y + 50 - 0.5x - 0.5y = 100 ] [ 2.5x + 1.5y = 50 ] [ 5x + 3y = 100 ]
現在我們只需要解這個方程就能得到所有的可能組合。具體步驟如下：
-
逐一嘗試 ( x ) 的值從0到100之間的所有整數，判斷是否有對應的 ( y ) 和 ( z ) 滿足方程。
-
確保 ( x, y, z ) 都是非負整數。
實現代碼
我們可以使用簡單的C語言代碼來計算所有滿足條件的組合。
#include <stdio.h>
?
int main() {int x, y, z;int count = 0;
?for (x = 0; x <= 100; x++) {for (y = 0; y <= 100; y++) {z = 100 - x - y;if (z >= 0 && (5 * x + 3 * y == 100)) {printf("大駱駝: %d, 中駱駝: %d, 小駱駝: %d\n", x, y, z);count++;}}}
?printf("組合的總數: %d\n", count);
?return 0;
}
解釋代碼
-
雙重循環：外部循環遍歷大駱駝的數量 ( x )，內部循環遍歷中駱駝的數量 ( y )。
-
計算小駱駝的數量 ( z )：根據 ( z = 100 - x - y ) 計算。
-
判斷條件：檢查 ( z ) 是否為非負整數，并且檢查方程 ( 5x + 3y = 100 ) 是否成立。
-
輸出結果：如果條件滿足，輸出對應的 ( x, y, z ) 的值并計數。
這段代碼會輸出所有可能的駱駝組合，并且打印出組合的總數。
 圖像閾值)
