【leetcode】c语言刷题总结_leetcode malloc

C 基础知识

• 分配内存

s=（int *）malloc（sizeof（int））

sizeof计算（int）所占的字节数，malloc分配这么多字节数的空间，s应该是int型，所以要转换成（int *）型

• 二维数组申请动态分配内存

使用malloc函数，先分配第一维的大小，再循环分配每一维的大小。

a=(int **) malloc(sizeof(int *) * r)

首先，这句话的意思bai就是使用malloc申请du sizeof(int*)*r这么大的内存空间。

其次，因为zhimallo的返回值是void*类型，所dao以要进行一个类型转换，你可以转换成任何的类型。

a=(int**)malloc(sizeof(int*)*3);
for(i=0;i<3;i++){
    a[i]=(int*)malloc(sizeof(int)*4);
}
1
2
3
4

• 力扣中的传参含义

int** generate(int numRows, int* returnSize, int** returnColumnSizes)
1

那么returnColumnSizes是什么？
是一个一维数组的地址的地址。（地址即指针）

return-Column-Sizes，类似于returnSize，是一个“返回值”，返回的信息是二维数组的列数。

returnSize中要返回的信息是二维数组的行数。

1. returnColumnSizes	        *//是一维数组的地址的地址*
2. \* returnColumnSizes		    *//是一维数组的地址*
3. (* returnColumnSizes)[i]	*//是一维数组的i个元素*
1
2
3

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

快排+双指针
int comp(const void *a,const void *b)
{
    return *(int *)a - *(int *)b;
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    if (numsSize == 0) {
        return 0;
    }
    int **ret = (int **)malloc(sizeof(int *) * (numsSize + 1) * 6);
    *returnSize = 0;
    short left = 0;
    short right = numsSize - 1;;
    int target = 0;
    
    *returnColumnSizes = malloc(sizeof(int) * (numsSize + 1) * 6);
    qsort(nums, numsSize, sizeof(int), comp);
    ret[*returnSize] = malloc(sizeof(int) * 3);

    while (left + 1 < right) {
        int i = left + 1;
        int j = right;
        target = 0 - nums[left];
        while (i < j) {
            if (nums[i] + nums[j] < target) {
                i++;
            } else if (nums[i] + nums[j] > target) {
                j--;
            } else {
                ret[*returnSize][0] = nums[left];
                ret[*returnSize][1] = nums[i];
                ret[*returnSize][2] = nums[j];
                (*returnColumnSizes)[*returnSize] = 3;
                (*returnSize)++;
                ret[*returnSize] = malloc(sizeof(int) * 3);

                while(nums[i] == nums[++i] && i < j) {}
                while(nums[j] == nums[--j] && i < j) {}
            }
        }
        while(nums[left] == nums[++left] && left + 1 < right) {}
    }
    
    return ret;
}
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

四数之和

void quickSort(int* nums, int first, int end) {					//快速排序 
	int temp, l, r;
	if (first >= end) {
		return;
	}
	temp = nums[first];
	l = first;
	r = end;
	while (l < r) {
		while (l < r && nums[r] >= temp) {
			r--;
		}
		if (l < r) {
			nums[l] = nums[r];
		}
		while (l < r && nums[l] <= temp) {
			l++;
		}
		if (l < r) {
			nums[r] = nums[l];
		}
	}
	nums[l] = temp;
	quickSort(nums, first, l - 1);
	quickSort(nums, l + 1, end);
}

void paixu(int* nums,int numsSize){
int temp;
for(int i=0;i<numsSize-1;i++){
for(int j=0;j<numsSize-1-i;j++){
if(nums[j]>nums[j+1]){
temp=nums[j];
nums[j]=nums[j+1];
nums[j+1]=temp;
}
}
}
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
	int sum = 0;							//和
	int base_alloc_size = 16;				//基本内存
	int** res = (int**)malloc(sizeof(int*) * base_alloc_size);
	(*returnSize) = 0;
	*returnColumnSizes = (int*)malloc(sizeof(int) * base_alloc_size);

	if (numsSize < 4 || nums == NULL) {
		return NULL;
	}

	//quickSort(nums, 0, numsSize - 1);                          			//排序
    paixu(nums,numsSize);

	for (int i = 0; i < numsSize - 3; i++) {
		if (i > 0 && nums[i] == nums[i - 1]) {							//去重
			continue;
		}
		for (int j = i + 1; j < numsSize - 2; j++) {
			if (j > i + 1 && nums[j] == nums[j - 1]) {					//去重
				continue;
			}
			int left = j + 1;
			int right = numsSize - 1;
			while (left < right) {
				sum = nums[i] + nums[j] + nums[left] + nums[right];
				if (sum == target) {
					res[*returnSize] = (int*)malloc(sizeof(int) * 4);
					res[*returnSize][0] = nums[i];
					res[*returnSize][1] = nums[j];
					res[*returnSize][2] = nums[left];
					res[*returnSize][3] = nums[right];

					(*returnColumnSizes)[*returnSize] = 4;
					(*returnSize)++;

					while (left < right && nums[left] == nums[left + 1]) {		//去重
						left++;
					}
					left++;
				}
				else if (sum < target) {
					left++;
				}
				else {
					right--;
				}

				if (*returnSize == base_alloc_size) {							//空间不足，扩充内存
					base_alloc_size = base_alloc_size * 2;
					res = (int**)realloc(res, base_alloc_size * sizeof(int*));
					(*returnColumnSizes) = (int*)realloc((*returnColumnSizes), base_alloc_size * sizeof(int));
				}
			}
		}
	}
	return res;
}

