Implement pow(x, n), which calculates x raised to the power n (i.e. xn). Example 1: Input: x = 2.00000, n = 10 Output: 1024.00000 Example 2: Input: x = 2.10000, n = 3 Output: 9.26100 Example 3: Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Constraints: -100.0 < x < 100.0 -231 <= n <= 231-1 -104 <= xn <= 104 ...
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7], 1 2 3 4 5 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: ...
Given a non-empty array of integers, return the k most frequent elements. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size. It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique. You can return the answer in any order. Solution: ...
Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1: 1 2 Input: [1,2,3] Output: 6 Example 2: 1 2 Input: [1,2,3,4] Output: 24 Note: The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000]. Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer. Solution: ...
A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company has is the one with headID. Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also it’s guaranteed that the subordination relationships have a tree structure. The head of the company wants to inform all the employees of the company of an urgent piece of news. He will inform his direct subordinates and they will inform their subordinates and so on until all employees know about the urgent news. ...
For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees. A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations. Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivelent or false otherwise. ...
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. 1 2 3 4 5 6 7 8 Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II. ...
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle 1 2 3 4 5 6 [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). ...
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition: 1 2 3 4 5 6 struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. ...
Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image. Example: Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,4,7,5,3,6,8,9] Explanation: Note: The total number of elements of the given matrix will not exceed 10,000. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public int[] findDiagonalOrder(int[][] A) { if (A == null || A.length == 0) { return new int[]{}; } int rows = A.length; int cols = A[0].length; int[] list = new int[rows * cols]; int row = 0; int col = 0; int direction = 1; for (int i = 0; i < list.length; i++) { list[i] = A[row][col]; if (direction == 1) { if (col == cols - 1) { direction = -1; row++; } else if (row == 0) { col++; direction = -1; } else { row--; col++; } } else { if (row == rows - 1) { col++; direction = 1; } else if (col == 0) { row++; direction = 1; } else { row++; col--; } } } return list; } }