LeetCode的题目非常是碎片化时间来做，而且可以尝试最新的C++标准和多种语言， 正好要学习Java，就C++和Java两种语言来做题，如果碰到可以用immutable方式的题目就再用Scala做一下。
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.
<p>Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
Tags: Array, HashTable
C++
class Solution { // (both index1 and index2) are not zero-based.
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, size_t> umap;
for (size_t i = 0; i < nums.size(); ++i) {
auto item = nums[i];
if (umap.find(target - item) == umap.end()) {
umap[item] = i;
} else {
return vector<int>{umap[target - item], i};
}
}
return vector<int>{-1, -1};
}
};
Java
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hm = new HashMap<>();
for (int i = 0; i != nums.length; ++i) {
int complement = target - nums[i];
if (hm.get(complement) != null) {
return new int[] {hm.get(complement), i};
} else {
hm.put(nums[i], i);
}
}
return null;
}
}
Scala
object Solution {
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
var ht = collection.mutable.Map.empty[Int, Int]
for (i <- 0 until nums.size) {
val tmp = target - nums(i)
if (ht.contains(tmp)) {
return Array(ht(tmp), i)
} else {
ht(nums(i)) = i
}
}
Array(-1, -1)
}
}
2. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Tags: Linked List, Math
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(-1);
ListNode* ptr = &dummy;
int carry = 0;
while (l1 != nullptr || l2 != nullptr) {
int a = 0;
if (l1 != nullptr) {
a = l1->val;
l1 = l1->next;
}
int b = 0;
if (l2 != nullptr) {
b = l2->val;
l2 = l2->next;
}
int sum = a + b + carry;
carry = sum / 10;
ptr->next = new ListNode(sum % 10);
ptr = ptr->next;
}
if (carry > 0) {
ptr->next = new ListNode(carry);
}
return dummy.next;
}
};
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carrier = 0;
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null || l2 != null) {
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int val = x + y + carrier;
carrier = val / 10;
cur.next = new ListNode(val % 10);
cur = cur.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carrier > 0) {
cur.next = new ListNode(carrier);
}
return dummy.next;
}
}
Scala
/**
* Definition for singly-linked list.
* class ListNode(var _x: Int = 0) {
* var next: ListNode = null
* var x: Int = _x
* }
*/
object Solution {
def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
var dummyNode = new ListNode(0)
var cur = dummyNode
var carry = 0
def addInternal(l1: ListNode, l2: ListNode): Unit = {
if (l1 != null || l2 != null) {
var a = if (l1 != null) l1.x else 0
var b = if (l2 != null) l2.x else 0
var sum = a + b + carry
cur.next = new ListNode(sum % 10)
cur = cur.next
carry = sum / 10
addInternal(if (l1 != null) l1.next else null, if(l2 != null) l2.next else null)
}
}
addInternal(l1, l2)
if (carry > 0) {
cur.next = new ListNode(carry)
}
dummyNode.next
}
}
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
<p>Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
Tags: Hash Table, Two Pointers, String
C++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ret = 0;
vector<int> ht(256, -1);
int i = 0;
for (int j = 0; j < s.size(); ++j) {
auto k = ht[s[j]];
if (k >= i) {
i = k + 1;
} else {
ret = std::max(ret, j - i + 1);
}
ht[s[j]] = j;
}
return ret;
}
};
Java
public class Solution {
public int lengthOfLongestSubstring(String s) {
int ret = 0;
Map<Character, Integer> hm = new HashMap<>();
int i = 0;
for (int j = 0; j < s.length(); ++j) {
int k = hm.getOrDefault(s.charAt(j), -1);
if (k >= i) {
i = k + 1;
} else {
ret = Math.max(ret, j - i + 1);
}
hm.put(s.charAt(j), j);
}
return ret;
}
}
4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
<p>Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
<p>Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Tags: Divide and Conquer, Binary Search, Array
C++
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
auto sz = nums1.size() + nums2.size();
if (sz & 0x01) {
auto ret = findKthElement(begin(nums1), nums1.size(), begin(nums2), nums2.size(), sz / 2 + 1);
//auto ret = findKthElement(nums1.data(), nums1.size(), nums2.data(), nums2.size(), sz / 2 + 1);
return static_cast<double>(ret);
} else {
auto ret1 = findKthElement(begin(nums1), nums1.size(), begin(nums2), nums2.size(), sz / 2);
auto ret2 = findKthElement(begin(nums1), nums1.size(), begin(nums2), nums2.size(), sz / 2 + 1);
//auto ret1 = findKthElement(nums1.data(), nums1.size(), nums2.data(), nums2.size(), sz / 2);
//auto ret2 = findKthElement(nums1.data(), nums1.size(), nums2.data(), nums2.size(), sz / 2 + 1);
return (static_cast<double>(ret1) + static_cast<double>(ret2)) / 2.0;
}
}
private:
int findKthElement(const int* nums1, size_t len1, const int* nums2, size_t len2, size_t k) {
if (len1 > len2) {
return findKthElement(nums2, len2, nums1, len1, k);
}
if (len1 == 0) {
return nums2[k - 1];
}
if (k == 1) {
return min(nums1[k - 1], nums2[k - 1]);
}
auto dis1 = min(k / 2, len1);
auto dis2 = k - dis1;
if (nums1[dis1 - 1] < nums2[dis2 - 1]) {
return findKthElement(nums1 + dis1, len1 - dis1, nums2, len2, k - dis1);
} else if (nums1[dis1 - 1] > nums2[dis2 - 1]) {
return findKthElement(nums1, len1, nums2 + dis2, len2 - dis2, k - dis2);
} else {
return nums1[dis1 - 1];
}
return -1;
}
int findKthElement(vector<int>::const_iterator begin_1,
size_t len_1,
vector<int>::const_iterator begin_2,
size_t len_2,
size_t k) {
if (len_1 > len_2) {
return findKthElement(begin_2, len_2, begin_1, len_1, k);
}
if (len_1 == 0) {
return *(begin_2 + k - 1);
}
if (k == 1) {
return std::min(*begin_1, *begin_2);
}
auto dis_1 = std::min(k / 2, len_1);
auto dis_2 = k - dis_1;
if (*(begin_1 + dis_1 - 1) < *(begin_2 + dis_2 - 1)) {
return findKthElement(begin_1 + dis_1, len_1 - dis_1, begin_2, len_2, k - dis_1);
} else if (*(begin_1 + dis_1 - 1) > *(begin_2 + dis_2 - 1)) {
return findKthElement(begin_1, len_1, begin_2 + dis_2, len_2 - dis_2, k - dis_2);
} else {
return *(begin_1 + dis_1 - 1);
}
return -1;
}
};
Java
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
if ((len & 0x01) == 0x01) {
return findKthElement(nums1, 0, nums2, 0, len / 2 + 1);
} else {
double left = findKthElement(nums1, 0, nums2, 0, len / 2);
double right = findKthElement(nums1, 0, nums2, 0, len / 2 + 1);
return (left + right) / 2.0;
}
}
private double findKthElement(int[] nums1, int start1, int[] nums2, int start2, int k) {
if ((nums1.length - start1) > (nums2.length - start2)) {
return findKthElement(nums2, start2, nums1, start1, k);
}
if ((nums1.length - start1) <= 0) {
return (double) nums2[start2 + k - 1];
}
if (k == 1) {
return Math.min((double) nums1[start1], (double) nums2[start2]);
}
int dis1 = Math.min(k / 2, nums1.length - start1);
int dis2 = k - dis1;
if (nums1[start1 + dis1 - 1] < nums2[start2 + dis2 - 1]) {
return findKthElement(nums1, start1 + dis1, nums2, start2, k - dis1);
} else if (nums1[start1 + dis1 - 1] > nums2[start2 + dis2 - 1]) {
return findKthElement(nums1, start1, nums2, start2 + dis2, k - dis2);
} else {
return (double) nums1[start1 + dis1 - 1];
}
}
}
5. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
<p>Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
<p>Example:
Input: "cbbd"
Output: "bb"
Tags String
注意C++的substr和Java的substring的区别
C++
class Solution {
public:
string longestPalindrome(string s) {
int start = 0;
int len = 1;
for (int i = 0; i < s.length(); ++i) {
auto cur = _getLongestPalindromeLength(s, i);
if (cur > len) {
len = cur;
start = i - (len - 1) / 2;
}
}
return s.substr(start, len);
}
private:
inline int _getLongestPalindromeLength(const string &s, int i) {
return max(_getLongestPalindromeLength(s, i, i), _getLongestPalindromeLength(s, i, i + 1));
}
inline int _getLongestPalindromeLength(const string &s, int left, int right) {
while (left >= 0 && right < static_cast<int>(s.length()) && s[left] == s[right]) {
--left;
++right;
}
return right - left - 1;
}
};
Java
public class Solution {
public String longestPalindrome(String s) {
int len = 1;
int start = 0;
for (int i = 0; i < s.length(); ++i) {
int cur = getLongestPalindromeLength(s, i);
if (cur > len) {
len = cur;
start = i - (len - 1) / 2;
}
}
return s.substring(start, start + len);
}
private int getLongestPalindromeLength(String s, int i) {
return Math.max(getLongestPalindromeLength(s, i, i), getLongestPalindromeLength(s, i, i + 1));
}
private int getLongestPalindromeLength(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
--left;
++right;
}
return right - left - 1;
}
}
6. ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
Tags: string
C++
class Solution {
public:
string convert(string s, int numRows) {
if (numRows <= 1 || numRows >= static_cast<int>(s.size())) {
return s;
}
vector<string> ret(numRows, "");
int row_cursor = 0;
int step = 0;
for (size_t idx = 0; idx != s.size(); ++idx) {
ret[row_cursor].push_back(s[idx]);
if (row_cursor == 0) {
step = 1;
} else if (row_cursor == numRows - 1) {
step = -1;
}
row_cursor += step; // update row_cursor
}
string result;
result.reserve(numRows);
for_each(ret.begin(), ret.end(), [&result](string& item) { result += std::move(item); });
return result;
}
};
Java
public class Solution {
public String convert(String s, int numRows) {
if (s.isEmpty() || numRows ==1 || numRows >= s.length()) {
return s;
}
ArrayList<StringBuilder> ret = new ArrayList<>(Collections.nCopies(numRows, null));
int idx = 0;
int step = 0;
for (int i = 0; i < s.length(); ++i) {
if (ret.get(idx) == null) {
ret.set(idx, new StringBuilder());
}
ret.get(idx).append(s.charAt(i));
if (idx == numRows - 1) {
step = -1;
} else if (idx == 0) {
step = 1;
}
idx += step;
}
for (int i = 1; i < ret.size(); ++i) {
ret.get(0).append(ret.get(i));
}
return ret.get(0).toString();
}
}
7. Reverse Integer
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Tags: Math
C++
class Solution {
public:
int reverse(int x) {
int ret = 0;
for ( ; x != 0; x /= 10) {
int tail = x % 10;
int tmp = ret * 10 + tail;
if ((tmp - tail) / 10 != ret) { // overflow
return 0;
}
ret = tmp;
}
return ret;
}
};
class Solution {
public:
int reverse(int x) {
int flag = x < 0 ? -1 : 1;
int ret = 0;
while (x != 0) {
int cur = (x % 10) * flag;
if (ret > INT_MAX / 10 || (ret == INT_MAX / 10 && cur > INT_MAX % 10)) {
return 0;
}
ret = 10 * ret + cur;
x /= 10;
}
return flag * ret;
}
};
Java
public class Solution {
public int reverse(int x) {
int ret = 0;
for ( ; x != 0; x /= 10) {
int tail = x % 10;
int tmp = ret * 10 + tail;
if ((tmp - tail) / 10 != ret) {
return 0;
}
ret = tmp;
}
return ret;
}
}
public class Solution {
public int reverse(int x) {
int ret = 0;
int flag = x < 0 ? -1 : 1;
while (x != 0) {
int cur = (x % 10) * flag;
if (ret > Integer.MAX_VALUE / 10 || (ret == Integer.MAX_VALUE / 10 && cur > Integer.MAX_VALUE % 10)) {
return 0;
}
ret = 10 * ret + cur;
x /= 10;
}
return flag * ret;
}
}
8. String to Integer (atoi)
Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
<p>Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Tags: Math, String
C++
class Solution {
public:
int myAtoi(string str) {
int ret = 0;
auto int_max = std::numeric_limits<int>::max();
auto int_min = std::numeric_limits<int>::min();
auto iter = std::begin(str);
while (*iter == ' ') {
++iter;
}
bool negative = false;
if (*iter == '-' || *iter == '+') {
if(*iter == '-') {
negative = true;
}
++iter;
}
for ( ; iter != std::end(str) && std::isdigit(*iter); ++iter) {
int cur = *iter - '0';
if (ret > int_max / 10 || (ret == int_max / 10 && cur > int_max % 10)) {
return negative ? int_min : int_max;
}
ret = ret * 10 + cur;
}
return negative ? -ret : ret;
}
};
Java
public class Solution {
public int myAtoi(String str) {
int ret = 0;
boolean negative = false;
int idx = 0;
// deal empty string which not the same as C++ and String is iteratable (java Collections)
if (str.isEmpty()) {
return ret;
}
// remove leading space
for ( ; str.charAt(idx) == ' '; ++idx) {}
// get flag
if (str.charAt(idx) == '+' || str.charAt(idx) == '-') {
negative = (str.charAt(idx) == '-' ? true : false);
++idx;
}
// parsing digit chars
for ( ; idx < str.length(); ++idx) {
int cur = str.charAt(idx) - '0';
if (cur < 0 || cur > 9) {
break;
}
if (ret > Integer.MAX_VALUE / 10 || (ret == Integer.MAX_VALUE / 10 && Integer.MAX_VALUE % 10 < cur)) {
return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
}
ret = ret * 10 + cur;
}
return negative ? -ret : ret;
}
}
9. Palindrome Number
Tags: String
Cpp
class Solution {
public:
bool isPalindrome(int x) {
string s1 = std::move(std::to_string(x));
string s2(s1);
reverse(s1.begin(), s1.end());
return s1 == s2;
}
};
Java
public class Solution {
public boolean isPalindrome(int x) {
String a = String.valueOf(x);
String b = (new StringBuilder(a)).reverse().toString();
return a.equals(b);
}
}
10. Regular Expression Matching
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.<p>The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char s, const char p)
<p>Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a") ? true
isMatch("aa", ".") ? true
isMatch("ab", ".") ? true
isMatch("aab", "ca*b") ? true
Tag: String, Dynamic Programming, Backtracking
Use Dynamic Programming
Cpp
class Solution {
public:
bool isMatch(string s, string p) {
// last char is the key postion, which may be '*' or not
// match[i][j] record the s[0 : i - 1] matched p[0 : j - 1] so
// match[0][0] = true, match[1 : ][0] = false, match[0][1 : ] = (j > 1 && match[0][j - 2] && p[j - 1] == '*')
// match[i][j] = p[j - 1] != '*' && (match[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.'))
// match[i][j] = p[j - 1] == '*' && (match[i][j - 2] || (match[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 1] == '.')))
vector<vector<bool>> match(s.length() + 1, vector<bool>(p.length() + 1, false));
match[0][0] = true;
for (size_t i = 1; i < match.size(); ++i) {
match[i][0] = false;
}
for (size_t j = 1; j < match[0].size(); ++j) {
match[0][j] = (j > 1) && match[0][j - 2] && (p[j - 1] == '*');
}
for (size_t i = 1; i < match.size(); ++i) {
for (size_t j = 1; j < match[0].size(); ++j) {
if (p[j - 1] != '*') {
match[i][j] = match[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
} else { // p[j - 1] is '*' so p[j - 2] must exist and match[i - 1][j] covers match[i - 1][j - 2]
match[i][j] = match[i][j - 2] || (match[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
}
}
}
return match.back().back();
}
};
Java
public class Solution {
public boolean isMatch(String s, String p) {
// last char is the key postion, which may be '*' or not
// match[i][j] record the s[0 : i - 1] matched p[0 : j - 1] so
// match[0][0] = true, match[1 : ][0] = false, match[0][1 : ] = (j > 1 && match[0][j - 2] && p[j - 1] == '*')
// match[i][j] = p[j - 1] != '*' && (match[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.'))
// match[i][j] = p[j - 1] == '*' && (match[i][j - 2] || (match[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 1] == '.')))
boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
match[0][0] = true;
for (int i = 1; i < match.length; ++i) {
match[i][0] = false;
}
for (int j = 1; j < match[0].length; ++j) {
match[0][j] = (j > 1) && match[0][j - 2] && p.charAt(j - 1) == '*';
}
for (int i = 1; i < match.length; ++i) {
for (int j = 1; j < match[0].length; ++j) {
if (p.charAt(j - 1) != '*') {
match[i][j] = match[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
} else { // p[j - 1] is '*' so p[j - 2] must exist and match[i - 1][j] covers match[i - 1][j - 2]
match[i][j] = match[i][j - 2] || (match[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
}
}
}
return match[s.length()][p.length()];
}
}
Use Backtracking
class Solution {
public:
bool isMatch(string s, string p) {
return isMatch(s.c_str(), p.c_str());
}
private:
// use c++ string's feature (end with '\0') to avoid some condition check in java
inline bool charMatch(const char *s, const char *p) {
return (*s == *p || (*p == '.' && *s != '\0'));
}
bool isMatch(const char *s, const char *p) {
if (*p == '\0') {
return *s == '\0';
}
if (*(p + 1) != '*') {
return charMatch(s, p) && isMatch(s + 1, p + 1);
} else if (charMatch(s, p)) {
return isMatch(s + 1, p) || isMatch(s, p + 2);
} else {
return isMatch(s, p + 2);
}
}
};
11. Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
Tags: two pointer
Cpp
class Solution {
public:
int maxArea(vector<int>& height) {
int ret = 0;
if (height.size() < 2) {
return ret;
}
size_t left = 0;
size_t right = height.size() - 1;
while (left < right) {
ret = max(ret, min(height[left], height[right]) * static_cast<int>(right - left));
height[left] < height[right] ? ++left : --right;
}
return ret;
}
};
Java
public class Solution {
public int maxArea(int[] height) {
int ret = 0;
if (height.length < 2) {
return ret;
}
int left = 0;
int right = height.length - 1;
while (left < right) {
ret = Math.max(ret, Math.min(height[left], height[right]) * (right - left));
if (height[left] < height[right]) {
++left;
} else {
--right;
}
}
return ret;
}
}
12. Integer to Roman
Cpp
class Solution {
public:
string intToRoman(int num) {
vector<string> symbol{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
vector<int> value{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string ret;
for (int i = 0; num > 0; ++i) {
while (num >= value[i]) {
num -= value[i];
ret += symbol[i];
}
}
return ret;
}
};
Java
public class Solution {
public String intToRoman(int num) {
String ret = "";
ArrayList<String> symbol = new ArrayList(
Arrays.asList("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"));
ArrayList<Integer> value = new ArrayList(
Arrays.asList(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1));
for (int i = 0; num > 0; ++i) {
while (num >= value.get(i)) {
num -= value.get(i);
ret = ret + symbol.get(i);
}
}
return ret;
}
}
13. Roman to Integer
Cpp
class Solution {
public:
int romanToInt(string s) {
int ret = 0;
int pre = 0;
unordered_map<char, int> umap {
make_pair('I', 1), make_pair('V', 5), make_pair('X', 10), \
make_pair('L', 50), make_pair('C', 100), make_pair('D', 500), \
make_pair('M', 1000)};
for (const auto& c : s) {
int cur = umap.at(c);
if (cur <= pre) {
ret += cur;
} else {
ret += cur - 2 * pre; // ret = ret - pre + cur - pre
}
pre = cur;
}
return ret;
}
};
Java
public class Solution {
public int romanToInt(String s) {
HashMap<Character, Integer> hmap = new HashMap<>();
hmap.put('I', 1);
hmap.put('V', 5);
hmap.put('X', 10);
hmap.put('L', 50);
hmap.put('C', 100);
hmap.put('D', 500);
hmap.put('M', 1000);
int ret = 0;
int pre = 0;
for (int i = 0; i < s.length(); ++i) {
int cur = hmap.get(s.charAt(i));
if (cur <= pre) {
ret += cur;
} else {
ret = ret - 2 * pre + cur;
}
pre = cur;
}
return ret;
}
}
14. Longest Common Prefix
Cpp
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() < 1) {
return string("");
}
for (size_t cursor = 0; cursor < strs[0].size(); ++cursor) {
auto cur = strs[0][cursor];
for (size_t i = 1; i < strs.size(); ++i) {
if (cur != strs[i][cursor]) {
return strs[0].substr(0, cursor);
}
}
}
return strs[0];
}
};
Java
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length <= 0) {
return "";
}
for (int cursor = 0; cursor < strs[0].length(); ++cursor) {
char pre = strs[0].charAt(cursor);
for (int i = 1; i < strs.length; ++i) {
if (cursor >= strs[i].length() || strs[i].charAt(cursor) != pre) {
return strs[0].substring(0, cursor);
}
}
}
return strs[0];
}
}
15. 3Sum
Cpp
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
int len = static_cast<int>(nums.size());
std::sort(nums.begin(), nums.end());
for (int i = 0; i < len - 2 && nums[i] <= 0; ++i) {
// remove possible duplicate results
if (i > 0 && nums[i] == nums[i -1 ]) {
continue;
}
int left = i + 1;
int right = len - 1;
while (left < right) {
auto sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
ret.push_back(vector<int>{nums[i], nums[left++], nums[right--]});
// remove possible duplicate results
while (left < right && nums[left] == nums[left - 1]) {
++left;
}
while (left < right && nums[right] == nums[right + 1]) {
--right;
}
} else if (sum > 0) {
--right;
} else {
++left;
}
}
}
return ret;
}
};
Java
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
int len = nums.length;
Arrays.sort(nums);
for (int i = 0; i < len - 2 && nums[i] <= 0; ++i) {
// remove possible duplicate results
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = len - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
ret.add(new ArrayList(Arrays.asList(nums[i], nums[left], nums[right])));
++left;
--right;
// remove possible duplicate results
while (left < right && nums[left] == nums[left - 1]) {
++left;
}
while (left < right && nums[right] == nums[right + 1]) {
--right;
}
} else if (sum > 0) {
--right;
} else {
++left;
}
}
}
return ret;
}
}
16. 3sum closet
Cpp
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int len = nums.size();
assert(len >= 3);
int min_diff = INT_MAX;
std::sort(nums.begin(), nums.end());
for (int i = 0; i < (len - 2); ++i) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = len - 1;
while (left < right) {
int cur_diff = nums[i] + nums[left] + nums[right] - target;
if (cur_diff == 0) {
return target;
} else if (cur_diff > 0) {
right--;
} else {
left++;
}
min_diff = abs(cur_diff) < abs(min_diff) ? cur_diff : min_diff;
}
}
return min_diff + target;
}
};
Java
public class Solution {
public int threeSumClosest(int[] nums, int target) {
int len = nums.length;
int minDiff = Integer.MAX_VALUE;
Arrays.sort(nums);
for (int i = 0; i < len - 2; ++i) {
// avoid duplicate calc
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = len - 1;
while (left < right) {
int curDiff = nums[i] + nums[left] + nums[right] - target;
if (curDiff == 0) {
return target;
} else if (curDiff > 0) {
--right;
} else {
++left;
}
if (Math.abs(curDiff) < Math.abs(minDiff)) {
minDiff = curDiff;
}
}
}
return minDiff + target;
}
}
17. Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Tags: backtracking, string
Cpp
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> ret;
if (digits.empty()) {
return ret;
}
vector<string> keyboard{" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
// return letterCombinationsIterative(digits, keyboard);
letterCombinations(ret, "", 0, digits, keyboard);
return ret;
}
private:
void letterCombinations(vector<string> &ret, const string &cur, size_t idx,
const string &digits, const vector<string> &keyboard) {
if (idx >= digits.size()) {
ret.push_back(cur);
} else {
for (auto c : keyboard[digits[idx] - '0']) {
letterCombinations(ret, cur + c, idx + 1, digits, keyboard);
}
}
}
vector<string> letterCombinationsIterative(const string &digits, const vector<string> &keyboard) {
vector<string> ret{""};
for (auto d : digits) {
vector<string> tmp;
for (auto r : ret) {
for (auto c : keyboard[d - '0']) {
tmp.push_back(r + c);
}
}
ret.swap(tmp);
}
return ret;
}
};
Java
public class Solution {
public List<String> letterCombinations(String digits) {
List<String> ret = new ArrayList<>();
if (digits.isEmpty()) {
return ret;
}
ArrayList<String> keyboard = new ArrayList(
Arrays.asList(" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"));
// return letterCombinationsIterative(digits, keyboard);
letterCombinationsRecursive(ret, "", 0, digits, keyboard);
return ret;
}
private void letterCombinationsRecursive(List<String> ret, String cur, int idx,
String digits, List<String> keyboard) {
if (idx >= digits.length()) {
ret.add(cur);
} else {
String key = keyboard.get(digits.charAt(idx) - '0');
for (int i = 0; i < key.length(); ++i) {
letterCombinationsRecursive(ret, cur + key.charAt(i), idx + 1, digits, keyboard);
}
}
}
private List<String> letterCombinationsIterative(String digits, List<String> keyboard) {
List<String> ret = new ArrayList<>();
ret.add("");
for (int i = 0; i < digits.length(); ++i) {
List<String> tmp = new ArrayList<>();
for (String r : ret) {
int cur = digits.charAt(i) - '0';
for (int j = 0; j < keyboard.get(cur).length(); ++j) {
tmp.add(r + keyboard.get(cur).charAt(j));
}
}
ret = tmp;
}
return ret;
}
}
Scala
object Solution {
def letterCombinations(digits: String): List[String] = {
val ret = List[String]()
val keyboard = Array(" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
digits.isEmpty match {
case true => ret
case false =>
//letterCombinationsIterative(digits, keyboard)
letterCombinationsRecursive(0, digits, keyboard)
}
}
private def letterCombinationsRecursive(start: Int, digits: String, keyboard: Array[String]): List[String] = {
if (start >= digits.size) {
List("")
} else {
val tmp = letterCombinationsRecursive(start + 1, digits, keyboard)
(for {
k <- keyboard(digits(start) - '0')
t <- tmp
} yield (k + t)).toList
}
}
private def letterCombinationsIterative(digits: String, keyboard: Array[String]): List[String] = {
digits.foldLeft(List("")) { (ret, d) => ret.flatMap { r => keyboard(d - '0').map { k => r + k } } }
}
}
18. 4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.<p>For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
Tags: two pointer
Cpp
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ret;
if (nums.size() < 4) {
return ret;
}
sort(nums.begin(), nums.end());
vector<int> cur;
ksum(ret, 0, 4, cur, target, nums);
return ret;
}
private:
void ksum(vector<vector<int>> &ret, int start, int k, vector<int> &cur,
int target, const vector<int> &nums) {
if (k * nums.front() > target || k * nums.back() < target) {
return;
} else if (k == 2) {
int left = start;
int right = nums.size() - 1;
while (left < right) {
auto sum = nums[left] + nums[right] - target;
if (sum == 0) {
auto tmp = cur;
tmp.push_back(nums[left]);
tmp.push_back(nums[right]);
ret.push_back(tmp);
++left;
--right;
// avoid possible duplicates
while (left < right && nums[left] == nums[left - 1]) {
++left;
}
while (left < right && nums[right] == nums[right + 1]) {
--right;
}
} else if (sum > 0) {
--right;
} else {
++left;
}
}
} else {
for (int i = start; i < nums.size() -k + 1; ++i) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
cur.push_back(nums[i]);
ksum(ret, i + 1, k - 1, cur, target - nums[i], nums);
cur.pop_back();
}
}
}
};
Java
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ret = new ArrayList<>();
if (nums.length < 4) {
return ret;
}
Arrays.sort(nums);
List<Integer> cur = new ArrayList<>();
ksum(ret, 0, 4, cur, target, nums);
return ret;
}
private void ksum(List<List<Integer>> ret, int start, int k,
List<Integer> cur, int target, int[] nums) {
if (k * nums[0] > target || k * nums[nums.length - 1] < target) {
return;
} else if (k == 2) {
int left = start;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right] - target;
if (sum == 0) {
List<Integer> tmp = new ArrayList<>(cur);
tmp.add(nums[left]);
tmp.add(nums[right]);
ret.add(tmp);
++left;
--right;
// avoid possible duplicates
while (left < right && nums[left] == nums[left - 1]) {
++left;
}
while (left < right && nums[right] == nums[right + 1]) {
--right;
}
} else if (sum > 0) {
--right;
} else {
++left;
}
}
} else {
for (int i = start; i < nums.length - k + 1; ++i) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
cur.add(nums[i]);
ksum(ret, i + 1, k - 1, cur, target - nums[i], nums);
cur.remove(cur.size() - 1);
}
}
}
}
Scala
object Solution {
def fourSum(nums: Array[Int], target: Int): List[List[Int]] = {
var ret: List[List[Int]] = List()
if (nums.size < 4) return ret
val sortedNums = nums.sorted
var cur: List[Int] = List()
def ksum(start: Int, k: Int, target: Int): Unit = {
if (k == 2) {
var left = start;
var right = sortedNums.size - 1
while (left < right) {
var sum = sortedNums(left) + sortedNums(right) - target
if (sum == 0) {
var tmp = cur ::: List(sortedNums(left), sortedNums(right))
ret = ret ::: List(tmp)
left += 1
right -= 1
while (left < right && sortedNums(left) == sortedNums(left - 1)) left += 1
while (left < right && sortedNums(right) == sortedNums(right + 1)) right -= 1
} else if (sum > 0) {
right -= 1
} else left += 1
}
} else {
for (i <- start until sortedNums.length - k + 1) {
if (i == start || sortedNums(i) != sortedNums(i - 1)) {
var tmp = cur
cur = cur ::: List(sortedNums(i))
ksum(i + 1, k - 1, target - sortedNums(i))
cur = tmp
}
}
}
}
ksum(0, 4, target)
ret
}
}
19. Remove Nth Node From End of List
Tags: List
Cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy = ListNode(0);
dummy.next = head;
ListNode *first = &dummy;
for (int i = 0; i < n; ++i) {
if (first == nullptr) {
return nullptr;
} else {
first = first->next;
}
}
ListNode *pre = &dummy;
for (; first != nullptr && first->next != nullptr; first = first->next) {
pre = pre->next;
}
auto tmp = pre->next->next;
delete pre->next;
pre->next = tmp;
return dummy.next;
}
};
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
for (int i = 0; i < n; ++i) {
if (first == null) {
return null;
} else {
first = first.next;
}
}
ListNode ptr = dummy;
for (; first != null && first.next != null; first = first.next) {
ptr = ptr.next;
}
ListNode tmp = ptr.next.next;
ptr.next = null;
ptr.next = tmp;
return dummy.next;
}
}
20. Valid Parentheses
Tags: Stack
Cpp
class Solution {
public:
bool isValid(string s) {
stack<char> stc;
for (auto c : s) {
if (isLeft(c)) {
stc.push(c);
} else if (stc.empty()) {
return false;
} else if (isMatch(stc.top(), c)) {
stc.pop();
} else {
return false;
}
}
return stc.empty();
}
private:
bool isLeft(char c) {
return (c == '(' || c == '{' || c == '[');
}
bool isMatch(char l, char r) {
if (l == '(') {
return r == ')';
} else if (l == '{') {
return r == '}';
} else if (l == '[') {
return r == ']';
} else {
return false;
}
}
};
Java
public class Solution {
public boolean isValid(String s) {
Stack<Character> stc = new Stack<>();
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (isLeft(c)) {
stc.push(c);
} else if (stc.empty()) {
return false;
} else if (isMatch(stc.peek(), c)) {
stc.pop();
} else {
return false;
}
}
return stc.empty();
}
private boolean isLeft(char c) {
return (c == '(' || c == '{' || c == '[');
}
private boolean isMatch(char l, char r) {
if (l == '(') {
return r == ')';
} else if (l == '{') {
return r == '}';
} else if (l == '[') {
return r == ']';
} else {
return false;
}
}
};
Scala
object Solution {
def isValid(s: String): Boolean = {
val parenthesesMap = Map('(' -> ')', '{' -> '}', '[' -> ']')
val ret = s.foldLeft(List[Char]()) { (stc, c) =>
c match {
case '(' | '{' | '[' => c :: stc
case ')' | '}' | ']' =>
if (stc.isEmpty) return false
else if (parenthesesMap.get(stc.head) != Some(c)) return false
else stc.tail
}
}
ret.isEmpty
}
}
21. Merge Two Sorted Lists
Cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
} else if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
Scala
/**
* Definition for singly-linked list.
* class ListNode(var _x: Int = 0) {
* var next: ListNode = null
* var x: Int = _x
* }
*/
object Solution {
def mergeTwoLists(l1: ListNode, l2: ListNode): ListNode = {
(l1, l2) match {
case (null, _) => l2
case (_, null) => l1
case _ => (l1.x < l2.x) match {
case true =>
l1.next = mergeTwoLists(l1.next, l2)
l1
case false =>
l2.next = mergeTwoLists(l1, l2.next)
l2
}
}
}
}
22. Generate Parentheses
Cpp
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ret;
generateParenthesis(ret, "", n, n);
return ret;
}
private:
void generateParenthesis(vector<string> &ret, string cur, int curLeftNum, int curRightNum) {
if (curLeftNum == 0 && curRightNum == 0) {
ret.push_back(cur);
}
if (curLeftNum > 0) {
generateParenthesis(ret, cur + '(', curLeftNum - 1, curRightNum);
}
if (curRightNum > curLeftNum) {
generateParenthesis(ret, cur + ')', curLeftNum, curRightNum - 1);
}
}
};
Java
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> ret = new ArrayList<>();
generateParenthesis(ret, "", n, n);
return ret;
}
private void generateParenthesis(List<String> ret, String cur, int curLeftNum, int curRightNum) {
if (curLeftNum == 0 && curRightNum == 0) {
ret.add(cur);
}
if (curLeftNum > 0) {
generateParenthesis(ret, cur + "(", curLeftNum - 1, curRightNum);
}
if (curRightNum > curLeftNum) {
generateParenthesis(ret, cur + ")", curLeftNum, curRightNum - 1);
}
}
}
Scala
object Solution {
def generateParenthesis(n: Int): List[String] = {
generateInternal(List[String](), "", n, n)
}
private def generateInternal(ret: List[String], cur: String, curLeftNum: Int, curRightNum: Int): List[String] = {
if (curLeftNum == 0 && curRightNum == 0) {
ret ::: List(cur)
} else {
val ret1 = {
if (curLeftNum > 0)
generateInternal(ret, cur + "(", curLeftNum - 1, curRightNum)
else
ret
}
val ret2 = {
if (curRightNum > curLeftNum)
generateInternal(ret1, cur + ")", curLeftNum, curRightNum - 1)
else
ret1
}
ret2
}
}
}
23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Tags: Linked List, Divide and Conquer, Heap
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) {
return nullptr;
}
for (int sz = static_cast<int>(lists.size()); sz > 1; ) {
int offset = (sz + 1) / 2;
for (int i = 0; i < sz / 2; ++i) {
lists[i] = mergeTwoLists(lists[i], lists[i + offset]);
}
sz = offset;
}
return lists.front();
}
private:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
} else if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
for (int sz = lists.length; sz > 1; ) {
int offset = (sz + 1) / 2;
for (int i = 0; i < sz / 2; ++i) {
lists[i] = mergeTwoLists(lists[i], lists[i + offset]);
}
sz = offset;
}
return lists[0];
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
Tags: LinkedList
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode dummy(1);
dummy.next = head;
auto pre = &dummy;
for (auto cur = head; cur != nullptr && cur->next != nullptr; cur = cur->next) {
auto tmp = cur->next;
cur->next = tmp->next;
tmp->next = cur;
pre->next = tmp;
pre = cur;
}
return dummy.next;
}
};
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(1);
dummy.next = head;
ListNode pre = dummy;
for (ListNode cur = head; cur != null && cur.next != null; cur = cur.next) {
ListNode tmp = cur.next;
cur.next = tmp.next;
tmp.next = cur;
pre.next = tmp;
pre = cur;
}
return dummy.next;
}
}
25. Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Tags: Array, HashTable
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy = ListNode(0);
dummy.next = head;
auto pre = &dummy;
auto ptr = &dummy;
for (int i = 0; i < k && ptr != nullptr; ++i) {
ptr = ptr->next;
}
while (ptr != nullptr) {
auto nextDummy = pre->next;
for (int i = 1; i < k; ++i) {
auto tmp = pre->next->next;
pre->next->next = ptr->next;
ptr->next = pre->next;
pre->next = tmp;
}
pre = nextDummy;
ptr = nextDummy;
for (int i = 0; i < k && ptr != nullptr; ++i) {
ptr = ptr->next;
}
}
return dummy.next;
}
};
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode ptr = dummy;
for (int i = 0; i < k && ptr != null; ++i) {
ptr = ptr.next;
}
while (ptr != null) {
ListNode nextDummy = pre.next;
for (int i = 1; i < k; ++i) {
ListNode tmp = pre.next.next;
pre.next.next = ptr.next;
ptr.next = pre.next;
pre.next = tmp;
}
pre = nextDummy;
ptr = nextDummy;
for (int i = 0; i < k && ptr != null; ++i) {
ptr = ptr.next;
}
}
return dummy.next;
}
}
26. Remove Duplicates from Sorted Array
Cpp
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int pre = -1;
for (int cur = 0; cur < static_cast<int>(nums.size()); ++cur) {
if (pre == -1) {
++pre;
} else if (nums[cur] != nums[cur - 1]) {
nums[++pre] = nums[cur];
}
}
return pre + 1;
}
};
Java
public class Solution {
public int removeDuplicates(int[] nums) {
int pre = -1;
for (int cur = 0; cur < nums.length; ++cur) {
if (pre == -1) {
++pre;
} else if (nums[cur] != nums[cur - 1]) {
nums[++pre] = nums[cur];
}
}
return pre + 1;
}
}
Scala
object Solution {
def removeDuplicates(nums: Array[Int]): Int = {
var pre = -1
for (cur <- 0 until nums.length) {
if (pre == -1) {
pre += 1
} else if (nums(cur) != nums(cur - 1)) {
pre += 1
nums(pre) = nums(cur)
}
}
return pre + 1
}
}
27. Remove Element
C++
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int ret = 0;
for (auto n : nums) {
if (n != val) {
nums[ret++] = n;
}
}
return ret;
}
};
Java
class Solution {
public int removeElement(int[] nums, int val) {
int ret = 0;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] != val) {
nums[ret++] = nums[i];
}
}
return ret;
}
}
Scala
object Solution {
def removeElement(nums: Array[Int], v: Int): Int = {
var ret = 0
for (i <- 0 until nums.size) {
if (nums(i) != v) {
nums(ret) = nums(i)
ret += 1
}
}
return ret
}
}
28. Implement strStr
Tags: Two Pointers, String
C++
class Solution {
public:
int strStr(string haystack, string needle) {
int ret1 = strStrBackoff(haystack, needle);
int ret2 = strStrBruteForce(haystack, needle);
int ret3 = strStrKMP(haystack, needle);
cout << ret1 << " " << ret2 << " " << ret3 << endl;
assert(ret1 == ret2 && ret2 == ret3);
return ret1;
}
private:
int strStrBruteForce(const string &source, const string &target) {
int src_len = static_cast<int>(source.size());
int tgt_len = static_cast<int>(target.size());
for (int i = 0; i <= src_len - tgt_len; ++i) {
int j = 0;
for ( ; j < tgt_len && source[i + j] == target[j]; ++j) {}
if (j == tgt_len) {
return i;
}
}
return -1;
}
int strStrBackoff(const string &source, const string &target) {
int src_len = static_cast<int>(source.size());
int tgt_len = static_cast<int>(target.size());
int i = 0;
int j = 0;
for ( ; i < src_len && j < tgt_len; ++i) {
if (source[i] == target[j]) {
++j;
} else {
i -= j;
j = 0;
}
}
if (j == tgt_len) {
return i - tgt_len;
}
return -1;
}
int strStrKMP(string source, string target) {
if (target.empty()) {
return 0;
}
auto getPattern = [](const string& str) {
vector<int> pattern(str.length(), 0);
int k = 0;
for (size_t i = 1; i < str.length(); ++i) {
while (k > 0 && str[k] != str[i]) {
k = pattern[k - 1];
}
if (str[k] == str[i]) {
++k;
}
pattern[i] = k;
}
return pattern;
};
auto pattern = getPattern(target);
int k = 0;
for (size_t i = 0; i < source.length(); ++i) {
while (k > 0 && source[i] != target[k]) {
k = pattern[k - 1];
}
if (source[i] == target[k]) {
++k;
}
if (k == target.length()) {
return i - k + 1;
}
}
return -1;
}
};
Java
class Solution {
public int strStr(String haystack, String needle) {
int ret1 = strStrBruteForce(haystack, needle);
int ret2 = strKMP(haystack, needle);
int ret3 = strStrBackoff(haystack, needle);
System.out.println("ret1 = " + ret1 + " ret2 = " + ret2 + " ret3 = " + ret3);
assert ret1 == ret2;
assert ret2 == ret3;
return ret2;
}
private int strStrBackoff(String source, String target) {
int i = 0;
int j = 0;
for ( ; i < source.length() && j < target.length(); ) {
if (source.charAt(i) == target.charAt(j)) {
++j;
} else {
i -= j;
j = 0;
}
++i;
}
if (j == target.length()) {
return i - j;
}
return -1;
}
private int strStrBruteForce(String source, String target) {
for (int i = 0; i <= source.length() - target.length(); ++i) {
int j = 0;
for ( ; j < target.length() && source.charAt(i + j) == target.charAt(j); ++j) {}
if (j == target.length()) {
return i;
}
}
return -1;
}
private List<Integer> kmpPattern(String target) {
List<Integer> pattern = new ArrayList<>(Collections.nCopies(target.length(), 0));
int k = 0;
for (int i = 1; i < target.length(); ++i) {
while (k > 0 && target.charAt(k) != target.charAt(i)) {
k = pattern.get(k - 1);
}
if (target.charAt(k) == target.charAt(i)) {
++k;
}
pattern.set(i, k);
}
return pattern;
}
private int strKMP(String source, String target) {
if (target.isEmpty()) {
return 0;
}
List<Integer> pattern = kmpPattern(target);
int k = 0;
for (int i = 0; i < source.length(); ++i) {
while (k > 0 && source.charAt(i) != target.charAt(k)) {
k = pattern.get(k - 1);
}
if (source.charAt(i) == target.charAt(k)) {
++k;
}
if (k == target.length()) {
return i - k + 1;
}
}
return -1;
}
}
33. Search in Rotated Sorted Array
Tags: Binary Search
Cpp
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = static_cast<int>(nums.size()) - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] >= nums[left]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
};
Java
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] >= nums[left]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
}
34. Search for a Range
Cpp
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ret{-1, -1};
ret[0] = findLowerBound(nums, target);
ret[1] = findUpperBound(nums, target);
return ret;
}
private:
int findLowerBound(const vector<int>& nums, int target) {
int left = 0;
int right = static_cast<int>(nums.size()) - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
// move left to get first greater or equal than target
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return nums[left] == target ? left : -1;
}
int findUpperBound(const vector<int>& nums, int target) {
int left = 0;
int right = static_cast<int>(nums.size()) - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
// move right to get first less or equal than target
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return nums[right] == target ? right : -1;
}
};
Java
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = {-1, -1};
ret[0] = lowerBound(nums, target);
ret[1] = upperBound(nums, target);
return ret;
}
private int lowerBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (nums[left] == target) {
return left;
} else {
return -1;
}
}
private int upperBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
if (nums[right] == target) {
return right;
} else {
return -1;
}
}
}
46. Permutations
Tags: Backtracking
C++
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ret;
permute(ret, nums, 0);
return ret;
}
private:
void permute(vector<vector<int>>& ret, vector<int>& nums, int start) {
if (start == nums.size()) {
ret.push_back(nums);
} else {
for (size_t i = start; i != nums.size(); ++i) {
swap(nums[start], nums[i]);
permute(ret, nums, start + 1);
swap(nums[start], nums[i]);
}
}
}
};
Java
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
List<Integer> numList = Arrays.stream(nums).boxed().collect(Collectors.toList());
permute(ret, numList, 0);
return ret;
}
private void permute(List<List<Integer>> ret, List<Integer> nums, int start) {
if (start >= nums.size()) {
ret.add(new ArrayList(nums));
} else {
for (int i = start; i < nums.size(); ++i) {
Collections.swap(nums, start, i);
permute(ret, nums, start + 1);
Collections.swap(nums, start, i);
}
}
}
}
47. Permutations II
Tags: Backtracking
C++
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ret;
permutation(ret, nums, 0);
return ret;
}
private:
void permutation(vector<vector<int>>& ret, vector<int>& nums, size_t start) {
if (start >= nums.size()) {
ret.push_back(nums);
} else {
for (size_t idx = start; idx != nums.size(); ++idx) {
if (std::find(nums.begin() + start, nums.begin() + idx, nums[idx]) == (nums.begin() + idx)) {
swap(nums[idx], nums[start]);
permutation(ret, nums, start + 1);
swap(nums[idx], nums[start]);
}
}
}
}
};
Java
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
List<Integer> numList = Arrays.stream(nums).boxed().collect(Collectors.toList());
permute(ret, numList, 0);
return ret;
}
private void permute(List<List<Integer>> ret, List<Integer> nums, int start) {
if (start >= nums.size()) {
ret.add(new ArrayList(nums));
} else {
for (int i = start; i < nums.size(); ++i) {
int idx = start;
for ( ; idx < i; ++idx) {
if (nums.get(idx) == nums.get(i)) {
break;
}
}
if (idx < i) {
continue;
}
Collections.swap(nums, start, i);
permute(ret, nums, start + 1);
Collections.swap(nums, start, i);
}
}
}
}
94. Binary Tree Inorder Traversal
Tags: Tree
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
// return inorderTraversalIterative(root);
return inorderTraversalMorris(root);
}
private:
vector<int> inorderTraversalMorris(TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
auto cur = root;
while (cur != nullptr) {
if (cur->left == nullptr) {
ret.push_back(cur->val);
cur = cur->right;
} else {
auto pre = cur->left;
while (pre->right != nullptr && pre->right != cur) {
pre = pre->right;
}
if (pre->right == nullptr) {
pre->right = cur;
cur = cur->left;
} else {
ret.push_back(cur->val); // move to if would make this preorderTraversal
pre->right = nullptr;
cur = cur->right;
}
}
}
return ret;
}
vector<int> inorderTraversalIterative(const TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
stack<const TreeNode*> stc;
auto ptr = root;
while (ptr != nullptr || !stc.empty()) {
if (ptr == nullptr) {
ptr = stc.top();
stc.pop();
ret.push_back(ptr->val);
ptr = ptr->right;
} else {
stc.push(ptr);
ptr = ptr->left;
}
}
return ret;
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) {
return ret;
}
TreeNode cursor = root;
Stack<TreeNode> stc = new Stack<>();
while (cursor != null || !stc.empty()) {
if (cursor == null) {
cursor = stc.peek();
stc.pop();
ret.add(cursor.val);
cursor = cursor.right;
} else {
stc.push(cursor);
cursor = cursor.left;
}
}
return ret;
}
}
103. Binary Tree Zigzag Level Order Traversal
Tags: Tree, BFS
C++
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ret;
if (root == nullptr) {
return ret;
}
vector<TreeNode*> curLevel{root};
bool flag = false;
while (!curLevel.empty()) {
vector<TreeNode*> nextLevel;
vector<int> cur;
cur.reserve(curLevel.size());
if (flag) {
for (auto itr = curLevel.rbegin(); itr != curLevel.rend(); ++itr) {
cur.push_back((*itr)->val);
}
} else {
for (auto itr = curLevel.begin();itr != curLevel.end(); ++itr) {
cur.push_back((*itr)->val);
}
}
for (auto node : curLevel) {
if (node->left != nullptr) {
nextLevel.push_back(node->left);
}
if (node->right != nullptr) {
nextLevel.push_back(node->right);
}
}
flag = !flag;
std::swap(curLevel, nextLevel);
ret.push_back(std::move(cur));
}
return ret;
}
};
Java
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if (root == null) {
return ret;
}
List<TreeNode> curLevel = new ArrayList<>();
boolean flag = false;
curLevel.add(root);
while (!curLevel.isEmpty()) {
List<TreeNode> nextLevel = new ArrayList<>();
List<Integer> cur = new ArrayList<>();
if (flag) {
for (int i = curLevel.size() - 1; i >= 0; --i) {
cur.add(curLevel.get(i).val);
}
} else {
for (TreeNode n : curLevel) {
cur.add(n.val);
}
}
for (TreeNode node : curLevel) {
if (node.left != null) {
nextLevel.add(node.left);
}
if (node.right != null) {
nextLevel.add(node.right);
}
}
ret.add(new ArrayList<>(cur));
flag = !flag;
curLevel = nextLevel;
nextLevel = null;
}
return ret;
}
}
112. Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/
4 8
/ /
11 13 4
/ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
Tags: Tree, Backtracking
C++
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == nullptr) {
return false;
}
sum -= root->val;
if (isLeaf(root)) {
return sum == 0;
} else {
return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
}
}
private:
inline bool isLeaf(const TreeNode* root) {
return root != nullptr && root->left == nullptr && root->right == nullptr;
}
};
Java
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (isLeaf(root)) {
return sum == root.val;
} else {
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
private boolean isLeaf(TreeNode node) {
return node.left == null && node.right == null;
}
}
113. Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/
4 8
/ /
11 13 4
/ \ /
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
Tags: Tree, Backtracking
C++
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> ret;
vector<int> path;
pathSum(root, sum ,ret, path);
return ret;
}
private:
void pathSum(const TreeNode* root, int sum, vector<vector<int>>& ret, vector<int>& path) {
if (root == nullptr) {
return;
}
path.push_back(root->val);
sum -= root->val;
if (isLeaf(root) && sum == 0) {
ret.push_back(path);
} else {
pathSum(root->left, sum, ret, path);
pathSum(root->right, sum, ret, path);
}
path.pop_back();
}
inline bool isLeaf(const TreeNode* root) {
return root != nullptr && root->left == nullptr && root->right == nullptr;
}
};
Java
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> ret = new LinkedList<>();
LinkedList<Integer> cur = new LinkedList<>();
pathSum(ret, cur, root, sum);
return ret;
}
private void pathSum(List<List<Integer>> ret, LinkedList<Integer> cur, TreeNode root, int sum) {
if (root == null) {
return;
}
sum -= root.val;
cur.add(root.val);
if (isLeaf(root) && sum == 0) {
ret.add(new LinkedList<>(cur));
} else {
pathSum(ret, cur, root.left, sum);
pathSum(ret, cur, root.right, sum);
}
cur.removeLast();
}
private boolean isLeaf(TreeNode root) {
return root != null && root.left == null && root.right == null;
}
}
121. Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Tags: Dynamic Programming
C++
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) {
return 0;
}
int ret = 0;
int last_min = prices[0];
for (size_t i = 1; i < prices.size(); ++i) {
ret = std::max(prices[i] - last_min, ret);
last_min = std::min(prices[i], last_min);
}
return ret;
}
};
Java
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 0) {
return 0;
}
int ret = 0;
int curMin = prices[0];
for (int i = 1; i < prices.length; ++i) {
ret = Math.max(ret, prices[i] - curMin);
curMin = Math.min(prices[i], curMin);
}
return ret;
}
}
122. Best Time to Buy and Sell Stock II
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Tags: Greedy
C++
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ret = 0;
for (size_t i = 1; i < prices.size(); ++i) {
auto tmp = prices[i] - prices[i - 1];
ret += (tmp > 0 ? tmp : 0);
}
return ret;
}
};
Java
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 0) {
return 0;
}
int ret = 0;
for (int i = 1; i < prices.length; ++i) {
ret += Math.max(prices[i] - prices[i - 1], 0);
}
return ret;
}
}
144. Binary Tree Preorder Traversal
Tags: Tree
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
//return preorderTraversalIterative(root);
return preorderTraversalMorris(root);
}
private:
vector<int> preorderTraversalMorris(TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
// swap left and right and ret make it postorderTraversal
auto cur = root;
while (cur != nullptr) {
if (cur->left == nullptr) {
ret.push_back(cur->val);
cur = cur->right;
} else {
auto pre = cur->left;
while (pre->right != nullptr && pre->right != cur) {
pre = pre->right;
}
if (pre->right == nullptr) {
ret.push_back(cur->val); // move it to else make this inorderTraversa;
pre->right = cur;
cur = cur->left;
} else {
pre->right = nullptr;
cur = cur->right;
}
}
}
return ret;
}
vector<int> preorderTraversalIterative(const TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
stack<const TreeNode*> stc;
auto ptr = root;
while (ptr != nullptr || !stc.empty()) {
if (ptr == nullptr) {
ptr = stc.top();
stc.pop();
}
ret.push_back(ptr->val);
if (ptr->right != nullptr) {
stc.push(ptr->right);
}
ptr = ptr->left;
}
return ret;
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) {
return ret;
}
TreeNode cursor = root;
Stack<TreeNode> stc = new Stack<>();
while (cursor != null || !stc.empty()) {
if (cursor == null) {
cursor = stc.peek();
stc.pop();
}
ret.add(cursor.val);
if (cursor.right != null) {
stc.push(cursor.right);
}
cursor = cursor.left;
}
return ret;
}
}
145. Binary Tree Postorder Traversal
Tags: Tree
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
//return postorderTraversalIterative(root);
return postorderTraversalMorris(root);
}
private:
vector<int> postorderTraversalMorris(TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
// swap preorder's left and right and reverse ret makes this postorderTraversal
auto cur = root;
while (cur != nullptr) {
if (cur->right == nullptr) {
ret.push_back(cur->val);
cur = cur->left;
} else {
auto pre = cur->right;
while (pre->left != nullptr && pre->left != cur) {
pre = pre->left;
}
if (pre->left == nullptr) {
ret.push_back(cur->val);
pre->left = cur;
cur = cur->right;
} else {
pre->left = nullptr;
cur = cur->left;
}
}
}
reverse(ret.begin(), ret.end());
return ret;
}
vector<int> postorderTraversalIterative(const TreeNode* root) {
vector<int> ret;
if (root == nullptr) {
return ret;
}
// swap preorder's left and right and reverse ret makes this postorderTraversal
stack<const TreeNode*> stc;
auto ptr = root;
while (ptr != nullptr || !stc.empty()) {
if (ptr == nullptr) {
ptr = stc.top();
stc.pop();
}
ret.push_back(ptr->val);
if (ptr->left != nullptr) {
stc.push(ptr->left);
}
ptr = ptr->right;
}
reverse(ret.begin(), ret.end());
return ret;
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) {
return ret;
}
// swap preorder's left and right and reverse ret makes this postorderTraversal
TreeNode cursor = root;
Stack<TreeNode> stc = new Stack<>();
while (cursor != null || !stc.empty()) {
if (cursor == null) {
cursor = stc.peek();
stc.pop();
}
ret.add(cursor.val);
if (cursor.left != null) {
stc.push(cursor.left);
}
cursor = cursor.right;
}
Collections.reverse(ret);
return ret;
}
}
173. Binary Search Tree Iterator
mplement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
Tags: Tree
C++
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
for ( ; root != nullptr; root = root->left) {
stc.push(root);
}
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !stc.empty();
}
/** @return the next smallest number */
int next() {
auto ret = stc.top()->val;
auto ptr = stc.top()->right;
stc.pop();
for ( ; ptr != nullptr; ptr = ptr->left) {
stc.push(ptr);
}
return ret;
}
private:
stack<TreeNode*> stc;
};
Java
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
public BSTIterator(TreeNode root) {
for ( ; root != null; root = root.left) {
stc.push(root);
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stc.empty();
}
/** @return the next smallest number */
public int next() {
int ret = stc.peek().val;
TreeNode cursor = stc.peek().right;
stc.pop();
for ( ; cursor != null; cursor = cursor.left) {
stc.push(cursor);
}
return ret;
}
private Stack<TreeNode> stc = new Stack<>();
}
236. Lowest Common Ancestor of a Binary Tree
Tags: Tree
C++
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) {
return root;
}
// find lca node or at least one of (p, q) in left and right subtree
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
// if both left and right are not null (p, q) must exist in left and right that root
// is the lca; if left or right is null, lca is in another subtree (right or left).
if (left == nullptr) {
return right;
} else if (right == nullptr) {
return left;
} else {
return root;
}
}
};
Java
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
// find lca node or at least one of (p, q) in left and right subtree
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// if both left and right are not null (p, q) must exist in left and right that root
// is the lca; if left or right is null, lca is in another subtree (right or left).
if (left == null) {
return right;
} else if (right == null) {
return left;
} else {
return root;
}
}
}
