“【Leetcode】1-7"
[toc]
1. [Array]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.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
python solution：
class Solution(object):
def twoSum(self, nums, target):
for i in range(len(nums)):
j=target-nums[i]
if j in nums and nums.index(j)!=i:
return [i,nums.index(j)]
c solution
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int* res = (int *)malloc(sizeof(int) * 2);
* returnSize=0;
for(int i = 0; i < numsSize-1; i++) {
for(int j = i + 1; j < numsSize; j++) {
if(nums[i] + nums [j] == target) {
res[0] = i;
res[1] = j;
*returnSize = 2;
return res;
}
}
}
return res;
}
c++ solution
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.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
python solution
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
re=ListNode(0)
r=re
carry=0
while(l1 or l2):
x=l1.val if l1 else 0
y=l2.val if l2 else 0
s=carry+x+y
carry=s//10
r.next=ListNode(s%10)
r=r.next
if(l1!=None):l1=l1.next
if(l2!=None):l2=l2.next
if(carry>0):
r.next=ListNode(1)
return re.next
c++ solution
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode vHead(0), *p = &vHead;
int flag = 0;
while (l1 || l2 || flag) {
int tmp = 0;
if (l1 != nullptr) tmp += l1->val;
if (l2 != nullptr) tmp += l2->val;
tmp += flag;
flag = tmp / 10;
tmp %= 10;
ListNode *next = l1 ? l1 : l2;
if (next == nullptr) next = new ListNode(tmp);
next->val = tmp;
p->next = next;
p = p->next;
l1 = l1 ? l1->next : nullptr;
l2 = l2 ? l2->next : nullptr;
}
return vHead.next;
}
};
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
python solution
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:return 0
left = 0
lookup = set()
n = len(s)
max_len = 0
cur_len = 0
for i in range(n):
cur_len += 1
while s[i] in lookup:
lookup.remove(s[left])
left += 1
cur_len -= 1
if cur_len > max_len:max_len = cur_len
lookup.add(s[i])
return max_len
4. [Array]Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
python solution
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
median = 0
n1 = len(nums1)
n2 = len(nums2)
i = 0
j = 0
nums3=[]
while n1>0 and n2>0:
if nums1[i]<nums2[j] :
nums3.append(nums1[i])
i += 1
n1 -= 1
else:
nums3.append(nums2[j])
j += 1
n2 -= 1
if n1 == 0 and n2 != 0:
for k in range(j,len(nums2)):
nums3.append(nums2[k])
elif n2 == 0 and n1 != 0 :
for p in range(i,len(nums1)):
nums3.append(nums1[p])
if len(nums3)%2 == 0:
return (nums3[len(nums3)//2]+nums3[len(nums3)//2 - 1])/2
else:
return nums3[(len(nums3)-1)//2]
Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
python solution
class Solution:
def reverse(self, x: int) -> int:
if x>0:
num=int(str(x)[::-1])
if num>pow(2,31)-1:
num=0
elif x<0:
num=int(str(x)[::-1][:-1])
if num>pow(2,31):
num=0
else:
num=-num
else:
num=0
return num
[DP]Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
python solution:
- 最长公子串:
class Solution:
def longestPalindrome(self, s: str) -> str:
s_ = s[::-1]
n = len(s)
if n == 0:
return s
while n>0:
for i in range(len(s)-n+1):
if s[i:i+n] in s_:
if s_.index(s[i:i+n]) + n + i == len(s):
return s[i:i+n]
n -= 1
这个办法属于暴力解法,会超出运行时间.
- 动态规划:
class Solution:
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size < 2:
return s
dp = [[False for _ in range(size)] for _ in range(size)]
max_len = 1
start = 0
for i in range(size):
dp[i][i] = True
for j in range(1, size):
for i in range(0, j):
if s[i] == s[j]:
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
else:
dp[i][j] = False
if dp[i][j]:
cur_len = j - i + 1
if cur_len > max_len:
max_len = cur_len
start = i
return s[start:start + max_len]