数据结构题目贴

发表于 2020-02-14更新于 2020-02-24字数统计 3.5k阅读时长 23m

(408)

前言

鸽🕊了自己很久的数据结构刷题！！

必须整活起来！

加油！

打卡记录：

应该坚持天数：11 实际坚持天数：11

刷题数：12

2020年二月(2月14开始)

2月14日

情人节苦逼的我还是得整活！！

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

1
2
3
4
public:
    bool Find(int target, vector<vector<int> > array) {
        }
};

解法：

https://blog.nowcoder.net/n/d332492753844d18aa4edc484e3c1318?f=comment

个人的想法是这里的四(二)，可是不会代码实现(老不会递归了！）

法一是最优的，法二也很秀思路可以理解一下。

第一天心得：好烦啊第一题都不会，佛了！继续努力吧。早上起来一定要再看一遍

2020.2.15 0:23

2月15日

刷他娘的！

题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

1
2
3
4
5
6
class Solution {
public:
	void replaceSpace(char *str,int length) {
        
	}
};

解法：

个人的想法是从前到后，然后新建一个字符串，一个个复制，当遇到空格时就替换（一系列操作），然后最后再复制回原来的。

这方法缺点就是，空间复杂度比较高。

大佬有两种解释做法：

1、比较笨的就是从前到后，遇到的就整体后移，这样很慢，后面的字符会重复移动，但是不用开新空间。

2、比较推荐的就是从后往前的后移，每个字符移动一次，这样移动的次数会大大减少，（这里有一个细节就是先计算了替换了空格之后的长度，后移时，直接移到最后面）

第二天心得：确实牛逼的人好牛逼

2月16日

明天开始网课了，有点想吐

题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {

    }
};

解法：

四种思路：

有四种思路，第一就是利用栈先入后出的特性完成，第二就是存下来然后进行数组翻转。第三是利用递归,第四种 迭代法。

这里前两种是常规也是正常的思路，第三第四种方法思想比较秀

栈思路：

数组翻转：数组翻转可以用C++自带的函数，也可以自己实现
//reverse(value.begin(),value.end()); //C++自带的翻转函数

递归思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> value;
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode *p=NULL;
        p=head;
        if(p!=NULL){
            if(p->next!=NULL){
                printListFromTailToHead(p->next);
            }
            value.push_back(p->val);
        }
        return value;
    }
};

迭代法：

总结为：先存储当前节点的下一节点，再反转当前节点的pnext指针，最后重置head头部。

注意：若head指向Null而不放数据，则prev、curr、next应相应改变

2

个人一开始想法是偏向于第四种，但是由于题意不名，不知道能更改next指针。

第三天心得：坚持第三天，感觉有点意思

2月17日

原本今天要做树的题的，但是发现自己知识点十分不咋地牢固，重新要开始复习了，就跳了一题做了，节省时间复习一下。

题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution
{
public:
    void push(int node) {
        
    }
    int pop() {    
    
    }
private:
    stack<int> stack1;
    stack<int> stack2;
};

解答

太水了我都会做，一个用来入栈，一个用来出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {
        int a;
        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                a=stack1.top();
                stack2.push(a);
                stack1.pop();
            }
        }
        a=stack2.top;
        stack2.pop;
    }
private:
    stack<int> stack1;
    stack<int> stack2;
};

要注意的是，不是每次的都pop完，所以仅当stack2空时才能让stack1入栈，因为stack2里的都是先的。

第四天心得：细节要注意，基础要注意！

2月18日

放假一个月了，在家舒服了。

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

1
2
3
4
5
6
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        
    }
};

解答

这题第一眼看到想法就是脑瘫题，tm的不就是简单的遍历查找吗？然后越看越不对，越想越不对劲，怎么这样嘛！

然后看了大家讨论才知道这题考点是查找的方式。

计算数组是排序的，再线性地查找就显得不高效了。排序数组，自然要想到二分查找。只是这里的操作和常规二分查找不同。

3

可以通过a[right]和a[mid]的关系来判断mid降落在前后哪一个部分,本题最巧妙的一点是，当出现特殊情况：a[left]==a[right] 的时候的处理。

当a[left]==a[right] ，假如a[mid]=a[right]的时候，根本没法判断。

我一开始想到的处理方法是当出现a[left]==a[right]=a[mid]这种情况是就用最坏的方法——直接遍历查找返回，但后来看到讨论区有人的更优的解法：在前期就去掉a[left]==a[right]的情况，缩小区域，排除掉特这种特殊情况：

1
2
3
4
while(a[right]==a[left]){
	right--;
	left++;
}

非常的妙啊，基本是这道题最秀的地方了

