Leetcode刷题每日记录

alanyannick

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

感觉自己需要一个环境来总结和打卡。刷题没法避免就好好消化基础吧，上岸加油呀.

每日刷题记录开始 :D

alanyannick

Easy #13. Roman to Integer
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol    Value
I          1
V          5
X          10
L          50
C          100
D          500
M          1000
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Example 1:
Input: s = "III"
Output: 3
Example 2:
Input: s = "IV"
Output: 4

Solution:
思路：把罗马数字转为阿拉伯数字，直接根据规律转就可以了。但是edge case一个取巧的方式去处理后面一个数字比前面小的情况，需要用index i+1, i+2 来跳过。比如： IV是4，需要判断V是否比I大，如果大，就是i+2，这里两个元素为一个数，otherwise，i+1 比如 VI = 5+1 =6。遇到这种情况，一般来说，用while index +1 < len(string)来作为loop会比for i in range(0, len(string))更清晰。

写成算法就是：
0. 一个hash table查找罗马数字对应的int。
1.【check current index value】 and 【check future index value】，这里需要注意如果是index是末位也就是len(s)+1时，没有future value，设置为0.
2. 判断current value和future value情况:
            如果当前比后面大，那么就是VI的情况，直接把当前final_int + current value, index + 1
            否则，final_int + future_value-current_value, index + 2
清晰简洁，DONE

class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
# Hash table O(N)
int_roman_dict = {"I":1, "V":5,
"X": 10, "L":50,
"L": 50, "C":100,
"D": 500, "M":1000}
print int_roman_dict
# insight: get the nums of current
# index + 1 | index + 2
# if current nums > previous, update nums = previous + current
# otherwise: + current
# Initial parameter
final_int = 0
current_value = 0
future_value = 0
index = 0
# Time: O(N)
while index + 1 <= len(s):
# check value
current_value = int_roman_dict[s[index]]
# Begining from index 1
if index + 1 < len(s): # 1 < 2
future_value = int_roman_dict[s[index+1]]
else:
future_value = 0
# update current value: updated_final_int + current
if future_value > current_value:
final_int += (future_value - current_value)
index = index + 2
else:
final_int += current_value
index = index + 1
return final_int

复制代码

alanyannick

本帖最后由 alanyannick 于 2021-6-1 07:45 编辑

Easy #53. Maximum Subarray 最大子数组组合
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1

Solution:
找组合->DP or DivConq，其中暴力法都是穷举所有可能性的题，一般就可以就用DP来优化解决 or Divide&Conquer先分解成N个子问题然后merge得到最优解。
其中【暴力穷举的函数就是DP的状态转移方程】。因此，这类型的题一般都可以用DP，来用【备忘录 or DP hash table】记录下之前算过的结果，空间换时间。然后，备忘录只需要【存储之前的两个状态】，做到【状态压缩】，就可以把O(N)的空间复杂度简化为(1)。子问题是相互独立的。
动态规划之所以比暴力算法快，是因为动态规划技巧【消除了重叠子问题】。

DP问题总结:
"计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
1.列出动态转移方程，就是在解决“如何穷举”的问题。
之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。
2.备忘录、DP table 就是在追求“如何聪明地穷举”。
用空间换时间的思路，是降低时间复杂度的不二法门"
【后续再系统刷类型题来总结。】

DP和Divide&Conquer的区别是：
分而治之：在子问题上做更多的工作，因此有更多的时间消耗。在分而治之中，【子问题彼此独立】。（比如二分）
动态编程：仅解决一次子问题，然后将其存储在表中。在动态编程中，【子问题不是独立的，是重叠子问题，大大优化运算效率】。
DP会记住重叠部分，从而获得优于“分而治之”的优势。

通常这两者都需要好好准备，因为有时候考官会想知道其他的解法:
Divide and conquer algorithms are a great way to evaluate your problem solving skills. Splitting problems into smaller subproblems (so that they can be solved easier) is one of the things that interviewers like to see in candidates. That’s why they love to ask dynamic programming problems or other algorithms such as binary search (which is an example of divide and conquer approach). It’s not about runtime or space efficiency, but more about your thought process.

Ideas:
这一题很明显，暴力解法就是通过for loop把所有可能性都穷举一遍。
因此状态转移方程其实就是:
1.每个subarray的子组合更新sub_max = max(current_value, current_value + sub_max)
2.找到sub_max,每次再和gloabal max更新。

