Given a n * n matrix grid of 0’s and 1’s only. We want to represent the grid with a Quad-Tree. Return the root of the Quad-Tree representing the grid. Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer. A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes: ...
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] Example 3: Input: matrix = [[1]] Output: [[1]] Example 4: Input: matrix = [[1,2],[3,4]] Output: [[3,1],[4,2]] Constraints: ...
You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. ...
Given the root of a binary tree, construct a 0-indexed m x n string matrix res that represents a formatted layout of the tree. The formatted layout matrix should be constructed using the following rules: The height of the tree is height and the number of rows m should be equal to height + 1. The number of columns n should be equal to 2height+1 - 1. Place the root node in the middle of the top row (more formally, at location res[0][(n-1)/2]). For each node that has been placed in the matrix at position res[r][c], place its left child at res[r+1][c-2height-r-1] and its right child at res[r+1][c+2height-r-1]. Continue this process until all the nodes in the tree have been placed. Any empty cells should contain the empty string “”. Return the constructed matrix res. ...
Given a string s, return all the palindromic permutations (without duplicates) of it. You may return the answer in any order. If s has no palindromic permutation, return an empty list. Example 1: Input: s = "aabb" Output: ["abba","baab"] Example 2: Input: s = "abc" Output: [] Constraints: 1 <= s.length <= 16 s consists of only lowercase English letters. Solution class Solution { public List<String> generatePalindromes(String s) { Set<String> res = new HashSet<>(); int[] freq = new int[256]; int count = 0; for (char c : s.toCharArray()) { freq[c]++; } if (!canPermute(freq)) { return Collections.emptyList(); } char mid = ' '; int k = 0; char[] st = new char[s.length() / 2]; for (int i = 0; i < freq.length; i++) { if (freq[i] % 2 == 1) { mid = (char) i; } for (int j = 0; j < freq[i] / 2; j++) { st[k++] = (char) i; } } permute(0, st, mid, res); return new ArrayList<>(res); } void permute(int i, char[] st, char mid, Set<String> res) { if (i == st.length) { String m = ((mid == ' ') ? "": "" + mid); String val = new String(st) + m + new StringBuilder(new String(st)).reverse().toString(); res.add(val); } else { for (int j = i; j < st.length; j++) { swap(i, j, st); permute(i + 1, st, mid, res); swap(i, j, st); } } } boolean canPermute(int[] freq) { int count = 0; for (int f: freq) { count += f % 2; } return count <= 1; } void swap(int i, int j, char[] st) { char t = st[i]; st[i] = st[j]; st[j] = t; } }
Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters. Letters are case sensitive, for example, “Aa” is not considered a palindrome here. Example 1: Input: s = "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7. Example 2: Input: s = "a" Output: 1 Example 3: Input: s = "bb" Output: 2 Constraints: ...
Given a string s, return true if a permutation of the string could form a palindrome. Example 1: Input: s = "code" Output: false Example 2: Input: s = "aab" Output: true Example 3: Input: s = "carerac" Output: true Constraints: 1 <= s.length <= 5000 s consists of only lowercase English letters. Solution class Solution { public boolean canPermutePalindrome(String s) { int[] freq = new int[256]; for (char c: s.toCharArray()) { freq[c]++; } int count = 0; for (int f: freq) { count += f % 2; } return count <= 1; } }
You are given an m x n grid rooms initialized with these three possible values. -1 A wall or an obstacle. 0 A gate. INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF. ...
Given an integer array nums, return the number of longest increasing subsequences. Notice that the sequence has to be strictly increasing. Example 1: Input: nums = [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7]. Example 2: Input: nums = [2,2,2,2,2] Output: 5 Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5. Constraints: ...
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that: Every adjacent pair of words differs by a single letter. Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. sk == endWord Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, …, sk]. ...