Leetcode刷题每日记录

alanyannick

Easy #21. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = []
Output: []
Example 3:
Input: l1 = [], l2 = [0]
Output: [0]

Solution:
典型的linkedin list变换指针来排序的题目。每次只需要根据当前的val来判断是否需要改变pointer，linked到两个list其中的pointer，然后移到下一位。
写成算法就是:
1.先初始化一个新的node，拿到pointer
2.判断L1 L2同时存在的情况，哪个value大link哪个value，link的操作为【prev.next = l1】, 然后【update l1的指针为 l1 = l1.next】
3.因为是sorted list，一个linked list'走完，只需要把接下来的元素linkedin到我们建立的pointer即可。
4.返回Node_pointer使用head.next

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
# Create a pointer
head = ListNode(0)
# get the head
prev = head
# check L1 and L2
while l1 and l2:
if l1.val < l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
# update the pointer
prev = prev.next
# link the rest of the list
if l1 is not None:
prev.next = l1
else:
prev.next = l2
# return Node_pointer
return head.next

复制代码

alanyannick

Easy #26. Remove Duplicates from Sorted Array
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.
Example 2:
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 length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Solution:
需要把sortedlist中的重复的元素拿走，并用inplace的操作。基本上看到inplace的操作就是双指针-Two_pointers.一个是iteration的变量index,用来【每次+1控制循环】，一个是更新当前memory inplace操作的 exchanged_index, 【只有变化了才加1】

算法思路也很简单，就是
1.每次判断future_value是否和current_value一致，如果一致continue。
2.不一致则把不一致的替换到exchange_index+1 即第二个重复的元素(in-place) operation。
3.index-iteration每次都要+1
4.返回exchanged_index的长度，即为我们需要的array

class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# my thoughts: check the next one is equal to current value
# if it is, change the index, otherwise keep it.
# end_point will be the len(nums)
# Two Pointers
exchange_index = 0
index = 0
# [url=home.php?mod=space&uid=658482]@index[/url] for controlling the iterations
# @exchange_index for controlling the exchanged index
while index + 1 < len(nums):
current_value = nums[index]
future_value = nums[index+1]
# exchange logic
if current_value != future_value:
exchange_index = exchange_index + 1
nums[exchange_index] = future_value
# iteration
index += 1
return len(nums[:exchange_index+1])

复制代码

alanyannick

Easy #27 Remove Element 把特定值的element删掉
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3]

Solution:
in-place操作again, 明显双指针，但需要看这个指针怎么双。
这里是首尾可以节省效率即
1.首不断往后走，index+1, 直到他们首尾meet。
2.但首元素等于target时，则把首换到尾，尾巴的exchanged_index -1，节省memory。
基本双指针题目的套路都是这样，一个fast 快指针进行迭代循环+1，一个slow指针，来决定什么时候exchange，做完后即+1 or -1 update index。
3.最后返回len( nums[:exchanged_index])

class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
# Two_pointers
init_index = 0
exchange_index = len(nums)
# continue to exchange index to exchange index, til they meet
while init_index < exchange_index:
if nums[init_index] == val:
nums[init_index] = nums[exchange_index-1]
exchange_index -=1
else:
init_index +=1
return len(nums[:exchange_index])

复制代码

alanyannick

Easy #28. Implement strStr() 找到元素内是否含有需要的string，返回index

Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Example 3:
Input: haystack = "", needle = ""
Output: 0

Solution:
思路很简单，不断的判断是否当前index：index+len(needle)为needle即可。

class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
# needle is empty, return 0
if needle == "":
return 0
else:
# for loop in range(hello - ll = 3 +1)
for i in range(len(haystack) - len(needle) + 1):
# if i:i+len(needle) == needle
if haystack[i:i+len(needle)] == needle:
return i
return -1

复制代码

alanyannick

Easy #35. Search Insert Position 找到要插入的位置
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1

Solution:
给定一个target value要找到他需要插入或者等于他的index位置。
那判断条件就是
1.是否第一个元素比target大或者等于target，如果是返回他的index，
2.index+1在最后一位以及target是被两个元素夹着，如果是，返回index+1

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1

复制代码