class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int # 1.Brute force ideas
# 2. DP, optimized from brute-force ideas, find the local_optimial, and stack them together to get the global_optimal
# 3. Divide and Conquer: binary divide, find the local_optimimal, then stack them together to get the global_optimal
@Note
# check_later Algorithm @DP, @DFS/BFS, @Recurrive, @Greedy, @Divide&Conquer
# Initialize our variables using the first element.
current_array = max_array = nums[0]
# Start with the 2nd element since we already used the first one.
for value in nums[1:]:
# update the max_array by max(max_array, current_array)
# continuly sum them up
# DP: sub_max => whole_max
# Update the local optimal value by max (current_i, current_array+i)
# Update the global optimal value
current_array = max(value, current_array + value)
max_array = max(max_array, current_array)
# f(n) = f(n-1 {max_value|current_array} ) <-
current_array <- f(n-2 {current_array|value})
return max_array

复制代码

alanyannick

Easy #94. Binary Tree Inorder Traversal 树的中序遍历
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]

Solution:
树的遍历，两种解法。
递归：
模版

# recursive
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if root:
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
# # iterative
# def inorderTraversal(self, root):
# res, stack = [], []
# while True:
# while root:
# stack.append(root)
# root = root.left
# if not stack:
# return res
# node = stack.pop()
# res.append(node.val)
# root = node.right

复制代码

非递归:
非递归使用栈的解法，也是符合本题要求使用的解法之一，需要用栈来做，思路是从根节点开始，
1.先将根节点压入栈:
tree_stack.append(root)
2.然后再将其所有左子结点压入栈:
root = root.left
3.然后取出栈顶节点，保存节点值，再将当前指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子结点压入栈中。这样就保证了访问顺序为左-根-右
            # get the left tree firstly, then pop
            node = tree_stack.pop()
            # get left tree vale
            trav_inorder.append(node.val)
            # update root index, go back to parent
            root = node.right

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
tree_stack = []
trav_inorder = []
while root or tree_stack:
if root:
tree_stack.append(root)
root = root.left
else:
# get the left tree firstly, then pop
node = tree_stack.pop()
# get left tree vale
trav_inorder.append(node.val)
# update root index, go back to parent
root = node.right
return trav_inorder

复制代码

alanyannick

Day1
Array(顺序存储), Linked List(链式存储) 作为记忆唤醒其它的data structure。
大概4-5天，刷完#100内Easy题目来熟悉每种题目的熟练度。
适合自己的方式：1)先读题，搞清楚题目可能需要的Data Structure, 2) 正常的算法逻辑流程应该怎么走 3) 是否有edge case。

Easy#1 2Sum

Given an array of integer nums and an integer target, return indices of the two numbers such that they add up to target.Example:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Tag:
Array, Hash Table

Solution:
基本思路很简单，暴力解法可以用两个For loop不断地search list i, j=i+1里是否有匹配的。但这样导致了很多冗余运算with O(N**2)复杂度。

优化解:
1.通过一个dict存储已经search过的element, 并把element的value as dict key, and its index as value
2.判断条件需要看是否有相应的key value在dict里面进行O(1)的hash table查找，如果存在就return 当前的index 以及对应key的value(index)
3.否则加入dict。

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# Step1: save the checked data
# Step2: get the previous and current index
# Dict - restore the data that we checked before
checked_dict = {}
# Get the value and index, if we didnt see it, save it to dict.
for index, value in enumerate(nums):
if (target-value) not in checked_dict:
checked_dict[value] = index
else:
return [index, checked_dict[(target-value)]]

复制代码

时间复杂度: O(N) with one for loop, 空间复杂度: O(1) with one hash_table.

alanyannick

Easy #7 Reverse Integer
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 [-231, 231 - 1], then return 0.

Example 1:
Input: x = 123
Output: 321
Example 2:
Input: x = -123
Output: -321
Example 3:
Input: x = 120
Output: 21

Solution:
题目想要的很简单, 也就是说需要做一个整数的翻转
0. 将数字直接转成array，用str(), 然后，直接可以用[::-1]来做，但是有following的case judgement。
1.遇到“-”需要保留，这里就可以用一个sign function来做到，if <0 -1*x, otherwise x.
2.edge case在遇到末尾为0的时候，需要省略，这里就可以聪明的用int(x)，来做。
3.超过一定规模需要return 0, 最后判断加一个if。