//调试
int main() {
	int num[] = { 1, 0, -1, 0, -2, 2 };
	int* nums = (int*)num;
	int numsSize = sizeof(num) / sizeof(int);
	int target = 0;
	int* returnSize = (int*)malloc(sizeof(int) * 1);
	//这里的内存分配最大值,即排列组合知识,C几取3
	//C6取3 == 20
	int** returnColumnSizes = (int**)malloc(sizeof(int*) * 1);
	int** res = fourSum(nums, numsSize, target, returnSize, returnColumnSizes);

	for (int i = 0; i < *returnSize; i++) {				//打印
		for (int j = 0; j < 4; j++) {
			printf("%d ", res[i][j]);
		}
		printf("\n");
	}
	return 0;
}
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

字母异位词分组

• defaultdict的使用介绍

https://www.cnblogs.com/dancesir/p/8142775.html

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        from collections import defaultdict
        strs_dict=defaultdict(list)
        res=[]
        for str in strs:
            key=''.join(sorted(list(str)))
            strs_dict[key] += str.split(',')
        for v in strs_dict.values():
            res.append(v)
        return res
1
2
3
4
5
6
7
8
9
10
11

预测赢家

对玩家1来说

从左端取数：nums[left]-玩家2从[left+1,n]之间取数

从右端取数：nums[right]-玩家从[left] [right-1]之间取数

最后玩家1的得分情况就是这两种情况的最大值

bool PredictTheWinner(int* nums, int numsSize){
    int dp[numsSize];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < numsSize; i++) {
        dp[i] = nums[i];
    }

    for (int i = numsSize - 2; i >= 0; i--) {
        for (int j = i+1; j < numsSize; j++) {
            dp[j] = fmax(nums[i] - dp[j], nums[j] - dp[j-1]);
        }
    }

    return dp[numsSize-1] >= 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

存在重复元素

• qsort

#include<stdlib.h>

void qsort(void*, size_t, size_t, int ( * )(const void * ,  const void *  ))
1
2
3

1. 第一个参数为待排序数组首地址，可直接输入待排序数组名，或是指向数组的指针；
2. 第二个参数为数组长度；
3. 第三个参数为数组元素所占字节，可直接用sizeof(a[0])计算字数组单个元素的节数；
4. 第四个参数为所调用函数的指针，函数名即是函数的指针，可直接写函数名；

int cmp(const void*a, const void*b) {
    return *(int*)a - *(int*)b;
}

bool containsDuplicate(int* a, int n)
{
    if (a == NULL || n <= 0) {
        return false;
    }
    qsort(a, n, sizeof(int), cmp);
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1]) {
            return true;
        }
    }
    return false;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

表示数值的字符串

bool scanUnsignedInt(char **ps) {
    const char *before = *ps;

    while (**ps != '\0' && **ps >= '0' && **ps <= '9') {
        ++(*ps);
    }

    return *ps > before;
}
bool scanInt(char **s) {
    if (**s == '+' || **s == '-') 
        ++(*s);
    return scanUnsignedInt(s);
}
bool isNumber(char* s){
    if (s == NULL) return false;
    while (*s == ' ') {
        ++s;
    }
    bool numeric = scanInt(&s);

    if (*s == '.') {
        ++s;

        numeric = scanUnsignedInt(&s) || numeric;
    }

    if (*s == 'e' || *s == 'E') {
        ++s;

        numeric = numeric && scanInt(&s);
    }
    while (*s == ' ')
        ++s;
    return numeric && *s == '\0';
}

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

加一

int *plusOne(int *digits, int digitsSize, int *returnSize) {

    for (int i = digitsSize - 1; i >= 0; i--) {
        if (digits[i] == 9) {
            digits[i] = 0;
        } else {
            digits[i]++;
            *returnSize = digitsSize;
            return digits;
        }
    }
    int *result = (int *) malloc(sizeof(int) * (digitsSize + 1));
    memset(result, 0, (digitsSize + 1) * sizeof(int));
    result[0] = 1;
    *returnSize = digitsSize + 1;
    return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

钥匙和房间

用深入优先搜索的方式，就是先找到一个房间的钥匙，然后依次拿着这个钥匙去进入所有能开的房间为止，直到没有新的房间或者房间里钥匙为空，就退出该节点的索引。因为找到了一个钥匙就会一直往下走直到不能深入为止，因此叫做深度遍历优先。

模板用于参考：
void Dfs()
{
if (越界、特殊状态等不符合要求) {
return;
}
if (满足退出条件) {
return;
}
for (扩展方式 如何向下一层走) {
if (扩展后的状态合法) {
…; 维护标记; dfs(); (还原标记等)
}
}
}

main函数中一开始进入DFS时，给一个初始位置就好

/* 使用了全局变量用于维护visited状态, 注意记得每一轮清零 */
int g_visited[1000] = { 0 };

void Dfs(int** rooms, int currRoom, int* roomsColSize)
{
	/* 退出条件：当前房间里没有钥匙或者节点都已经被访问过 */
	if (g_visited[currRoom] == 1) {
		return;
	} else {
		g_visited[currRoom] = 1;
	}

	if (roomsColSize[currRoom] == 0) {
		return;
	} else {
		for (int loop = 0; loop < roomsColSize[currRoom]; loop++) {
			Dfs(rooms, rooms[currRoom][loop], roomsColSize);
		}
	}
	return;
}

bool canVisitAllRooms(int** rooms, int roomsSize, int* roomsColSize) {
	int sum = 0;
    memset(&g_visited, 0, sizeof(g_visited));
	/* 使用DFS的做法 */
	Dfs(rooms, 0, roomsColSize);

	for (int k = 0; k < roomsSize; k++) {
		if (g_visited[k] == 1) {
			sum++;
		}
	}
	if (sum == roomsSize) {
		return true;
	} 
	return false;
}

链接：https://leetcode-cn.com/problems/keys-and-rooms/solution/dfs-cyu-yan-by-code_is_future/

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

中序遍历

//方法二：迭代法
//1,遍历节点A，将节点压入栈中，
//2,遍历A的左支，
//3,A出栈，访问A
//4,遍历A的右支
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int     iMax        = 100;
    int     iTop        = 0;
    int*    pRet        = NULL;
    int     iRetSize    = 0;

    struct TreeNode*    pTmp    = root;
    struct TreeNode*    pStrTreeBuf[iMax];       //建立节点指针数组，模拟栈保存节点

    pRet = (int*)malloc(sizeof(int) * iMax);
    memset(pRet, 0x00, sizeof(int) * iMax);

    while((pTmp != NULL) || (iTop != 0))
    {
        while(pTmp != NULL)
        {
            //1,遍历节点，将检点压入栈中
            pStrTreeBuf[iTop] = pTmp;
            iTop += 1;

            //2,遍历左支
            pTmp = pTmp->left;
        }

        //3,出栈，访问节点
        iTop -= 1;
        pTmp = pStrTreeBuf[iTop];
        pRet[iRetSize] = pTmp->val;
        iRetSize += 1;

        //4,遍历右支
        pTmp = pTmp->right;
    }

    //5,返回
    *returnSize = iRetSize;
    return pRet;
}

