Posts

Showing posts with the label Math

[LeetCode] 65. Valid Number

Validate if a given string is numeric. Some examples: "0"  =>  true " 0.1 "  =>  true "abc"  =>  false "1 a"  =>  false "2e10"  =>  true Note:  It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. Thought process: There are several rules to enforce: There must be at least one number. e must come after some number and be followed by some number. Point cannot come after e. + and - can only appear in two positions: at the start of the string or right after e. There cannot be characters other than digits, e, point, + or -, or space. We can use several boolean flags to make these happen. 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 class Solution { public boolean isNumber ( String s ) { s = s . trim (); boolea...

[LeetCode] 66. Plus One

Given a non-negative integer represented as a  non-empty  array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list. Thought process: We don't know if the result array will have the same length as the input array. Therefore, we can use a list to hold the sum, and copy the numbers over to the result array. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int [] plusOne ( int [] digits ) { List < Integer > list = new ArrayList <>(); int sum = digits [ digits . length - 1 ] + 1 ; int carry = sum / 10 ; list . add ( sum % 10 ); int i = digits . length - 2 ; while ( i >= 0 || carry > 0 ) { int digit = i >= 0 ? digits [ i...

[LeetCode] 268. Missing Number

Given an array containing  n  distinct numbers taken from  0, 1, 2, ..., n , find the one that is missing from the array. For example, Given  nums  =  [0, 1, 3]  return  2 . Note : Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity? Thought process: Use the XOR operation. a ^ a = 0. Since the numbers run from 0 to n, nums[i] ^ i = 0. If there's no number missing, nums[0] ^ 0 ^ nums[1] ^ 1 ^ ... ^ nums[n] ^ n = 0. Now that there's one number missing, the result of the above XOR calculation will give me the missing number. Solution: 1 2 3 4 5 6 7 8 9 10 11 class Solution { public int missingNumber ( int [] nums ) { int i = 0 ; int xor = 0 ; for (; i < nums . length ; i ++) { xor ^= i ^ nums [ i ]; } return xor ^ i ; } } Time complexity: O(n). S...

[LeetCode] 670. Maximum Swap

Given a non-negative integer, you could swap two digits  at most  once to get the maximum valued number. Return the maximum valued number you could get. Example 1: Input: 2736 Output: 7236 Explanation: Swap the number 2 and the number 7. Example 2: Input: 9973 Output: 9973 Explanation: No swap. Note: The given number is in the range [0, 10 8 ] Thought process: Iterate through the digits from left to right. For each digit, iterate through the digits to its right. Try swap every digit that's larger than current digit. If there is a larger number after the swap, return the largest. Otherwise, continue to the next digit. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int maximumSwap ( int num ) { String s = Integer . toString ( num ); int len = s . length (); int max = num ; for ( int i = 0 ; i < len ; i ++) { ...

[LeetCode] 273. Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2 31  - 1. For example, 123 -> "One Hundred Twenty Three" 12345 -> "Twelve Thousand Three Hundred Forty Five" 1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" Thought process: Iterate the number from right to left. One thousand at a time. For each thousand, iterate through the digits from right to left. Based on the index of the current digit, there are several cases: index == 1:  digit == 0: left > 0: append "x-ty" to words. Increment index and right shift number. left == 0: continue. left == 1: append "x-teen" to words. Increment index and right shift number. Otherwise, append number to words. index == 2: digit == 0: continue. digit > 0: since the special cases are already covered in the previous case. Append "x-ty" to words. index == 3: di...

[LeetCode] 168. Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example: 1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB Thought process: Think of the result as a number format where each digit can have 26 numbers. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public String convertToTitle ( int n ) { StringBuilder sb = new StringBuilder (); while ( n > 0 ) { n --; sb . append (( char )( 'A' + n % 26 )); n /= 26 ; } return sb . reverse (). toString (); } } Time complexity: O(n / 26) = O(n).

[LeetCode] 43. Multiply Strings

Given two non-negative integers  num1  and  num2  represented as strings, return the product of  num1  and  num2 . Note: The length of both  num1  and  num2  is < 110. Both  num1  and  num2  contains only digits  0-9 . Both  num1  and  num2  does not contain any leading zero. You  must not use any built-in BigInteger library  or  convert the inputs to integer  directly. Thought process: Use an array to keep track of the products of each pair of digits and add them together. When doing multiplication, I need to align the numbers to the right. So I need to iterate through the product array from right to left. 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 class Solution { public String multiply ( String num1 , String num2 ) { int [] products = new int [ num1 . length () + num2 . len...

[LeetCode] 13. Roman to Integer

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. Thought process: Iterate the numeral. Add every character together and subtract the special cases (e.g. IV). There is going to be at most one occurrence of each special case. 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 romanToInt ( String s ) { int sum = 0 ; for ( char c : s . toCharArray ()) { switch ( c ) { case 'I' : sum ++; break ; case 'V' : sum += 5 ; break ; case 'X' : sum += 10 ; break ; case 'L' : sum += 50 ; break ; ...

[LeetCode] 535. Encode and Decode TinyURL

Note: This is a companion problem to the  System Design  problem:  Design TinyURL . TinyURL is a URL shortening service where you enter a URL such as  https://leetcode.com/problems/design-tinyurl  and it returns a short URL such as  http://tinyurl.com/4e9iAk . Design the  encode  and  decode  methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL. Thought process: Use a simple counter. Solution 1 (counter): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public class Codec { private int i ; private Map < Integer , String > map ; public Codec () { i = 0 ; map = new HashMap <>(); } // Encodes a URL to a shortened URL. public String encode ( String longUrl )...

[LeetCode] 523. Continous Subarray Sum

Given a list of  non-negative  numbers and a target  integer  k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of  k , that is, sums up to n*k where n is also an  integer . Example 1: Input: [23, 2, 4, 6, 7], k=6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6. Example 2: Input: [23, 2, 6, 4, 7], k=6 Output: True Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42. Note: The length of the array won't exceed 10,000. You may assume the sum of all the numbers is in the range of a signed 32-bit integer. Thought process: Obtain the prefix sum at each index and brute force the sum of every sub-array. Solution 1 (prefix sum): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public boolean checkSubarraySum ( int [] nums , int k )...