九日集训Day4指针

一、概念定义

1、指针即地址

计算机中所有的数据都必须放置在内存中，不同类型的数据占用的字节数也不一样，例如 32位整型int占据 4 个字节，64位整型long long占据 8 个字节，字符型char占据 1 个字节。 为了能够正确地访问这些数据，必须为每个字节都编上编号，每个字节的编号是唯一的。 我们把内存中字节的编号称为 地址 或 指针。地址从 0 开始依次递增，对于 32 位环境下，程序能够使用的内存为 4GB，最小的地址为 0，最大的地址为 0XFFFFFFFF。

2、指针的定义

在C语言中，可以用一个变量来存放指针，这种变量称为指针变量。指针变量的值，通俗来说就是某一个变量的地址。 现在假设有一个char·类型的变量x，它存储了字符'o'，并占用了地址为0xCF的内存（地址通常用十六进制表示）。另外有一个指针变量p，它的值为0xCF，正好等于变量x的地址，这种情况我们就称p指向了x，或者说p是指向变量x的指针。

其中 p 是指针变量名，x 是被指向的变量的变量名；0xCF是 指针变量 p 的值，也是 x 的地址；'o'是 x 的值。

3、定义指针变量

定义指针变量和普通变量类似，只不过在变量名前面加上一个星号*即可。C语言实现如下：

DataType *dataName;

我们用到最多的指针变量类型为整型，可以这么写：int *p;

对于字符类型的指针变量，可以这么写：char *p;

4、取地址

我们回到上面的问题，假设 是一个字符型变量， 是 的地址，那么伪代码应该是这样的：

char x='o';
char *p=(x)的地址;


而实际写代码的时候，我们通过&来表示取地址符号，也就是代码可以写成：

5、数组的地址

对于数组而言，其中的元素的地址都是连续的，数组第一个元素的地址可以用数组名来表示，实现如下：

int a[]={5,2,0,1,3,1,4};
int *p=a;


简而言之，p 指向数组第一个元素的地址，a 也是数组第一个元素的地址。

6、解引用

解引用是取地址的逆操作，即根据给定的地址，获取它的值。用*运算符来实现，如下：

int a;
int *p=&a;
a==*p;


一句话解释，p 代表 a 的地址，*p 代表 a 的值；

7、内存申请

C语言中，利用函数malloc来申请内存，传入参数为申请内存的字节数，返回值为申请到的内存的首地址，是什么类型的地址，就要强转成什么类型，如下：

int *p=(int *)malloc(1024);


p 代表的是申请到的内存，并且有效内存字节数为 1024。 如果我们要申请一个长度为 的整型数组的内存，可以这么写：

int *p=(int *)malloc(sizeof(int)*n);


其中 sizeof(int) 表示的是一个 int 占用的字节数，那么一个长度为 n 的 int 类型的数组，需要的字节数自然就是 sizeof(int) * n。

8、返回数组

一般在刷题的时候，要求返回一个数组，这就比较尴尬，尴尬在哪里呢？ 因为函数只能有一个返回值，而数组除了需要知道数组的首地址，还需要知道数组元素的个数。 所以，LeetCode 的做法是，通过函数的参数传递一个指针变量进来，然后让调用者去填充这个指针变量，如下：

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


这里的 returnSize 是一个指针，它指向的就是一个代表数组长度的变量，它是没有赋值的，需要我们通过解引用对它进行赋值。 函数的调用方，其实是这么调用的：

int a[7]={5,2,0,1,3,1,4};
int rSize;
int *ret=getList(a,7,&rSize);


这里的 &rSize 含义就是取了 rSize 的地址，传递给 returnSize 时，自然就成了指针。这样，在函数内部对*returnSize 进行修改，自然就改了 rSize 的值，调用函数的一方自然就知道这个数组的长度了。 好了，今天的内容比较难，如果不懂，一定要在评论区留言告诉我，我会不断改善这块内容，争取能让更多的人听懂。

9、范式

所谓范式，就是规范写法的意思。就是按照这种规范写法写，能解决大部分问题。有关返回一维数组的问题，我们有通用范式，如下：

