算法算是从高三暑假就开始学了吧，但是后来学pwn之后也没时间学算法，学的一点也就应付一下数据结构与算法的期末考试有点用了…
为了提高编程和算法能力（混30分综测）准备开始刷题…目标是刷完100题！比起Acwing感觉leetcode难的多
上学期还说，用C打算法比赛的不是纯纯怨种吗，于是我来当怨种了（狗头）
两数之和
题目描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
思路1：双重循环暴力解
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
for(int i = 0; i < numsSize; i++){
for(int j = i + 1; j < numsSize; j++){
if(nums[i] + nums[j] == target){
int* ret = malloc(sizeof(int) * 2);
ret[0] = i;
ret[1] = j;
*returnSize = 2;
return ret;
}
}
}
*returnSize = 0;
return NULL;
}思路2：利用哈希表判断循环到的数之前的数中有没有与该数相加等于目标数的，没有就将该数加入哈希表，时间复杂度降为O(1)
但是C语言的哈希函数所需头文件要自己导入，比赛的时候也没有，所以我就没写，就学习了一下思路
两数相加
题目描述：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。
考点大概就是链表操作吧…需要考虑进位和两个链表长度不同的情况
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode *ret = NULL, *curr = NULL;
int cnt = 0;
while(l1 || l2){
int val1 = l1 ? l1->val : 0;
int val2 = l2 ? l2->val : 0; //其中一个链表空了就取值为0
int sum = val1 + val2 + cnt;
if(ret == NULL){
ret = curr = malloc(sizeof(struct ListNode));
curr->val = sum % 10;
curr->next = NULL;
} //为头结点赋值
else{
curr->next = malloc(sizeof(struct ListNode));
curr->next->val = sum % 10;
curr = curr->next;
curr->next = NULL;
}
cnt = sum / 10; //计算进位
if(l1)
l1 = l1->next;
if(l2)
l2 = l2->next;
}
if(cnt > 0){
curr->next = malloc(sizeof(struct ListNode));
curr->next->val = cnt;
curr->next->next = NULL;
} //两个链表均为空之后多出的进位
return ret;
}无重复字符的最长子串
题目描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
思路：滑动窗口，遍历每一位计算最长无重复字符的子串并记录最大长度
int lengthOfLongestSubstring(char * s){
int len = strlen(s);
int res = 0; //记录最大长度
for (int i = 0; i < len; i++) {
int visited[128] = {0}; //用于判断是否有重复
int max = 0;
for (int j = i; j < len && !visited[s[j]]; j++) {
visited[s[j]] = 1;
max++;
}
if (max > res)
res = max;
}
return res;
}寻找两个正序数组的中位数
题目描述：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
思路1：直接合并两个数组去中位数
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
int size = nums1Size + nums2Size;
int q[size + 1], i = 0, j = 0, tmp = 1;
while(i < nums1Size && j < nums2Size){
if(nums1[i] < nums2[j])
q[tmp++] = nums1[i++];
else
q[tmp++] = nums2[j++];
}
while(i < nums1Size)
q[tmp++] = nums1[i++];
while(j < nums2Size)
q[tmp++] = nums2[j++];
if(size % 2){
return q[size / 2 + 1];
}else{
return (q[size / 2] + q[size / 2 + 1]) / 2.0;
}
}思路2：已知两数组长度，求中位数只要知道中间位置的数不一定要将数组合并
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int size = nums1Size + nums2Size;
int i = 0, j = 0, count = 0;
int res1 = 0, res2 = 0;
while (i < nums1Size || j < nums2Size) {
if (j == nums2Size || (i < nums1Size && nums1[i] < nums2[j])) {
count++;
if (count == size / 2) {
res1 = nums1[i];
}
if (count == size / 2 + 1) {
res2 = nums1[i];
break;
}
i++;
} else {
count++;
if (count == size / 2) {
res1 = nums2[j];
}
if (count == size / 2 + 1) {
res2 = nums2[j];
break;
}
j++;
}
}
if (size % 2 == 1) {
return res2;
} else {
return (res1 + res2) / 2.0;
}
}思路3：中位数查找算法
- 使用二分搜索找到一个划分点将两个数组分成左右两部分，使得左边部分的所有元素都小于右边部分的元素。
- 根据划分后两个部分的长度，判断是否找到了中位数。如果总长度为奇数，则中位数就是划分点左边部分的最大元素；如果总长度为偶数，则中位数是划分点左右两边部分的最大元素和最小元素的平均值。
- 如果划分点左边部分的最大元素大于右边部分的最小元素，则需要调整划分点，继续进行二分搜索。
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
if(nums1Size > nums2Size)
{
return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
} //首先要满足第一个数组小于第二个数组
int total = nums1Size + nums2Size; //总计的数字，用于计算
int left = 0, right = nums1Size;
while(left <= right)
{
int i = (left+right)/2; //i为第一个数组线左边的数量
int j = (total + 1) / 2 - i; //j为第二个数组线左边的数量，使用total计算，如果total为奇数，线就偏向右边，如果偶数，分割线左右两边相等
if(i < nums1Size && nums2[j-1] > nums1[i]) //nums2[j-1] > nums1[i]表示线要右移，如果i==nums1Size那么就不用右移了
{
left = i + 1;
}
else if(i > 0 && nums1[i-1] > nums2[j]) //nums1[i-1] > nums2[j]表示线要左移，如果i==0，就不用左移了
{
right = i - 1;
}
else
{
int max_left = 0; //以下对分割线左右四个元素操作
if(i == 0) //如果数组一分割线左边为0个，左边最大就是数组二分割线左边第一个
{
max_left = nums2[j-1];
} else if(j == 0) //如果数组二分割线左边为0个，左边最大就是数组一分割线左边第一个
{
max_left = nums1[i-1];
} else //否则就判断分割线左边两个的最大值
{
max_left = fmax(nums1[i-1], nums2[j-1]);
}
if(total % 2 == 1) //如果是奇数，就返回左边最大值，因为线是偏右边的
{
return max_left;
}
int min_right = 0;
if(i == nums1Size) //找右边最大值，偶数取左右两边最大值的平均数
{
min_right = nums2[j];
}
else if(j == nums2Size)
{
min_right = nums1[i];
}
else
{
min_right = fmin(nums1[i], nums2[j]);
}
return (max_left + min_right) / 2.0;
}
}
return 0;
}最长回文子串
题目描述：给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
思路：遍历所有的两个字符和三个字符的子串，记录符合回文子串的左右两边下标，遍历这个数组中的左右下标，并且通过while循环找出两边第一个不相同的位置，得到以该位置为中心的回文子串长度，记录最大长度并返回
char* longestPalindrome(char* s) {
int i = 0, j = 0, left[2005], right[2005], length = strlen(s), index = 0, max = 0, resl = 0;
char* res = (char*)malloc(sizeof(char) * (length + 1));
//find index
while(i + 1 < length){
if(s[i] == s[i + 1]){
left[index] = i;
right[index] = i + 1;
index++;
}
i++;
}
while(j + 2 < length){
if(s[j] == s[j + 2]){
left[index] = j;
right[index] = j + 2;
index++;
}
j++;
}
i = 0; j = 0;
//enlarge
while(i < index){
while(left[i] > 0 && right[i] < length - 1 && s[left[i]] == s[right[i]]){
left[i]--;
right[i]++;
}
if(s[left[i]] != s[right[i]]){
left[i]++;
right[i]--;
}
if(right[i] - left[i] + 1 > max){
max = right[i] - left[i] + 1;
resl = left[i];
}
i++;
}
//return string
if(length == 1 || index == 0){
res[0] = s[0];
res[1] = '\0';
}
else{
for(i = 0; i < max; i++)
res[i] = s[resl + i];
res[max] = '\0';
}
return res;
}