极客20届第二周练习

「爱情、让人受尽委屈。」 2022-12-18 05:51 80阅读 0赞

## 前言 ##

第二周 相信大家已经学会一些基础语法了 但是可能对`指针`的理解 对`结构体` `链表`等数据结构的认识 乃至`类`的认识 还有欠缺

于是这周我们将深入这部分内容 以题目为驱动来做些事情

另外按照惯例 每道题都有**骚操作的空间** 。

最后，**思路为王**

--------------------

## 第一题 经典送分前缀和 ##

**基础知识点**

*  指针 函数等概念
 *  如何申请内存空间
 *  暴力模拟

**高级知识点**

*  记忆化搜索
 *  前缀和

**段位**  
黑铁~白银

**背景**

数组nums的`前缀和`的计算公式为：`getSum[i] = sum(nums[0]…nums[i])`

请返回 nums 的动态和。

传入的 nums指针所指向空间**已经被释放**

**示例 1：**

> 输入：nums = \[1,2,3,4\]  
> 输出：\[1,3,6,10\]  
> 解释：动态和计算过程为 \[1, 1+2, 1+2+3, 1+2+3+4\] 。

**示例 2：**

> 输入：nums = \[1,1,1,1,1\]  
> 输出：\[1,2,3,4,5\]  
> 解释：动态和计算过程为 \[1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1\] 。

**数据范围**  
程序能解决的n**越大越好** 不限制

**代码示例**

int* getSum(int* nums, int numsSize, int* returnSize){
        
    
    }

**拓展**  
如果传入的`nums`数组指向空间**没有被释放** 应该怎么做可以省一点空间

--------------------

## 第二题 可能没有用到算法的题目 ##

**基础知识点**

*  二维指针 函数等概念
 *  暴力模拟
 *  细心

**高级知识点**

*  莫得

**段位**  
黑铁

**背景**

给定一个正整数 n，打印输出一个包含 1 到  n 2 n^2 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

**示例 1：**

> 输入: 3  
> 输出:  
> \[  
> \[ 1, 2, 3 \],  
> \[ 8, 9, 4 \],  
> \[ 7, 6, 5 \]  
> \]

**数据范围**  
程序能解决的n**越大越好** 不限制

**代码示例**

int** generateMatrix(int n){
        
    
    }

--------------------

## 第三题 我就贪那点水 ##

**基础知识点**

*  指针 函数等概念

**高级知识点**

*  贪心 二分
 *  优先队列 或者 哈希表 或者 链表等 同样效果的数据结构

**段位**  
黄金

**背景**  
假设我有 n 个湖泊，下雨的时候，如果第 n 个湖泊是空的，那么它就会装满水，否则这个湖泊会发生洪水。你的目标**是避免任意一个湖泊发生洪水**。

给你一个整数数组 rains ，其中：

*  rains\[i\] > 0 表示第 i 天时，第 rains\[i\] 个湖泊会下雨。
 *  rains\[i\] == 0 表示第 i 天没有湖泊会下雨，你可以选择 一个 湖泊并 抽干 这个湖泊的水。

请返回一个数组 ans ，满足：

*  ans.length == rains.length
 *  如果 rains\[i\] > 0 ，那么ans\[i\] == -1 。
 *  如果 rains\[i\] == 0 ，ans\[i\] 是你第 i 天选择抽干的湖泊。

如果有多种可行解，请返回它们中的 任意一个 。如果没办法阻止洪水，请返回一个 空的数组 。

如果你抽干一个满水湖泊，它会变空。如果抽空湖泊，则无事发生（详见示例 4）。

传入的 rains、returnSize指针所指向空间**没有**被释放

**示例 1：**

> 输入：rains = \[1,2,3,4\]  
> 输出：\[-1,-1,-1,-1\]  
> 解释：第一天后，装满水的湖泊包括 \[1\]  
> 第二天后，装满水的湖泊包括 \[1,2\]  
> 第三天后，装满水的湖泊包括 \[1,2,3\]  
> 第四天后，装满水的湖泊包括 \[1,2,3,4\]  
> 没有哪一天你可以抽干任何湖泊的水，也没有湖泊会发生洪水。

