- LeetCode 每日一题(1-2) 2022-7-2 六
- 1. Two Sum [^1]
- 思路
- python
- c#
- c++
- 2. Add Tow Numbers [^2]
- 思路
- python
- c#
- c++
- 挖坑
- 引用
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
- 2 <= nums.length <= 1 0 4 10^4 104
- − 1 0 9 -10^9 −109 <= nums[i] <= 1 0 9 10^9 109
- − 1 0 9 -10^9 −109 <= target <= 1 0 9 10^9 109
- Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O ( n 2 ) O(n^2) O(n2) time complexity?
思路如何快速找到互补的数的下标，用字典存
pythonclass Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
ret = []
if len(nums) <= 2:
ret.append(0)
ret.append(1)
return ret
tempMap = {}
for i in range(0, len(nums)):
if nums[i] in tempMap.keys():
ret.append(tempMap[nums[i]])
ret.append(i)
return ret
tempMap[target - nums[i]] = i
return ret
c#36 ms 89.23%
16.6 MB 5.01%
57 / 57
public class Solution {
public int[] TwoSum(int[] nums, int target) {
int[] ret = new int[2] { 0, 1 };
if (nums.Length <= 2)
{
return ret;
}
Dictionary tempMap = new Dictionary();
for (int i = 0; i < nums.Length; ++i)
{
if (tempMap.ContainsKey(nums[i]))
{
ret[0] = tempMap[nums[i]];
ret[1] = i;
return ret;
}
tempMap[target - nums[i]] = i;
}
return ret;
}
}
c++128 ms 95.89%
43.7 MB 17.43%
57 / 57
class Solution {
public:
vector twoSum(vector& nums, int target) {
vector ret = vector();
if (nums.size() <= 2)
{
ret.push_back(0);
ret.push_back(1);
return ret;
}
std::unordered_map tempMap = unordered_map(); // 使用 hashMap
for (int i = 0; i < nums.size(); ++i)
{
auto it = tempMap.find(nums[i]);
if (it != tempMap.end())
{
ret.push_back(tempMap[nums[i]]);
ret.push_back(i);
return ret;
}
tempMap[target - nums[i]] = i;
}
return ret;
}
};
2. Add Tow Numbers 28 ms 92.08%
10.5 MB 42.58%
57 / 57
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 contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Constraints:
- The number of nodes in each linked list is in the range [1, 100].
- 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
从低到高按顺序相加就行了，这样可以自然的处理进位。
python# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
ret = ListNode()
if l1 == None and l2 == None:
return ret
carryVal = False
curNode = ret
while True:
v1 = 0
if l1 != None:
v1 = l1.val
v2 = 0
if l2 != None:
v2 = l2.val
curNode.val = v1 + v2 + carryVal
if curNode.val > 9:
carryVal = True
curNode.val -= 10
else:
carryVal = False
if l1 != None:
l1 = l1.next
if l2 != None:
l2 = l2.next
if l1 == None and l2 == None:
if carryVal:
curNode.next = ListNode()
curNode.next.val = 1
break
else:
curNode.next = ListNode()
curNode = curNode.next
return ret
c#60 ms 72.09%
14.9 MB 84.76%
1568 / 1568
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
ListNode ret = new ListNode();
ListNode curNode = ret;
bool carry = false;
while (l1 != null || l2 != null)
{
int v1 = l1 != null ? l1.val : 0;
int v2 = l2 != null ? l2.val : 0;
curNode.val = v1 + v2 + (carry ? 1 : 0);
if (curNode.val > 9)
{
carry = true;
curNode.val -= 10;
}
else
{
carry = false;
}
l1 = l1 != null ? l1.next : null;
l2 = l2 != null ? l2.next : null;
if (l1 == null && l2 == null)
{
if (carry)
{
curNode.next = new ListNode(1);
}
break;
}
else
{
curNode.next = new ListNode();
curNode = curNode.next;
}
}
return ret;
}
}
c++80 ms 94.70%
48.2 MB 58.12%
1568 / 1568
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode * ret = new ListNode();
ListNode * curNode = ret;
bool carry = false;
while (l1 != nullptr || l2 != nullptr)
{
int v1 = l1 != nullptr ? l1->val : 0;
int v2 = l2 != nullptr ? l2->val : 0;
curNode->val = v1 + v2 + carry;
if (curNode->val > 9)
{
carry = true;
curNode->val -= 10;
}
else
{
carry = false;
}
l1 = l1 != nullptr ? l1->next : nullptr;
l2 = l2 != nullptr ? l2->next : nullptr;
if (l1 == nullptr && l2 == nullptr)
{
if (carry)
{
curNode->next = new ListNode(1);
}
break;
}
else
{
curNode->next = new ListNode();
curNode = curNode->next;
}
}
return ret;
}
};
挖坑20 ms 88.94%
69.4 MB 66.81%
1568 / 1568
- 未完成的坑: 在c++、python、c#中有哪些常用的词典，这些词典的实现原理和使用注意事项
1. 两数之和 - 力扣 (LeetCode) ↩︎
2. 两数相加 - 力扣 (LeetCode) ↩︎
