geeky

Sum of Left Leaves

Posted on

screen-shot-2016-11-15-at-4-25-23-pm

Problem:

Find the sum of all left leaves in a given binary tree.

Example:

3
/ \
9 20
/ \
15 7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

Solution:

For tree traversal, think in recursion way first. The point is to catch the left leaves. So the base case  includes catching a left leaf. Then just recursively call itself on both left subtree and right subtree to find all the left leaves.

Palindrome LinkedList

Posted on

Screen Shot 2016-11-14 at 10.37.43 AM.png

Problem:

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

Solution:

The general idea is to partition the list into left and right parts. Reverse the one half list, it should be the same list as the other half. To partition, use slow and fast pointers and be careful about the boundary null pointers.

 

 

Longest Palindrome

Posted on

Problem

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input: “abccccdd” Output: 7 Explanation: One longest palindrome that can be built is “dccaccd”, whose length is 7.

screen-shot-2016-11-13-at-5-09-25-pm

Solution

Thanks to a brilliant idea from one coder. Use the logic true/false cases to achieve fast run time. Add length by two each time when evaluate. No adding when flipped odd times. In this way, only the even numbered appearance is calculated.

 

Find All Anagrams in a String

Posted on

Screen Shot 2016-11-10 at 4.12.34 PM.png

Problem:

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Solution:

Create a sliding window to compare. When compare the existence of lowercase letters, use ASICII codes as the index key in an array and store the existence # as the value. Use equals() method from java Array library to judge.

 

 

 

 

 

 

Factorial Trailing Zeroes

Posted on

Problem

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Solution

0 in the number is coming from 10. 10 = 2 * 5. So must count the number of 2*5 pairs in n!.

The naive way is to use n! % 5 each time, add the counter until n! % 5 != 0. However, n! is easy to overflow. So this problem we cannot do the calculation of n!.

To count the number of 5, we can just use the result of n/5.                                                          i.e. 5! -> 5/5 = 1        10! -> 10/5 = 2  However, for 25! or 125! or (5^x)!, this includes 25, 125, some 5^x numbers contain more than one 5. So need to add these concealed 5 together. Therefore, the total number of 5 is n/5 + n/25 + n/125 + …. until 5^x > n.

After the judgement of OJ, when n is too big, it means 5^x may get too big to overflow, so the parameter to store this number (i) must be set as long type to avoid overflow.

screen-shot-2016-10-16-at-5-18-04-pm

 

Palindrome Number

Posted on

screen-shot-2016-09-24-at-5-20-07-pm

Problem

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Solution

The inversed version of palindrome numbers are the same as themselves. So inverse the number first. For the digit manipulations of the integers, use % and / to get every digit of an integer.

Find the Difference

Posted on

Problem

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

 

Solution

screen-shot-2016-09-10-at-8-53-55-pm

For problems of finding the difference, first think about XOR operation. Two points about XOR must be comfortable with:

  • 0 ^ A = A
  • XOR is commutable, so sequence not matters

Secondly, think about the length of s and t. t must have one more letter than s. Combined with the commutation of XOR, two XOR operations can be put under the same for loop.