- 博客(38)
- 收藏
- 关注
RSS订阅原创 540. 有序数组中的单一元素（二分查找，java）
540. 有序数组中的单一元素给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。示例 1:输入: nums = [1,1,2,3,3,4,4,8,8]输出: 2示例 2:输入: nums = [3,3,7,7,10,11,11]输出: 10提示:1 <= nums.length <= 1050 <= nums[i] <= 105方法一：时间复杂度O(n)直接遍历数组，判断当前元素是否与左右元素中的一个相等，注意是否会出
2021-09-26 15:48:08
130
1
原创 69. x 的平方根（java，二分查找，面试常见题型）
69. x 的平方根给你一个非负整数 x ，计算并返回 x 的 平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。思路：二分查找，注意用x/mid防止溢出，同时要注意0不能做分母class Solution { public int mySqrt(int x) {// 二分查找，[1,x]之间找 if (x==0) return 0; int l=
2021-09-17 16:56:53
161
原创 524. 通过删除字母匹配到字典里最长单词(Java，双指针，排序)
524. 通过删除字母匹配到字典里最长单词给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。思路：现将列表中元素按从大到小的顺序排序，对于长度相同的，按照字典序排序再使用双指针判断当前元素能否通过s删除部分字符得到。class Solution { public String findLongestWo
2021-09-15 16:40:41
131
原创 680. 验证回文字符串 Ⅱ（java，双指针）
680. 验证回文字符串 Ⅱ给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。提示:1 <= s.length <= 105s 由小写英文字母组成本题难点：存在一次删除机会，所以只要（i，j-1）或（i+1,j）范围内存在回文串就可以返回true思路：（双指针与贪心算法结合）用双指针判断是否为正常回文串，若不是判断（i，j-1）或（i+1,j）范围内是否为回文串。class Solution { public boolean validPalindr
2021-09-13 16:30:47
133
原创 633. 平方数之和（java，双指针）
633. 平方数之和注意：在运算时可能会发生int型溢出，计算时要使用long（一）双指针class Solution { public boolean judgeSquareSum(int c) { long i=0; long j=(long) Math.sqrt(c); //可能会出现i*i+j*j>2^31-1的情况，所以先赋值给一个long，再进行比较 long sum=0; while(i<=j) {
2021-09-11 20:49:44
107
原创 142. 环形链表 II（java，Floyd判圈法）
142. 环形链表 II给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。说明：不允许修改给定的链表。进阶：你是否可以使用 O(1) 空间解决此题？/** * Definition for singly-linked list. * class ListN
2021-09-07 22:13:39
91
原创 剑指 Offer 22. 链表中倒数第k个节点（Java，快慢指针）
剑指 Offer 22. 链表中倒数第k个节点题目描述：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。思路：定义两个指针，一个快指针fast，一个慢指针slowfast先从头开始遍历k个节点，slow再从头开始遍历，当fast遍历到链表尾时，slow指向倒数第k个节点/** * Definit
2021-09-02 16:43:21
39
原创 88. 合并两个有序数组(Java，双指针)
88. 合并两个有序数组给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。当前最后一个位置为两个数组中还没有排序过的值得最大值若nums2中还有剩余，则直接放在前面class Solution { public void merge(int[]
2021-07-05 21:22:25
174
原创 167. 两数之和 II - 输入有序数组(Java,双指针)
167. 两数之和 II - 输入有序数组双指针双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针。若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的区域即为当前的窗口），经常用于区间搜索。若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是排好序的。题目描述：给定一个已按照升序排列的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。函数应该以长度为
2021-07-03 16:27:52
100
原创 122. 买卖股票的最佳时机 II(Java，贪心算法)
122. 买卖股票的最佳时机 II给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。思路：贪心算法，一次遍历，只要今天价格小于明天价格就在今天买入然后明天卖出，时间复杂度O(n)[7, 1, 5, 6] 第二天买入，第四天卖出，收益最大（6-1），所以一般人可能会想，怎么判断不是第三天就卖出了呢? 这
2021-07-03 09:13:40
136
原创 763. 划分字母区间(Java，贪心算法)
763. 划分字母区间字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。示例：输入：S = “ababcbacadefegdehijhklij”输出：[9,7,8]解释：划分结果为 “ababcbaca”, “defegde”, “hijhklij”。每个字母最多出现在一个片段中。像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。提示：S的长度在[
2021-07-01 17:22:05
236
原创 452. 用最少数量的箭引爆气球(java,贪心算法)
452. 用最少数量的箭引爆气球题目描述：气球在一个水平数轴上摆放，可以重叠，飞镖垂直射向坐标轴，使得路径上的气球都会刺破。求解最小的投飞镖次数使所有气球都被刺破。思路：贪心算法，使每支箭射中的气球最多，即只要满足该气球坐标小于或等于当前箭的范围即没被射中的气球的最小end，都可以被一起击破官方解释：我们唯一的要求就是：原本引爆的气球只要仍然被引爆就行了。这样一来，我们找出原本引爆的气球中右边界位置最靠左的那一个，将这支箭的射出位置移动到这个右边界位置，这也是最远可以往右移动到的位置：如图
2021-06-28 22:03:08
191
原创 739.每日温度（java）
739. 每日温度思路：使用双重循环，从后往前判断。最后一个数字对应计数为0，其余数字离该数字最近的比该数字大的数字的索引。（或者从前往后，找到第一个比当前数据大的数据的索引）缺点：时间复杂度太太太大class Solution { public int[] dailyTemperatures(int[] T) { //从后往前找 int top=0; int[] count=new int[T.length]; int[] stack=new
2021-04-04 19:49:30
120
原创 时间序列类型
单变量时间序列具有单一时间依赖变量的序列如 温度-时间（一个时间对应一个温度）多变量时间序列具有一个以上的时间依赖变量。每个变量不仅取决于其过去的值，而且还对其他变量有一定的依赖性假设我们的数据集包括过去两年的汗水百分比、露点、风速、云层覆盖率等，以及温度值。在这种情况下，有多个变量被认为是最佳预测温度。像这样的系列将属于多元时间序列的范畴...
2021-03-22 09:26:42
465
转载 数据清洗
数据清洗主要包括：纠正错误、删除重复项、统一规格、修正逻辑、转换构造、数据压缩、补足残缺/空值、丢弃数据/变量。纠正错误常见的错误形式包括：1） 数据值错误：数据直接是错误的，例如超过固定域集、超过极值、拼写错误、属性错误、源错误等。2）数据类型错误：数据的存储类型不符合实际情况，如日期类型的以数值型存储，时间戳存为字符串等。3）数据编码错误：数据存储的编码错误，例如将UTF-8写成UTF-80。4）数据格式错误：数据的存储格式问题，如半角全角字符、中英文字符等。5）数据异常错误：如数值数据
2021-03-21 21:50:44
1071
原创 86. 分隔链表（Java）
86. 分隔链表给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。思路：该链表没有头结点，加上一个头结点方便插入和删除遍历链表（结束条件为p!=null）1）找到第一个不小于x的节点X并记录位置2）X前的所有节点不需要改变3）X后所有值小于x的节点均需按照与按原顺序插入到节点X之前时间复杂度：遍历一次链表 O(N)/** * Definition for singly-linke
2021-01-03 20:17:03
126
原创 605. 种花问题（Java，贪心算法）
605. 种花问题假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。思路：在开头、结尾处：有两个连续的0可以放一朵花在其余位置：每三个连续的0可以放一朵花，且最后一个0可以作为下一段判断的起始寻找三个连
2021-01-03 18:32:55
270
原创 435. 无重叠区间（Java，贪心算法）
435. 无重叠区间给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。注意:可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。思路：贪心算法每次选结尾最小的区间将二维数组按intervals[i][1]从小到大排序，每次取不与当前空间相交的end最小的区间，用区间总数-不相交的区间数=需删除的最小区间数class Solution { public int eraseOverlapIntervals(int[
2021-01-02 19:11:46
442
原创 1046. 最后一块石头的重量（Java）
1046. 最后一块石头的重量有一堆石头，每块石头的重量都是正整数。每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。思路：使用递归每次用最大的两个数的差来代替最大的两个数注意：java数组
2020-12-30 15:41:31
195
1
原创 330. 按要求补齐数组（Java）
330. 按要求补齐数组（????????????????????????????????）给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。思路：贪心算法找到当前数据（原有的+新加入的）所能覆盖的最大连续范围一个数组[a1,a2,a3…an]当前能用和表示的数字区间为[1,right]，此时往数组内补充新数
2020-12-29 21:31:51
293
转载 梯度下降和随机梯度下降
梯度下降和随机梯度下降目标函数大多数机器学习或者深度学习算法都涉及某种形式的优化。 优化指的是改变 以最小化或最大化某个函数 f(x) 的任务。 我们通常以最小化 f(x) 指代大多数最优化问题。 最大化可经由最小化算法最小化 -f(x) 来实现。我们把要最小化或最大化的函数称为目标函数或准则。 当我们对其进行最小化时，我们也把它称为代价函数、损失函数或误差函数。 下面，我们假设一个损失函数为其中然后要使得最小化它。注意：这里只是假设，不用知道这个目标函数就是平方损失函数等等，然后肯定有
2020-12-29 09:32:08
2090
原创 205. 同构字符串（Java）
205. 同构字符串（与290类似，290是判断字符串规律是否相同）给定两个字符串 s 和 t，判断它们是否是同构的。如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。思路：hashmap的应用要满足两个条件：1.相同的字母要替换成相同的2.不同的字母被替换成不同的每个字符第一次出现时作为键，替换他的字符作为值class Solution { publ
2020-12-27 21:33:39
172
原创 135. 分发糖果（Java，贪心算法）
135. 分发糖果（ ???? ???? ???? ???? ???? ???? ???? ????）老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？思路：每个元素均和两边元素比较：分两次遍历，第一次遍历从前向后，实现左规则，第二次遍历从后向前，实现右规则（规则的定义
2020-12-25 21:44:12
378
原创 455. 分发饼干（Java，贪心算法）
455. 分发饼干假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。思路：将s和g从小到大排序，记录s中有几项比g大class Solution { public int fi
2020-12-25 20:09:00
393
原创 387. 字符串中的第一个唯一字符（Java）
387. 字符串中的第一个唯一字符给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。思路：遍历字符串并用哈希表记录每个字符出现的次数，由于本题目中的字符串只包含小写字母，因此使用长为26的数组存每个字母出现的次数。再次遍历该字符串，返回第一个出现次数为1的字符的索引有出现次数均大于1，则返回-1.时间复杂度O(N)空间复杂度O(26)注：数组完成初始化后，内存空间中针对该数组的各个元素就有个一个默认值： 基本数据类型的整数类型（byte、
2020-12-23 20:04:44
71
原创 20. 有效的括号（Java）
20. 有效的括号（Java）给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。思路：栈的应用使用栈时一定要考虑栈空的情况，防止溢出左括号入栈，右括号判断栈顶是否为能与之匹配的左括号，若能则栈顶元素出栈，若不能或当前栈为空，则为不符合的序列。遍历完所有字符后若栈空，则字符串有效，否则无效class Solution { pu
2020-12-22 19:09:40
120
原创 316. 去除重复字母（Java）
316. 去除重复字母给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。思路：使用栈，遍历字符串s，1)若当前字符大于栈顶字符或栈为空，则当前字符直接入栈；2)若栈中已存在当前字符则直接跳过当前元素；3)若当前字符小于栈顶字符，则循环判断当前字符之后的字符串是否包含栈顶字符，若包含则栈顶元素出栈，直到栈为空或当前字符大于栈顶字符为止，并将当前字符入栈。遍历字符串结束后，栈中即为满足要求的子串。class
2020-12-22 16:26:07
610
原创 34. 在排序数组中查找元素的第一个和最后一个位置(Java，二分查找）
34. 在排序数组中查找元素的第一个和最后一个位置（二分查找法）给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。进阶：你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？思路：从前向后遍历到最后一个不大于target的，其索引用start标记，从后向前遍历到最后一个不小于target的，索引用end标记，若nums[start]=nums[end]=ta
2020-12-21 21:42:23
316
原创 389. 找不同（Java）
389. 找不同给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。思路：将字符串s，t转换为字符数组并排序，在遍历字符数组，找出不同的字符代码：class Solution { public char findTheDifference(String s, String t) { char ss[]=s.toCharArray(); char tt[]=t.toCharAr
2020-12-21 15:53:52
111
原创 3. 无重复字符的最长子串：滑动窗口（Java）
3. 无重复字符的最长子串给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: s = “abcabcbb”输出: 3解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。示例 2:输入: s = “bbbbb”输出: 1解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。示例 3:输入: s = “pwwkew”输出: 3解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。请注意，你的答案必须是 子串 的长度，“p
2020-12-17 18:53:46
117
原创 238. 除自身以外数组的乘积（Java）
238. 除自身以外数组的乘积 : (给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。示例:输入: [1,2,3,4]输出: [24,12,8,6]提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此???? ???? ???? ???? ???? ??
2020-12-16 21:26:16
140
原创 290. 单词规律（Java）
290. 单词规律给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。示例1:输入: pattern = “abba”, str = “dog cat cat dog”输出: true示例 2:输入:pattern = “abba”, str = “dog cat cat fish”输出: false示例 3:输入: patte
2020-12-16 20:41:35
172
原创 49. 字母异位词分组（Java）
49. 字母异位词分组给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。示例:输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]输出:[[“ate”,“eat”,“tea”],[“nat”,“tan”],[“bat”]]说明：所有输入均为小写字母。不考虑答案输出的顺序。思路：使用Map，将排序后的字符串作为key，将原始字符串组成的列表作为value，每个key对应的value为具有相同字母的字符串有相
2020-12-16 17:17:15
219
原创 java中Collection和List的常用方法（待补充）
List和Collection都是接口，不能直接创建对象，只能通过实现该接口的子类来创建对象java.util集合：即一个储存或者获取数据的容器。一般分为：List，Set，Map三类，关系如图所示：List接口是继承Collection接口，所以Collection集合中有的方法，List集合也继承过来。Java的Collection集合的常用方法方法名说明boolean add(E e)向集合添加元素e，若指定集合元素改变了则返回trueboolean addA
2020-12-15 20:41:19
382
原创 7.整数反转（Java）（待编辑）
7.整数反转给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例 1:输入: 123输出: 321示例 2:输入: -123输出: -321示例 3:输入: 120输出: 21注意:假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。思路：先转成字符数组，先判断是否为负数,再依次遍历每个元素，转成整数，借助long类型来判断int类型溢出缺点：类型转换时间
2020-12-14 11:22:55
38
原创 2.两数相加（Java）
2.两数相加知识点：Java链表给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807思路：遍历两个链表（长度相等和长度
2020-12-13 21:32:02
251
原创 217.存在重复元素（java）
217. 存在重复元素给定一个整数数组，判断是否存在重复元素。如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。思路：排序后相同的元素一定出现在相邻的位置，通过遍历整个序列判断是否存在重复元素class Solution { public boolean containsDuplicate(int[] nums) { //排序后判断后一个与前一个是否相同 Arrays.sort(nums);
2020-12-13 20:20:38
137
原创 376.摆动序列（C语言）
376.摆动序列如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也
2020-12-12 18:33:03
1255
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人