LeetCode个人笔记????‍???? LeetCode 精选 TOP 面试题

98 阅读 0 评论 65 点赞

我是靠谱客的博主隐形歌曲，最近开发中收集的这篇文章主要介绍LeetCode个人笔记????‍???? LeetCode 精选 TOP 面试题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

????‍???? LeetCode 精选 TOP 面试题

文章目录

????‍???? LeetCode 精选 TOP 面试题
@[toc]
[1. 两数之和](https://leetcode-cn.com/problems/two-sum/)
[2. 两数相加](https://leetcode-cn.com/problems/add-two-numbers/)
[3. 无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)
[4. 寻找两个正序数组的中位数](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/)
[5. 最长回文子串](https://leetcode-cn.com/problems/longest-palindromic-substring/)
[7. 整数反转](https://leetcode-cn.com/problems/reverse-integer/)
[8. 字符串转换整数 (atoi)](https://leetcode-cn.com/problems/string-to-integer-atoi/)
[11. 盛最多水的容器](https://leetcode-cn.com/problems/container-with-most-water/)
[13. 罗马数字转整数](https://leetcode-cn.com/problems/roman-to-integer/)
[15. 三数之和](https://leetcode-cn.com/problems/3sum/)
[17. 电话号码的字母组合](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/)
[19. 删除链表的倒数第N个节点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
[29. 两数相除](https://leetcode-cn.com/problems/divide-two-integers/)
[33. 搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/)
[36. 有效的数独](https://leetcode-cn.com/problems/valid-sudoku/)
[44. 通配符匹配](https://leetcode-cn.com/problems/wildcard-matching/)
[49. 字母异位词分组](https://leetcode-cn.com/problems/group-anagrams/)
[55. 跳跃游戏](https://leetcode-cn.com/problems/jump-game/)
[62. 不同路径](https://leetcode-cn.com/problems/unique-paths/)
[66. 加一](https://leetcode-cn.com/problems/plus-one/)
[73. 矩阵置零](https://leetcode-cn.com/problems/set-matrix-zeroes/)

1. 两数之和

简单

哈希

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = dict()
        for i in range(len(nums)): d[nums[i]] = i
        for i in range(len(nums)):
            if target - nums[i] in d and i != d[target - nums[i]]:
                return [i, d[target - nums[i]]]

2. 两数相加

中等

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

# 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: ListNode, l2: ListNode) -> ListNode:
        p1, p2, flag = l1, l2, 0
        head = ListNode(0)			# 伪头节点
        p = head
        while p1 or p2:
            tmp = flag
            if p1: 
                tmp += p1.val
                p1 = p1.next
            if p2: 
                tmp += p2.val
                p2 = p2.next
            node, flag = ListNode(tmp % 10), tmp // 10
            p.next = node
            p = p.next
        if flag: p.next = ListNode(1)
        return head.next

3. 无重复字符的最长子串

中等

滑动窗口+哈希

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left, right, res, uoset = 0, 0, 0, set()
        while right < len(s):
            if right < len(s) and s[right] not in uoset:
                uoset.add(s[right])
                right += 1
            else:
                uoset.remove(s[left])
                left += 1
            res = max(res, right - left)
        return res

优化一点点

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left, right, res, uomap = 0, 0, 0, dict()
        while right < len(s):
            if right < len(s) and s[right] not in uomap:
                uomap[s[right]] = right
            else:
                left = max(left, uomap[s[right]] + 1)
                uomap[s[right]] = right
            right += 1
            res = max(res, right - left)
        return res

4. 寻找两个正序数组的中位数

困难

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

**进阶：**你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

归并排序思想，统计

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        maxlen, i, j = len(nums1) + len(nums2), 0, 0
        pre, cur = -1, -1
        for idx in range(0, maxlen // 2 + 1):
            pre = cur
            if j >= len(nums2) or (i < len(nums1) and nums1[i] < nums2[j]):
                cur = nums1[i]
                i += 1
            else:
                cur = nums2[j]
                j += 1
        return cur if maxlen % 2 == 1 else (pre + cur) / 2

划分数组

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2): 
            nums1, nums2 = nums2, nums1
        n, m = len(nums1), len(nums2)
        left, right, total_left = 0, n, (n + m + 1) // 2
        while left < right:
            i = left + (right - left + 1) // 2
            j = total_left - i
            if i > 0 and nums1[i - 1] > nums2[j]: right = i - 1
            else: left = i
        i = left
        j = total_left - i
        nums1_left  = -infinty if i == 0 else nums1[i - 1]
        nums1_right = infinty  if i == n else nums1[i]
        nums2_left  = -infinty if j == 0 else nums2[j - 1]
        nums2_right = infinty  if j == m else nums2[j]
        if (n + m) % 2 == 1:
            return max(nums1_left, nums2_left)
        else:
            return (max(nums1_left, nums2_left) + min(nums1_right, nums2_right)) / 2
        return 0

5. 最长回文子串

中等

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

func longestPalindrome(s string) string {
    begin, maxlen := 0, 1
    getPalindromeLength := func(s string, i, j int) int {
        left, right := i, j
        for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left - 1, right + 1 {}
        return right - left - 1
    }
    for i := 0; i < len(s) - 1; i++ {
        len1 := getPalindromeLength(s, i, i + 1)
        len2 := getPalindromeLength(s, i, i)
        if(len1 > maxlen) {
            begin = i - (len1 - 1) / 2
            maxlen = len1
        }
        if(len2 > maxlen) {
            begin = i - (len2 - 1) / 2
            maxlen = len2
        }
    }
    return s[begin : begin + maxlen]
}

7. 整数反转

简单

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123
输出: 321

注意:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

func reverse(x int) int {
    const INT_MAX = 0x7fffffff
    const INT_MIN = ^INT_MAX
    res := 0
    for x != 0 {
        if((x > 0 && (res > INT_MAX / 10 || (res == INT_MAX / 10 && x % 10 > 7))) || 
            (x < 0 && (res < INT_MIN / 10 || (res == INT_MIN / 10 && x % 10 > 8)))){
            return 0
        }
        res = res * 10 + x % 10
        x /= 10
    }
    return res
}

8. 字符串转换整数 (atoi)

中等

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示：

本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

func myAtoi(s string) int {
    if len(s) == 0 {
        return 0
    }
    const INT_MAX = 0x7FFFFFFF
    const INT_MIN = ^INT_MAX
    res, pos, notNegative := 0, 0, true
    // 空格
    for pos < len(s) && s[pos] == ' ' {
        pos++
    }
    // 符号
    if pos < len(s) && s[pos] == '-' {
        notNegative = false
        pos++
    } else if pos < len(s) && s[pos] == '+' {
        pos++
    }
    num := 0
    for pos < len(s) && int(s[pos]) >= int('0') && int(s[pos]) <= int('9') {
        num = int(s[pos]) - int('0')
        if notNegative && (res > INT_MAX / 10 || (res == INT_MAX / 10 && num > 7)) {
            return INT_MAX
        } else if !notNegative && (res > INT_MAX / 10 || (res == INT_MAX / 10 && num > 8)) {
            return INT_MIN
        }
        res = res * 10 + num
        pos++
    }
    if notNegative {
        return res
    }
    return -res
}

11. 盛最多水的容器

中等

给你 n 个非负整数 a1，a2，...，a``n，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

**说明：**你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

双指针

func maxArea(height []int) int {
    high, wide, area := 0, 0, 0
    left, right, res := 0, len(height) - 1, 0
    for left < right {
        wide = right - left
        if height[left] < height[right] {
            high = height[left]
            left++
        } else {
            high = height[right]
            right--
        }
        area = high * wide
        if area > res {
            res = area
        }
    }
    return res
}

13. 罗马数字转整数

简单

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

func romanToInt(s string) int {
    uomap, res := make(map[string]int), 0
    uomap["I"], uomap["V"], uomap["X"] = 1, 5, 10
    uomap["L"], uomap["C"], uomap["D"], uomap["M"] = 50, 100, 500, 1000
    for i := 0; i < len(s); i++ {
        if i < len(s) - 1 && uomap[string(s[i])] < uomap[string(s[i + 1])] {
            res -= uomap[string(s[i])]
        } else {
            res += uomap[string(s[i])]
        }
    }
    return res
}

15. 三数之和

中等

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

func threeSum(nums []int) [][]int {
    n := len(nums)
    sort.Ints(nums)
    ans := make([][]int, 0)
    for first := 0; first < n; first++ {
        if first > 0 && nums[first] == nums[first - 1] {
            continue
        }
        target := -1 * nums[first]
        second := first + 1
        third := n - 1
        for second < third {
            // fmt.Printf("%d, %dn", second, third)
            if second > first + 1 && nums[second] == nums[second - 1] {
                second++
                continue
            }
            if nums[second] + nums[third] > target {
                third--
            }else if nums[second] + nums[third] < target {
                second++
            }else {
                ans = append(ans, []int{nums[first], nums[second], nums[third]})
                second++
                third--
            }
        }
    }
    return ans
}

17. 电话号码的字母组合

中等

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

var phoneMap map[string]string = map[string]string{
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
}

var combinations []string

func dfs(digits, curStr string, idx int) {
	if idx == len(digits) {
		combinations = append(combinations, curStr)
		return
	}
	if str, exist := phoneMap[string(digits[idx])]; exist {
		for i := 0; i < len(str); i++ {
			dfs(digits, curStr + string(str[i]), idx + 1)
		}
	}
}

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	combinations = make([]string, 0)
	dfs(digits, "", 0)
	return combinations
}

19. 删除链表的倒数第N个节点

中等

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	slow, fast, cnt := head, head, 0
	for cnt < n {
		fast = fast.Next
		cnt++
	}
	if fast == nil {	// 删除第一个节点的特殊情况
		return head.Next
	}
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	// 此时slow指向待删除节点的前一个节点
	slow.Next = slow.Next.Next
	return head
}

29. 两数相除

中等

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

class Solution {
public:
    int divide(int dividend, int divisor) {
        long long x = abs(dividend);
        long long y = abs(divisor);
        if(y > x) return 0;
        long long res = 0, tmp = 0;
        while(tmp + y <= x){
            long k = 1, t = y;       
            while(tmp + (t << 1) < x){
                k <<= 1;
                t <<= 1;
            }
            res += k;
			tmp += t;
        }
        res = (dividend > 0) ^ (divisor > 0) ? -res : res;
        return res > INT_MAX || res < INT_MIN ? INT_MAX : res;
    }
};

33. 搜索旋转排序数组

二分查找

给你一个整数数组 nums ，和一个整数 target 。

该整数数组原本是按升序排列，但输入时在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r, p = 0, len(nums) - 1, 0
        if len(nums) == 0: return -1
        while l < r:	# 二分查找旋转点
            m = l + (r - l) 
            if nums[m] > nums[r]: l = m + 1
            elif nums[m] < nums[r]: r = m
            else: r -= 1
        p = l
        if p == 0: l, r = 0, len(nums) - 1
        elif target > nums[0]: l, r = 0, p - 1
        elif target < nums[0]: l, r = p, len(nums) - 1
        else: return 0
        while l < r:	# 二分查找target
            m = l + (r - l) // 2
            if nums[m] > target: r = m
            elif nums[m] < target: l = m + 1
            else: return m
        return -1 if nums[l] != target else l

36. 有效的数独

中等

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
		bool f1 = true, f2 = true, f3 = true;
		for(int i = 0; i < 9; i++){
			int arr1[10] = {0};
			int arr2[10] = {0};
			for(int j = 0; j < 9; j++){
				if(board[i][j] != '.'){
					if(arr1[board[i][j] - '0'] == 1){
						f1 = false;
					}
					arr1[board[i][j] - '0'] = 1;
				}
				if(board[j][i] != '.'){
					if(arr2[board[j][i] - '0'] == 1){
						f2 = false;
					}
					arr2[board[j][i] - '0'] = 1;
				}
			}
		}
		int bx = 0, by = 0;
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				//一个九宫格
				int arr[10] = {0};
				for(int n = 0; n < 3; n++){
					for(int m = 0; m < 3; m++){
						char ch = board[i * 3 + n][j * 3 + m];
						if(ch != '.'){
							if(arr[ch - '0'] == 1){
								f3 = false;
							}
							arr[ch - '0'] = 1;
						}
					}
				}
				
			}
		}
		return f1 && f2 && f3;
    }
};

44. 通配符匹配

困难

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = p.size(), m = s.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            if (p[i - 1] == '*')
                dp[i][0] = dp[i - 1][0];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[i - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
                else if (p[i - 1] == s[j - 1] || p[i - 1] == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[n][m];
    }
};

49. 字母异位词分组

哈希

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int idx = 0;
        vector<vector<string>> res;
        unordered_map<string, int> uomap;
        for (auto& str : strs) {
            string s = str;
            sort(s.begin(), s.end());
            if (uomap.find(s) == uomap.end()) {
                uomap.insert(make_pair(s, idx++));
                res.push_back(vector<string>());
            }
            res[uomap[s]].emplace_back(str);
        }
        return res;
    }
};

55. 跳跃游戏

贪心

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

class Solution {
public:
    bool canJump(vector<int>& nums) {
		int k = 0;	//当前位置能走到最远的idx
		for(int i = 0; i < nums.size(); i++){
			if(i > k) return false;
			k = max(k, i + nums[i]);
		}
		return true;
    }
};

62. 不同路径

深度优先搜索，动态规划，组合数学

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

记忆化递归

class Solution {
public:
	int dfs(int i, int j, int& m, int& n, vector<vector<int>>& mem){
		if(i >= m || j >= n) return 0;
		if(i == m - 1 && j == n - 1) return 1;
		if(mem[i][j] == -1){
			mem[i][j] = dfs(i + 1, j, m, n, mem) + dfs(i, j + 1, m, n, mem);
		}
		return mem[i][j];
	}
    int uniquePaths(int m, int n) {
    	vector<vector<int>> mem(m, vector<int>(n, -1));
    	return dfs(0, 0, m, n, mem);
    }
};

动态规划

class Solution {
public:
    int uniquePaths(int m, int n) {
		vector<vector<int>> dp(m, vector<int>(n, 1));
		for(int i = 1; i < m; i++)
			for(int j = 1; j < n; j++)
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		return dp[m - 1][n - 1];
    }
};

组合数学

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, n - 1)

66. 加一

简单

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
		int n = digits.size();
		digits[n - 1]++;
		for(int i = n - 1; i >= 0 && digits[i] > 9; i--){
			if(i == 0){
				digits.insert(digits.begin(), 1);
				digits[1] = 0;
				digits[0] = 1;
			}
			else{
				digits[i] = 0;
				digits[i - 1]++;
			}
		}
		return digits;
    }
};

73. 矩阵置零

中等

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用**原地算法。**

方法一：使用额外空间

复杂度分析

时间复杂度：O(M times N)O(M×N)，其中 MM 和 NN 分别对应行数和列数。
空间复杂度：O(M+N)O(M+N)。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
		set<int> row, col;
        int n = matrix.size(), m = matrix[0].size();
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(matrix[i][j] == 0){
					row.insert(i);
					col.insert(j);
				}
			}
		}
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(row.find(i) != row.end()) matrix[i][j] = 0;
				if(col.find(j) != col.end()) matrix[i][j] = 0;
			}
		}
    }
};

