- 博客(10)
- 收藏
- 关注
RSS订阅原创 链表带环问题，解剖快慢指针
至于找入环节点，我们可以这样想：如果知道环的长度或者其整数倍，那么让快指针先走环的长度的距离，在让慢指针从头节点开始和快指针每次走一步，这样他们任何时刻的距离差就是环长，那么当慢指针到达入环的节点时，快指针刚好在环中转了一圈回到入口，这时他们相等，入口就找到了。这时会发现如果链表不带环，则直到快指针走到nullptr，慢指针处于链表中部，他们不会相遇。假设相遇时，慢指针走了k步，则快指针走了2k步，2k-k=k,k是多走的距离，也就是环长的整数倍，就相当于知道了环的长度。
2024-12-08 23:00:03
209
原创 结构体内存对齐，memmove与memcpy的区别
功能是把source位置开始的num个字节的数据拷贝到dest位置，而当这两个地址存在重叠时，memcpy可能达不到想要的效果。3. 结构体总⼤⼩为最⼤对⻬数（结构体中每个成员变量都有⼀个对⻬数，所有对⻬数中最⼤的）的。4. 如果嵌套了结构体的情况，嵌套的结构体成员对⻬到⾃⼰的成员中最⼤对⻬数的整数倍处，结构。体的整体⼤⼩就是所有最⼤对⻬数（含嵌套结构体中成员的对⻬数）的整数倍。2. 其他成员变量要对⻬到某个数字（对⻬数）的整数倍的地址处。对⻬数 = 编译器默认的⼀个对⻬数 与 该成员变量⼤⼩的较⼩值。
2024-12-05 23:35:00
302
原创 指针类型的意义
例如，int*的指针解引用得到自int*开始向后四个字节的空间，+1往后跳过四个字节的距离，char*指针解引用得到自char*开始向后1个字节的空间，+1往后跳过1个字节的距离。有了指针，我们就可以通过函数操作我们开的空间，因为函数传参是转值，会新开辟空间，在被调用函数中操作不影响主调函数，如果可以传地址，就可以在空间中为所欲为。数组arr中存放元素个数为n的一维数组，于是arr作为数组首元素的地址，它加a跳过一维数组的大小的a倍的范围，解引用拿到。当然，这段存放其他数据地址的空间也有属于自己的地址。
2024-12-03 21:51:46
351
原创 数组、简单函数
2.当arr被用作sizeiof的运算对象，此时的结果是整个数组的大小，单位是字节（Byte）。3.当用作decltype的参数，以及typeid的运算对象时，不会发生隐式类型转换。一个 除了1和它本身 ，再没有其他因子的数是素数，优化：偶数一定不是素数。的运算对象，此时结果是整个数组的地址，不是首元素地址。1. 当arr被用作。
2024-11-26 21:35:38
85
原创 用哨兵节点简化链表的插入、删除操作
加入哨兵节点后的插入操作：由于链表一定不为空，所以无需判断，只需要逐次遍历链表，找到尾节点，然后把新节点链入尾部。，如果为空，插入节点作为链表头节点返回。不为空，遍历链表至最后一个节点，tail->next=newnode;由于通常是单向链表，所以一般要保存要删除节点的上一个节点（由于头节点没有上一个节点，所以要单独处理），2.判断 要删除的节点 是否是头节点，若是，返回头节点的下一个节点。哨兵节点通常位于链表的头部，它的值没有任何意义。让上一个节点指向要删除节点的下一个节点。需要判断给的链表是否为空。
2024-11-23 10:28:30
188
原创 剑指offer 第九题 乘积小于k的连续子数组个数
主要是因为存在大量的重复计算,比如我们在遍历完区间[a,a+1,...,b]之后,i由a移动到a+1,这时,我们要继续遍历[a+1,b],即product*=j,会发现这个操作在上一次循环已经做过了,这就是问题所在,那么该如何避免重复呢?,所以可以放心的++i,这时product中记录的就是[i+1,j+1 ]的所有数字之积,一直向右移动i,直到product小于k,接着就到。这种思路在脑海里可以抽象成, 一个人在马路上从左往右走,每走一步,就转身回头看看,每走一步,就回头看看......
2024-11-15 23:06:41
205
原创 从O(n)到O(lgn)的经典优化思路
可以对上述思路做调整：当被除数大于除数，则比较被除数是否大于除数的2^1倍，如果是，则继续比较被除数是否大于除数的2^2倍，以此类推，直到被除数最多大于除数的2^k倍，则商累加2^k，被除数减去除数的2^k后，再依次与除数的2^1，2...做比较，重复上述过程，直到被除数小于除数（假设为正数）由于每次将除数翻倍，则时间复杂度为O(lgn)。和1相同，可以通过递归 x*pow(x,n-1)这种思路，由于每次将n减去1，时间复杂度仍然为O(n)，而且大家想想，求1的2147483647有多恐怖。
2024-11-01 15:15:40
318
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人