Leetcode

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order. Example 1: Input: [-4,-1,0,3,10] Output: [0,1,9,16,100] Example 2: Input: [-7,-3,2,3,11] Output: [4,9,9,49,121] Note: 1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A is sorted in non-decreasing order. Solution: /** * Forward declaration of guess API. * @param num your guess * @return -1 if num is lower than the guess number * 1 if num is higher than the guess number * otherwise return 0 * int guess(int num); */ public class Solution extends GuessGame { public int guessNumber(int n) { int l = 0; int r = n + 1; while (l < r) { int mid = l + (r - l) / 2; int guess = guess(mid); if (guess == 0) { return mid; } if (guess == 1) { l = mid; } else { r = mid + 1; } } return r; } }

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. Example: Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5 Solution: ...

We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked. Every time you guess wrong, I’ll tell you whether the number is higher or lower. You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0): -1 : My number is lower 1 : My number is higher 0 : Congrats! You got it! Example : ...

he i-th person has weight people[i], and each boat can carry a maximum weight of limit. Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit. Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.) Example 1: Input: people = [1,2], limit = 3 Output: 1 Explanation: 1 boat (1, 2) Example 2: ...

Every non-negative integer N has a binary representation. For example, 5 can be represented as “101” in binary, 11 as “1011” in binary, and so on. Note that except for N = 0, there are no leading zeroes in any binary representation. The complement of a binary representation is the number in binary you get when changing every 1 to a 0 and 0 to a 1. For example, the complement of “101” in binary is “010” in binary. ...

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1. Two nodes of a binary tree are cousins if they have the same depth, but have different parents. We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree. Return true if and only if the nodes corresponding to the values x and y are cousins. ...

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1. Examples: s = "leetcode" return 0. s = "loveleetcode", return 2. Note: You may assume the string contain only lowercase letters. Solution: class Solution { public int firstUniqChar(String s) { Map<Character, Integer> freq = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); freq.put(c, freq.getOrDefault(c, 0) + 1); } for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (freq.get(c) == 1) { return i; } } return -1; } }

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1,1,2,2] Output: 2 Solution: class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } }

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false. Each letter in the magazine string can only be used once in your ransom note. Example 1: Input: ransomNote = "a", magazine = "b" Output: false Example 2: Input: ransomNote = "aa", magazine = "ab" Output: false Example 3: ...

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels. The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so “a” is considered a different type of stone from “A”. ...