编程之旅-Day40Day40-学习内容：

125 阅读 0 评论 83 点赞

我是靠谱客的博主美满小懒猪，这篇文章主要介绍编程之旅-Day40Day40-学习内容：，现在分享给大家，希望可以做个参考。

Day40-学习内容：

1.剑指Offer

面试题52：求两个链表的第一个公共结点

面试题27：二叉树的镜像

2.Leetcode

例1:二叉搜索树的最近公共祖先

例2:二叉树的最近公共祖先

例3:爬楼梯

例4:编辑单词间的距离

3.华为机试题

例1:字符个数统计

例2:数字颠倒

1.剑指Offer

面试题52：求两个链表的第一个公共结点

题目描述：

输入两个链表，找出它们的第一个公共结点。

思路：长短指针

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==nullptr||pHead2==nullptr){
            return nullptr;
        }
        ListNode* pNode1=pHead1;   //分别求长度
        ListNode* pNode2=pHead2;
        int len1=0;
        int len2=0;
        while(pNode1!=nullptr){
            len1++;
            pNode1=pNode1->next;
        }
        while(pNode2!=nullptr){
            len2++;
            pNode2=pNode2->next;
        }
        
        ListNode* pLong=pHead1;   //长链表先走几步
        ListNode* pShort=pHead2;
        int diff=len1-len2;
        if(len2>len1){
            pLong=pHead2;   //长链表先走几步
            pShort=pHead1;
            diff=len2-len1;
        }
        for(int i=0;i<diff;i++){
            pLong=pLong->next;
        }
        
        while(pLong&&pShort&&(pLong!=pShort)){  //得到公共节点
            pLong=pLong->next;
            pShort=pShort->next;
        }
        return pLong;
    }
};

面试题27：二叉树的镜像

题目描述：

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
二叉树的镜像定义：源二叉树 
    	    8
    	   /  
    	  6   10
    	 /   / 
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  
    	  10   6
    	 /   / 
    	11 9 7  5

思路：画图找规律，递归思想

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot==nullptr){
            return;
        }
        if(pRoot->left==nullptr&&pRoot->right==nullptr){
            return;
        }
        TreeNode *pTemp=pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=pTemp;
        if(pRoot->left){
            Mirror(pRoot->left);
        }
        if(pRoot->right){
            Mirror(pRoot->right);
        }
    }
};

2.Leetcode

例1:二叉搜索树的最近公共祖先

题目描述：

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

思路：递归，利用二叉搜索树的特点

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr||p==nullptr||q==nullptr){
            return nullptr;
        }
        int big=p->val;
        int small=q->val;
        if(q->val>p->val){
            big=q->val;
            small=p->val;
        }
        if(root->val>=small&&root->val<=big){
            return root;
        }
        else if(root->val>small&&root->val>big){
            return lowestCommonAncestor(root->left,p,q);
        }
        else{
            return lowestCommonAncestor(root->right,p,q);
        }
    }
};

例2:二叉树的最近公共祖先

题目描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路：递归

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root){
            return NULL;
        }
        if (root == p || root == q){
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root -> left, p, q);
        TreeNode* right = lowestCommonAncestor(root -> right, p, q);
        if (left && right){ //  p, q 分别位于 x 的左子树和右子树；
            return root;
        }else if (left){ // p, q 都在 x 的左子树（也包括祖先其自身，另一个字节点在左子树）；
            return left;
        }else if (right){ // p, q 都在 x 的右子树（也包括祖先其自身，另一个字节点在右子树）；
            return right;
        }
        return NULL;
    }
};

例3:爬楼梯

题目描述：

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

代码：

方法1:暴力法，超时不通过！

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int climbStairs(int n) {
        if(n<1){
            return 0;
        }
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
};

方法2:非递归，用for循环模拟

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int climbStairs(int n) {
        int result = 1, pre = 0;
        for (int i = 1; i <= n; i++) {
            int tmp = result;
            result += pre;
            pre = tmp;
        }
        return result;
    }
};

