焦作做网站推广,开发商破产了购房者怎么办,seo搜索引擎优化技术教程,网页链接怎么打开先做几个练习回顾一下前两个博的 顺序表:
1.给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度.不需要使用额外的数组空间,你必须在原地修改数组并使用O(1)额外空间的条件下完成.
给定 nums [0, 0, 1, 1 ,1, 2, 2, 3, 3, 4],…先做几个练习回顾一下前两个博的 顺序表:
1.给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度.不需要使用额外的数组空间,你必须在原地修改数组并使用O(1)额外空间的条件下完成.
给定 nums [0, 0, 1, 1 ,1, 2, 2, 3, 3, 4],函数应该返回新的长度5,并且原数组 nums 的前5个元素被修改为0, 1, 2, 3, 4 int removeDuplicates(int* nums, int numSize){ if (numsSize 1) return numsSize; int i 0, j 1, idx 0; while (j numsSize){ nums[idx] nums[i]; if (num[i] nums[j]){ //找到非重复元素的第一个位置 while (j numsSize nums[i] nums[j]) j; i j; j; } else{ i; j; } } if (i numsSize) nums[idx] num[i]; return idx; } 2.合并两个有序数组,给你两个有序整数数组nums1和nums2,请你将nums2合并到nums1中,使nums1成为一个有序数组.
说明:初始化nums1和nums2的元素数量分别为 m 和 n. 你可以假设nums1有足够的空间(空间大于或等于 mn)来保存nums2中的元素 实例:nums1 [1, 2, 3, 0, 0], m 3 nums2 [2, 5, 6], n 3 输出[1, 2, 2, 3, 5, 6]
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int* nums3 (int*)malloc(sizeof(int)* (m n)); int i 0, j 0, idx 0; //同时遍历 while (i m j n){ if (nums1[i] nums2[j]){ nums3[idx] nums1[i]; } else{ nums3[idx] nums2[j]; } } //判断 是否有剩余元素 if (i m) memcpy(nums3 idx, nums1 i, sizeof(int)* (m - i)); if (j n) memcpy(nums3 idx, nums2 j, sizeof(int)* (n - j)); memcpy(nums1, nums3, sizeof(int)* (m n)); free(nums3); }
换一种方法(插入):
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int i m - 1, j n - 1, idx m n - 1; while (i 0 j 0){ if (nums1[i] nums2[j]) nums1[idx--] nums1[i--]; else nums1[idx--] nums2[j--]; } //判断nums2中是否有剩余元素 if (j 0){ memcpy(nums1, nums2, sizeof(int)* (j 1)); } 3.旋转数组 给定一个数组,将数组中的元素向右移动k个位置,其中k是非负数
示例: 输入:[1, 2, 3, 4, 5, 6, 7] 和 k 3 输出:[5, 6, 7, 1, 2, 3, 4]
void reverse(int* num, int start, int end){ while (start end){ int tmp num[start]; num[start] num[end]; num[end] tmp; start; --end; } } void rotate(int* nums, int numsSize, int k){ k % numsSize; reverse(nums, 0, numsSize - k - 1); reverse(nums, numsSize - k, numsSize - 1); reverse(nums, 0, numsSize - 1); }
4.数组形式的整数加法
对于非负整数X而言,X的数组形式是每位数字按照从左到右的顺序形成的数组.例如,如果X 1231,那么其数组形式为[1, 2, 3, 1]
给定非负整数X的数组形式A,返回整数XK的数组形式
示例:输入:A [1, 2, 0, 0], k 34 输出:[1,2,3,4] 解释:1200 34 1234 int* addToArrayForm(int* A, int ASize, int k, int* returnSize){ //获取数字K的长度 int len 0; int tmp k; while (tmp){ len; tmp / 10; } //获取结果的最大长度 int arrLen len ASize ? len 1 : ASize 1; int* ret (int*)malloc(sizeof(int)* arrLen); //从个位开始相加 int end ASize - 1; //上一步进位 int step 0; int idx 0; while (end 0 || k 0){ //每一位的结果包含了进位 对应位的值 //首先加进位值 int curRet step; if (end 0) curRet A[end]; if (k 0) curRet k % 10; //处理进位 if (curRet 9){ step 1; curRet - 10; }
else step 0; //保存当前位的结果:逆序存放 ret[idx] curRet; //累加高位的值 --end; k / 10; } //判断最高位是否拥有进位 if (step 1) ret[idx] 1; //逆转 int start 0; end idx - 1; while (start end){ int tmp ret[start]; ret[start] ret[end]; ret[end] tmp; start; -- end; } //返回结果的长度 *returnSize idx; return ret; } 链表
链表的结构非常多样,以下情况组合起来就有八种链表结构:
1.单向,双向
2.带头,不带头
3.循环,非循环
虽然有这么多的链表结构,但我们实际最常用的还是两种结构:
1.无头单向非循环链表:结构简单,一般不会单独存数据.实际中更多是作为其他数据结构的子结构,如哈希桶,图的邻接表等.笔试面试中出现较多.
2.带头双向循环链表 写单链表的一些接口(和上一博一样写头插头删尾插尾删查找销毁等...只不过上个是顺序表这个是单链表)
#includestdio.h #includestdlib.h #includestring.h
typedef int LDataType; typedef struct listNode{ LDataType _data; struct listNode* _next; }listNode;
typedef struct list{ //存放第一个节点的地址 listNode* _head; }list;
void listInit(list* lst){ //初始化为空的链表 if (lst NULL) return; lst-_head NULL; }
listNode* creatNode(LDataType val){ listNode* node (listNode*)malloc(sizeof(listNode)); node-_data val; node-_next NULL; return node; } //尾插 void listPushBack(list* lst,LDataType val){ if (lst NULL) return; //第一种 空链表插入第一个数据 if (lst-_head NULL){ //创建节点 lst-_head creatNode(val); } else{ //遍历,找到最后一个节点 listNode* tail lst-_head; while (tail-_next ! NULL){ tail tail-_next; } //插入 tail-_next creatNode(val); }
} //尾删 void listPopBack(list* lst){ if (lst NULL || lst-_head NULL) return; struct listNode* tail lst-_head; struct listNode* prev NULL; //遍历 找到最后一个节点 while (tail-_next ! NULL){ prev tail; tail tail-_next; } //删除节点 free(tail); //修改指向 if (prev NULL) //删除的是头结点,更新头结点 lst-_head NULL; else prev-_next NULL; }
//头插 void listPushFront(list* lst, LDataType val){ if (lst NULL) return; //空的链表,插入第一个数据 if (lst-_head NULL) lst-_head creatNode(val); else{ listNode* node creatNode(val); listNode* next lst-_head; //head,node,next lst-_head node; node-_next next; } }
//头删 void listPopFront(list* lst){ if (lst NULL || lst-_head NULL) return; struct listNode* next lst-_head-_next; //释放头结点 free(lst-_head); lst-_head next; }
//中间位置的插入 void listInsertAfter(listNode* cur, LDataType val){ listNode* node creatNode(val); listNode* next cur-_next; //cur node next cur-_next node; node-_next next;
}
//删除cur节点的下一个节点 void listEraseAfter(listNode* cur){ //cur next next-next listNode* next cur-_next; if (next NULL) return; listNode* nextnext cur-_next; free(next); cur-_next nextnext; }
listNode* listFind(list* lst, LDataType val){ if (lst NULL || lst-_head NULL) return NULL; //从第一个节点开始遍历 listNode* cur lst-_head; while (cur){ if (cur-_data val) return cur; cur cur-_next; } return NULL; }
void listDestory(list* lst){ if (lst NULL || lst-_head) return; //从第一个节点释放 listNode* cur lst-_head; while (cur){ listNode* next cur-_next; //释放节点 free(cur); cur next; } lst-_head NULL; }
void test(){ list lst; listInit(lst); listPushFront(lst, 5); listPushFront(lst, 4); listPushFront(lst, 3); listPushFront(lst, 2); listPushFront(lst, 1); listNode* cur listFind(lst, 3); listInsertAfter(cur, 33); cur listFind(lst, 2); listEraseAfter(cur); }
void listDestory(list* lst){
} //void test(){ // list lst; // listInit(lst); // listPushBack(lst, 1); // listPushBack(lst, 2); // listPushBack(lst, 3); // listPushBack(lst, 4); // listPushBack(lst, 5); // // listPopBack(lst); // listPopBack(lst); // listPopBack(lst); // listPopBack(lst); // listPopBack(lst); // // listPushFront(lst, 5); // listPushFront(lst, 4); // listPushFront(lst, 3); // listPushFront(lst, 2); // listPushFront(lst, 1); // // listPopFront(lst); // listPopFront(lst); // listPopFront(lst); // listPopFront(lst); // listPopFront(lst); //}
int main(){ test(); system(pause); return 0; }
