Press "Enter" to skip to content

Posts published in June 2018

花花酱 LeetCode 863. All Nodes Distance K in Binary Tree

Problem

题目大意:给你一棵二叉树(根结点root)和一个target节点。返回所有到target的距离为K的节点。

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node.  The answer can be returned in any order.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
Output: [7,4,1]
Explanation: 
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.

Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.

Note:

  1. The given tree is non-empty.
  2. Each node in the tree has unique values 0 <= node.val <= 500.
  3. The target node is a node in the tree.
  4. 0 <= K <= 1000.

Solution1: DFS + BFS

Use DFS to build the graph, and use BFS to find all the nodes that are exact K steps from target.

Time complexity: O(n)

Space complexity: O(n)

C++

Array version

Solution 2: Recursion

Recursively compute the distance from root to target, and collect nodes accordingly.

Time complexity: O(n)

Space complexity: O(n)

 

花花酱 LeetCode 860. Lemonade Change

Problem

At a lemonade stand, each lemonade costs $5.

Customers are standing in a queue to buy from you, and order one at a time (in the order specified by bills).

Each customer will only buy one lemonade and pay with either a $5$10, or $20 bill.  You must provide the correct change to each customer, so that the net transaction is that the customer pays $5.

Note that you don’t have any change in hand at first.

Return true if and only if you can provide every customer with correct change.

 

Example 1:

Input: [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:

Input: [5,5,10]
Output: true

Example 3:

Input: [10,10]
Output: false

Example 4:

Input: [5,5,10,10,20]
Output: false
Explanation: 
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can't give change of $15 back because we only have two $10 bills.
Since not every customer received correct change, the answer is false.

Solution: Simulation + Greedy

Always use 10 bill first.

Time complexity: O(n)

Space complexity: O(1)

C++

 

花花酱 LeetCode 525. Contiguous Array

Problem

题目大意:求最长子数组,要求其中0和1的数量相等。

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

Solution: HashTable

Prefix sum + hashtable

Time complexity: O(n)

Space complexity: O(n)

V2: Using array instead of a hashtable

Time complexity: O(2*n + 1 + n)

Space complexity: O(2*n + 1)

 

花花酱 LeetCode 567. Permutation in String

Problem

题目大意:给你s1, s2,问你s2的子串中是否存在s1的一个排列。

https://leetcode.com/problems/permutation-in-string/description/

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

  1. The input strings only contain lower case letters.
  2. The length of both given strings is in range [1, 10,000].

Solution: Sliding Window

Time Complexity: O(l1 + l2 * 26) = O(l1 + l2)

Space Complexity: O(26 * 2) = O(1)

C++

Related Problems

花花酱 LeetCode 605. Can Place Flowers

Problem

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots – they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

  1. The input array won’t violate no-adjacent-flowers rule.
  2. The input array size is in the range of [1, 20000].
  3. n is a non-negative integer which won’t exceed the input array size.

Solution: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++