import math
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
# Data Structure: Int to Str(), Reverse Function (Olog(N)
# Op:
# Edge case: 1. (-2)**31, 2**31-1 -> return 0 2. 0 -> return 0
# Sign = "-" by (-1)
# Main Algorithhm
if x > 0:
x = str(x)[::-1]
if x < 0:
x = -1 * int(str(x)[1:][::-1])
# change the x to interger
x = int(x)
# Edge case
if x < math.pow(-2,31) or x > math.pow(2,31) -1:
return 0
else:
return x

复制代码

alanyannick

Easy: #9. Palindrome Number
Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

Solution:
判断是否回文，和之前题目一样，简单的str转换数字为array，然后看[::-1]的array是否和原数一样即可。

class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
x = str(x)
if x == x[::-1]:
return True
else:
return False

复制代码

alanyannick

Day 1总结，刷了四道题目，基本就是
1.熟悉最重要的array
2.dict(hash_table),key-value用法, if i in dict | dict = {} dict[key] = value
3.str转换(int)为array，以及不同for loop(while, for i in range, for i, value in enumerate() )的用法。

难度不大，刷起来比较舒适，但速度比预期的至少10道少了，加速~

YSY86

一天四五道我觉得足够了，好好理解归纳吃透刷个两个月也有200多道的积累了。加油

alanyannick

YSY86 发表于 2021-05-29 06:34:39
一天四五道我觉得足够了，好好理解归纳吃透刷个两个月也有200多道的积累了。加油

好呀，我找找节奏先，谢谢!

alanyannick

Day 2 Easy #14 Longest Common Prefix 找到最长公共子序列
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Solution:
文章需要找到一个序列N个元素内的最长公共子序列，题目很简单，从0开始判断是否有公同元素就好了，延伸的题目(abopa <- abp == 3，最长公共元素，有点难后面check）。

写成算法就是
1.从flower,flow,flight中取一个string的第一个元素进行遍历。
2.在另外两个string的for loop里面找到是否有一样的元素。
3. 判断跳出条件两个，一是原始index超出了string的长度，二是不一样的元素。
跳出的时候返回strs[0][:index]。

class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
# Step1: check each element in the first string
# Step2: check each element with the other two
# Step3: if the other two doesn't have the same characters return str[:index]
# otherwise: continue
# Edge case:
# 1.strs == "" return strs[0], == null return ""
# 2.flow ==4 | flower ==6; flow index will be out of index
# judgement of null strings
if not strs:
return ""
# Algorithm:
# need index, so use index as for loop rather than elements
for index in range(len(strs[0])): # which is the flower
# Get the elements
element = strs[0][index]
# check f,l,o,w,e,r,in the other two strings
for string in strs[1:]:
# Return condition:
# 1.index > string_lens (flow|flower)
# 2. value != string[index]
if index >= len(string) or element != string[index]:
return strs[0][:index]
return strs[0]

复制代码

alanyannick

Easy #20. Valid Parentheses 问括号，并找到是否回文，一般都是暗示栈的题目。
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([)]"
Output: false
Example 5:
Input: s = "{[]}"
Output: true

Solution:
思路很简单，建立hash table，添加首先的edgecase 【0.右括号为起点跳出。】
核心为【找到open_bracket和close_bracket能够消除】
用一个stack遇到open_bracket每次存起来，遇到close_bracket则判断
1.左括号与右括号不match
2.当前括号和pop出来的(hash_table映射)不一致
return False
最终return 判断cache_list是否清零了,清零则为True回文，反之则为False。

class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
# Get a cache, and check whether we have that cache in the hash table
# check value in Hashtable
hash_table = { ']':'[' ,
')':'(' ,
'}':'{' }
# close bracket first
if s[0] in "],),}":
return False
else:
cache_list = []
# cache_list
# if element in open closet, append it into cache_list
# elif element in close closet
# check its hash_table by poping it from cache_list
# if it cannot be found, then return false
for element in s:
if element in hash_table.values():
cache_list.append(element)
elif element in hash_table.keys():
if cache_list == [] or hash_table[element] != cache_list.pop():
return False
else:
return False
# check len(cache_list) > 0 ,which is cache_list == []
return cache_list == []

复制代码

Leetcode刷题每日记录

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

浏览过的版块