Month: September 2016
Palindrome Number
Problem
Determine whether an integer is a palindrome. Do this without extra space.
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
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
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.
In Memory of Nausicaa 