后面就没什么特别的，看了一圈也没有什么别的方法，按照上面的去做吧,下面附上个人ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minNumberInRotateArray(vector<int> a) 
	{
        int left=0,mid;
		int right=a.size()-1;
		if (right==-1)
			return 0;
		while(a[right]==a[left])
		{
			right--;
			left++;
		}
		while(a[left]>a[right])
		{
			mid=left+(right-left)/2;
			if(a[right]>a[mid])
				right=mid;
			else if(a[right]<=a[mid])
				left=mid+1;
		}
		return a[left];
    }
};

第五天心得：虽然题目不难，但能大致自己打出来，有一点进步了，加油。

2月19日

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39 

1
2
3
4
5
6
class Solution {
public:
    int Fibonacci(int n) {
        
    }
};

解答

斐波那契数列

这个博客里面讲的非常详细，值得注意一点的是，关于讨论区很巧妙的解答，实际上就是第二种方法循环的简化版形式。

其中第四种方法，我还看不懂，等我复习完线性代数一定来

第六天心得：今天好水啊。

2月20日

今天第一题更水了，我打算做两题

题目1描述

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

1
2
3
4
5
6
class Solution {
public:
    int jumpFloor(int number) {
        
    }
};

解法

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

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

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

所以，这个不就是斐波那契数列吗？

当然这个是有点特殊的斐波那契

​ | 1, (n=1)

f(n) = | 2, (n=2)

​ | f(n-1)+f(n-2) ,(n>2,n为整数)

就不能用昨天的法3了，法4能不能我不知道。

总之很水。

题目2描述

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

1
2
3
4
5
6
class Solution {
public:
    int jumpFloorII(int number) {

    }
};

解法

吐了，记录第一题才来第二题，发现不都是斐波那契那个blog里面的吗，又水了一道，看来今天是想给我放假的。

不过今天这样还是有收获的，这道题的话就是f(n)=1+f(1)+f(2)+ ··· +f(n-1)

f(n)=2f(n-1)，递归一下f(n)=2^(n-1)

1
return pow(2,number-1);

就行了

第七天心得：今天好水啊！但是对递归的概念有一点明白。

2月21日

昨天就看到今天会很水了。

题目描述

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

比如n=3时，2*3的矩形块有3种覆盖方法：

4

解答

还是斐波那契。5

代码一样的

第八天心得：水，但是还是要学会一点。

2月22日

今天人有点傻了。

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

1
2
3
4
5
6
class Solution {
public:
     int  NumberOf1(int n) {
         
     }
};

解答

一般方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//-------------可能陷入死循环的解法---------------------
    public static int NumberOf1_CanNotUse(int n) {
        int count = 0;
        while (n != 0) {
            /*
            * 用1和n进行位与运算，
            * 结果要是为1则n的2进制形式
            * 最右边那位肯定是1，否则为0
            */
            if ((n & 1) == 1) {
                count++;
            }
            //把n的2进制形式往右推一位
            n = n >> 1;
        }
        return count;
    }

死循环？是因为负数右移，最左边的用1填充 ，这样可以改成

1
n=n>>>1    //逻辑右移

还可以：

1
2
3
4
5
6
7
8
9
10
11
12
//思想：用1（1自身左移运算，其实后来就不是1了）和n的每位进行位与，来判断1的个数
    private static int NumberOf1_low(int n) {
        int count = 0;
        int flag = 1;
        while (flag != 0) {
            if ((n & flag) != 0) {
                count++;
            }
            flag = flag << 1;
        }
        return count;
    }

特殊方法：

1
2
3
4
5
6
7
8
9
10
public class Solution { 
      public int NumberOf1(int n) { 
          int count = 0; 
           while(n!= 0){ 
               count++; 
               n = n & (n - 1); 
            } 
          return count; 
      } 
  }

​ 如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。

​ 举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

第9天心得：位运算，不会，真实。

2月23日

我以为我早想清楚

不由自主恍恍惚惚又走回头路

再看一眼有过的幸福

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0 

1
2
3
4
5
6
class Solution {
public:
    double Power(double base, int exponent) {
    
    }
};

解答

我自己ac的是用最笨的方法——暴力，一个个乘；

但这题是典型的快速幕，正所谓快速幂，就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。 具体算法原理以及优化可看下面的网站。

快速幂算法（全网最详细地带你从零开始一步一步优化）

本题用快速幂的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    double Power(double base, int exponent) {
        long long p = abs((long long)exponent);
      double r = 1.0;
        while(p){
            if(p & 1) r *= base;
            base *= base;
            p >>= 1;
        }
        return exponent < 0 ? 1/ r : r;
    }
};

第10天心得：算法的改进和差距真的影响好大！

2月24日

怎么今天上传更新了好久还没好。

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

1
2
3
4
5
6
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        
    }
};

解答

非常，没意思的一道题阿，一点巧妙或者特殊的东西都没有。

就是最简单的处理：

法一：开多余的数组存完放回去

法二：从左开始，遇到偶数，就从此向后找到第一个奇数，插入并将这段整体后移。

没意思啊！

第11日心得：水题真的没意思。