初级算法(更新中)

编程能力就像任何其他技能一样，也是一个可以通过 刻意练习 大大提高的。

删除排序数组中的重复项

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)

PS：第一种双指针显然是比逆序删除的效率要高的，当然还有正序删除需要处理索引挺麻烦而且效率很低，试了下会超时。

买卖股票的最佳时机 II

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])

PS：这题用贪心要更简单一些，动态规划有点复杂化了把问题，不过可以用来练练

关于DP代码的解释：

定义如下：

• dp[i][0]表示第i天手里没有股票的最大利润

• dp[i][1]表示第i天手里有股票的最大利润

我们先想如果当天手里没有股票，只有两种情况，第一种是昨天有的股票今天卖了，这时的利润为dp[i-1][1] + prices[i]，第二种是昨天没有股票，今天也没有买股票，这时候的利润为dp[i-1][0]，我们需要取最大的情况：

即 dp[i][0]=max(dp[i-1][1] + prices[i], dp[i-1][0])

如果当天手里有股票，也只有两种情况，第一种是昨天的股票在今天没有去卖，利润为dp[i-1][1]，另一种情况是今天买了新的股票，利润为dp[i-1][0] - prices[i]，我们仍要取最大情况：

即 dp[i][1]=max(dp[i-1][1], dp[i-1][0] - prices[i])

综上所述，我们只需要遍历一遍得到最后一天的手里有股票和没有股票情况下的利润，取最大值即可。

旋转数组

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

PS：第一种方法注意用nums[:]对临时的nums[n-k:] + nums[0:n-k]进行浅拷贝，第二种方法将整个数组看成一个环形，每个元素后移K个位置如图：

但是这里需要注意如果下一个位置是已经访问过的，会导致无限循环，需要用vis记录当前位置是否已经被访问！

存在重复元素

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

PS：位运算应该是最简单的方法了，异或运算我们可以知道：

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

而且异或运算支持交换律，所以出现两次的数字经过连续异或后都最终变成0，0和只出现一次的数字异或的结果就是那个数字本身。

两个数组的交集 II

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

PS：两种方法，第一种用哈希表记录元素出现次数应该是最容易想到的方法，第二种先对原数组升序排序，然后用两个指针遍历两个数组，如果指针的两个数组元素相等则加入答案的列表中，如果不同，则让元素值低一些的指针右移即可。

加一

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

PS：倒着遍历，如果当前数字小于9则对当前元素+1返回即可，如果等于9则置零继续检查更高位，直到遇到小于9的元素，如果遍历完成还未返回，说明这个数组的元素全是9，所以最后需要在数组最前面插入1

移动零

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

PS：逆序删除比较容易处理，但是效率低于第二种方式，第二种方式类似使用指针记录遍历到第几个非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.

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

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

PS：这题暴力的写法可以更优雅一些，不需要这么多的IF，当然这题还有其他方法，想到用位运算做的都是啥天才呀！

旋转图像

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.

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

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().

Input: haystack = "hello", needle = "ll"
Output: 2

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