LeetCode刷题笔记(1)

一个人的命运啊,不仅要考虑历史的进程,还要考虑个人的努力,近期明显懈怠下来的笔者决定开启LeetCode刷题大业,从第一题开始按顺序刷掉LeetCode算法题,把解题的笔记放在这里,希望跟各位读者多多交流。

编程语言,话不多说,即刻开始:

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

这道题目要求找出一个List中的两个数,使得他们的和等于给定的,然后返回这两个数在List中的位置,笔者第一时间的想法便是遍历整个List,对每一个小于的数,看List中是否有这个数,再返回他们的位置,也就是下面的解法2,解法3是解法2更Pythonic的形式,由于列表查找的时间复杂度是O(n),所以整个算法的时间复杂度是O(n^2)。

那么如果想要增加效率,可以将列表查找转换为hash table也就是Python里的Dict对象,也就是下文中的解法1,因为hash table的查找速度近乎于O(1),所以整个算法的时间复杂度是O(n)。

2. Add two numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

这道题目要求我们实现整数的加法,这跟计算机ALU中加法器的原理是类似的,每一位加完之后会得到该位的结果和一个进位,进位的值只能取1或0。这里用到Python自带的一个很方便的函数可以返回两数相除的商和余数,商为进位,余数则为该位剩下的值。

值得注意的是,由于每个ListNode对象是单向传递的,所以需要在一开始保留一个根部的指针指向和的末位,计算完成后返回这个根部的指针。

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

算法题里面的一大类就是各种字符串操作题,本题要求找出最小不重复子字符串的长度,所以用变量储存当前找到的字符串,如果找到更长的,再加以替换,直到遍历完毕。

本题还有一种思路,因为题目只要求长度,所以可以只找位置之间的差别,不用存储子字符串,实现方法与上面类似。

第一次刷题,先放三道,欢迎大家交流讨论指正,有想一起刷题的同志可以私信我~

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180509G1LG5D00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券