补充内容 (2021-05-31 14:57 +8:00):
class Solution(object):
def searchInsert(self, nums, target):
      """
      :type nums: List[int]
      :type target: int
      :rtype: int
      """
      for index in range(0, l...

alanyannick

Day2 总结，刷了7道题主要为
1.array inplace的双指针问题，基本看到inplace即为这一类的题目，需要一个fast指针用来在while迭代，以及一个slow指针用来做inplace节省memory的操作。最后通过slow指针来取到要用的array，array[:exchanged_index]。

2.linked list进行sort merge的时候，要用ListNode(0)先建立一个Node：
# class ListNode(object):
#    def __init__(self, val=0, next=None):
#       self.val = val
#       self.next = next
然后将指针初始化。head = ListNode(0); prev_pointer = head
每次update 指针进行link的时候，用 prev_pointer.next = L1来建立，并用L1 = L1.next移动指针。L1.val来拿到值。
最后用prev_pointer = prev_pointer.next来拿到下一个地址的pointer位置。最最后，返回的时候，返回的是head.next。

3.看到括号，判断回文题目基本就是stack。必要的条件就是hash_table提前建好索引，一个cache_list存储每次的变量，然后判断是否和stack.pop元素一致。最后，cache_list == [] 来判断stacl是否为空。同时dict还可以用dict.keys(), dict.values()来拿到list，判断是否在元素内。

4.最大公共子序列，即先取出一个序列，然后再在剩下两个序列里找什么时候不一致，return。

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 58. Length of Last Word 最后一个可以搜索到的word的长度
Given a string s consists of some words separated by spaces, return the length of the last word in the string. If the last word does not exist, return 0.
A word is a maximal substring consisting of non-space characters only.
Example 1:
Input: s = "Hello World"
Output: 5
Example 2:
Input: s = " "
Output: 0

Solution:
通过这道题就可以训练起来自己解决问题的思路和方法，比如【Main Algorithm/Data Strcuture -> Blue Print Pipeline -> Edge Case】
1.看到这道题就有基本的 basic ideas 是一个需要用什么【main algorithm】为split(' ')，以及用[::-1] or pop()找到最后一个word方法的题
2.然后就需要想，整个流程的【Blue Print】整个大的流程，比如先split, 然后不断在stack中pop最后一个，得到长度。
3.最后就需要想edge case，比如“a ”怎么办？也就是需要对pop出来的元素做一个len() >=1 的判断。

因此解法很明显：
1.Split“ ” 得到array
2.对arry loop循环pop
3.直到pop( )出来的元素element>= 1长度，说明拿到的是word，返回长度，否则找不到为0

class Solution(object):
def lengthOfLastWord(self, s):
"""
:type s: str
:rtype: int
"""
# Ideas -> Blue_Print -> Solution -> Edge_Case
# split usage
# Thoughts: 1. Split it into seperated words by split(' ')
# 2. Get the last one element
# 3. Calculate the lens, if lens>=1, return.
# Main algorithm: str.split(" ")
# example:
# 2. "a " -> "a", ""
# 1. " " -> "", ""
# 0. "abv alv" -> "abv", "alv"
array_str = s.split(" ")
# if array == null, then it means False, can break the loop, return 0
# else: len(element) >= 1: return len(element)
while array_str:
element = array_str.pop()
if len(element) >= 1:
return len(element)
return 0

复制代码

alanyannick

Easy #66. Plus One 进位1题目
Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Example 1:
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Solution:
需要找出+1进位后的数字是多少，比如1231 + 1 = 1232， 1239 + 1 = 1240， 999 + 1 = 1000
进位的题目一般两个要点: 1.carry控制进位，通过carry%进位threshold来控制 2.carry控制进位后剩余的值，通过carry//进位threshold来清空1。
这题，除了用这种还可以巧妙用符合int规则的10进位来写，即把1231list先换成char，然后再用 list( str(int（x）+1) )切换回来。

class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
# 1,2,3 + 1 => 124
# 2,9,9 + 1 => 300
# 9,9,9 + 1 => 1000
# Main algorithm:
# 1. return array[-1] + 1
# 2. edge case: current_last_9 + 1 = 0
# 9, 9 => 1, 0, 0
# Get interger nums:
char = ''
for i in digits:
char = char + str(i)
# Transfer it to int+1 and return list(str())
return list(str(int(char)+1))

复制代码

alanyannick

本帖最后由 alanyannick 于 2021-6-1 08:14 编辑

Easy #67. Add Binary 进位2题目
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Solution:
和上2题说的一样，主数据结构为string.append，和进位运算(%, //)，然后思考blue print，判断len a, b, carry来进行加法，最后return edge case需要倒置Done。
1.用len_a,len_b,carry >0 控制循环然后len_a, len_b 每次-1， final='' 来叠加要的值
2.如果还存在a, b, carry 就都需要进行加法运算。
3.运算逻辑为，carry存储a, b的值，然后carry%2 进行进位， carry//2进行清位
4.return final[::-1]因为运算的逻辑是从后向前append的，需要倒置

class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
# list a, list b, carry, final
len_a, len_b, carry, final = len(a), len(b), 0, ''
a = list(a)
b = list(b)
while len_a > 0 or len_b > 0 or carry > 0 :
if len_a > 0:
carry += int(a[len_a-1])
len_a -= 1
if len_b > 0:
carry += int(b[len_b-1])
len_b -= 1
# handle carry
final = final + str(carry%2)
# @Trick, //2 to update the ^2 operation
carry = carry // 2
return final[::-1]

复制代码

Leetcode刷题每日记录

浏览过的版块