The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.
Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
114. Flatten Binary Tree to Linked List
Given the root of a binary tree, flatten the tree into a “linked list”:
- The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
- The “linked list” should be in the same order as a pre-order traversal of the binary tree.
2162. Minimum Cost to Set Cooking Time
A generic microwave supports cooking times for:
- at least 1 second.
- at most 99 minutes and 99 seconds.
To set the cooking time, you push at most four digits. The microwave normalizes what you push as four digits by prepending zeroes. It interprets the first two digits as the minutes and the last two digits as the seconds. It then adds them up as the cooking time. For example,
- You push 9 5 4 (three digits). It is normalized as 0954 and interpreted as 9 minutes and 54 seconds.
- You push 0 0 0 8 (four digits). It is interpreted as 0 minutes and 8 seconds.
- You push 8 0 9 0. It is interpreted as 80 minutes and 90 seconds.
- You push 8 1 3 0. It is interpreted as 81 minutes and 30 seconds.
You are given integers startAt, moveCost, pushCost, and targetSeconds. Initially, your finger is on the digit startAt. Moving the finger above any specific digit costs moveCost units of fatigue. Pushing the digit below the finger once costs pushCost units of fatigue.
There can be multiple ways to set the microwave to cook for targetSeconds seconds but you are interested in the way with the minimum cost.
Return the minimum cost to set targetSeconds seconds of cooking time.
Remember that one minute consists of 60 seconds.
A Bitset is a data structure that compactly stores bits.
Implement the Bitset class:
- Bitset(int size) Initializes the Bitset with size bits, all of which are 0.
- void fix(int idx) Updates the value of the bit at the index idx to 1. If the value was already 1, no change occurs.
- void unfix(int idx) Updates the value of the bit at the index idx to 0. If the value was already 0, no change occurs.
- void flip() Flips the values of each bit in the Bitset. In other words, all bits with value 0 will now have value 1 and vice versa.
- boolean all() Checks if the value of each bit in the Bitset is 1. Returns true if it satisfies the condition, false otherwise.
- boolean one() Checks if there is at least one bit in the Bitset with value 1. Returns true if it satisfies the condition, false otherwise.
- int count() Returns the total number of bits in the Bitset which have value 1.
- String toString() Returns the current composition of the Bitset. Note that in the resultant string, the character at the ith index should coincide with the value at the ith bit of the Bitset.
416. Partition Equal Subset Sum
Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Given a rows x cols binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
378. Kth Smallest Element in a Sorted Matrix
Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
You must find a solution with a memory complexity better than O(n2).