编程之旅-Day24目录

130 阅读 0 评论 86 点赞

我是靠谱客的博主追寻保温杯，这篇文章主要介绍编程之旅-Day24目录，现在分享给大家，希望可以做个参考。

题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路：分解、图形化、理清思路，时间复杂度O(n),空间复杂度O(1).

代码：

复制代码

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        CloneNode(pHead);
        CloneRandomNode(pHead);
        return ReconnectNode(pHead);
    }
    void CloneNode(RandomListNode* pHead){
        RandomListNode* pNode=pHead;
        while(pNode!=nullptr){
            RandomListNode* pCloned=new RandomListNode(pNode->label);
            //pCloned->label=pNode->label;
            pCloned->random=nullptr;
            pCloned->next=pNode->next;
            pNode->next=pCloned;
            pNode=pCloned->next;      
        }
    }
    void CloneRandomNode(RandomListNode* pHead){
        RandomListNode* pNode=pHead;
        
        while(pNode!=nullptr){
            RandomListNode* pCloned=pNode->next;
            if(pNode->random!=nullptr){
                pCloned->random=pNode->random->next;
            }
            pNode=pCloned->next;
        }
    }
    
    RandomListNode* ReconnectNode(RandomListNode* pHead){
        RandomListNode* pNode=pHead;
        RandomListNode* pClonedHead=nullptr;
        RandomListNode* pCloned=nullptr;
        
        if(pNode!=nullptr){
            pClonedHead=pCloned=pNode->next;
            pNode->next=pCloned->next;
            pNode=pNode->next;
        }
        while(pNode!=nullptr){
            pCloned->next=pNode->next;
            pCloned=pCloned->next;
            pNode->next=pCloned->next;
            pNode=pNode->next;
        }
        return pClonedHead;
    }
};

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        CloneNode(pHead);
        CloneRandomNode(pHead);
        return ReconnectNode(pHead);
    }
    void CloneNode(RandomListNode* pHead){
        RandomListNode* pNode=pHead;
        while(pNode!=nullptr){
            RandomListNode* pCloned=new RandomListNode(pNode->label);
            //pCloned->label=pNode->label;
            pCloned->random=nullptr;
            pCloned->next=pNode->next;
            pNode->next=pCloned;
            pNode=pCloned->next;      
        }
    }
    void CloneRandomNode(RandomListNode* pHead){
        RandomListNode* pNode=pHead;
        
        while(pNode!=nullptr){
            RandomListNode* pCloned=pNode->next;
            if(pNode->random!=nullptr){
                pCloned->random=pNode->random->next;
            }
            pNode=pCloned->next;
        }
    }
    
    RandomListNode* ReconnectNode(RandomListNode* pHead){
        RandomListNode* pNode=pHead;
        RandomListNode* pClonedHead=nullptr;
        RandomListNode* pCloned=nullptr;
        
        if(pNode!=nullptr){
            pClonedHead=pCloned=pNode->next;
            pNode->next=pCloned->next;
            pNode=pNode->next;
        }
        while(pNode!=nullptr){
            pCloned->next=pNode->next;
            pCloned=pCloned->next;
            pNode->next=pCloned->next;
            pNode=pNode->next;
        }
        return pClonedHead;
    }
};

面试题：跳台阶

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

思路：对于本题,前提只有一次1阶或者2阶的跳法。

a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);

b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)

c.由ab假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)

d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

e.可以发现最终得出的是一个斐波那契数列.

代码：

复制代码

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

面试题：变态跳台阶

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路：关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:

f(1) = 1

f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。

f(3) = f(3-1) + f(3-2) + f(3-3)

...

f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)

说明：

1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的跳法数。

2）n = 1时，只有1种跳法，f(1) = 1

3) n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1），f(2) = f(2-1) + f(2-2)

4) n = 3时，会有三种跳得方式，1阶、2阶、3阶，

那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)

因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)

5) n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：

f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)

6) 由以上已经是一种结论，但是为了简单，我们可以继续简化：

f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)

可以得出：

f(n) = 2*f(n-1)

7) 得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：

| 1 ,(n=0 )

