SnowMoon-Haoyu's Blog - 记录成长,变得更强!
剑指offer刷题9——搜索与回溯算法(简单)
剑指 Offer 32 - II. 从上到下打印二叉树 II 难度 简单 从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。 例如: 给定二叉树: [3,9,20,null,null,15,7], 12345 3 / \9 20 / \ 15 7 返回其层次遍历结果: 12345[ [3], [9,20], [15,7]] 提示: 节点总数 <= 1000 注意:本题与主站 102 题相同:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ 解题思路: 建议先做 面试题32 - I. 从上到下打印二叉树 再做此题,两题仅有微小区别,即本题需将 每一层打印到一行 。 I. 按层打印: 题目要求的二叉树的 从上至下 打印(即按层打印),又称为二叉树的 广度优先搜索(BFS)。BFS 通常借助 队列 的先入先出特性来实现。 II. 每层打印到一行: 将本层全部节点打印到一行,并将下一层全部节点加入队列,以此类推,即可分为多行打印。 代码 123456 ...
剑指offer刷题7——搜索与回溯算法(简单)
剑指 Offer 32 - I. 从上到下打印二叉树 难度 中等 从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。 例如: 给定二叉树: [3,9,20,null,null,15,7], 12345 3 / \9 20 / \ 15 7 返回: 1[3,9,20,15,7] 提示: 节点总数 <= 1000 思路 层序遍历。 特殊情况:树为空,直接返回一个空容器 算法流程: 将根节点入队,进入循环 队头元素出队的同时队头元素的左右非空节点入队,同时将队头元素的数值推入返回的容器内。 代码 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solutio ...
剑指offer刷题7——查找算法(中等)
剑指 Offer 50. 第一个只出现一次的字符 难度 简单 在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。 示例: 12345s = "abaccdeff"返回 "b"s = "" 返回 " " 限制: 10 <= s 的长度 <= 50000 思路 建立一个大小为 26 的数组统计字符串中各个字母出现的次数,遍历字符串,将第一个出现次数为1的字母输出,没有则输出空格’ ’ 代码 12345678910111213class Solution {public: char firstUniqChar(string s) { int CHAR[26] = {0}; int i; for( i = 0; i < s.size(); i++ ) CHAR[s[i]-'a']++; for( i = 0; i ...
剑指offer刷题6——查找算法(中等)
剑指 Offer 11. 旋转数组的最小数字 难度 简单 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。 示例 1: 12输入:[3,4,5,1,2]输出:1 示例 2: 12输入:[2,2,2,0,1]输出:0 注意:本题与主站 154 题相同:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/ 思路 解题思路: 为精简篇幅,本文将数组 numbers 缩写为 nums。 如下图所示,寻找旋转数组的最小元素即为寻找 右排序数组 的首个元素 nums[x] ,称 x 为 旋转点 。 排序数组的查找问题首先考虑使用 二分法 解决,其可将 遍历法 的 线性级别 时间复杂度降低至 对数级别 。 算法流程: 初始化: 声明 i, j 双指针分别指向 nums 数组左右两端; 循环二分: 设 m = (i + j) / 2为 ...
剑指offer刷题5——查找算法(中等)
剑指 Offer 04. 二维数组中的查找 难度 中等 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 示例: 现有矩阵 matrix 如下: 1234567[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]] 给定 target = 5,返回 true。 给定 target = 20,返回 false。 限制: 120 <= n <= 10000 <= m <= 1000 思路 若使用暴力法遍历矩阵 matrix ,则时间复杂度为 O(NM)O(NM) 。暴力法未利用矩阵 “从上到下递增、从左到右递增” 的特点,显然不是最优解法。 刚开始的想法是行内做二分,列内也做二分,每次排除四分之三的数据,然后发现等矩阵小了之后好像就不方便找了,写起 ...
剑指offer刷题4——字符串(简单)
剑指 Offer 05. 替换空格 难度简单152收藏分享切换为英文接收动态反馈 请实现一个函数,把字符串 s 中的每个空格替换成"%20"。 示例 1: 12输入:s = "We are happy."输出:"We%20are%20happy." 限制: 10 <= s 的长度 <= 10000 思路 建立一个大小为3*Size(保证足够用来替换)的新的字符串str,遍历s并复制进入str中,每次遇到空格就复制"%20",最后新建一个大小为替换后的字符数的字符串STR,把str中有效位复制进STR并返回 代码 1234567891011121314151617181920212223class Solution {public: string replaceSpace(string s) { int i,Size,j; Size = s.length(); string str(3*Size,'0'); ...
剑指offer刷题3——链表2(简单)
剑指 Offer 24. 反转链表 难度 简单 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 12输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL 限制: 10 <= 节点个数 <= 5000 1.迭代(双指针) 考虑遍历链表,并在访问各节点时修改 next 引用指向,算法流程见注释。 复杂度分析: 时间复杂度 O(N)O(N) : 遍历链表使用线性大小时间。 空间复杂度 O(1)O(1) : 变量 pre 和 cur 使用常数大小额外空间。 代码 123456789101112131415161718192021222324/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} ...
剑指offer刷题2——链表1(简单)
剑指 Offer 06. 从尾到头打印链表 难度 简单 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 示例 1: 12输入:head = [1,3,2]输出:[2,3,1] 限制: 10 <= 链表长度 <= 10000 通过次数277,964 提交次数369,505 思路 辅助栈法: 遍历整个链表,把所有元素压入堆栈中,最后把堆栈中的元素顺序弹出并存储到 Vector 容器中返回 算法流程: 入栈: 遍历链表,将各节点值 push 入栈。 出栈: 将各节点值 pop 出栈,存储于Vector并返回。 代码 12345678910111213141516171819202122232425262728/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class ...
剑指offer刷题1——栈与队列
剑指 Offer 09. 用两个栈实现队列 难度 简单 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 示例 1: 1234输入:["CQueue","appendTail","deleteHead","deleteHead"][[],[3],[],[]]输出:[null,null,3,-1] 示例 2: 1234输入:["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"][[],[],[5],[2],[],[]]输出:[null,-1,null,null,5,2] 提示: 1 <= values <= 10 ...
数据结构刷题笔记14
11-散列2 Hashing (25 分) The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be H(k**ey)=k**ey%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions. Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to b ...
数据结构刷题笔记13
11-散列1 电话聊天狂人 (25 分) 给定大量手机用户通话记录,找出其中通话次数最多的聊天狂人。 输入格式: 输入首先给出正整数N(≤105),为通话记录条数。随后N行,每行给出一条通话记录。简单起见,这里只列出拨出方和接收方的11位数字构成的手机号码,其中以空格分隔。 输出格式: 在一行中给出聊天狂人的手机号码及其通话次数,其间以空格分隔。如果这样的人不唯一,则输出狂人中最小的号码及其通话次数,并且附加给出并列狂人的人数。 输入样例: 123456413005711862 1358862583213505711862 1308862583213588625832 1808792583215005713862 13588625832//结尾无空行 输出样例: 1213588625832 3//结尾无空行 代码 本篇文章主要代码源自于陈越姥姥的课程里的小白专场 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596 ...
数据结构刷题笔记12
10-排序4 统计工龄 (20 分) 给定公司N名员工的工龄,要求按工龄增序输出每个工龄段有多少员工。 输入格式: 输入首先给出正整数N(≤105),即员工总人数;随后给出N个整数,即每个员工的工龄,范围在[0, 50]。 输出格式: 按工龄的递增顺序输出每个工龄的员工个数,格式为:“工龄:人数”。每项占一行。如果人数为0则不输出该项。 输入样例: 123810 2 0 5 7 2 5 2//结尾无空行 输出样例: 1234560:12:35:27:110:1//结尾无空行 这题取了个巧,都没排序,直接按照工龄从低到高且不为空顺序输出了 #include<stdio.h> #include<stdlib.h> int main() { int i, x, n; scanf("%d", &n); int s[51] = {0}; for(i = 0; i < n; i ++) { scanf("%d", &x); ...
数据结构刷题笔记11
09-排序2 Insert or Merge (25 分) According to Wikipedia: Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain. Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repea ...
CSAPP6——程序机器级表示2
汇编入门(二) x86-64 架构中的整型寄存器如下图所示(暂时不考虑浮点数的部分) 仔细看看寄存器的分布,我们可以发现有不同的颜色以及不同的寄存器名称,黄色部分是 16 位寄存器,也就是 16 位处理器 8086 的设计,然后绿色部分是 32 位寄存器(这里我是按照比例画的),给 32 位处理器使用,而蓝色部分是为 64 位处理器设计的。这样的设计保证了令人震惊的向下兼容性,几十年前的 x86 代码现在仍然可以运行! 前六个寄存器(%rax, %rbx, %rcx, %rdx, %rsi, %rdi)称为通用寄存器,有其『特定』的用途: %rax(%eax) 用于做累加 %rcx(%ecx) 用于计数 %rdx(%edx) 用于保存数据 %rbx(%ebx) 用于做内存查找的基础地址 %rsi(%esi) 用于保存源索引值 %rdi(%edi) 用于保存目标索引值 而 %rsp(%esp) 和 %rbp(%ebp) 则是作为栈指针和基指针来使用的。下面我们通过 movq 这个指令来了解操作数的三种基本类型:立即数(Imm)、寄存器值(Reg)和内存值(Mem)。 对于 mov ...
CSAPP5——程序机器级表示
从C到机器代码 机器代码就是处理器能够直接执行的字节层面上的程序,但是对于人类来说基本上是不可读的,所以把字节按照具体含义进行『翻译』,就成了人类可读的汇编代码。注意这里的用词是『翻译』而不是『编译』,可以认为汇编代码就是机器代码的可读形式。 C->可执行程序: C 语言代码(a.c)经过编译器的处理(gcc -0g -S)成为汇编代码(a.s) 汇编代码(a.s)经过汇编器的处理(gcc 或 as)成为对象程序(a.o) 对象程序(a.o)以及所需静态库(lib.a)经过链接器的处理(gcc 或 ld)最终成为计算机可执行的程序 先来看一段C代码及其经过汇编产生的代码 12345678// C 代码*dest = t;// 对应的汇编代码movq %rax, (%rbx)// 对应的对象代码0x40059e: 46 89 03 C 代码的意思很简单,就是把值 t 存储到指针 dest 指向的内存中。对应到汇编代码,就是把 8字节(也就是四个字, Quad words)移动到内存中(这也就是为什叫做 movq)。t 的值保存在寄存器 %rax 中,dest 指向的地 ...
avatar
🐟认真摸鱼中
雪月
本网站是我的个人博客,主要用于记录我个人学习的内容以及一些杂谈、心情记录、文摘等
前往小窝
公告栏
本网站是我的个人博客,主要用于记录我个人学习的内容以及一些杂谈、心情记录、文摘等
最新文章
小站资讯
文章数目 :
59
本站总字数 :
8.8w
本站访客数 :
本站总访问量 :
最后更新时间 :
空降评论复制本文地址
随便逛逛昼夜切换美化设置切换全屏打印页面