LeetCode (used to call i has 1337 code) is a social platform for preparing IT technical interviews. We strive to provide you with the best learning experience in preparing interviews for companies in the IT industry.
To be successful in a technical interview, we believe it is mainly repeating these three important steps:
Code. Read. Discuss.
We strive to provide you the LeetCode platform as the ultimate solution for preparing technical interviews.
1. Code -> Code solution using the Online Judge system.
2. Read -> Read high quality article featuring in-depth thought process. Also read other LeetCoders’ code.
3. Discuss -> Discuss your thoughts about the problem with other LeetCoders.
We hope that through our platform, you will grow into a LeetCoder. Not only will you be successful in all of your interviews, and most importantly, you will be a better coder in general !
算法問題: Same Tree 問題描述:
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
算法問題: Scramble String 問題描述:
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
1. 3-dimensional dp. Contributed by yinlinglin. I really appreciate it!
'dp[k][i][j] == true' means string s1(start from i, length k) is a scrambled string of
string s2(start from j, length k).
2. Recursion + pruning.
bool isScrambleRe(Iterator s1, Iterator s2, int len) {
if (!hasSameLetters(s1, s2, len)) return false;
if (len == 0 || len == 1) return true;
for (int i = 1; i < len; ++i) // highlight
if (isScrambleRe(s1, s2, i) && isScrambleRe(s1 + i, s2 + i, len - i) ||
isScrambleRe(s1, s2 + len - i, i) && isScrambleRe(s1 + i, s2, len - i))
return true;
return false;
}
bool hasSameLetters(Iterator s1, Iterator s2, int len) {
int count[256] = {0};
for (int i = 0; i < len; ++i) count[*s1++]++;
for (int i = 0; i < len; ++i) count[*s2++]--;
for (int i = 0; i < 256; ++i)
if (count[i] != 0) return false;
return true;
}
};
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
return searchMatrix_2(matrix, target);
}
// Solution 1.
bool searchMatrix_1(vector<vector<int> > &matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int N = matrix.size(), M = matrix[0].size();
int i = 0, j = N-1;
while (i <= j)
{
int mid = (i + j) / 2;
if (matrix[mid][0] == target) return true;
else if (matrix[mid][0] < target) i++;
else j--;
}
int row = j;
if (row < 0) return false;
i = 0, j = M - 1;
while (i <= j)
{
int mid = (i + j) / 2;
if (matrix[row][mid] == target) return true;
else if (matrix[row][mid] < target) i++;
else j--;
}
return false;
}
// Solution 2.
bool searchMatrix_2(vector<vector<int> > &matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int N = matrix.size(), M = matrix[0].size();
int i = 0, j = M * N - 1;
while (i <= j)
{
int mid = (i + j) / 2;
int row = mid / M, col = mid % M;
if (matrix[row][col] == target) return true;
else if (matrix[row][col] < target) i = mid + 1;
else j = mid - 1;
}
return false;
}
};
It takes O(lgN) to find both the lower-bound and upper-bound.
代碼:
class Solution {
public:
vector<int> searchRange(int A[], int n, int target) {
vector<int> res(2, -1);
int lower = getLowerBound(A, n, target);
int upper = getUpperBound(A, n, target);
if (lower <= upper)
{
res[0] = lower;
res[1] = upper;
}
return res;
}
int getLowerBound(int A[], int n, int target)
{
int l = 0, u = n-1;
while (l <= u)
{
int mid = (l + u) / 2;
if (A[mid] < target)
l = mid + 1;
else
u = mid - 1;
}
return l;
}
int getUpperBound(int A[], int n, int target)
{
int l = 0, u = n-1;
while (l <= u)
{
int mid = (l + u) / 2;
if (A[mid] <= target)
l = mid + 1;
else
u = mid - 1;
}
return u;
}
};
算法問題: Search in Rotated Sorted Array 問題描述:
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
論壇通告:
個人空間:
論壇轉跳:
贊 
花籃 
投訴
踩 
分享