方法二：不使用额外空间的暴力

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
		set<int> row, col;
        int n = matrix.size(), m = matrix[0].size();
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(matrix[i][j] == 0){
					for(int _i = 0; _i < n; _i++){
						if(matrix[_i][j] != 0){
							matrix[_i][j] = -123456789;
						}
					}
					for(int _j = 0; _j < m; _j++){
						if(matrix[i][_j] != 0){
							matrix[i][_j] = -123456789;
						}
					}
				}
			}
		}
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(matrix[i][j] == -123456789){
					matrix[i][j] = 0;
				}
			}
		}
    }
};

最后

以上就是隐形歌曲为你收集整理的LeetCode个人笔记????‍???? LeetCode 精选 TOP 面试题的全部内容，希望文章能够帮你解决LeetCode个人笔记????‍???? LeetCode 精选 TOP 面试题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：算法基础
浏览次数：98 次浏览
发布日期：2023-08-22 14:50:15
本文链接：https://www.kaopuke.com/article/k-p-k_14_uzo_18_f1_14__7__18_x.html

LeetCode个人笔记????‍???? LeetCode 精选 TOP 面试题

概述

????‍???? LeetCode 精选 TOP 面试题

文章目录

1. 两数之和

2. 两数相加

3. 无重复字符的最长子串

