- 博客(68)
- 收藏
- 关注
RSS订阅原创 剑指offer-----丑数
剑指offer-----丑数题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。实现创建数组保存已找到的丑数，res[index]根据丑数的定义，除了res[0] = 1，丑数数组的每个数应该是前面的丑数乘以2，3，5的结果。接下来应该思考的是如何保存丑...
2020-05-05 17:58:50
106
原创 Java中的继承
Java中的继承继承中需要注意的地方，列出来提醒我自己继承：继承是从已有类得到继承信息创建新类的过程。提供继承信息的类被称为父类（超类、基类）；得到继承信息的类被称为子类（派生类）。继承让变化中的软件系统有了一定的延续性，同时继承也是封装程序中可变因素的重要手段。Java 中一个子类只能继承一个父类 (而C++/Python等语言支持多继承)子类会继承父类的所有 public 的字段和方...
2020-05-04 23:45:21
145
原创 剑指offer-----链表中的第 K 结点
链表中的第 K 结点题目描述输入一个链表，输出该链表中倒数第k个结点。实现public class TheLastKNodeInTheList { public ListNode FindKthToTail(ListNode head,int k) { if (head == null) { return null; }...
2020-04-17 18:39:26
104
原创 剑指offer-----调整数组顺序使奇数位于偶数前面
调整数组顺序使奇数位于偶数前面题目描述输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。实现遍历数组，直接在数组内进行奇偶数的交换若数组长度为 0 或 1 时，不用进行任何操作，直接返回；（因此遍历从第二个数字开始）当前数字为奇数时，且当前数字的前一个数字为偶数，交换...
2020-04-17 18:31:28
104
原创 剑指offer-----数值的整数次方
数值的整数次方实现给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0。实现快速幂（二分）baseexp = baseexp/2 * baseexp/2 = (base2)exp/2当 exp 为偶数，baseexp = (base2)exp/2当 exp 为奇数，baseexp...
2020-04-16 19:57:02
90
原创 剑指offer-----反转链表
反转链表题目描述输入一个链表，反转链表后，输出新链表的表头。实现链表为空，返回 null链表只有一个结点，返回头结点 head一般情况实现反转创建新的头结点 newHead，若原链表结点遍历完，将最后一个结点指向 newHeadpublic class ReverseLinkedList { public ListNode ReverseList(ListNod...
2020-04-16 18:08:08
79
原创 剑指offer-----顺时针打印矩阵
顺时针打印矩阵题目描述输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16，则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.实现从四个方向遍历数组，定义四个边界，打印过程中不断收缩边界上边界 top = 0下边界...
2020-04-16 17:49:38
99
原创 剑指offer-----包含min函数的栈
包含 min 函数的栈题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。实现创建两个栈，栈A 和栈B栈A 表示原栈中的正常数据栈B 表示栈A每一层栈帧对应的最小值(1) 入栈：先把 node 插入到 栈A 中如果 栈B ...
2020-04-16 17:07:05
85
原创 剑指offer-----栈的压入，弹出序列
栈的压入，弹出序列题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。实现创建一个新的栈 B，将 pushA 的元素依次入栈依次判断新的栈 B 的元素是否与 po...
2020-04-16 16:49:16
86
原创 剑指offer-----二叉树的镜像
二叉树的镜像题目描述操作给定的二叉树，将其变换为源二叉树的镜像。实现递归：遍历 + 交换/** * Author: lisiyu * Created: 2020/4/13 */public class MirrorImageOfBinaryTree { public void Mirror(TreeNode root) { if (root == null...
2020-04-13 22:57:37
74
原创 剑指offer-----树的子结构
树的子结构题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）实现首先，两树任一为空，则返回 false；然后，root2 是 root1 的子结构，有三种情况：(1) root2 是 root1 的一个子结构(2) root2 是 root1 的左子树的一个子结构(3) root2 是 root1 的右子树的一个子结构最后，...
2020-04-13 22:54:46
73
原创 剑指offer-----旋转数组的最小数字
旋转数组的最小数字题目描述把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。实现public int minNumberInRotateArray(int [] ...
2020-04-05 23:06:32
72
原创 剑指offer-----斐波那契数列
斐波那契数列题目描述大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39实现法1递归时间复杂度：O(2^n)空间复杂度：O(n)public int Fibonacci1(int n) { if (n == 0) { return 0; } if (n == 1) { ...
2020-04-05 22:17:27
76
原创 剑指offer-----二进制中1的个数
二进制中1的个数题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。实现两种方法的时间复杂度和空间复杂度均为 O(1)法1每一位都与1相与，结果不等于0的就在sum上加1public int NumberOf1(int n) { int sum = 0; int a = 1; for (int i = 0; i < 32; i++) ...
2020-04-05 19:59:20
74
原创 剑指offer-----矩形覆盖
矩形覆盖题目描述我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？实现f(1) = 1f(2) = 2f(3) = 3f(4) = 5……思路与斐波那契数列相同public int RectCover(int target) { /** * f(1) = 1 * f(2) = ...
2020-04-05 17:18:39
92
原创 剑指offer-----变态跳台阶
变态跳台阶题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。实现f(1) = 1f(2) = 2f(3) = 4……f(n) = 2^(n-1) 或 f(n) = 2 * f(n-1)public int JumpFloorII(int target) { if (target == 1) { ...
2020-04-02 23:12:01
68
原创 剑指offer-----跳台阶
跳台阶题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。实现法1public int JumpFloor1(int target) { if (target == 1) { return 1; } if (target == 2) { return 2;...
2020-04-02 23:07:58
66
原创 剑指offer-----用两个栈实现队列
用两个栈实现队列题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。实现import java.util.Stack;public class TwoStacksForQueue { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer...
2020-04-02 23:05:28
56
原创 剑指offer-----用两个栈实现队列
用两个栈实现队列题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。实现import java.util.Stack;public class TwoStacksForQueue { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer...
2020-04-01 23:03:02
69
原创 剑指offer-----重建二叉树
重建二叉树题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。实现递归时间复杂度：O(n)空间复杂度：O(n)public TreeNode reConstructBinaryTree(...
2020-04-01 23:00:02
79
原创 剑指offer-----从尾到头打印链表
从尾到头打印链表题目描述输入一个链表，按链表从尾到头的顺序返回一个ArrayList。实现法1：借助 list.add(index, value) , 非递归时间复杂度：O(n^2)空间复杂度：O(n)public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) { ArrayList&...
2020-03-31 12:31:00
67
原创 剑指offer-----替换空格
替换空格题目描述请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。实现法1：直接替换使用字符串的 replaceAll 方法public String replaceSpace1(StringBuffer str) { String ret = str.toString(...
2020-03-31 12:17:05
73
原创 剑指offer-----二维数组中的查找
二维数组中的查找题目描述在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。实现法1：暴力法时间复杂度：O(n^2)空间复杂度：O(1)public boolean Find1(int target, int [][] array) { ...
2020-03-31 12:06:03
59
原创 子串判断-----牛客
/** * Author: lisiyu * Created: 2020/3/24 */public class Substr { public boolean[] chkSubStr(String[] p, int n, String s) { boolean[] booleans = new boolean[n]; for (int i = 0;...
2020-03-24 22:00:03
98
原创 汽水瓶 ----- 牛客
汽水瓶 ----- 牛客递归1 个空瓶 = 0 瓶汽水 + 0 个空瓶2 个空瓶 = 1 瓶汽水 + 0 个空瓶3 个空瓶 = 1 瓶汽水 + 1 个空瓶f(1) = 0f(2) = 0f(3) = 1f(4) = f(3 + 1)= 1 瓶汽水 + 2 个空瓶= 1 + f(2)= 2 瓶汽水 + 0 个空瓶f(5) = f(3 + 2)= 1 瓶汽水 + 3 个空瓶...
2020-03-03 22:14:30
152
原创 LeetCode 268 ----- 缺失数字
LeetCode 268 ----- 缺失数字题目描述给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。实现1：位运算（异或）数组元素与数组下标逐个进行异或，结果再与数组长度异或，结果就是缺失的数字时间复杂度：O(n)空间复杂度：O(1)public int missingNumber1(int[] nums) { ...
2020-02-13 21:07:09
106
原创 LeetCode 189 ----- 旋转数组
LeetCode 189 ----- 旋转数组题目描述定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 O(1) 的 原地 算法。实现1：直接遍历时间复杂度：O(n*k)空间复杂度：O(1)public void rotate1(int[] nums, int k) { ...
2020-02-11 22:06:06
59
原创 LeetCode 169 ----- 多数元素
LeetCode 169 ----- 多数元素题目描述给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。法 1：直接遍历时间复杂度 O(n*2)空间复杂度 O(1)public int majorityElement1(int[] nums) { int len ...
2020-02-09 21:59:03
118
原创 LeetCode 167 ----- 两数之和2-输入有序数列
LeetCode 167 ----- 两数之和2-输入有序数列题目描述给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。说明：返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。实现1...
2020-02-08 22:08:08
112
原创 LeetCode 122 ----- 买卖股票的最佳时机
LeetCode 122 ----- 买卖股票的最佳时机题目描述给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。思路1：峰谷法时间复杂度 O(n)空间复杂度 O(1)// 法 1：峰谷法// 时间复杂度 ...
2020-02-07 21:50:34
72
原创 LeetCode 121 ----- 买卖股票的最佳时机
LeetCode 121 ----- 买卖股票的最佳时机题目描述给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。思路1：直接遍历时间复杂度：O(n2)，循环了 (n(n-1)) / 2 次空间复杂度：O(1)，只使用了两个变量 max 和 ...
2020-02-07 21:44:01
90
原创 LeetCode 119 ----- 杨辉三角
LeetCode 119 ----- 杨辉三角题目描述给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。进阶：空间复杂度 O(k)实现import java.util.ArrayList;import java.util.List;/** * Author: lisiyu * Created: 2020/2/1 */// LeetCode 119 ----...
2020-02-02 23:17:31
133
原创 LeetCode 118 ----- 杨辉三角
LeetCode 118 ----- 杨辉三角题目描述给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。思路第一行是固定的， 就只有1第二行是固定的，就只有两个1任意一行，开头和结尾都是1第 i 行，有 i 列第 i 行的 j 列，这个数字是根据 i -1 行，j -1 列的和 j 列相加第 i 行的第 0 列和 最后一列 都是 1实现import ...
2020-02-01 11:16:51
92
原创 LeetCode 88 ----- 合并两个有序数组
LeetCode 88 ----- 合并两个有序数组题目描述给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。初始化 nums1 和 nums2 的元素数量分别为 m 和 n。你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。三种方法：双指针-----从前到后...
2020-01-31 22:11:26
65
原创 LeetCode 66 ----- 加一
LeetCode 66 ----- 加一题目描述给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。思路从右向左遍历数组加 1 后判断哟没有进位，有进位则当前为置为 0，前一位加 1，循环下去，直至没有进位，退出循环，返回进位后的的数组；（例：269—270）...
2020-01-31 11:57:34
97
原创 LeetCode 53 ----- 最大子序和
LeetCode 53 ----- 最大子序和题目描述给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。思路1：直接遍历为每个子序列定义一个开始和结尾，为 start 和 end，start <= end定义一个最大值，Integer.MIN_VALUE外循环遍历 start，内循环遍历 end，逐个元素相加，找到和的最大值/...
2020-01-21 22:48:10
164
原创 Leecode 35 ----- 搜索插入位置
Leecode 35 ----- 搜索插入位置题目描述给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。思路二分查找时间复杂度：O(log n)在这里插入代码片左侧下标 left = 0；右侧下标 right = 0；判断：while (left <= right)中间下...
2020-01-20 20:36:33
176
1
原创 LeetCode 27 ----- 移除元素
LeetCode 27 ----- 移除元素题目描述给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。思路快慢指针（i 是慢指针，j 是快指针）nums[j] = val ...
2020-01-19 17:23:04
111
原创 LeetCode 26 ----- 删除排序数组中的重复项
LeetCode 26 ----- 删除排序数组中的重复项题目描述给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。思路快慢指针 a 和 b遍历数组比较 nums[a] 和 nums[b] 是否相等两者相等， b+1两者不相等，将 nums[...
2020-01-14 11:33:36
105
原创 LeetCode1 ----- 两数之和
LeetCode1 ----- 两数之和题目描述给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。思路**直接遍历外层循环计算当前数组值与 target 的差值内层循环在数组中寻找该差值找到后返回当前两个值的下标实现/** * Author: lisiyu * Created: 2020/1/10 */...
2020-01-12 20:49:13
72
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人