Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
left,right = 0,1
while right <= len(nums) - 1:
if nums[left] == nums[right]:
right += 1
else:
left += 1
nums[left] = nums[right]
return left + 1
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
for i in range(len(nums) - 1, 0, -1):
if nums[i] == nums[i-1]:
del nums[i]
return len(nums)
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
mp = 0
for i in range(1, len(prices)):
if prices[i] - prices[i-1] > 0:
mp += prices[i] - prices[i-1]
return mp
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n == 1:
return 0
dp = [[0,0] for _ in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1,n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
return max(dp[n-1])
Given an array, rotate the array to the right by k steps, where k is non-negative.
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
nums[:] = nums[n-k:] + nums[0:n-k]
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
temp = nums[0]
idx = 0
n = len(nums)
vis = [False for _ in range(n)]
cnt = 0
while cnt < n:
idx = (idx + k) % n
if vis[idx]:
idx = (idx + 1) % n
temp = nums[idx]
else:
vis[idx] = True
t = nums[idx]
nums[idx] = temp
temp = t
cnt += 1
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Input: nums = [1,2,3,1]
Output: true
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
s = set()
for i in nums:
if i in s:
return True
else:
s.add(i)
return False
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
nums.sort()
for i in range(1,len(nums)):
if nums[i-1] == nums[i]:
return True
return False
PS:正常做法应该就是放集合表确定不重复叭,排序效率要低一些,直接暴力的话过不了的。
只出现一次的数字
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Input: nums = [4,1,2,1,2]
Output: 4
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for i in nums:
ans ^= i
return ans
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
m = {}
for i in nums1:
if i in m:
m[i] += 1
else:
m[i] = 1
ans = []
for i in nums2:
if m.get(i) and m.get(i) > 0:
ans.append(i)
m[i] -= 1
return ans
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
p1, p2 = 0, 0
ans = []
nums1.sort()
nums2.sort()
while p1 < len(nums1) and p2 < len(nums2):
if nums1[p1] == nums2[p2]:
ans.append(nums1[p1])
p1 += 1
p2 += 1
else:
if nums1[p1] > nums2[p2]:
p2 += 1
else:
p1 += 1
return ans
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.
Increment the large integer by one and return the resulting array of digits.
Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
for i in range(len(digits) - 1, -1, -1):
if digits[i] != 9:
digits[i] += 1
return digits
else:
digits[i] = 0
return [1] + digits
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
for i in range(len(nums) - 1, -1, -1):
if nums[i] == 0:
del nums[i]
nums.append(0)
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
idx = -1
for i in range(len(nums)):
if nums[i] != 0:
idx += 1
nums[idx] = nums[i]
for i in range(idx + 1, len(nums)):
nums[i] = 0
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.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
d = {}
for i in range(len(nums)):
if target - nums[i] in d:
return [d[target-nums[i]],i]
else:
d[nums[i]] = i
return []
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
PS:有人相爱,有人夜里开车看海,有人 leetcode 第一题都做不出来。
有效的数独
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
row = [[False for _ in range(10)] for _ in range(10)]
col = [[False for _ in range(10)] for _ in range(10)]
grid = [[False for _ in range(10)] for _ in range(10)]
for i in range(9):
for j in range(9):
if board[i][j] != '.':
if row[i][int(board[i][j])]:
return False
else:
row[i][int(board[i][j])] = True
if col[j][int(board[i][j])]:
return False
else:
col[j][int(board[i][j])] = True
if grid[i // 3 * 3 + j // 3][int(board[i][j])]:
return False
else:
grid[i // 3 * 3 + j // 3][int(board[i][j])] = True
return True
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
for i in range(len(matrix) // 2):
matrix[i], matrix[len(matrix) - 1 - i] = matrix[len(matrix) - 1 - i], matrix[i]
for i in range(len(matrix)):
for j in range(i + 1, len(matrix)):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
PS:观察规律即可,简单的数组操作
字符串
反转字符串
Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
class Solution:
def reverseString(self, s: List[str]) -> None:
h, t = 0, len(s) - 1
while h <= t:
s[h], s[t] = s[t], s[h]
h += 1
t -= 1
PS:当然,直接用 reverse 也是可以的💩
整数反转
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Input: x = 123
Output: 321
class Solution:
def reverse(self, x: int) -> int:
ans = 0
flag = False
if x < 0:
flag = True
x = -x
while x > 0:
ans *= 10
ans += x % 10
x //= 10
return (-ans if flag else ans) if -2**31 <= ans <= 2**31 - 1 else 0
class Solution:
def reverse(self, x: int) -> int:
x = str(x)
if x[0] == '-':
x = x[0] + x[-1:-len(x):-1]
else:
x = x[::-1]
x = int(x)
return x if -2**31 <= x <= 2**31 - 1 else 0
PS:Python中第二种方法居然比第一种快
字符串中的第一个唯一字符
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Input: s = "loveleetcode"
Output: 2
class Solution:
def firstUniqChar(self, s: str) -> int:
m = {}
for i in s:
if i in m:
m[i] += 1
else:
m[i] = 1
for k,v in m.items():
if v == 1:
for i in range(len(s)):
if s[i] == k:
return i
return -1
PS:或许用自制的哈希表(两个数组)会更快一些
有效的字母异位词
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Input: s = "anagram", t = "nagaram"
Output: true
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
m = {}
for i in s:
if i in m:
m[i] += 1
else:
m[i] = 1
for i in t:
if m.get(i) and m[i] > 0:
m[i] -= 1
else:
return False
return True
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
a = sorted(list(s))
b = sorted(list(t))
return a == b
PS:emm,最好用第一种方法
验证回文串
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
class Solution:
def isPalindrome(self, s: str) -> bool:
s = [_ for _ in s if _.isalpha() or _.isdigit()]
left, right = 0, len(s) - 1
while left <= right:
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
PS:注意题目中的 “removing all non-alphanumeric characters” 先去除所有的非字母数组后验证回文,类似反转字符串的双指针操作。
字符串转换整数 (atoi)
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).
The algorithm for myAtoi(string s) is as follows:
Read in and ignore any leading whitespace.
Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1.
Return the integer as the final result.
Note:
Only the space character ' ' is considered a whitespace character.
Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
Input: s = " -42"
Output: -42
Explanation:
Step 1: " -42" (leading whitespace is read and ignored)
^
Step 2: " -42" ('-' is read, so the result should be negative)
^
Step 3: " -42" ("42" is read in)
^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.
class Solution:
def myAtoi(self, s: str) -> int:
idx = 0
for i in s:
if i != ' ':
break
idx += 1
if idx == len(s):
return 0
sign = 1
if s[idx] == '-' or s[idx] == '+':
if s[idx] == '-':
sign = -1
idx += 1
ans = 0
for i in range(idx, len(s)):
if not s[i].isdigit():
break
else:
temp = ans
ans *= 10
# if ans // 10 != temp:
# return 2 ** 31 - 1 if sign else -2 ** 31
# 如果你用的语言int为32位,需要在这里提前判断越界,py就无所谓了
ans += int(s[i])
return ans * sign if -2 ** 31 <= ans * sign <= 2 ** 31 - 1 else (2 ** 31 - 1 if sign == 1 else -2 ** 31)
PS:按照题目要求慢慢判断就行了,注意越界要提前判断,py的话可以在最后判断。
实现 strStr()
Implement strStr().
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
h = 0
n = 0
while h < len(haystack):
if haystack[h] == needle[n]:
h += 1
n += 1
if n == len(needle):
return h - len(needle)
else:
h -= n
h += 1
n = 0
return -1