4. 寻找两个正序数组的中位数

5. 最长回文子串

7. 整数反转

8. 字符串转换整数 (atoi)

11. 盛最多水的容器

13. 罗马数字转整数

15. 三数之和

17. 电话号码的字母组合

19. 删除链表的倒数第N个节点

29. 两数相除

33. 搜索旋转排序数组

36. 有效的数独

44. 通配符匹配

49. 字母异位词分组

55. 跳跃游戏

62. 不同路径

66. 加一

73. 矩阵置零

最后

评论列表共有 0 条评论

发表评论取消回复

LeetCode个人笔记????‍???? LeetCode 精选 TOP 面试题

概述

????‍???? LeetCode 精选 TOP 面试题

文章目录

1. 两数之和

2. 两数相加

3. 无重复字符的最长子串

4. 寻找两个正序数组的中位数

5. 最长回文子串

7. 整数反转

8. 字符串转换整数 (atoi)

11. 盛最多水的容器

13. 罗马数字转整数

15. 三数之和

17. 电话号码的字母组合

19. 删除链表的倒数第N个节点

29. 两数相除

33. 搜索旋转排序数组

36. 有效的数独

44. 通配符匹配

49. 字母异位词分组

55. 跳跃游戏

62. 不同路径

66. 加一

73. 矩阵置零

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复