leetcode 78,236,300

时间:2024-01-04 16:49:32

---恢复内容开始---

2018.3.16目前已刷27题,打卡记录有意思的题目。

leetcode78 subsets 思路1:DFS遍历子集,每遇到一个数就把该数加上原来的子集变成新的子集。

class Solution {
private:
void DFS(int index,vector<int> t,vector<int>& nums,vector<vector<int>> & res){
res.push_back(t);
for(int i = index;i<nums.size();i++){
t.push_back(nums[i]);
DFS(i+,t,nums,res);
t.pop_back();
}
} public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> t;
DFS(,t,nums,res);
return res;
}
};

思路2:采用位运算,是否取某个数组成子集视为0101的序列。

236  求二叉树的最低公共祖先

思路1:求出根节点到所求节点的路径,最后求两个路径的最后一个公共节点

class Solution {
//pNode是要打印的节点,pRoot是工作指针
bool getNodePath(TreeNode* pRoot,TreeNode * pNode,vector<TreeNode*> &path){
if(!pRoot) return false;
path.push_back(pRoot);
if(pRoot==pNode) return true;
bool found=false;
if(pRoot->left) found=getNodePath(pRoot->left,pNode,path);
if(!found&&pRoot->right) found=getNodePath(pRoot->right,pNode,path);
if(!found) path.pop_back();
return found; }
TreeNode* getLastCommonNode(const vector<TreeNode*> &pPath,const vector<TreeNode*> &qPath){
TreeNode* res;
vector<TreeNode*>::const_iterator iteratorP = pPath.begin();
vector<TreeNode*>::const_iterator iteratorQ = qPath.begin();
while(iteratorP != pPath.end() && iteratorQ != qPath.end()){
if(*iteratorP == *iteratorQ) res=*iteratorP;
iteratorP++;
iteratorQ++;
}
return res;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> pPath,qPath;
if(!root || !p || !q) return nullptr;
getNodePath(root,p,pPath);
getNodePath(root,q,qPath);
return getLastCommonNode(pPath,qPath);
}
};

思路2:先序遍历

 class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || root == p || root == q) return root;
//如果没有匹配到节点 就会返回null
//但凡匹配到任何一个节点,都不会返回null;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
//如果左边,右边都找到了节点,那就是最近的公共祖先
if (left && right)
return root;
return left == NULL ? right : left;
}
};

leetcode690,题目虽然简单,但是因为某个变量没有初始化为0,导致相同的测试用例和代码在本地执行与提交代码跑出来结果不同。这个低级错误真是让人脸红啊~~

leetcode300 最长不上升子序列

方法一:动态规划算法。状态转移方程   dp[i]=max{1,dp[j]+1}  (j=1,2,...,i-1 && A[j]<A[i])

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.empty()) return ;
int maxLen=;
vector<int> dp= vector<int>(nums.size(), );
for(int i=;i<nums.size();i++){
for(int j=;j<i;j++){
if(nums[i]>nums[j] && dp[i]<dp[j]+)
dp[i]=dp[j]+;
}
maxLen=dp[i]>maxLen?dp[i]:maxLen;
}
return maxLen;
}
};

方法二: