Task1——两数之和

标签: 算法训练

目录

前言:

题目:

示例:

暴力解题过程:

解题思路:

解题结果:

哈希解题过程:

解题思路:

解题结果:

总结与思考:

来源:

参考:


前言:

本题的采用C语言解决问题,并使用了两种解题思路。

题目:

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力解题过程:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int* idx = (int*)malloc(sizeof(int)*2);
    for(int i=0; i<numsSize-1; i++)
    {
        for(int j=i+1; j<numsSize; j++)
        {
            if(nums[i]+nums[j] == target)
            {
                idx[0] = i;
                idx[1] = j;
                returnSize[0] = 2;
                return idx;
            }
        }
    }
    returnSize = 0;
    return 0;
}

解题思路:

  1. 题目中表明,传入的数组中最多有一个有效答案,所以对数组进行遍历即可。
  2. 因为找两数之和,所以从第一个元素开始遍历至最后一个元素,最多的遍历次数为n!(其中n为数组长度)

解题结果:

哈希解题过程:


#include <math.h> 
#define hash_fn(key, size) (abs(key%size)+1) // 使用0判断hash是否填充
#define prob_fn(key, size) (abs(key%size)+1) // 使用0判断hash是否填充

typedef struct _HashTable_t
{
    int hash; // 用于判断当前哈希数组元素是否有填充,若为0即为无填充
    int key;  // 键 -- 唯一性
    int val;  // 值 -- 存放被查询元素
}HashTable_t;

void HashInsert(HashTable_t* t, int tSize, int key, int val)
{
    int hash = hash_fn(key, tSize);
    int idx = hash;
    // 寻找哈希表中为0的数组元素
    while (t[idx].hash)
    {
	idx = prob_fn(idx, tSize);
    }
    // 将目标哈希数组填充
    t[idx] = (HashTable_t){ hash, key, val };
}

#include <stdbool.h>
bool HashFind(HashTable_t* t, int size, int key, int* val) 
{
    // 获取指定键的哈希值
    int hash = hash_fn(key, size);
    int idx = hash;
    // 寻找hash非0,且键相等的元素
    while (t[idx].hash && t[idx].key != key)
    {
	idx = prob_fn(idx, size);
    }
    val[0] = t[idx].val;
    // 返回hash值是否相同
    return t[idx].hash == hash;
}

#include <stdlib.h>
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* p = (int*)malloc(sizeof(int) * 2);
    // 由于传进来的参数中包含数组的长度
    // 所以分配足够的哈希空间
    int tSize = numsSize * 2; 
    HashTable_t *t = calloc(tSize+1, sizeof(HashTable_t));
    for (int i = 0; i < numsSize; i++)
    {
        // 寻找数值为 (target-nums[i]) 的元素的索引
	if (HashFind(t, tSize, target - nums[i], &p[1]))
	{
            // 找到后,将索引存储于缓存 p 中
	    p[0] = i;
	    *returnSize = 2;
            free(t);
	    return p;
	}
	else
	{
            // 否则将键值对 -- nums[i]:i 存放于哈希表中
	    HashInsert(t, tSize, nums[i], i);
	}
    }
    *returnSize = 0;
    free(p);
    free(t);
    return 0;
}

解题思路:

  1. 本题可以换一个角度考虑:已知target和nums[i],寻找两者之差的数值是否在nums中,并且获得其坐标值
  2. 问题就转换为数据搜索查询
  3. 哈希表(散列表)既有数组快速查询的优点,又有链表快速插入、删除的优点。在数据存储查询的领域中十分常用
  4. 借鉴哈希表和本题的思路,将已知元素nums[n]作为键(本题中所有的nums必不重复)通过哈希算法填充到指定的哈希表中,可以实现时间为O(1)的查询速度
  5. 用于本题的哈希算法 #define(key, size) ((key%size) + 1) // 0作为判断非空,所以数值整体+1
  6. 实现哈希的插入、寻找算法
  7. 循环调用即可