int *func(int *nums,int numsSize,int *returnSize){ //(2)
int *ret=(int *)malloc(sizeof(int) *xxx); //(3)
//TODO //(4)
*returnSize = xxx; //(5)
return ret; //(6)
}


• (1) 这一句话一般是系统提示你，需要申请内存，并且返回申请内存的首地址；


• (2) 这里会有两个返回值，一个是数组首地址（体现在返回值上），一个是数组大小（体现在指针传参上）；


• (3) 利用 malloc 申请一块自定义大小的内存；


• (4) 做你要做的事情；


• (5) 利用解引用，将需要返回的数组的长度告诉调用者；


• (6) 返回申请的数组内存的数组首地址；

10、概念总结

今天一下子接触到了太多概念，最后做个统一的总结：

二、题目分析

1、重新排列数组

给你一个数组 nums，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。

int *shuffle(int *nums,int numsSize,int n,int *returnSize){
int i;
int *ret=(int *)malloc(sizeof(int) *numsSize);
for(i=0;i if(i&1) ret[i]=nums[n+i/2];
else ret[i]=nums[(i+1)/2];
}
*returnSize = numsSize;
return ret;
}


• (1) 这句话是核心，返回的数组必须是通过malloc进行内存分配的，因为调用者会对它进行free的清理操作；


• (2) 这个函数的返回值是int *，即返回的是一个数组的首地址，但是数组的大小也需要让调用者知道，所以通过一个传参returnSize来传递出去；


• (3) 申请一个长度为numsSize的数组，首地址为ret；


• (4) 根据题目要求，将nums的数据填充到ret中；


• (5) 最后，别忘了利用解引用，将需要返回的数组的长度告诉调用者；


• (6) 返回你申请的数组的首地址；

2、数组串联

给你一个长度为 n 的整数数组 nums。请你构建一个长度为 2n 的答案数组 ans，数组下标 从 0 开始计数 ，对于所有 0 ≤ i ＜ n 的 i ，满足下述所有要求：ans[i]==nums[i] 且 ans[i+n]==nums[i]，具体而言，ans由两个 nums数组 串联 形成。返回数组 ans。