f(n) = | 1 ,(n=1 )

| 2*f(n-1),(n>=2)

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int jumpFloorII(int number) {
        if(number==0){
            return -1;
        }
        else if(number==1){
            return 1;
        }
        else{
            return 2*jumpFloorII(number-1);
        }

    }
};

2.Leetcode

例1:加油站索引

题目描述：

There are N gas stations along a circular route, where the amount of gas at station i isgas[i].

You have a car with an unlimited gas tank and it costscost[i]of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

思路：

从start出发，如果油量足够，可以一直向后走 end++；油量不够的时候， start向后退最终 start == end的时候，如果有解一定是当前 start所在位置。

考察点：贪心算法

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int start=gas.size()-1;
        int end=0;
        int sum=gas[start]-cost[start];
        while(start>end){
            if(sum>=0){
                sum+=gas[end]-cost[end];
                ++end;
            }
            else{
                --start;
                sum+=gas[start]-cost[start];
            }
            
        }
        return sum>=0?start:-1;
    }
};

解析：

　　贪心算法是指：在每一步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。

　　贪心算法每一步必须满足一下条件：

　　1、可行的：即它必须满足问题的约束。

　　2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。

　　3、不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。

https://www.cnblogs.com/xsyfl/p/6938642.html

例2:三角形最短路径和

题目描述：

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

复制代码

1
2
3
4
5
6
7
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is11(i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

考察点：动态规划

思路：

// 给定一个三角形，找出从顶到底的最小路径和，每一步可以从上一行移动到下一行相邻的数字

// [

// [2], [2],

// [3,4], [3, 4], [2],

// [6,5,7], ==> [7, 6, 10] ==> [9, 10] ==> [11]

// [4,1,8,3]

// ]

* 自底向上 dp: 不需要额外的空间

* dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]

* dp[i][j]: 表示到达 (i, j)最小路径的总和

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    //从下往上找，不使用额外空间，缺点是修改了输入
    int minimumTotal(vector<vector<int> > &triangle) {
        for(int i=triangle.size()-2;i>=0;i--){
            for(int j=0;j<triangle[i].size();j++){
                triangle[i][j]+=min(triangle[i+1][j],triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
};

例3:不同子序列树

题目描述：

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,"ACE"is a subsequence of"ABCDE"while"AEC"is not).

Here is an example:
S ="rabbbit", T ="rabbit"

Return3.

思路：

//array(i , j ) 表示T[0,j] 在S[0，i] 中的匹配个数

//如果不使用S[i] , 那么f(i , j) = f(i-1 , j)

//如果使用了S[i] , 那么一定有 S[i] == T[j] , f( i , j ) = f(i -1 , j -1 )

//所以当S[i]==T[j]时，有array( i , j ) = array( i -1 , j ) +　array(i - 1 , j - 1);

//当S[i]!=T[j]时，有array( i , j ) = array( i -1 , j );

//在使用中不难发现该dp二维数组可以降维，注意改变数组元素值时由后往前

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numDistinct(string S, string T) {
        int len=T.size();
        vector<int> array(len+1);
        array[0]=1;
        for(int i=1;i<S.size()+1;i++){
            for(int j=min(i,len);j>0;j--){
                if(S[i-1]==T[j-1]){
                    array[j]=array[j]+array[j-1];
                }
            }
        }
        return array[len];
    }
};

最后

以上就是追寻保温杯最近收集整理的关于编程之旅-Day24目录的全部内容，更多相关编程之旅-Day24目录内容请搜索靠谱客的其他文章。

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

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

编程之旅-Day24目录

目录

1.剑指Offer

面试题35：复杂链表的复制

面试题：跳台阶

面试题：变态跳台阶

2.Leetcode

例1:加油站索引

例2:三角形最短路径和

例3:不同子序列树

最后

评论列表共有 0 条评论

发表评论取消回复

编程之旅-Day24目录

目录

1.剑指Offer

面试题35：复杂链表的复制

面试题：跳台阶

面试题：变态跳台阶

2.Leetcode

例1:加油站索引

例2:三角形最短路径和

例3:不同子序列树

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复