概述
力扣(LeetCode)刷题
【力扣】1、两数之和
【力扣】2、两数相加
文章目录
- 力扣(LeetCode)刷题
- 前言
- 一、题目
- 二、题解
- 1.双指针法
- 2.暴力法
- 3.散列法
- 4.排序查找法
- 总结
前言
最近疫情又开始严重了起来，宅在家里太无聊了，闲着也是闲着，刷刷力扣玩。由于是练习算法，所以我更倾向于用C语言来实现，我对C语言的用法还停留在大学，如果有哪里写的不对的地方也欢迎各位小伙伴提出
一、题目
码云
来源：力扣（LeetCode）
先来看下题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍
你可以按任意顺序返回答案
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
二、题解
这个题目主要有四种解法，如下：
1.双指针法
这个解法是参考力扣评论里的方法，这里就叫它双指针法吧。不过效率有点慢，运行了几次只超过了 5%的用户，在这里也列举一下吧
#include <stdio.h>
#include <stdlib.h>
/**
* 双指针法
* @param nums
* @param numSize
* @param target
* @param returnSize
* @return
*/
int *twoSum(int *nums, int numSize, int target, int *returnSize) {
int slow = 0;
int quick = 1;
while (quick < numSize) {
if (nums[slow] + nums[quick] == target) {
*returnSize = 2;
int *ret = (int *) malloc(sizeof(int) * 2);
ret[0] = slow;
ret[1] = quick;
return ret;
}
if (quick == numSize - 1) {
slow += 1;
quick = slow + 1;
} else {
quick += 1;
}
}
*returnSize = 0;
return NULL;
}
2.暴力法
这个题目最直观的解法就是直接双循环，计算结果和目标值进行比较。不过这里可以做一点小小的优化，由于第一层已经循环过的没必要再循环一次，所以第二层循环从第一层的下标位置+1开始循环即可。这个解法用时大约击败50%左右的用户。代码如下：
/**
* 暴力法
* @param nums
* @param numSize
* @param target
* @param returnSize
* @return
*/
int *twoSum(int *nums, int numSize, int target, int *returnSize) {
for (int i = 0; i < numSize; ++i) {
for (int j = i + 1; j < numSize; ++j) {
if (target == nums[i] + nums[j]) {
*returnSize = 2;
int *ret = (int *) malloc(sizeof(int) * 2);
ret[0] = i;
ret[1] = j;
return ret;
}
}
}
*returnSize = 0;
return NULL;
}
3.散列法
散列法主要就是采取空间换时间的方式来提高执行效率，利用一个map，对数组值和下标进行存储，值为key，下标为value，就不需要进行二次遍历了。由于题目说的是：数组中同一个元素在答案里不能重复出现，所以不会存在覆盖的问题，这个解法大概击败85%左右的用户。由于C语言没有现成的HashMap给我们用，这里只能自己实现一个拙劣的HashMap了
先申明一个table.h，用来指定map的结构和方法，代码如下：
#ifndef LEET_CODE_TABLE_H
#define LEET_CODE_TABLE_H
#define TABLE_DEFAULT_SIZE 10
typedef struct entry {
int key;
int val;
struct entry *next;
} Entry;
typedef struct table {
Entry **nodes;
Entry *(*get)(struct table *ht, int key);
int (*put)(struct table *ht, int key, int val);//定义函数指针
void (*clear)(struct table *ht);
} HashTable;
Entry *get(HashTable *ht, int key);
HashTable *create();
void clear(HashTable *ht);
int put(HashTable *ht, int key, int val);
unsigned int hash(int key);
#endif //LEET_CODE_TABLE_H
再来一个table.c具体实现它，代码如下：
#include <stdlib.h>
#include "table.h"
HashTable *create() {
HashTable *table = NULL;
size_t size = sizeof(Entry) * TABLE_DEFAULT_SIZE;
table = malloc(sizeof(HashTable));
table->nodes = malloc(size);
for (int i = 0; i < TABLE_DEFAULT_SIZE; i++) {
table->nodes[i] = NULL;
// 初始化
}
table->get = get;
table->put = put;
table->clear = clear;
return table;
}
Entry *get(HashTable *ht, int key) {
// 计算索引
unsigned int index = hash(key);
return ht->nodes[index];
}
unsigned int hash(int key) {
unsigned int hash = 5381;
hash += (hash << 5) + key;
return (hash & 0x7FFFFFFF) % TABLE_DEFAULT_SIZE;
}
int put(HashTable *ht, int key, int val) {
// 计算下标
unsigned int index = hash(key);
Entry *newNode = malloc(sizeof(Entry));
newNode->key = key;
newNode->val = val;
newNode->next = NULL;
if (ht->nodes[index] == NULL) {
ht->nodes[index] = newNode;
// 无冲突
} else {
/**
* 值一样，不操作
*/
if (ht->nodes[index]->val == val) {
free(newNode);
newNode = NULL;
return 0;
}
// 有冲突
Entry *node = ht->nodes[index];
while (node->next != NULL) {
node = node->next;
// 迭代
}
node->next = newNode;
// 给链表赋值
}
return 1;
}
void clear(HashTable *ht) {
if (ht != NULL) {
for (int i = 0; i < TABLE_DEFAULT_SIZE; i++) {
Entry *node = ht->nodes[i];
if (node != NULL) {
Entry *tmp = node;
while (node->next != NULL) {
tmp = node->next;
free(node);
node = tmp;
}
}
}
free(ht->nodes);
ht->nodes = NULL;
ht->get = NULL;
ht->put = NULL;
ht->clear = NULL;
free(ht);
ht = NULL;
}
}
然后就可以用table实现散列解法了，代码如下：
nt *twoSum(int *nums, int numSize, int target, int *returnSize) {
HashTable *map = create();
for (int i = 0; i < numSize; ++i) {
int num = target - nums[i];
Entry *node = map->get(map, num);
if (node != NULL) {
while (node != NULL) {
if (node->val != i && (nums[i] + node->key == target)) {
*returnSize = 2;
int *ret = (int *) malloc(sizeof(int) * 2);
ret[0] = i;
ret[1] = node->val;
map->clear(map);
return ret;
}
node = node->next;
}
}
map->put(map, nums[i], i);
}
*returnSize = 0;
map->clear(map);
return NULL;
}
4.排序查找法
这个方法，主要思想是先对数组进行排序，然后在利用算法提高查找效率。这个解法大概击败90%左右的用户
先申明一个sort.h，代码如下：
#ifndef LEET_CODE_SORT_H
#define LEET_CODE_SORT_H
int *mergeSort(int *nums, int numsSize);
void merge(int *nums, int left, int mid, int right, int *temp);
void sort(int *nums, int numsSize, int left, int right, int *temp);
int search(int *nums, int numsSize, int goal);
int getIndex(int *nums, int numsSize, int goal, int from);
#endif //LEET_CODE_SORT_H
再来一个sort.c具体实现它，代码如下：
#include <stdlib.h>
#include "sort.h"
int search(int *nums, int numsSize, int goal) {
int low = 0;
int high = numsSize - 1;
if (nums[high] < goal || nums[low] > goal) {
return -1;
}
int mid;
while (low <= high) {
mid = (high + low) >> 1;
if (nums[mid] > goal) {
high = mid - 1;
} else if (nums[mid] < goal) {
low = mid + 1;
} else {
return mid;
}
}
return -1;
}
int getIndex(int *nums, int numsSize, int goal, int from) {
for (int i = from; i < numsSize; ++i) {
if (nums[i] == goal) {
return i;
}
}
return -1;
}
int *mergeSort(int *nums, int numsSize) {
int *temp = (int *) malloc(sizeof(int) * numsSize);
int *copy = (int *) malloc(sizeof(int) * numsSize);
for (int i = 0; i < numsSize; ++i) {
copy[i] = nums[i];
}
sort(copy, numsSize, 0, numsSize - 1, temp);
free(temp);
temp = NULL;
return copy;
}
void sort(int *nums, int numsSize, int left, int right, int *temp) {
if (left < right) {
int mid = (left + right) / 2;
sort(nums, numsSize, left, mid, temp);
sort(nums, numsSize, mid + 1, right, temp);
merge(nums, left, mid, right, temp);
}
}
void merge(int *nums, int left, int mid, int right, int *temp) {
int i = left;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= right) {
if (nums[i] < nums[j]) {
temp[index++] = nums[i++];
} else {
temp[index++] = nums[j++];
}
}
while (i <= mid) {
temp[index++] = nums[i++];
}
while (j <= right) {
temp[index++] = nums[j++];
}
index = 0;
while (left <= right) {
nums[left++] = temp[index++];
}
}
然后就可以用sort实现排序查找解法了，代码如下：
int *twoSum(int *nums, int numSize, int target, int *returnSize) {
int *sort = mergeSort(nums, numSize);
for (int i = 0; i < numSize; ++i) {
int goal = target - nums[i];
int index = search(sort, numSize, goal);
if (index != -1) {
int sourceIndex = getIndex(nums, numSize, goal, i + 1);
if (sourceIndex != -1) {
*returnSize = 2;
int *ret = (int *) malloc(sizeof(int) * 2);
ret[0] = i;
ret[1] = sourceIndex;
return ret;
}
}
}
*returnSize = 0;
free(sort);
sort = NULL;
return NULL;
}
这里排序算法使用的是归并排序，查找算法使用的是二分查找。其他的排序查找算法这里没有进行测试，有兴趣的小伙伴可以自己去试试看
总结
以上就是我所知道的两数之和解法，如果还有其他解法或者错误的地方欢迎各位小伙伴提出
最后
以上就是哭泣皮卡丘为你收集整理的【力扣】1、两数之和力扣(LeetCode)刷题前言一、题目二、题解总结的全部内容，希望文章能够帮你解决【力扣】1、两数之和力扣(LeetCode)刷题前言一、题目二、题解总结所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复