网站建设7个基本流程步骤有哪些,丰都网站建设联系电话,专业建设网站的,外包公司拖欠工资怎么办1. BM17 二分查找 要求#xff1a;给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中的 target#xff0c;如果目标值存在返回下标#xff08;下标从 0 开始#xff09;#xff0c;否则返回 -1。
输入#xff1a…1. BM17 二分查找 要求给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标下标从 0 开始否则返回 -1。
输入[-1,0,3,4,6,10,13,14],13
返回值6
说明13 出现在nums中并且下标为6 1.1 自己的整体思路
使用二分法先定义三个指针左指针右指针中间指针。比较中间指针对应数值与目标数值是否相等如果相等直接返回该点索引如果目标值大于中间值则移动左指针另其为中间指针加上1如果目标值小于中间值则移动右指针另其为中间指针减1。直到左指针大于右指针结束整个循环这时是没有找到与目标值对应的索引的。
#include stdbool.h
#include stdlib.h
int search(int* nums, int numsLen, int target ) {// write code hereint n_pre 0; //首指针位置int n_next numsLen - 1; //尾部指针位置int n_mid (n_pre n_next) / 2; //中间指针位置if (numsLen 0) { //数组为空的情况return -1;}while ( nums[n_mid] ! target ) { //中间值是否等于目标值if ( nums[n_mid] target) { //目标值在中间右侧n_pre n_mid 1; //更新左索引n_mid (n_pre n_next)/2; //更新中间索引}else {n_next n_mid - 1; //更新右索引n_mid (n_pre n_next)/2; //更新中间索引}if ( n_pre n_next ) { //左指针大于右指针,结束整个循环return -1;}}return n_mid;
}开始上面的结束条件写成了这样的了 if ( n_pre n_next ) { //没有找到最终两个索引会重合 会出现在右边的情况不是一直到最后都会重合的if (nums[n_pre ] target) {return n_pre ;}else {return -1;}}认为两个指针一定会重合只要判断重合时候的情况就能结束整个循环,但是未通过所有的测试。
1.2 其他的方法标准判断方法 判断条件是左索引是否大于右索引。
int search(int* nums, int numsLen, int target ) {// write code hereif(numsLen 0) return -1;int left0, rightnumsLen-1;while(leftright) {int mid left(right-left)/2;if(nums[mid]target) return mid;if(nums[mid]target) leftmid1;if(nums[mid]target) rightmid-1;}return -1;
}2. BM21 旋转数组的最小数字 要求有一个长度为 n 的非降序数组比如[1,2,3,4,5]将它进行旋转即把一个数组最开始的若干个元素搬到数组的末尾变成一个旋转数组比如变成了[3,4,5,1,2]或者[4,5,1,2,3]这样的。请问给定这样一个旋转数组求数组中的最小值。
输入[3,4,5,1,2]
返回值1这个题开始使用的分类讨论的情况情况太多了最后也没有写出来下面是参考大佬的写法 核心思想
1.计算中间位置 mid并与 right 指针所指向的元素进行比较 如果 rotateArray[mid] rotateArray[right]说明最小值在 mid 右侧将 left 更新为 mid 1。 如果 rotateArray[mid] rotateArray[right]说明最小值在 mid 左侧或就是 mid将 right 更新为 mid。 如果 rotateArray[mid] rotateArray[right]无法确定最小值在哪一侧但是可以排除 right 指针所指向的元素将 right 向前移动一位缩小搜索范围。 2. 循环继续直到 left 和 right 指针相邻或重合。最终right 指向的位置即为最小值所在位置。
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {int left0, rightrotateArrayLen-1;while(leftright) {int mid left(right-left)/2;if(rotateArray[mid]rotateArray[right]) leftmid1; //说明最小值在右边else if(rotateArray[mid]rotateArray[right]) rightmid; //说明最小值在左边else right--; //22212或者10111 //不能说明在左边还是右边但是肯定不是右值索引减去1再进行比较 //关注右边从右边出发}return rotateArray[right];
}3. BM23 二叉树的前序遍历 要求给你二叉树的根节点 root 返回它节点值的前序遍历。
输入{1,#,2,3}
返回值[1,2,3]3.1 自己的整体思路
使用二叉树的前序遍历方法递归完成二叉树元素的访问。这里访问二叉树的元素需要传一个变量接收数组的索引地址因为最后结果需要返回该索引值。
具体代码如下
#include assert.h
#include stdbool.h
#include stdio.h
#include stdlib.h
void visit_root(struct TreeNode* p ,int *arr, int *a){ //访问二叉树的元素存到数组中去*(arr *a) p-val;//arr[*a] p-val; //写成这样也是可以的// *a; //这样是错的优先级不一样的优先级要高(*a); //索引加1}void Preorder(struct TreeNode* p , int *arr, int *a){ //遍历二叉树if (p ! NULL) {visit_root(p , arr, a);Preorder(p-left, arr, a); //递归左子结点 //这行代码为空的时候才会运行到下一行Preorder(p-right, arr, a ); //递归右子结点}
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){//前序遍历 先根再左再右struct TreeNode* cur root; //接收根结点int* result (int *)malloc(100 * sizeof(int)); //申明一个100的空数组int a 0; //接收数组的索引int *i a; //接收a的地址Preorder(cur, result, i); //遍历二叉树 *returnSize *i; //必须给行号 卡了半天return result;
}3.2 大佬的方法
先判断二叉树有多少元素这样再动态申请多大的内存。遍历二叉树即可。
int TreeSize(struct TreeNode* root)
{if(rootNULL){return 0;}return TreeSize(root-left)TreeSize(root-right)1;
}
void preorder(struct TreeNode* root, int* a,int *i)
{if(rootNULL){return ;}a[*i]root-val;(*i);preorder(root-left,a,i);preorder(root-right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize )
{ int i0; int sizeTreeSize(root);int* a(int*)malloc(size*sizeof(int));preorder(root,a,i);*returnSizesize;return a;
}3.3 小结
3.3.1 malloc函数 mallocmemory allocation函数是用于动态分配内存的标准库函数之一。它是在程序运行时从堆heap中申请一块指定大小的内存空间以供程序使用。 malloc函数的原型如下 size要分配的内存空间的大小以字节为单位。通常使用sizeof运算符来计算要分配的空间大小以确保正确性。 返回值malloc函数返回一个void指针指向已分配内存块的起始地址。由于返回类型是void *您需要将这个通用指针转换为适当类型的指针然后才能访问和操作分配的内存。
void *malloc(size_t size);举例分配一个包含10个int元素的数组: int *array (int *)malloc(10 * sizeof(int));注意
malloc分配的内存块是未初始化的其中的值是不确定的。您应该确保在使用之前将其初始化。在使用完分配的内存后必须使用free函数释放它以避免内存泄漏。在调用malloc后应该检查返回的指针是否为NULL以防止内存分配失败。malloc函数分配的内存是在堆上与局部变量不同不会在函数退出后销毁需要手动释放。
3.3.2 *和的优先级
操作符的优先级比*操作符更高因此会先执行操作然后再执行*操作。下面的a是一个int型变量指针
*a; //指针会往下加1再去该地址里面的值地址变了
(*a); //取指针a对应的变量值把变量值加1地址没变