**示例 2：**

> 输入：rains = \[1,2,0,0,2,1\]  
> 输出：\[-1,-1,2,1,-1,-1\]  
> 解释：第一天后，装满水的湖泊包括 \[1\]  
> 第二天后，装满水的湖泊包括 \[1,2\]  
> 第三天后，我们抽干湖泊 2 。所以剩下装满水的湖泊包括 \[1\]  
> 第四天后，我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。  
> 第五天后，装满水的湖泊包括 \[2\]。  
> 第六天后，装满水的湖泊包括 \[1,2\]。  
> 可以看出，这个方案下不会有洪水发生。同时， \[-1,-1,1,2,-1,-1\] 也是另一个可行的没有洪水的方案。

**示例 3：**

> 输入：rains = \[1,2,0,1,2\]  
> 输出：\[\]  
> 解释：第二天后，装满水的湖泊包括 \[1,2\]。我们可以在第三天抽干一个湖泊的水。  
> 但第三天后，湖泊 1 和 2 都会再次下雨，所以不管我们第三天抽干哪个湖泊的水，另一个湖泊都会发生洪水。

**示例 4：**

> 输入：rains = \[69,0,0,0,69\]  
> 输出：\[-1,69,1,1,-1\]  
> 解释：任何形如 \[-1,69,x,y,-1\], \[-1,x,69,y,-1\] 或者 \[-1,x,y,69,-1\] 都是可行的解，其中 1 <= x,y <= 10^9

**示例 5：**

> 输入：rains = \[10,20,20\]  
> 输出：\[\]  
> 解释：由于湖泊 20 会连续下 2 天的雨，所以没有没有办法阻止洪水。

**数据范围**  
 1 < = r a i n s . l e n g t h < = 1 0 5 1 <= rains.length <= 10^5 1<=rains.length<=105

0 < = r a i n s \[ i \] < = 1 0 9 0 <= rains\[i\] <= 10^9 0<=rains\[i\]<=109

**代码示例**

int* avoidFlood(int* rains, int rainsSize, int* returnSize){
        
    
    }

--------------------

## 第四题 最短路径问题 ##

**基础知识点**

*  二维指针 函数等概念
 *  暴力递归

**高级知识点**

*  经典动态规划

**段位**  
黑铁~黄金

**背景**

给定一个包含非负整数的 `m x n` 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

传入的 grid、gridSize、gridColSize指针所指向空间**没有**被释放

**示例 1：**

> 输入:  
> \[  
> \[1,3,1\],  
> \[1,5,1\],  
> \[4,2,1\]  
> \]  
> 输出: 7  
> 解释: 因为路径 1→3→1→1→1 的总和最小。

**数据范围**  
程序能解决的n**越大越好** 不限制

**代码示例**

int minPathSum(int** grid, int gridSize, int* gridColSize){
        
    
    }

--------------------

## 第五题 给萌新留活路的链表 ##

**基础知识点**

*  指针 函数等概念
 *  链表
 *  动态申请内存

**段位**  
白银？

**背景**  
请实现一个**链表** 链表元素包含参数`index` 与`value`

链表功能能够实现增删改查

*  增 给定序号（index，即插入的位置）与元素值（value） 增加元素
 *  删 给定序号（index），删除元素
 *  改 给定序号（index），新的值（value），改变元素
 *  查 给定序号（index），返回值（value）
 *  查 返回所有的值（value），并且**进行排序和去重**，输出

--------------------

## 后记 要求 ##

请上交程序给你的组长 提供以下材料：

*  源代码 `.c` `.cpp` 或者`.java` （考指针的题目你就只能用`c`语言了）
 *  思路说明 建议不要仅仅用注释代替思路说明 除非真的很简单：）
 *  `每周周日24:00`为上交截止时间 早交有加分