Sum of Left Leaves

Posted on November 16, 2016

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 November 14, 2016

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 November 14, 2016

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.

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 November 11, 2016

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.