中正的网络日志
https://oj.leetcode.com/problems/reverse-integer/
循环求解即可。
class Solution
{
public:
int reverse(int x)
{
bool minus = false;
int res = 0;
if (x < 0)
{
x = -x;
minus = true;
}
while (x != 0)
{
int t;
t = x % 10;
x = x / 10;
res = res * 10 + t;
}
if (minus)
res = -res;
return res;
}
};
本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39157653
https://oj.leetcode.com/problems/median-of-two-sorted-arrays/
如果这道题的时间复杂度要求是O(m+n)的话， 就很简单了， 直接merge之后找出中位数即可。
如果时间复杂度要求为O(log(m+n))的话， 可以把这道题转化为求第k小的问题。
如果(m+n)是奇数的话， 中位数就是第（m+n）/2+1小； 如果(m+n)是偶数， 中位数就是第(m+n)/2小和第(m+n)/2+1小的平均数。
然后问题是如何求解第k小的数？
假设有两个数组：
A[0], A[1], ......A[m-1]
B[0], B[1], ......B[n-1]
两数组合并后为
C[0], C[1], ...... C[m+n-1]
不妨假设m和n都大于k/2, 比较A[k/2-1]和B[k/2-1]，
如果A[k/2-1] < B[k/2-1]， 那么A[k/2-1]及其左侧的元素一定小于合并后的第k小的那个数（即C[k-1]）
为什么？
可以通过反证来证明，
假设A[k/2-1]等于合并后第k小元素 (即C[k-1]),
那么实际最多有多少个元素比A[k/2-1]小呢？ A[0], A[1]......A[k/2-2]以及B[0], B[1].......B[k/2-2]， 共k-2个元素。 也就是说A[k/2-1]最好情况下是第k-1小元素(即C[k-2])
这与假设矛盾， 因此假设不成立
因此可以说， A[k/2-1]及其左侧元素一定小于合并后的第k小那个数， 这样就可以排除掉这一范围的数，从而缩小了问题规模。
当A为空或者B为空时， 返回B[k-1]或A[k-1]
当k == 1时， 返回A[0]和B[0]中较小的那个数
当A[k/2-1] == B[k/2-1]时， 返回A[k/2-1]
否则的话， 就递归缩小问题规模。
class Solution
{
public:
double findMedianSortedArrays(int A[], int m, int B[], int n)
{
if ((m + n) & 0x01)
return findKth(A, m, B, n, (m + n) / 2 + 1);
else
return (findKth(A, m, B, n, (m + n) / 2)
+ findKth(A, m, B, n, (m + n) / 2 + 1)) / 2;
}
double findKth(int A[], int m, int B[], int n, int k)
{
if (m > n)
return findKth(B, n, A, m, k);
else if (m == 0)
return B[k-1];
else if (k == 1)
return min(A[0], B[0]);
else
{
int ALeftCount = min(k / 2, m);
int BLeftCount = k - ALeftCount;
if (A[ALeftCount-1] == B[BLeftCount-1])
return A[ALeftCount-1];
else if (A[ALeftCount-1] < B[BLeftCount-1])
return findKth(A+ALeftCount, m-ALeftCount,
B, n, k-ALeftCount);
else//A[ALeftCount-1] > B[BLeftCount-1]]
return findKth(A, m,
B+BLeftCount, n-BLeftCount, k-BLeftCount);
}
}
};
http://blog.csdn.net/yutianzuijin/article/details/11499917
本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39156991
https://oj.leetcode.com/problems/reverse-words-in-a-string/
运用栈来解题， 先把s中的一个个单词解析出来压到栈里， 然后再出栈重组成s
有一些特殊的边界需要考虑， 比如连续出现两个空格， 单词的头尾部出现空格等等， 这些情况需要特殊处理一下。
从后向前进行循环
处理空格部分
如果结果res非空， 插入一个空格
处理非空格部分
class Solution
{
public:
void reverseWords(string &s)
{
if (s.empty())
return;
string word;
stack<string> stk;
s.push_back(' ');
for (int i = 0; i < s.size(); i++)
{
if (s[i] != ' ')
word.push_back(s[i]);
else if (i > 0 && s[i] == ' ' && s[i-1] != ' ')
{
stk.push(word);
word.clear();
}
}
s.clear();
if (stk.empty())
return;
while (true)
{
s += stk.top();
stk.pop();
if (stk.empty())
break;
else
s.push_back(' ');
}
return;
}
};
class Solution
{
public:
void reverseWords(string &s)
{
string res;
int i = s.size() - 1;
while (true)
{
while (s[i] == ' ' && i >= 0)
i--;
if (i < 0) break;
if (!res.empty())
res.push_back(' ');
string temp;
while (s[i] != ' ' && i >= 0)
{
temp.push_back(s[i]);
i--;
}
reverse(temp.begin(), temp.end());
res += temp;
if (i < 0) break;
}
s = res;
}
};
http://blog.csdn.net/kenden23/article/details/20701069
本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39138373
https://oj.leetcode.com/problems/palindrome-partitioning/
DFS来解决这个问题。
class Solution
{
public:
vector<vector<string>> partition(string s)
{
if (s.empty())
return res;
dfs(s, 0);
return res;
}
void dfs(const string &s, int index)
{
if (index == s.size())
res.push_back(solution);
else
{
for (int i = index; i < s.size(); i++)
{
string substr = s.substr(index, i-index+1);
if (isPalindrome(substr))
{
solution.push_back(substr);
dfs(s, i+1);
solution.pop_back();
}
}
}
}
bool isPalindrome(const string &s)
{
int left = 0;
int right = s.size() - 1;
while (left <= right)
{
if (s[left] != s[right])
return false;
left++;
right--;
}
return true;
}
vector<vector<string>> res;
vector<string> solution;
};
http://fisherlei.blogspot.com/2013/03/leetcode-palindrome-partitioning.html
本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39064961
https://oj.leetcode.com/problems/balanced-binary-tree/
平衡树的判定是每个结点的左右子树的高度差不能超过1
判定以某一节点为根的树是否为平衡树可以分解为两步：
判定左右子树的高度差是否不超过1
判定左右子树是否为平衡树
可以进行一点优化， 让解法以的两个判定在一起完成， 不过两个算法都是一个数量级的。
class Solution
{
public:
bool isBalanced(TreeNode *root)
{
if (!root)
return true;
int l = depth(root->left);
int r = depth(root->right);
if (l-r > -2 && l-r < 2
&& isBalanced(root->left)
&& isBalanced(root->right))
return true;
else
return false;
}
int depth(TreeNode *root)
{
if (!root)
return -1;
else
return max(depth(root->left), depth(root->right)) + 1;
}
};
class Solution
{
public:
bool isBalanced(TreeNode *root)
{
if (root == NULL)
return true;
else if (depth(root) == -2)
return false;
else
return true;
}
int depth(TreeNode *node)
{
if (node == NULL)
return -1;
int left = depth(node->left);
if (left == -2)
return -2;
int right = depth(node->right);
if (right == -2)
return -2;
if (left-right>1 || left-right<-1)
return -2;
return max(left, right) + 1;
}
};
http://blog.csdn.net/lanxu_yy/article/details/11883083
http://fisherlei.blogspot.com/2013/01/leetcode-balanced-binary-tree-solution.html
本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39028911
题目：
https://oj.leetcode.com/problems/binary-tree-postorder-traversal/
分析：
第一种方法，用递归的方法做
第二种方法，用迭代的方法做。 先挖个坑， 以后填上
代码：
class Solution
{
public:
vector<int> postorderTraversal(TreeNode *root)
{
postorder(root);
return res;
}
void postorder(TreeNode *root)
{
if (!root)
return;
postorderTraversal(root->left);
postorderTraversal(root->right);
res.push_back(root->val);
return;
}
private:
vector<int> res;
};
本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39028031