解题结果:

总结与思考:

通过上述两种解题思路的比较可以发现,暴力解题思路简单,并且实现起来很方便,但是在时间上面却输的特别惨。采用哈希表的数据结构与算法,在查找和插入元素过程中具有显著优势,因此在解题时间上面有“飞”的感觉。

通过本题,get到一个新技能,就是哈希表的运用。

来源:

https://leetcode-cn.com/problems/two-sum/

参考:

版权声明:本文为KingQian2018原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/KingQian2018/article/details/104586806

智能推荐

26_Python基础_继承

面向对象三大特性: 封装 根据 职责 将 属性 和 方法 封装 到一个抽象的 类 中 继承 实现代码的重用, 相同的代码不需要重复的编写 多态 不同的对象调用相同的方法,  产生不同的执行结果,  增加代码的灵活度 1.  单继承 1.1 概念 继承的概念:&...

循环

与任何程序设计语言一样Java利用条件语句与循环结构确定流程控制,一下总结一下Java中的循环语句: while do while for switch 对于golang来说: switch非常灵活。从第一个expr为true的case开始执行,如果case带有fallthrough,程序会继续执行下一条case,不会再判断下一条case的expr,如果之后的case都有fallthrough,d...

1638 统计只差一个字符的子串数目(动态规划)

1. 问题描述: 给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换一个不同字符以后,是 t 串的子串。换言之,请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。比方说, "computer" 和 "computation"...

websocket基本原理

HTTP中一个request只能有一个response。而且这个response也是被动的,不能主动发起 因此过去的服务端推送信息是通过客户端不停的轮询实现的 websocket是双向通信协议,提供了服务端主动推送信息的能力 需要客户端(浏览器)和服务端同时支持 如果经过代理的话,还需要代理支持,否则有些代理在长时间无通信时会自动切断连接 因此WS为了保证连接不被断掉,会发心跳 WebSocket...

mybatis+ehcache二级缓存

导入jar包 mapper.xml文件开启二级缓存 pojo类实现序列化接口 配置ehcache.xml 测试...

猜你喜欢

python+opencv实现图像拼接

任务 拍摄两张图片去除相同部分,拼接在一起 原图 结果 步骤 读取两张图片 使用sift检测关键点及描述因子 匹配关键点 处理并保存关键点 得到变换矩阵 图像变换并拼接 代码实现 扩展 这里对右边图像进行变换,右边变得模糊,可以修改代码对左边图像变换 这里只有两张图片拼接,可以封装实现多张图片拼接 可以修改代码实现上下图片的拼接...

python_sklearn机器学习算法系列之AdaBoost------人脸识别(PCA,决策树)

          注:在读本文之前建议读一下之前的一片文章python_sklearn机器学习算法系列之PCA(主成分分析)------人脸识别(k-NearestNeighbor,KNN)         本文主要目的是通过一个简单的小...

memmove函数与memcpy函数的模拟实现

memmove函数和memcpy函数都是在内存复制任意类型的,但是它俩也有区别。当源区域和目标区域有重复的,memmove函数会复制缓冲区重叠的部分,而memcpy相反,会报出未知错误。 下面给出两个函数的实现 首先,memmove函数。 实现的基本原理如下图。 具体代码如下: memcpy函数的实现很简单,就直接给出源代码了...

SpringFramework核心 - IOC容器的实现 - 总结

1. 概述 把Spring技术内幕第一章和第二章过了一遍,也做了一些笔记, 对IOC容器的实现有了一定皮毛理解,现在跟着源码再过一遍总结一下IOC容器的初始化,Bean的初始化的过程,做一下总结 ① IOC容器和简单工厂模式 在开始之前,先想想我们平时是怎么使用IOC容器为我们管理Bean的,假设我们要把下面的User类交给IOC容器管理 我们不想关心如何创建一个User对象实例的,仅仅在需要他的...