链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/chun-cdi-gui-fa-die-dai-fa-94er-cha-shu-de-zhong-x/

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

前、中、后序遍历

void PreOrder(struct TreeNode *root, int *ret, int *retIndex)
{
    if (root == NULL) {
        return;
    }
    /* 这行代码 ret[(*retIndex)++] = root->val; 放在这里，输出是前序遍历 */
    ret[(*retIndex)++] = root->val; //因为传入的是地址的值，所以这里要取指针
    PreOrder(root->left, ret, retIndex);
    /* 这行代码 ret[(*retIndex)++] = root->val; 放在这里，输出是中序遍历 */
    PreOrder(root->right, ret, retIndex);
    /* 这行代码 ret[(*retIndex)++] = root->val; 放在这里，输出是后序遍历 */
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int *preorderTraversal(struct TreeNode *root, int *returnSize)
{
    int retIndex = 0;
    int *ret = (int *)malloc(sizeof(int) * 100);
    memset(ret, 0, sizeof(int) * 100);

    PreOrder(root, ret, &retIndex);  //这里返回的是序列长度的地址，之后要传递给返回值的长度
    *returnSize = retIndex;

    return ret;
}

链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/cyu-yan-di-gui-100100-by-pandab-2/

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

二叉树的所有路径

• sprintf的使用

头文件：stdio.h

函数功能：格式化字符串，将格式化的数据写入字符串中。

函数原型：int sprintf(char *buffer, const char *format, [argument]…)

参数：

（1）buffer：是char类型的指针，指向写入的字符串指针；

（2）format：格式化字符串，即在程序中想要的格式；

（3）argument：可选参数，可以为任意类型的数据；

函数返回值：buffer指向的字符串的长度；

用处：

（1）格式化数字字符串：在这点上sprintf和printf的用法一样，只是打印到的位置不同而已，前者打印给buffer字符串，后者打印给标准输出，所以sprintf也可以用来将整型转化为字符串，比itoa效率高且如此地简便~比如：sprintf(buffer, “%d”, 123456);执行后buffer即指向字符串“123456”~

（2）连接字符：

#include<stdio.h>  
int main()  
{  
    char buffer[10];  
    char *a = “1234”;  
    char *b = “5678”;  
    sprintf(buffer, ”%s%s”, a, b);  
    printf(”%s\n”, buffer);  
    return 0;  
}

1
2
3
4
5
6
7
8
9
10
11

void get_path(char **array, struct TreeNode* root, int* returnSize, int *buf, int local)
{
    if (root == NULL) 
    {
        return;
    }
    if(!root->left && !root->right) 
    {
        //说明找到路了，把缓冲区的打印出来即可
        char *str = (char*)malloc(1024);
        int len = 0;
        for (int i = 0; i < local; i++) 
        {
            len += sprintf(str + len, "%d->", buf[i]);
        }
        sprintf(str + len, "%d", root->val);
        array[(*returnSize)++] = str;
    } 
    else 
    {
        // 把当前的值写进buf，层级+1，继续递归找路
        buf[local++] = root->val;
        get_path(array, root->left, returnSize, buf, local);
        get_path(array, root->right, returnSize, buf, local);
    }
}

/**
* Note: The returned array must be malloced, assume caller calls free().
*/
char ** binaryTreePaths(struct TreeNode* root, int* returnSize)
{
    char **ret = (char **)malloc(1024 * sizeof(char*));
    *returnSize = 0;
    int buf[1024] = {0};
    get_path(ret, root, returnSize, buf, 0);
    return ret;
}

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

前k个高频元素

int comp(const void*a,const void*b){
    return*(int*)a-*(int*)b;}

1
2
3

• const—表示常量，为了防止指针指向的内容被意外修改，设置为“只读”，即常量指针指向的区域不可修改。

先将变量a和b强制类型转换为int型指针，引用其中的值进行减法运算。void *a是一个空指针类型，可以存放任意类型的指针。

• 返回值—如果a > b，返回>0；如果a == b, 返回0；如果a < b，返回<0
  这里a和b的关系仅仅是逻辑上的，并不是值比较，所以排序的可以不仅是数字，还可以是字符。

https://leetcode-cn.com/problems/top-k-frequent-elements/solution/chashbiao-fa-fu-zhu-shi-by-zai-xia-dan-shen-wang/

//hash表，方法类似uthash，只是自己设定hash表格式，不使用库函数
struct node{
    int key;        //键值
    int count;      //数据
};

//hash表排序回调函数
int cmp(struct node* a,struct node* b)
{
    return b->count - a->count;
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    int i = 0,j = 0;
    struct node* hash = (struct node*)calloc(numsSize,sizeof(struct node));
    int index = 0;

    for(i = 0;i < numsSize;i++)
    {   
        //遍历哈希表查找是否存在相同键值的节点
        for(j = 0;j < index;j++)
        {
            if(nums[i] == hash[j].key)
            {
                hash[j].count++;
                break;
            }
        }
        if(j == index)
        {   
            //如果不存在相同键值的节点，则在哈希表中创建一个新节点
            hash[index].key = nums[i];
            hash[index++].count = 1;
        }
    }

    //哈希表按照从大到小的顺序进行排序
    qsort(hash,index,sizeof(struct node),cmp);
    //遍历哈希表前k个值，用键值替代数组中的值
    for(i = 0;i < k;i++)
    {
        nums[i] = hash[i].key;
    }
    *returnSize = k;

    return nums;
}

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

• calloc()

分配所需的内存空间，并返回一个指向他的指针。malloc不会设置分配的内存为0，但calloc会。

void *calloc(size_t nitems, size_t size)

1
2

参数

• nitems – 要被分配的元素个数。
• size – 元素的大小。

void *malloc(size_t size)

1
2

参数

• size – 内存块的大小，以字节为单位。

组合

核心思想是递归法，逻辑清楚，但抽象度很高

/方法一：回溯法
//1,结束条件，排列了K个数
//2,回溯处理：下层节点只能使用上层节点未使用过的整数

//优化一：回溯处理循环时减少循环次数(n - k + index + 1)

//函数一：求组合的数量
int getMaxComBineNum(int n, int k){
    int         iRet        = 0;
    int         i           = 0;
    long int    iTmp1       = 1;
    long int    iTmp2       = 1;

    for (i = 0; i < k; i++)
    {
        iTmp1 *= n - i;
        iTmp2 *= i + 1;
    }
    iRet = iTmp1 / iTmp2 + 1;
    return iRet;
}

//函数二：回溯函数
//1,val传入上一层的代入值，下一层只用后面的数字
//2,index 作为回溯函数下标，控制回溯层数
void backTrackCombine(int** pRet, int n, int k, int* pColSize, int* pRetNum, int val, int index){
    int     i       = 0;
    int     j       = 0;
    if (NULL == pRet[*pRetNum])
    {
        pRet[*pRetNum] = (int*)malloc(sizeof(int) * (k + 1));
        memset(pRet[*pRetNum], 0x00, sizeof(int) * (k + 1));
    }

    //1,结束条件
    if (index == k)
    {
        pColSize[*pRetNum] = k;
        *pRetNum += 1;
        pRet[*pRetNum] = (int*)malloc(sizeof(int) * (k + 1));
        memcpy(pRet[*pRetNum], pRet[(*pRetNum) - 1], sizeof(int) * (k + 1));
        return;
    }

    //2,回溯处理
    for (i = val + 1; i <= (n - k + index + 1); i++)
    {
        pRet[*pRetNum][index] = i;
        backTrackCombine(pRet, n, k, pColSize, pRetNum, i, index + 1);
    }

    return;
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
    int**       pRet        = NULL;
    int*        pColSize    = NULL;
    int         iMax        = 0;
    int         iRetNum     = 0;

    //1,计算组合数量，并初始化指针
    iMax = getMaxComBineNum(n, k);

    pRet = (int**)malloc(sizeof(int*) * iMax);
    memset(pRet, 0x00, sizeof(int*) * iMax);
    pColSize = (int*)malloc(sizeof(int) * iMax);
    memset(pColSize, 0x00, sizeof(int) * iMax);

    //2,回溯处理
    backTrackCombine(pRet, n, k, pColSize, &iRetNum, 0, 0);

    //3,返回
    *returnSize = iRetNum;
    *returnColumnSizes = pColSize;
    return pRet;
}

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

回溯法

选优搜索法，按照选优条件深度优先搜索。当发现某一步不是最优，就退回一步。

组合总和II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

题解：

①首先需要对candidates集合进行升序排列。这是因为排列之后，如果遇到某个集合里面的元素candidates[i]大于我们的目标值target,那么直接结束本次尝试，进行下一次回溯。便于处理，减少回溯次数。

②在回溯的过程中，建立一个临时的list集合temp，将当前处理的元素candidates[i]先加入temp中，加进去之后，target - candidates[i]；结束回溯的条件就是target = 0，当temp满足和为target的时候，代表他是一个解，因此加入res集合中。起到累加计算和的过程。

③在这道题中还有一个限制条件，就是不能有重复的解，因此要对回溯进行“剪枝”操作，因此在加入res集合之前，判断这个解是否已经在res中了，因此：temp not in res 时，作为一个解加入res。在第一次的代码中没有注意这一点，就出现了重复的解。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return []
        candidates.sort()
        n=len(candidates)
        res=[]
        def backtrace(i,temp,target):
            if target==0 and temp not in res:
                res.append(temp)
                return
            if i==n or target<candidates[i]:
                return 
            for j in range(i,n):
                backtrace(j+1,temp+[candidates[j]],target-candidates[j])

        backtrace(0,[],target)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

平衡二叉树

#define MAX(a,b) (a) >= (b) ? (a) : (b)
int nodeDepth(struct TreeNode* root)
{
    if (root == NULL)
        return 0;
    int leftDept = nodeDepth(root->left);
    int rightDept = nodeDepth(root->right);
    return MAX(leftDept + 1, rightDept + 1);
}
bool isBalanced(struct TreeNode* root){
    if (root == NULL)
        return true;
    
    return abs(nodeDepth(root->right) - nodeDepth(root->left)) <= 1 && isBalanced(root->right) && isBalanced(root->left);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

卡牌分组

int gcd(int x,int y){
    if(y==0) return x;
    return gcd(y,x%y);
}
//方法1 哈希表
bool hasGroupsSizeX(int* deck, int deckSize){
    int * arr = (int *)calloc(10000,sizeof(int));
    for(int i=0;i<deckSize;i++){
        arr[deck[i]]++;
    }
    int simnum=arr[0];
    for(int i=0;i<10000;i++){
        if(arr[i]==0) continue;
        if(arr[i]==1) return false;
        simnum=gcd(simnum,arr[i]);
        if(simnum==1) return false;
    }
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

交替位二进制数

给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。

bool hasAlternatingBits(int n){
    int pre=n&1;
    n>>=1;
    int a;
    while(n){
        a=n&1;
        if(pre==a) return false;
        else {
            n>>=1;
            pre=a;
        }
    }
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

字符串相加

char * addStrings(char * num1, char * num2){
int len1=strlen(num1);
int len2=strlen(num2);
int len3=fmax(len1,len2)+2;                //申请内存为最长字符串长度+2
//char * str1=(char*)malloc(sizeof(char)*(len3));
 char* str1 = calloc(len3,sizeof(char));   
for(int j=len3-2;j>=0;j--){
    len1--;
    len2--;
    if(len1<0 && len2<0) break;          
    if(len1>=0) str1[j]+=num1[len1]-'0';  
    if(len2>=0) str1[j]+=num2[len2]-'0';
    if(str1[j]/10>0){                     //这一位需要进位的情况
        str1[j-1]+=str1[j]/10;
        str1[j]=str1[j]%10;
    }
    str1[j]+='0';                         //数字转化为字符
}
if(str1[0]==0) return str1+1;             //第一为为0的话，就返回第二位
else str1[0]+='0';
return str1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

买卖股票的最佳时机 II

• 贪心算法：在每一步都做出当时看起来最佳的选择，即它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关）

解题思路：如果明天涨，利润=prices[明天]-prices[今天]

int maxProfit(int* prices, int pricesSize){
int max=0;
for(int i=0;i<pricesSize-1;i++){
    if(prices[i+1]>prices[i]){
        max+=prices[i+1]-prices[i];
    }
}
return max;
}

1
2
3
4
5
6
7
8
9
10

可被5整除的二进制前缀

给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。

返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。

• 示例 1：

输入：[0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。

bool* prefixesDivBy5(int* A, int ASize, int* returnSize){
int temp=0;
bool* ret=(bool*)malloc(ASize*sizeof(bool));
for(int i=0;i<ASize;i++){
    temp=(temp<<1)+A[i];       //利用左移一位操作
    temp = temp % 5;           //temp没有累加，而是保留上一次整除的值，这样可以提升运行时间
    if (temp ==0){
        ret[i]=true;
    }
    else{
        ret[i]=false;
    }
}
*returnSize=ASize;
return ret;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

不用加号的加法

//位运算，利用了异或和与的特性，异或操作和加法操作的区别在于异或操作在二进制状态下两个数同1不进位，只是置为0，其他均相同，那么使用与运算计算进位值，补齐异或操作的缺点即可，与运算中只有两个数二进制位同1才置为1，所以只要两个数相与，二进制数为1的地方就是需要进位的地方，再左移一位，得到的值就是异或操作模拟加和操作时需要的进位数，将其和结果异或，不断重复上述操作直到进位值为0返回结果
int add(int a, int b){
    while(b){
        //特别注意，由于题目中提到了可能为负数，int型的第32位为符号位，如果负数与操作后左移，会导致溢出，所以要将与运算结果先转换为无符号，再进行左移操作
        int diff = (unsigned int)(a & b) << 1;
        a = a ^ b;
        b = diff;
    }

    return a;
}

1
2
3
4
5
6
7
8
9
10
11
12

选择排序

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
void selection_sort(int arr[], int len)
{
	int i, j;
	for (i = 0; i < len - 1; ++i)
	{
		int min = i;
		for (j = i + 1; j < len; ++j)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}

		}
		swap(&arr[min], &arr[i]);
	}
}
int main()
{
	int a[] = { 1, 5, 3, 2, 4 };
	int len = (int)sizeof(a) / sizeof(*a);
	//int len =sizeof(a) / sizeof(*a);
	selection_sort(a, len);
	for (int i = 0; i < len; i++)
		printf("%d\n", a[i]);
	return 0;
}

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

转为小写字母

char * toLowerCase(char * str){
	if (str == NULL){
		return NULL;
	}
	int a = strlen(str);
	char *res = (char*)malloc((a + 10)*sizeof(char));
    //char *res=calloc(strlen(str)+1,sizeof(char));   //也可以不加‘\0’结束符，直接用calloc可以初始化
	for (int i = 0; i<a; i++){
		if (str[i] >= 65 && str[i] <= 90){
			res[i] = str[i] + 32;
			//printf("%s", res[i]);
		}
		else{
			res[i] = str[i];
		}
	}
	res[a] = '\0';             //要加一个结束符，负责会出现乱码
	printf("%s", res);
	return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

图

冗余连接II

• 并查集详解 https://blog.csdn.net/qq_41593380/article/details/81146850

在一些有N个元素的集合应用问题中，在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，期间要反复查找一个元素在哪个集合中。如果用正常的数据结构的话，空间和时间复杂度会较高。

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

int pre[2001]={0};
int find(int root){ //找根节点
    int son=root,tmp;
    while(root!=pre[root])   root=pre[root]; //当前节点非根节点，就向上找根节点
    while(son!=root){   //当前节点到根节点前一个结点都直接连接到根节点（压缩路径）
        tmp=pre[son];
        pre[son]=root;
        son=tmp;
    }
    return root;
}

void unionSet(int root1,int root2){ //注意union是关键字，不能直接用
    int x=find(root1);
    int y=find(root2);
    if(x!=y)    pre[x]=y;   //合并根节点
    return;
}

int* findRedundantDirectedConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize){
    int *ret=(int*)malloc(2*sizeof(int));
    for(int i=0;i<edgesSize+1;i++)  pre[i]=i;
    int x,y;
    for(int i=0;i<edgesSize;i++){
        x=find(edges[i][0]);
        y=find(edges[i][1]);
        if(x!=y)    unionSet(edges[i][0],edges[i][1]); //不同根，合并i两个节点的根节点
        else{   //返回同根最后的边
            ret[0]=edges[i][0];
            ret[1]=edges[i][1];
        }
    }
    *returnSize=2;
    return ret;
}

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

最大三角形面积

• inline

为解决一些频繁调用的小函数大量消耗空间（栈内存）的问题，引入了inline修饰符，表示为内联函数。在系统下，栈空间是有限的，假如频繁大量的使用就会造成因栈空间不足而导致程序出错的问题，如，函数的死循环递归调用的最终结果就是导致栈内存空间枯竭。

inline的使用时有所限制的，inline只适合函数体内部代码简单的函数使用，不能包含复杂的结构控制语句例如while、switch，并且不能内联函数本身不能是直接递归函数（即，自己内部还调用自己的函数）。

• 海伦公式

求三角形面积：

p=(a+b+c)/2;

s=sqrt(p*(p-a) *(p-b) *(p-c));//a、b、c是三个边长

inline double getLength(int *point1,int *point2){
     return sqrt(      (point1[0]-point2[0])*(point1[0]-point2[0]) + 
                       (point1[1]-point2[1])*(point1[1]-point2[1])                            
                );
}

double largestTriangleArea(int** points, int pointsSize, int* pointsColSize){
    int i,j,k;
    double a;
    double b;
    double c;
    double p;
    double s;
    double ret;
    for(i = 0; i < pointsSize - 2; i++) {
          for(j = i + 1; j < pointsSize - 1; j++) {
             for(k = j + 1; k < pointsSize; k++) {
                a = getLength(points[i],points[j]);
                b = getLength(points[i],points[k]);
                c = getLength(points[k],points[j]);
                p = (a+b+c)/2;
                s = sqrt(p*(p-a)*(p-b)*(p-c));
                ret = s > ret?  s:ret;
                //ret=ret>s?ret:s;            //写成这样用例不通过
            }
        }
    }
    return ret;
}

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

三角形的最大周长

int cmp (const void *a,const void *b) {
    return *(int *)a - *(int *)b;
}
int largestPerimeter(int* A, int ASize) 
{
    qsort(A, ASize, sizeof(int), cmp);
    for (int i = ASize - 1; i >= 2; i--) {
        if (A[i - 2] + A[i - 1] > A[i]) {
            return A[i] + A[i - 1] + A[i - 2];//不能在最后在输出，因为是排过序的所以最大的会替换掉之前的
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

仅仅反转字母

char * reverseOnlyLetters(char * s)
{
    int len = strlen(s), i, j = 0;
    char* stk = (char*)malloc(sizeof(char) * len);
    char* p = (char*)malloc(sizeof(char) * (len+1));
    int top = -1;
    for(i = 0 ; i < len; i++){
        if(isalpha(s[i])){
            stk[++top] = s[i];
        }
    }
    for(i = 0; i < len; i++){
        if(isalpha(s[i])){
            p[j++] = stk[top--];
        }
        else{
            p[j++] = s[i];
        }
    }
    p[j] = '\0';
    free(stk);  
    return p;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二叉搜索树转累加树

• 二叉搜索树

或者是一棵空树，或者：若他的左子树不空，则左子树上所有结点的值均小于它的根节点的值；若右子树不空，则右子树上的所有结点大于根节点的值；它的左右子树也分别为二叉排序树。

• return；——直接返回，不带任何返回参数。适用于void类型的函数
• return 0；——就是没有返回值

解题思路：反向中序遍历

struct TreeNode* dfs(struct TreeNode* proot,int* sum){
    if(proot==NULL)
    return;
    dfs(proot->right,sum);
    *sum+=proot->val;
    proot->val=*sum;
    dfs(proot->left,sum);
    return proot;
}

struct TreeNode* convertBST(struct TreeNode* root){
int sum=0;
dfs(root,&sum);
return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

分糖果

1. 数组的长度为[2, 10,000]，并且确定为偶数。
2. 数组中数字的大小在范围[-100,000, 100,000]内。

• 桶排序

划分多个范围相同的区间，每个子区间自排序，最后合并。

int distributeCandies(int* candies, int candiesSize)
{
    int ret=0,candies_count[200000+1]={0};    //根据数组长度设定大小

    for(int i=0;i<candiesSize;i++)
    {
        if(candies_count[candies[i]+100000]==0) //这里加10万是为了将负数转化为正数，从而和定义的数组匹配，以防止溢出
        {
            ret+=1;
        }
        candies_count[candies[i]+100000]+=1;
    }

    if(candiesSize/2>ret)
    {
        return ret;
    }
    
    return candiesSize/2;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

平衡二叉树

#define max(a,b) a>b?a:b
int treehigh(struct TreeNode* root)
{
    if(!root)
        return 0;
    int S1 = 1 + treehigh(root->left);
    int S2 = 1 + treehigh(root->right);
    return max(S1,S2);
}


bool isBalanced(struct TreeNode* root){
    if(!root)
        return true;
    int h1 = treehigh(root->left);
    int h2 = treehigh(root->right);
    if(h1 - h2 > 1 || h2 - h1 > 1)
        return false;

    return isBalanced(root->left) && isBalanced(root->right);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

从中序和后序遍历序列构造二叉树

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    if(postorderSize == 0 || inorderSize == 0)return NULL;      //叶子结点的左右子树为空

    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = postorder[postorderSize-1];                     //根结点值为后序遍历最后一位

    int left;
    for(left=0;left<inorderSize;left++){
        if(inorder[left] == root->val)break;                    //找到中序列表中的根结点，其索引为左子树结点个数
    }
    int right = inorderSize - left - 1;                         //计算右子树结点个数

    root->left = buildTree(inorder,left,postorder,left);        //递归构建左、右子树
    root->right = buildTree(inorder+left+1,right,postorder+left,right);

    return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

种花问题

bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n){
    short gap=1,i;
    for(i=0;i<flowerbedSize;i++){
        if(flowerbed[i]==0) gap++;
        else{
            n=n-(gap-1)/2;
            gap=0;
        }
    }
    if(gap!=0) n=n-gap/2;
    return n<=0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

二叉搜索树的公共祖先

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if(root == NULL){
        return NULL;
    }
    if(q->val > root->val && p->val > root->val){
       return lowestCommonAncestor(root->right , p, q);
    }else if(q->val < root->val && p->val < root->val){
       return lowestCommonAncestor(root->left , p, q);
    }
    return root;
}

1
2
3
4
5
6
7
8
9
10
11
12

缀点成线

bool checkStraightLine(int** coordinates, int coordinatesSize, int* coordinatesColSize){
    if (coordinates <= 2) return true;
    int a = coordinates[1][1] - coordinates[0][1];
    int b = coordinates[0][0] - coordinates[1][0];
    int c = coordinates[1][0]*coordinates[0][1] - coordinates[0][0]*coordinates[1][1];
    int i = 0;
    for (i = 2; i < coordinatesSize; i++){
        if ((a*coordinates[i][0] + b*coordinates[i][1] + c) != 0) return false;
    }
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12

比较含退格的字符串

#define MAXSTR 201
void Pushstr(char* str, char** top, char* stack)
{
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] == '#' && *top == stack) {
            continue;
        }
        if (str[i] == '#') {
            (*top)--;
            **top = '\0';
        } else {
            **top = str[i];
            (*top)++;
        }
    }  
}
bool backspaceCompare(char * S, char * T)
{
    char stackS[MAXSTR] = {0};
    char stackT[MAXSTR] = {0};
    char* topS = stackS;
    char* topT = stackT;
    Pushstr(S, &topS, stackS);
    // printf("%s\n",stackS);
    Pushstr(T, &topT, stackT);
    // printf("%s\n",stackT);
    if (!strcmp(stackS, stackT)) {
        return true;
    }
    return false;
}

char* BackSpace(char *s) 
{
    char *res = (char*)malloc(sizeof(char) * (strlen(s) + 1));
    memset(res, 0, sizeof(char) * (strlen(s) + 1));
    int index = 0;
    for (int i = 0; i < strlen(s); ++i) {  // 利用栈  遇到#回退  遇到字母入栈
        if (s[i] == '#') {
            if (strlen(res) == 0) {
                continue;
            } else {
                res[--index] = '\0';
            }
        } else {
            res[index++] = s[i];
        }
    }
    res[index] = '\0';  // 字符串最后加上'/0'
    return res;
}

bool backspaceCompare(char * S, char * T){
    char *s = BackSpace(S); // 回退空格
    char *t = BackSpace(T);
    int i = 0;
    while (s[i] != '\0' && t[i] != '\0') {
        if (s[i] != t[i]) {
            return false;
        }
        i++;
    }
    if (s[i] == '\0' && t[i] == '\0') {
        return true; // 完全相等 返回true
    }
    return false;
}

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
60
61
62
63
64
65
66
67
68

填充每个节点的下一个右侧节点指针II

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        """
        思路 :
            1:  从左往右层序遍历
            2:  if root 则next = root
            3：  else :下一层
        需要一个栈来存放当前节点，节点顺序 [左左->左右->右左->右右]
        :param root:
        :return:
        """
        if not root: # 排除root是空的情况
            return root
        l = [root]  # 当前栈
        
        prestark = []  # 当前层级
        while l:
            pre = l.pop(0)
            
            if pre.left:
                prestark.append(pre.left)
            if pre.right:
                prestark.append(pre.right)
            if not l:  # 当前栈遍历完了，开始串next
                
                for i in range(len(prestark) - 1):
                    prestark[i].next = prestark[i + 1]
                l += prestark # 重置下一层
                prestark = []  # 重置当前层
        return root

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

七进制数

char * convertToBase7(int num){
    if(num==0) return "0";
    char * retstr=malloc(12*sizeof(char));
    memset(retstr,0,12*sizeof(char));
    if(num<0){
        strcat(retstr,"-");           //将后边的字符串拼接到前边的字符串后
    }
    num=abs(num);
    char arr[12];
    memset(arr,0,12*sizeof(char));
    int i=0;
    while(num>0){
        arr[i]=(char)(num%7+'0');
        num=num/7;
        i++;
    }
    i--;
    for(;i>=0;i--){
        strncat(retstr,arr+i,1);  //将后边的字符串按给出的长度（参数3）拼接到前边的字符串后
    }
    return retstr;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

计数质数

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

int countPrimes(int n) {
    unsigned char *map = (unsigned char *)calloc(n, sizeof(unsigned char));
    int sq = (int)sqrt(n);
    for (int i = 2; i <= sq; i++) { // i 不需要遍历到 n，而只需到 sqrt(n) 即可
        if (map[i] == 0) {
            for (int j = i * i; j < n; j += i) { // 把 i 的整数倍都标记排除
                map[j] = 1;
            }                
        }
    }
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (map[i] == 0) {
            count++;
        }
    }
    return count;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二叉树递归插入

struct TreeNode* insertIntoBST(struct TreeNode* root, int val){
    if(root==NULL) {
        struct TreeNode* node = malloc(sizeof(struct TreeNode));
        node->val = val;
        node->left = NULL;
        node->right = NULL;
        return node;
    }

    if(root->val > val) {
        root->left = insertIntoBST(root->left, val);
    }

    if(root->val < val) {
        root->right = insertIntoBST(root->right, val);
    }

    return root;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

指针

• 指针就是内存地址，指针变量就是存储地址的变量

• 指针变量定义时，数据类型并不是指针变量的数据类型，而是其所指目标对象的数据类型

• &取地址运算符，p=&a—表明得到整型变量a的地址，并把该地址存入指针变量p中

• *间接运算符。星号如果不是在指针变量定义时出现，而是在某条语句的某个指针变量前出现，那么这个星号（ *）就是间接运算符，即取指针所指向变量的值。

• 指针变量空间的大小。定义指针变量后，系统会为该指针变量分配存放一个地址值的存储单元，存储单元的大小与该指针所指向内存空间的类型无关，一般情况下，32位系统分配4个字节，64位系统分配8个字节。可以用sizeof计算指针变量所占空间大小。

• 指针变量更多地应用于函数形参，因为C语言是传参调用的，如果函数形参是指针类型的，函数调用时，函数实参就会是变量的地址，所以函数形参就可以指向主调函数中的变量，再利用间接运算符操作主调函数中的变量。

空指针和void指针

• 空指针

空指针常量是一个值为0的整数常量表达式，NULL被定义为空指针常量。

空指针不指向任何空间，所以不能用间接运算符（*）取值。

• void指针

void指针是类型void*的指针，即未确定类型的指针，void *被称为万能指针。

若想声明一个可以接受任何类型指针参数的函数，可以将所需的参数设定为void*参数。

const指针常量

• 常量指针

int x=5,y=6;
const int *ptr=&x;     
*ptr=10;			   //错误，不能通过变量指针修改所指内容
x=10;				   //正确
ptr=&y;				   //正确，因为ptr本身是变量，可以指向其他整型变量

1
2
3
4
5
6

常量指针经常出现在函数形参中，避免在函数里通过指针改变他所指变量的值。

• 常量指针变量

int x=5,y=6;
int * const ptr=&x;     
*ptr=10;			   //正确，可以通过ptr修改指向的数据				   
ptr=&y;				   //错误，不能修改ptr的值，因为ptr本身是常量

1
2
3
4
5

• 指针常量

int x=5,y=6;
const int * const ptr=&x;     
*ptr=10;			   //错误，不能通过常量指针修改所指内容				   
ptr=&y;				   //错误，不能修改ptr的值，因为ptr本身是常量

1
2
3
4
5

指针与数组

int *p=a;
p--;(p++;)    //p++不是把p的值增1，而是让p指向数组的下一个单元

1
2
3

• 数组指针

一维数组指针的定义形式为：

int (*p) [10];

1
2

#include <stdio.h>
int main(){
  int a[5][3]={{1,2,3},{4,5,6},{7,8,9},{10,11,12},{13,14,15}};
  int (*p)[3]=a;                    //定义一个一维数组指向第一行
  int sum=0;
  for(int i=0;i<5;i++){
      for(int j=0;j<3;j++){
          sum+=*(*p+j);
      }
      p++;						 //指向下一行
  }
  printf("sum=%d\n",sum);
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 指针数组

一维指针数组的定义：

int *ptr[10];

1
2

指针数组也适用于指向若干字符串，使字符串的处理更加灵活方便。

指向函数的指针

函数包括一系列的指令，当它经过编译后，在内存中会占据一块内存空间，该空间有一个首地址，指针变量可以存储这个地址。存储这个地址的变量就是函数指针。

double (*funcPtr) (double,double);  //(*funPtr)括号不能省略

1
2

qsort()的使用

数组

//完全初始化
int a[5]={1,2,3,4,5};
//省略长度的初始化
int a[]={1,2,3,4,5};
//不完全初始化,未被初始化元素的值为0
int a[5]={1,2,3};


1
2
3
4
5
6
7
8

数据存储与运算

数据类型与变量

• 常量

使用const关键字定义一个符号常量：

const  double PI=3.14159;
//或者预编译定义
#define PI 3.14159


1
2
3
4
5

• 变量

c语言习题

1. 若有定义语句int a=7;float x=2.5,y=4.7;则表达式x+a%3*(int)(x+y)%2/4的值为多少？

解答步骤如下：

x+a%3*(int)(x+y)%2/4

=2.5+7%3*(int)(2.5+4.7)%2/4 //将a,x,y的值带入

=2.5+1*7%2/4 //(int)(2.5+4.7)=(int)7.1=7

=2.5+7%2/4 //运算符bai优先du级相同，按照从左到右进行计算

=2.5+1/4 //%为取余运算符，7除以2余数是1

=2.5 //1/4是两个整型相除，最后得到的类型也是整型0

2.假设所有变量均为整型，则表达式(x=2, y=5, y++, x+y)的值是

这是逗号表达式，运算顺序为最后一个式子x+y的结果，y=++该式等价于y=y++,就是y自加1，因而y的值变为6，而x值没有改变，因而x+y的值为8

3.int a=12345;printf("%2d\n",a);输出结果是什么

输出结果仍为12345.虽然给定列宽为2，但是实际列宽比这大，系统会自动补充至实际输出列宽

4.以下叙述正确的是___ A___。

A．当输入数据时，必须指明变量的地址，例如，scanf("%f",＆a);
B．只有格式控制，没有输入项，也能正确输入数据到内存。例如，scanf(“m=%d,n=%d”);
C．当输入一个实型数据时，格式控制部分可以规定小数点后的位数，例如，scanf("%5.1f",＆a);
D．输入项可以是一个实型常量，例如，scanf("%f",7.5);

选项B中没有给出输入项；选项C中的格式字符指定了小数位数；选项D中的输入项为一个常量；以上均是错误的。

5.若变量已正确定义，语句“if(a>b) k=0; else k=1;”和下面哪个选项等价

A、k=(a>b)?1:0; B、k=a>b; C、k=a<=b; D、a<=b ? 0 : 1;

6.设变量定义为“int a, b;”，执行下列语句时，输入下列哪个选项，a和b的值都是10。

scanf(“a=%d, b=%d”,&a, &b)；

D、a=10, b=10

7.设a为整型变量，下列选项中不能正确表达数学关系“10＜a＜15”的C语言表达式是（A）

A.10＜a＜15

B.a11‖a12‖a13‖a14

C.a＞10&&a＜15

D.!(a＜=10)&&!(a＞=15)。

​