![https://leetcode.com/problems/path-crossing/] Given a string path, where path[i] = ‘N’, ‘S’, ‘E’ or ‘W’, each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path. Return True if the path crosses itself at any point, that is, if at any time you are on a location you’ve previously visited. Return False otherwise. ...
![https://leetcode.com/problems/remove-outermost-parentheses/] A valid parentheses string is either empty (""), “(” + A + “)”, or A + B, where A and B are valid parentheses strings, and + represents string concatenation. For example, “”, “()”, “(())()”, and “(()(()))” are all valid parentheses strings. A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings. ...
Given two strings A and B of lowercase letters, return true if you can swap two letters in A so the result is equal to B, otherwise, return false. Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at A[i] and A[j]. For example, swapping at indices 0 and 2 in “abcd” results in “cbad”. Example 1: Input: A = “ab”, B = “ba” Output: true Explanation: You can swap A[0] = ‘a’ and A[1] = ‘b’ to get “ba”, which is equal to B. ...
Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned. Example 1: Input: 4 Output: 2 Example 2: Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned. ...
Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1: Input: [1,2,3] Output: 6 Example 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: class Solution { public int maximumProduct(int[] nums) { int s1 = Integer.MAX_VALUE; int s2 = Integer.MAX_VALUE; int b1 = Integer.MIN_VALUE; int b2 = Integer.MIN_VALUE; int b3 = Integer.MIN_VALUE; for (int value: nums) { if (value < s1) { s2 = s1; s1 = value; } else if (value < s2) { s2 = value; } if (value > b3) { b1 = b2; b2 = b3; b3 = value; } else if (value > b2) { b1 = b2; b2 = value; } else if (value > b1) { b1 = value; } } return Math.max(s1 * s2 * b3, b1 * b2 * b3); } }
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. 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 non-empty array of digits representing a non-negative integer, increment one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. Example 1: Input: [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Example 2: ...
The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note: 0 ≤ x, y < 231. Example: Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different. Solution: ...
Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ] Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { Map<Integer, List<Integer>> map = new TreeMap<>((a,b) -> { return b - a; }); dfs(root, 0, map); System.out.println(map); List<List<Integer>> result = new ArrayList<>(); for (List<Integer> levelNodes: map.values()) { result.add(levelNodes); } return result; } void dfs(TreeNode node, int level, Map<Integer, List<Integer>> map) { if (node == null) { return; } dfs(node.left, level + 1, map); addLevelNode(map, node.val, level); dfs(node.right, level + 1, map); } void addLevelNode(Map<Integer, List<Integer>> map, int val, int level) { List<Integer> levelList = map.getOrDefault(level, new ArrayList<>()); levelList.add(val); map.put(level, levelList); } }
You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins. Given n, find the total number of full staircase rows that can be formed. n is a non-negative integer and fits within the range of a 32-bit signed integer. Example 1: n = 5 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ Because the 3rd row is incomplete, we return 2. ...