方法3:动态规划

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int climbStairs(int n) {
        int* dp = new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

例4:编辑单词间的距离

题目描述：

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

思路：动态规划

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m=word1.size();
        int n=word2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));  // dp[i][j]代表由word1的前i个子串变为word2的前j个子串的花费
        // 其中i，j均可为0，代表空串:""
        
        for(int i=0;i<=m;i++){
            for(int j=0;j<=n;j++){    
                if(i==0){   // 首先初始化两个子串中有一个为空串的情况
                    dp[i][j]=j;
                } 
                else if(j==0){   // 首先初始化两个子串中有一个为空串的情况
                    dp[i][j]=i;
                }   
                else{  
// 如果这两个字符相等，那么交由上一种情况处理,如abc，dfc
                // 这种情况与ab，df花费是一样的
                // 不然就要在删除，插入，修改中取花费最小的那个
                    dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,(dp[i-1][j-1]+(word1[i-1]==word2[j-1]?0:1))));
                }
            }
        }
        return dp[m][n];
    }
};

3.华为机试题

例1:字符个数统计

题目描述：

编写一个函数，计算字符串中含有的不同字符的个数。字符在ACSII码范围内(0~127)。不在范围内的不作统计。

输入描述:

复制代码

1
输入N个字符，字符在ACSII码范围内。

输出描述:

输出范围在(0~127)字符的个数。

示例1

输入

复制代码

1
abc

输出

复制代码

1
3

思路：set用法

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <set>

using namespace std;

int main(){
    char c;
    set<char> s;
    while(cin>>c){
        if(c>=0&&c<=127){
            s.insert(c);
        }
    }
    cout << s.size() << endl;
}

例2:数字颠倒

题目描述：

输入一个整数，将这个整数以字符串的形式逆序输出

程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001

输入描述:

输入一个int整数

输出描述:

将这个整数以字符串的形式逆序输出

示例1

输入

复制代码

1
2
1516000

输出

复制代码

1
0006151

思路：整数转换为字符串

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>

using namespace std;

int main(){
    int n;
    while(cin>>n){
        string str;
        while(n){
            str+=(n%10)+'0';
            n=n/10;
        }
        cout << str << endl;
    }
    return 0;
}

例3:字符串翻转

题目描述：

写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。例如：

输入描述:

复制代码

1
输入N个字符

输出描述:

输出该字符串反转后的字符串

示例1

输入

复制代码

1
2
abcd

输出

复制代码

1
dcba

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    string str;
    while(getline(cin,str)){
        reverse(str.begin(),str.end());
        cout << str << endl;
    }
    return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

using namespace std;

int main(){
    string str;
    while(getline(cin,str)){
        string str2;
        int len=str.length();
        
        for(int i=len-1;i>=0;i--){
            str2+=str[i];
        }
        
        cout << str2 << endl;
    }
    return 0;
}

最后

以上就是美满小懒猪最近收集整理的关于编程之旅-Day40Day40-学习内容：的全部内容，更多相关编程之旅-Day40Day40-学习内容内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：计算机
浏览次数：125 次浏览
发布日期：2023-11-27 12:35:04
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_10_f1_13__23__2_3.html

编程之旅-Day40Day40-学习内容：

Day40-学习内容：

1.剑指Offer

面试题52：求两个链表的第一个公共结点

面试题27：二叉树的镜像

2.Leetcode

例1:二叉搜索树的最近公共祖先

例2:二叉树的最近公共祖先

例3:爬楼梯

例4:编辑单词间的距离

3.华为机试题

例1:字符个数统计

例2:数字颠倒

例3:字符串翻转

最后

评论列表共有 0 条评论

发表评论取消回复

编程之旅-Day40Day40-学习内容：

Day40-学习内容：

1.剑指Offer

面试题52：求两个链表的第一个公共结点

面试题27：二叉树的镜像

2.Leetcode

例1:二叉搜索树的最近公共祖先

例2:二叉树的最近公共祖先

例3:爬楼梯

例4:编辑单词间的距离

3.华为机试题

例1:字符个数统计

例2:数字颠倒

例3:字符串翻转

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复