- 博客(84)
- 收藏
- 关注
RSS订阅原创 AirSim搭建
在Windows下搭建AirSim环境1.安装Visual Studio这里题主安装的是2019，之前安装的。这里有个问题就是有些组件当时没勾选安装，现在要用怎么办，这里有个方法。找到Visual Studio Installer点击修改即可重新勾选需要的组件，这里题主都是默认，额外在单个组件中勾了一个2.安装虚幻引擎打开epic在左方选择虚幻引擎，在右方选择库，即可下载对应版本的虚幻引擎。3.下载编译AirSim源码打开Developer Command Prompt for
2022-03-27 19:01:47
1212
原创 剑指Offer30：连续子数组的最大和
输入一个长度为n的整型数组a，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)。思路：设dp[n]代表以当前元素为截止点的连续子序列（这个子序列必包括n）的最大和，当dp[n-1]大于0时，dp[n] = dp[n-1]加上当前数。public class Solution { public int FindGreatestSumOfSubArray(int[] array) { if(array == null || array.l
2021-10-14 16:25:41
134
原创 剑指Offer37：数字在升序数组中出现的次数
题目：给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数要求：空间复杂度 O(1)，时间复杂度 O(logn)思路：用二分查找找到k，找到k后，k的左右两边有可能还有k，再查看左右两边是否有k即可。import java.util.*;public class Solution { public int GetNumberOfK(int [] array , int k) { int index = Arrays.binarySearch
2021-10-14 14:47:00
151
原创 剑指Offer27：字符串的排列
题目：输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。数据范围：n < 10n<10要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)import java.util.*;public class Solution { public ArrayList<String> Permuta
2021-10-14 14:42:41
140
原创 剑指Offer61：序列化二叉树
题目：请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串
2021-10-13 22:44:29
57
原创 剑指Offer60：把二叉树打印成多行
题目：给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出。每一层输出一行。思路：层次遍历。import java.util.ArrayList;/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val;
2021-10-13 19:37:53
63
原创 剑指Offer58：对称的二叉树
题目：请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。思路：递归比较左边的左子树与右边的右子树、左边的右子树与右边的左子树。/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }
2021-10-13 19:16:39
52
原创 剑指Offer57：二叉树的下一个结点
题目：给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示解法：1.判断节点有没有右节点，如果有，则遍历右节点的左节点一直到底。2.如果没有右节点，我们就需要取出父节点，这里有两种情况，一是当前节点是父节点的左节点，那么返回父节点即可；二是当前节点是父节点的右节点，那么我们令当前节点等于父节点，直到当前节点为父节点
2021-10-13 16:28:48
39
原创 小数问题求解
题目：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。例子：[1,3,2,5]，1左边比1小的数没有；3左边比3小的数1；2左边比2小的数1；5左边比5小的数1，3，2；所以小和为 1+1+1+3+3 。思路：直接接很容易，就是遍历数的时候遍历之前的数，小于当当前数求和即可。这里可以转换思路，数的右边有多少大于当前数的，那么在小和里当前数就会出现多少次。例如：1右边比1大的数就是3，2，5，那么1在小和中会出现三次。我们利用归并排序的思想，我们把数不断切成两份，在排序的过程
2021-10-10 23:58:11
77
原创 求出现的奇数次的数（一个、两个）
异或运算：a ^ a = 0a ^ 0 = a异或运算与顺序无关a ^ b = b ^ a题目一一个数组只有一个数出现奇数次，其他都出现了偶数次，求这个数。思路：一直异或即可，因为出现偶数次的异或后都会变成0，最后就只剩出现奇数次的数。import java.util.*;public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); //接下来有n个数
2021-10-10 16:54:57
326
原创 剑指Offer39：平衡二叉树
题目：输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。样例解释：解法：在求左右子树深度的时候加个判定。public class Solution { private boolean isBalanced = true; public boolean
2021-10-06 00:13:30
60
原创 根据两种遍历结果求二叉树
要确定一个二叉树，必须知道中序遍历，然后再知道前序遍历和后序遍历一种即可，有前序和后序两种遍历结果无法确定二叉树。前序遍历、中序遍历确定二叉树前序遍历的第一个是根节点，根据根节点到中序遍历就能得到左右子树的划分，我们利用这个规则不断得到当前的根节点、左右子树，进行遍历。class Solution { public class TreeNode { public int val; public TreeNode left; p
2021-10-05 23:51:47
609
原创 剑指Offer26：二叉搜索树与双向链表
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示注意:1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继2.返回链表中的第一个节点的指针3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构4.你不用输出双向链表，程序会根据你的返回值自动打印输出解法：定义一个前置节点，当前节点的left等于前置节点，前置节点的right等于当前节点。public class
2021-10-05 23:19:32
64
原创 剑指Offer24：二叉树中和为某一值的路径
题目：输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。如二叉树root为{10,5,12,4,7},expectNumber为22解法：这里要注意的是路径必须是得到叶子节点的。我们用先序遍历，一直遍历到叶子节点且当target为0时满足条件，这时是的节点顺序就是符合条件的，这里要重新创建ArrayList对象，划分新的内存空间，因为结尾处要remove最后
2021-10-05 21:32:38
76
原创 操作系统1：常见知识总结
什么是操作系统？操作系统（Operating System，简称 OS）是管理计算机硬件与软件资源的程序，是计算机的基石。操作系统本质上是一个运行在计算机上的软件程序 ，用于管理计算机硬件和软件资源。 举例：运行在你电脑上的所有应用程序都通过操作系统来调用系统内存以及磁盘等等硬件。操作系统存在屏蔽了硬件层的复杂性。 操作系统就像是硬件使用的负责人，统筹着各种相关事项。操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。 内核是
2021-10-05 19:05:42
797
原创 剑指Offer23：二叉搜索树的后序遍历序列
题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜索树）解法：每颗子树都是搜索树，找到根节点（最后一位），左右子树分叉点，然后不断递归遍历即可。public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence == null || sequ
2021-10-04 16:03:30
42
原创 剑指Offer62：二叉搜索树的第k个结点
题目：给定一棵节点数为 n 二叉搜索树，请找出其中的第 k 小的TreeNode结点。解法：用中序遍历，遍历的第n的个节点就是第k小的。public class Solution { private TreeNode result; private int count; TreeNode KthNode(TreeNode pRoot, int k) { if(pRoot == null || k == 0) return null;
2021-10-04 13:45:55
60
原创 剑指Offer59：按之字形顺序打印二叉树
题目：给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）示例输入：{8,6,10,5,7,9,11}返回值：[[8],[10,6],[5,7,9,11]]解法：正常进行先序遍历，等到从右向左的时候把ArrayList逆转。import java.util.*;public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoo
2021-10-04 13:02:25
77
原创 剑指Offer42：和为S的两个数字
题目：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回两个数的乘积最小的，如果无法找出这样的数字，返回一个空数组即可。解法：使用双指针，一个指针指向元素较小的值，一个指针指向元素较大的值。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。如果两个指针指向元素的和 sum == target，那么得到要求的结果。如果 sum > target，移动较大的元素，使 sum 变小一些。如果 sum < target，移动
2021-10-03 21:17:19
44
原创 剑指Offer41：和为S的连续正数序列
题目：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?解法：假设输入sum=20，遍历的范围是1到 sum/2 + 1(因为最少要有两个数，所以不会超过sum/2，考虑到奇数的问题，加1)1.定义两个指针，左指针从1开始，右指针从2
2021-10-03 21:06:52
43
原创 剑指Offer33:丑数
题目：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。解法：我们可以维护三个list，分别是乘2得到的丑数，乘3得到的丑数，乘5得到的丑数，但这样复杂度较高，而且会得到重复的丑数。实际上每次我们只用比较3个数：用于乘2的最小的数、用于乘3的最小的数，用于乘5的最小的数。这样只需要维护三个指针，而不用维护三个数组。import java.util.*;public cl
2021-10-03 16:25:08
45
原创 剑指Offer32：把数组排成最小的数
题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。解法：关键在于如何判定两个数的大小位置。利用贪心的思想，整个数是最小的，那么任意两个数的排列也是较小的。所以判定方式为：若s1 + s2大于s2+s1，那么s1更大。import java.util.ArrayList;public class Solution { public String PrintMinN
2021-10-03 15:10:58
60
原创 剑指Offer31：整数中1出现的次数（从1到n整数中1出现的次数）
题目：输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，1~13中包含1的数字有1、10、11、12、13因此共出现6次解法一：暴力解法import java.util.*;public class Solution { public int NumberOf1Between1AndN_Solution(int n) { int count = 0; // 循环 1->n for(int i=1;i<=n;i++
2021-10-03 14:32:14
62
原创 剑指Offer28：数组中出现次数超过一半的数字
题目：给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。解法一：用一个Map装下每个数出现的次数。import java.util.*;public class Solution { public int MoreThanHalfNum_Solution(int [] array) { HashMap<Int
2021-10-03 12:30:47
109
原创 剑指Offer51：构建乘积数组
题目：给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。示例：输入：[1,2,3,4,5]输出：[120,60,40,30,24]解法：就是第 i 次遍历跳过 i
2021-10-03 10:29:41
47
原创 剑指Offer34：第一个只出现一次的字符
题目：在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）解法：每次用""来替换字符串的第i个字符，如果长度只减少 1 ，那么说明第 i 个字符只出现一次public class Solution { public int FirstNotRepeatingChar(String str) { for(int i=0;i<str.length();i++){ String temp
2021-10-03 10:29:26
39
原创 剑指Offer38：二叉树的深度
题目：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。解法一：递归public int TreeDepth(TreeNode root) { if(root==null){ return 0; } int left=TreeDepth(root.left); int right=TreeDepth(root.right); return Math.max(left,right)
2021-10-03 00:35:38
75
原创 剑指Offer55：链表中环的入口
题目：给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。示例：输入:{1,2,3,4,1,5}输出：节点1解法：有环就是会指向重复节点，重复的节点就是环的入口，遍历过程中输入与之前重复的节点即可。这里借助HashMap结构import java.util.*;public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead == null
2021-10-02 22:30:43
59
原创 剑指Offer36：两个链表的第一个公共节点
题目：输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。示例：输入：{1,2,3,6,7},{4,5,6,7}输出：{6,7}解法一：利用HashSet，先把一个链表装入HashSet，再遍历另一个链表。import java.util.*;public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHe
2021-10-02 22:30:15
38
原创 剑指Offer25：复杂链表的复制
题目：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。解法一：分两次遍历，第一次遍历建立一个正常链表，并且把节点都存储起来，第二次遍历把随即节点补上，这里要用到存储起来的节点。imp
2021-10-02 22:29:50
49
原创 剑指Offer56：删除链表中重复的节点
题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5解法：判断当前节点和之后节点有没有重复即可，比较特殊的就是需要有个前置节点来做处理。public class Solution { public ListNode deleteDuplication(ListNode pHead) { if(pHead ==
2021-10-02 22:29:30
45
原创 剑指Offer44：翻转单词
题目：牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？示例： 输入："nowcoder. a am I" 返回值："I am a nowcoder."解法：借助栈即可。import
2021-10-02 22:28:59
36
原创 剑指Offer64：滑动窗口的最大值
题目：给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,
2021-10-02 22:28:33
196
原创 0-1背包问题
背包问题题目描述有 N 件物品和一个容量为 V 的背包，第 i 件物品的体积是c[i]，价值是w[i]，忽略物体几何体积，认为只要背包剩余容量大于物品体积就能放进背包，求将哪些物品装入背包可使价值总和最大。问题解析非常常见的动态规划问题，对于所有的动态规划问题，核心就是状态转移方程。第一步都是确定状态。定义状态 dp[i][j] 是表示目前正在枚举第 i 个物品，目前已取的总体积为 j ，最大价值为 dp[i][j] 。第二步是找状态转移方程。物品只有拿和不拿两种选择(1)：假如不拿这个物品，
2021-09-30 13:33:50
211
原创 华为机考HJ16：购物单
import java.util.*;public class Main{ private static class Good{ int v;//价格 int p;//物品重要程度 int q;//物品所属主键ID int a1 = 0;//附件1ID int a2 = 0;//附件2ID public Good(int v,int p,int q){
2021-09-29 17:51:48
327
原创 kafka总结
Kafka 简介Apache Kafka起源于LinkedIn，后来于2011年成为开源Apache项目，然后于2012年成为First-class Apache项目。Kafka是用Scala和Java编写的。 Apache Kafka是基于发布订阅的容错消息系统。 它是快速，可扩展和设计分布。Kafka特点：可靠性：具有副本及容错机制。可扩展性：kafka无需停机即可扩展节点及节点上线。持久性：数据存储到磁盘上，持久性保存。性能：kafka具有高吞吐量。达到TB级的数据，也有非常稳定的性能。
2021-09-26 23:49:29
621
1
原创 hadoop总结
Hadoop 常用端口号dfs.namenode.http-address:50070dfs.datanode.http-address:50075SecondaryNameNode 辅助名称节点端口号：50090dfs.datanode.address:50010fs.defaultFS:8020 或者 9000yarn.resourcemanager.webapp.address:8088历史服务器 web 访问端口：19888Hadoop 配置文件以及简单的 Hadoop 集群搭建
2021-09-24 17:04:34
600
原创 数据结构6：数
介绍树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。类似于一个倒置的树。它具有以下的特点：没有父节点的节点称为根节点，任何非空树只有一个根节点任意两个节点有且仅有唯一的一条路径连通除了根节点外，每个子节点可以分为多个不相交的子树树里面没有环路(cycle)常用名词介绍：节点：树中的每个元素都可以统称为节点。根节点：顶层节点或者说没有父节点的节点。上图
2021-09-20 23:53:16
201
原创 剑指Offer20：从上往下打印二叉树
题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。思路：用一个队列按需要存放节点位置即可。从根节点开始，出队列，得到值，再把它的左右节点存进队列即可。import java.util.ArrayList;import java.util.Queue;import java.util.*;/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null;
2021-09-17 17:47:09
33
原创 数据结构5：队列
队列简介队列 是 先进先出( FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是 入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue常见队列：单队列、循环队列假设队列中有n个元素。访问：O（n）//最坏情况插入删除：O（1）//后端插入前端删除元素单队列单队列就是常见的队列, 每次添加元素时，都是添
2021-09-17 15:57:04
68
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人