leetcode (1、2、3）
- 2019 年 11 月 12 日
- 筆記
在 pycharm 和 IDEA 装ｌｅｅｔｃｏｄｅ插件, 刷起来贼爽
登录 leetcode 账号：开搞
要求 java 和 py 方法
之前写过，很快就不会了，果然还是要五毒刷题法
五毒刷题法 （极客覃超）
NO.1 leetcode 两数之和
题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]
py 代码解法
列表解法
def twoSum_1( nums, target): result = [] for i in range (len(nums)): onenum = nums[i] twonum = target - onenum if twonum in nums: j = nums.index(twonum) if i != j: result.append(i) result.append(j) return result
字典解法
def twoSum_2(nums,target): dict={} for i in range(len(nums)): m = nums[i] if target-m in dict: return [dict[target-m],i] dict[m] = i
字典推导式
def twosum_3(nums,target): l = len(nums) dict = {nums[i]:i for i in range(l)} print(dict) for j in range(l): a = nums[j] b = target - a if b in dict and j != dict[b]: return [j,dict[b]]
Java
- 一遍 hashmap 解法
class Solution { public int[] twoSum(int[] nums, int target) { /* 使用hashmap */ int[] res = new int[2]; Map<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int i = 0 ; i<nums.length;i++){ int othernums = target - nums[i]; if (map.get(othernums) != null){ res[0] = map.get(othernums); res[1] = i; } map.put(nums[i],i); } return res; }}
- 两次遍历 hashmap
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map = new HashMap<Integer, Integer>(); for(int i = 0; i<nums.length;i++){ map.put(nums[i],i); } for (int i = 0; i<nums.length;i++){ int othernum = target - nums[i]; if(map.containsKey(othernum) && map.get(othernum) != i){ return new int[] {i,map.get(othernum)}; } } return null; }}
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807
py 常规操作
class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: # 将链表转化列表 val1, val2 = [l1.val], [l2.val] while l1.next: val1.append(l1.next.val) l1 = l1.next while l2.next: val2.append(l2.next.val) l2 = l2.next # 反转列表 用join方法拼接数字 切片[::-1] num_1 = ''.join([str(i) for i in val1[::-1]]) num_2 = ''.join([str(i) for i in val2[::-1]]) sums = str(num_1 + num_2)[::-1] # 将sum转化成链表res # 头节点 res = head = ListNode(int(sums[0])) for i in range(1, len(sums)): # 拼接 head.next = ListNode(int(sums[i])) head = head.next return res
优化：不需要将整个数的和求出，只需要每一位对应相加，
思路：
将结果保存在一个新的链表中，使用两个指针，一个指向头节点，用于返回结果，另一个指向当前节点，用于计算并保存结果。遍历两个输入链表，逐位进行相加，若某一个链表遍历到了结尾，则取 0 参与运算。每一位的数字为两个数字对应位以及进位之和除 10 的余数，而该位是否有进位则是这个和除 10 的商。
class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: # 判断0 还是1 res = 0 root = n = ListNode(0) while l1 or l2 or res: v1 = v2 = 0 if l1: v1 = l1.val l1 = l1.next if l2: v2 = l2.val l2 = l2.next # divmod() 函数把除数和余数运算结果结合起来，返回一个包含商和余数的元组(a // b, a % b)。 res, val = divmod(v1 + v2 + res, 10) n.next = ListNode(val) n = n.next return root.next
Java
和上面 python 相同的思路
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode root = new ListNode(0); ListNode cur = root; int res = 0; // TODO 如果 l1 和l2为空 ，res = 0, pass res = 1 再执行一遍 while (l1 != null||l2 != null|| res !=0){ if (l1 != null) { res += l1.val; l1 = l1.next; } if (l2 != null) { res += l2.val; l2 = l2.next; } cur.next = new ListNode(res%10); res /= 10; cur = cur.next; } return root.next; }}
NO3、找出其中不含有重复字符的 最长子串 的长度。
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
hashset，哈希表两种解法
推荐 hashmap 时间复杂度 o(n)
py2 种解法
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if s == '': return 0 #这样必有一个 res = 1 i = 0 for j in range(1, len(s)): if s[j] not in s[i:j]: # s[j] 没有重复出现 res 取 j-i+1 res = max(res, j - i + 1 ) else: # s[j] 竟然重复出现了 如'abcaa' # s[i:j].index(s[j]) 指当前 i的位置 i += s[i:j].index(s[j]) + 1 return res
使用字典方法
推荐使用字典方法（性能速度高）
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: # start子字符串的起始位置 # maxlength 输出最大子序列的长度 start = maxLength = 0 # 记录每次遍历到的字符，key=char,value=index usedChar = {} for i in range(len(s)): # 如果字符存在于字典中，且位置是在起始位置的右边，说明遇到了重复字符 if s[i] in usedChar and start <= usedChar[s[i]]: # 将起始位置修改为重复字符第一次出现的位置的右邻 start = usedChar[s[i]] + 1 # 字符不存在于字典中 else: # 有可能start跳到重复字符，所以用max方法 maxLength = max(maxLength, i - start + 1) # 更新userdChar usedChar[s[i]] = i return maxLength
Java 解法
将 py 代码改写成 Java
import java.util.HashMap;//leetcode submit region begin(Prohibit modification and deletion)class Solution { public int lengthOfLongestSubstring(String s) { if (s.length() == 0) return 0; int max = 0; HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>(); for (int i = 0 ,j = 0; i < s.length(); i++) { // j是初始位置 重复出现字符 // j将起始位置修改为重复字符第一次出现的位置的右邻 if (hashMap.containsKey(s.charAt(i))) { j = Math.max(j, hashMap.get(s.charAt(i)) + 1); } // 更新hashmap hashMap.put(s.charAt(i), i); max = Math.max(max, i - j + 1); } return max; }}
