题解:根据描述,把行变成列,把列变成行。
vector<vector<int>> transpose(vector<vector<int>>& A) {
vector<vector<int>>ret;
vector<int>temp;
int m = A.size();//行数
int n = A[0].size();//列数
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
temp.push_back(A[j][i]);
}
ret.push_back(temp);
temp.clear();
}
return ret;
}
题解:根据描述,只需要找到层数最深的节点,然后找这些节点的公共祖先即可。
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
queue<TreeNode*>q;
vector<TreeNode*>node;
q.push(root);
while(!q.empty())
{//层序遍历,node向量保存每一层的节点
int len =q.size();
node.clear();
for(int i=0;i<len;i++){
TreeNode* tmp = q.front();
node.push_back(tmp);
q.pop();
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
}
while(true)
{//node节点找公共祖先
if(node.size()==1) return node[0];
else
{
TreeNode* p = node[0];
TreeNode* q = node[1];
node.erase(node.begin());
node.erase(node.begin());
TreeNode* tmp = lowestCommonAncestor(root,p,q);
node.push_back(tmp);
}
}
return NULL;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
if(!root||root==q||root==p) return root;
TreeNode*left = lowestCommonAncestor(root->left,p,q);
TreeNode*right = lowestCommonAncestor(root->right,p,q);
TreeNode* ret;
((ret=root)&&(left && right))||(ret = left)||(ret = right);
return ret;
}
题解:根据描述,只需要从N向上开始遍历,判断N是否同时满足回文和素数。在数字N大小在一千万和一亿之间,直接取N为一亿。因为在这范围没有满足的素数。
其实还可以优化,不存在位数个数是偶数的回文数且是素数的数,因此11至100,一千至一万,十万至一百万,一千万至一亿之间是不存在满足题目条件的数。
int primePalindrome(int N) {
while(true){
if(N==reverse(N)&&isPrime(N)) return N;
N++;
if(11<N&&N<100) N = 100;
if(1000<N&&N<10000) N = 10000;
if(100000<N&&N<1000000) N = 1000000;
if(10000000<N&&N<100000000) N = 100000000;
}
return 0;
}
bool isPrime(int N) {
if (N < 2) return false;
int R = (int) sqrt(N);
for (int d = 2; d <= R; ++d)
if (N % d == 0) return false;
return true;
}
int reverse(int N) {
int ans = 0;
while (N > 0) {
ans = 10 * ans + (N % 10);
N /= 10;
}
return ans;
}