int *getConcatenation(int *nums,int numsSize,int *returnSize){
int i;
int *ret=(int *)malloc(2*sizeof(int) *numsSize);
for(i=0;i *returnSize = 2*numsSize;
return ret;
}


• (1) 这题和上题的不同之处在于：申请一个长度为 2 * numsSize 的数组，首地址为 ret；


• (2) 根据题目要求，将 nums 的数据填充到 ret 中；


• (3) 别忘了利用解引用，将需要返回的数组的长度告诉调用者；


• (4) 返回你申请的数组的首地址；

3、基于排列构建数组

给你一个 从 0 开始的排列nums（下标也从 0 开始）。请你构建一个 同样长度 的数组ans，其中，对于每个 i (0≤i

int *buildArray(int *nums,int numsSize,int *returnSize){
int i;
int *ret=(int *)malloc(sizeof(int) *numsSize);
for(i=0;i ret[i] = nums[nums[i]];
}
*returnSize = numsSize;
return ret;
}


• (1) 除了这一步不同，其它都是上文提到的范式的内容。

4、前缀和

给你一个数组nums。数组「 动态和 」的计算公式为：runningSum[i]=sum(nums[0]…nums[i])。请返回 nums的动态和。”

int *runningSum(int *nums,int numsSize,int *returnSize){
int i;
int *ret=(int *)malloc(sizeof(int) *numsSize);
for(i=0;i ret[i]=nums[i];
if(i) ret[i]+=ret[i-1];
}
*returnSize = numsSize;
return ret;
}


• (1) 当 i=0 时， ret[0] = nums[0]；当 i > 0 时, ret[i] = ret[i−1] + nums[i]，O(1) 的时间复杂度计算每个元素的动态和。

5、左旋字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串 "abcdefg"和数字 ，该函数将返回左旋转两位得到的结果"cdefgab"。”

char *reverseLeftWords(char *s,int k){
int i;
int n=strlen(s);
char *ret=(char *)malloc((n+1)*sizeof(char));
for(i=0;i ret[i]=s[(i+k)%n];
}
ret[n]='\0';
return ret;
}


• (1) 注意，字符串需要多申请一个自己的内存，用来存放结尾标记\0；


• (2) 把字符串首位相接，循环取模；


• (3) 加上结尾标记以后，调用者就不需要知道实际字符串有多长，可以通过strlen来获取了；

6、IP地址无效化

给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。所谓无效化 IP 地址，其实就是用 "[.]"代替了每个 "."。”

char *defangIPaddr(char *address){
char *ret=(char *)malloc(1000*sizeof(char));
int returnSize=0;
int i;
for(i=0;address[i];i++){
if(address[i]=='.'){
ret[returnSize++]='[';
ret[returnSize++]='.';
ret[returnSize++]=']';
}else{
ret[returnSize++]='address[i]';
}
}
ret[returnSize]='\0';
return ret;
}


• (1) 直接在原字符串代替不好做，所以我们可以申请一个新的字符串，长度可以定长一点关系不大；


• (2) 然后遇到'.'字符，我们就在返回的字符串上加上三个字符：'['、'.'、']'，否则添加原字符；


• (3) 最后，在字符串末尾添加一个'\0'表示字符串结尾；

7、替换空格

请实现一个函数，把一个长度不大于 10000 的字符串 中的每个空格替换成 "%20"。”

char *replaceSpace(char *s){
char *ret=(char *)malloc(30001*sizeof(char));
int i,retSize=0;
for(i=0;s[i];i++){
if(s[i]=='.'){
ret[retSize++]='%%';
ret[retSize++]='2';
ret[retSize++]='0';
}else{
ret[retSize++]=s[i];
}
}
ret[retSize]='\0';
return ret;
}


• (1) 和上面那题的思路一模一样，只是需要注意字符串长度可能很长，如果 10000 个空格的话，替换完最多 30001 个字符；

三、课后习题

1、重新排列数组

给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。

请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。

class Solution {
public:
vector shuffle(vector& nums, int n) {
vector ret;
for(int i=0;i<2*n;i++){

if(i%2==0) ret.push_back(nums[i/2]);
else ret.push_back(nums[n+i/2]);
}
return ret;
}
};
//要不 还是继续用vector，别碰指针，你会变得不幸


2、数组串联

给你一个长度为 n 的整数数组 nums 。请你构建一个长度为 2n 的答案数组 ans ，数组下标 从 0 开始计数 ，对于所有 0 <= i

ans[i] == nums[i]

ans[i + n] == nums[i]

具体而言，ans 由两个 nums 数组 串联 形成。

返回数组 ans 。

class Solution {
public:
vector getConcatenation(vector& nums) {
vector ret;
int n=nums.size();
for(int i=0;i ret.push_back(nums[i]);
}
for(int i=0;i ret.push_back(nums[i]);
}
return ret;
}
};


3、基于排列构建数组

给你一个 从 0 开始的排列 nums（下标也从 0 开始）。请你构建一个 同样长度 的数组 ans ，其中，对于每个 i（0 <= i

从 0 开始的排列 nums 是一个由 0 到 nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。

class Solution {
public:
vector buildArray(vector& nums) {
int n=nums.size();
vector ret;
for(int i=0;i ret.push_back(nums[nums[i]]);
}
return ret;
}
};


4、一维数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

class Solution {
public:
vector runningSum(vector& nums) {
int n=nums.size();
vector ret;
for(int i=0;i int sum=0;
for(int j=0;j<=i;j++){

sum+=nums[j];
}
ret.push_back(sum);
}
return ret;
}
};


5、左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

class Solution {
public:
string reverseLeftWords(string s, int n) {
int len=s.length();
string str="";
str += s.substr(n,len-n);
str += s.substr(0,n);
return str;
}
};


6、IP 地址无效化

给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。

所谓无效化 IP 地址，其实就是用 "[.]" 代替了每个 "."。

class Solution {
public:
string defangIPaddr(string address) {
string s="";
int len=address.length();
for(int i=0;i if(address[i]!='.'){
s += address[i];
}else{
s += "[.]";
}
}
return s;
}
};


7、替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

class Solution {
public:
string replaceSpace(string s) {
string str="";
int len=s.length();
for(int i=0;i if(s[i]!=' '){
str += s[i];
}else{
str += "%20";
}
}
return str;
}
};