- 博客(165)
- 收藏
- 关注
RSS订阅原创 图论系列（1）——并查集介绍
前言：最近笔试面试碰到好几道与连通图有关的题目，正好从这些题抛砖引玉，好好看看应该怎么处理这方面的问题。问题描述：假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友…），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。假如：n = 5， m = 3， r = {{1 , 2} , {2 , 3} ,{4 , 5...
2018-09-12 10:13:27
517
原创 Java String专题（一）—— AbstractStringBuilder
1. 前言：最近准备面试，正好在看关于StringBuilder和StringBuffer的源码，发现它们两个类共同继承了一个抽象类AbstractStringBuilder作为它们的父类，那也就正好从这个类开始，开始整个Java String专题的解析。2. 关于AbstractStringBuilder类有一点要先说明，这个类提供的所有方法都没有加锁，所以是线程不安全的。2.1...
2018-08-29 14:59:32
510
原创 2019阿里校招测评题 物流派送员最短路径问题
题目：解题思路：还是尝试用全排列先去求个解出来，把所有可能的路径都求出来，找出最短的那个。但是感觉用启发式算法效果会更好，尝试使用两元素优化求解。代码实现：全排列版本：public class Test { private static int times = 0; private static int minCost = Integer.MAX_V...
2018-08-29 13:38:45
2395
原创 2019阿里校招测评题 光明小学完全图最短路径问题
题目：光明小学的小朋友们要举行一年一度的接力跑大赛了，但是小朋友们却遇到了一个难题：设计接力跑大赛的线路，你能帮助他们完成这项工作么？光明小学可以抽象成一张有N个节点的图，每两点间都有一条道路相连。光明小学的每个班都有M个学生，所以你要为他们设计出一条恰好经过M条边的路径。光明小学的小朋友们希望全盘考虑所有的因素，所以你需要把任意两点间经过M条边的最短路径的距离输出出来以供参考。你需要...
2018-08-29 13:38:34
856
原创 数据库锁整理
B+树在了解数据库索引之前，首先了解一下数据库索引的数据结构基础，B+treeB＋tree 是一个n叉树，每个节点有多个叶子节点，一颗B+树包含根节点，内部节点，叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上叶子节点的节点。B＋tree的性质：n棵子tree的节点包含n个关键字，不用来保存数据而是保存数据的索引。 所有的叶子结点中包含了全部关键字的信息，及指向...
2018-08-10 12:36:58
1733
原创 Leetcode 841. Keys and Rooms 钥匙和房间
题目：有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v ...
2018-07-28 15:46:52
742
原创 Leetcode 494. Target Sum 目标和
题目：给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。示例 1:输入: nums: [1, 1, 1, 1, 1], S: 3输出: 5解释: -1+1+1+1+1 = 3+1-1+1+1+1 = 3...
2018-07-13 23:12:55
492
原创 Leetcode 403. Frog Jump 青蛙过河
题目：一只青蛙想要过河。 假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。 青蛙可以跳上石头，但是不可以跳入水中。给定石子的位置列表（用单元格序号升序表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一个石子上）。 开始时， 青蛙默认已站在第一个石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格1跳至单元格2）。如果青蛙上一步跳跃了 k 个单...
2018-07-13 15:35:05
680
原创 最小堆--原理及JAVA实现
什么是堆最小堆是一种数据结构，有着如下特点：顺序：堆顶元素永远是最小的。形状：堆是一颗完全二叉树。这两个特性保证了堆在插入和删除的过程中最大时间复杂度也是满足O(logn)的，所以是一种非常高效的数据结构格式。更新堆的方式更新堆的两种方式，分别对应了插入元素和删除堆顶元素操作：自底向上自顶向下堆的实现可以使用数组作为隐式树（因为结构是完全二叉树），不使用索引为0的元素，从1开始。如果当前元素的下标...
2018-07-12 13:57:37
6177
原创 Leetcode 174. Dungeon Game 地下城游戏
题目：一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房...
2018-07-09 11:25:35
774
原创 Leetcode 560. Subarray Sum Equals K 和为K的子数组
题目：给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 :输入:nums = [1,1,1], k = 2输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。说明 :数组的长度为 [1, 20,000]。数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。解题思路：在当前元素出现之时，存在p个和可以...
2018-07-08 13:33:27
304
原创 牛客网系列--2017校招真题编程练习--滴滴出行--连续最大和
题目：输入描述:输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。输出描述:所有连续子数组中和最大的值。示例1输入复制3 -1 2 1输出复制3解题思路：判断连续元素求和是否大于0，如果累计的和小于0，就从当前元素开始重新求和。代码实现：public class Main {...
2018-07-08 12:30:15
316
原创 Leetcode 611. Valid Triangle Number 有效三角形的个数
题目：给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。示例 1:输入: [2,2,3,4]输出: 3解释:有效的组合是: 2,3,4 (使用第一个 2)2,3,4 (使用第二个 2)2,2,3注意:数组长度不超过1000。数组里整数的范围为 [0, 1000]。解题思路：先对数组进行排序，优先确定最大的边长，然后寻找第二第三条边的范围。代码实现：使用b...
2018-07-06 13:48:32
709
原创 Leetcode 234. Palindrome Linked List 回文链表
题目：请判断一个链表是否为回文链表。示例 1:输入: 1->2输出: false示例 2:输入: 1->2->2->1输出: true进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？解题思路：使用递归进行求解，判断每个对应元素是否相等。代码实现：/** * Definition for singly-linked list. * public...
2018-07-06 13:28:41
146
原创 Leetcode 680. Valid Palindrome II 验证回文字符串 Ⅱ
题目：给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。示例 1:输入: "aba"输出: True示例 2:输入: "abca"输出: True解释: 你可以删除c字符。注意:字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。解题思路：使用了two pointer算法结合了递归算法，最后判断是否合法。代码实现：class Solution { ...
2018-07-06 13:24:25
327
原创 Leetcode 26. Remove Duplicates from Sorted Array 删除排序数组中的重复项
题目：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。示例 1:给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。示例 2:给定 num...
2018-07-06 13:15:49
180
原创 Leetcode 414. Third Maximum Number 第三大的数
题目：给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。示例 1:输入: [3, 2, 1]输出: 1解释: 第三大的数是 1.示例 2:输入: [1, 2]输出: 2解释: 第三大的数不存在, 所以返回最大的数 2 .示例 3:输入: [2, 2, 3, 1]输出: 1解释: 注意，要求返回第三大的数，是指第...
2018-07-06 13:12:21
416
原创 Leetcode 242. Valid Anagram 有效的字母异位词
题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。示例 1:输入: s = "anagram", t = "nagaram"输出: true示例 2:输入: s = "rat", t = "car"输出: false说明:你可以假设字符串只包含小写字母。进阶:如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？解题思路：对...
2018-07-06 13:07:56
203
原创 Leetcode 345. Reverse Vowels of a String 反转字符串中的元音字母
题目：编写一个函数，以字符串作为输入，反转该字符串中的元音字母。示例 1：给定 s = "hello", 返回 "holle".示例 2：给定 s = "leetcode", 返回 "leotcede".注意:元音字母不包括 "y".解题思路：使用two pointer算法进行元素之间的替换。代码实现：class Solution { public String reverseVowels...
2018-07-06 13:02:40
286
原创 Leetcode 409. Longest Palindrome 最长回文串
题目：给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。注意:假设字符串的长度不会超过 1010。示例 1:输入:"abccccdd"输出:7解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。解题思路：计算每个字母出现的次数，获取每个字母出现的最大偶数，最后求和，...
2018-07-06 12:59:16
175
原创 Leetcode 637. Average of Levels in Binary Tree 二叉树的层平均值
题目：给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.示例 1:输入: 3 / \ 9 20 / \ 15 7输出: [3, 14.5, 11]解释:第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].注意：节点值的范围在32位有符号整数范围内。解题思路：使用bfs实现每层的平均值计算。代...
2018-07-06 12:44:00
235
原创 Leetcode 237. Delete Node in a Linked List 删除链表中的节点
题目：请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。现有一个链表 -- head = [4,5,1,9]，它可以表示为: 4 -> 5 -> 1 -> 9示例 1:输入: head = [4,5,1,9], node = 5输出: [4,1,9]解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变...
2018-07-05 23:30:44
105
原创 Leetcode 20. Valid Parentheses 有效的括号
题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例 1:输入: "()"输出: true示例 2:输入: "()[]{}"输出: true示例 3:输入: "(]"输出: false示例 4:输入: "([)]"输出:...
2018-07-05 23:29:21
109
原创 Leetcode 500. Keyboard Row 键盘行
题目：给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。示例1:输入: ["Hello", "Alaska", "Dad", "Peace"]输出: ["Alaska", "Dad"]注意:你可以重复使用键盘上同一字符。你可以假设输入的字符串将只包含字母。解题思路：代码实现：class Solution { public String[] find
2018-07-04 16:41:34
187
原创 Leetcode 695. Max Area of Island 岛屿的最大面积
题目：给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)示例 1:[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,...
2018-07-04 16:37:51
592
1
原创 Leetcode 507. Third Maximum Number 完美数
题目：对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。给定一个 正整数 n， 如果他是完美数，返回 True，否则返回 False 示例：输入: 28输出: True解释: 28 = 1 + 2 + 4 + 7 + 14 注意:输入的数字 n 不会超过 100,000,000. (1e8)解题思路：代码实现：class Solution { publ...
2018-07-04 16:18:21
223
原创 Leetcode 538. Convert BST to Greater Tree 把二叉搜索树转换为累加树
题目：给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。例如：输入: 二叉搜索树: 5 / \ 2 13输出: 转换为累加树: 18 / \...
2018-07-04 15:59:01
201
原创 Leetcode 90. Subsets II 子集 II
题目：给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例:输入: [1,2,2]输出:[ [2], [1], [1,2,2], [2,2], [1,2], []]解题思路：回溯法求解组合问题，求解方式都差不多。代码实现：class Solution { public List<List<...
2018-07-02 20:15:10
203
原创 Leetcode 78. Subsets 子集
题目：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例:输入: nums = [1,2,3]输出:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]解题思路：回溯法求组合问题。代码实现：class Solution { public List...
2018-07-02 20:06:20
186
原创 Leetcode 40. Combination Sum II 组合总和 II
题目：给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。 示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8,所求解集为:[ [1...
2018-07-02 17:23:28
261
原创 Leetcode 39. Combination Sum 组合总和
题目：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。说明：所有数字（包括 target）都是正整数。解集不能包含重复的组合。 示例 1:输入: candidates = [2,3,6,7], target = 7,所求解集为:[ [7]...
2018-07-02 16:23:53
165
原创 Leetcode 47. Permutations II 全排列 II
题目：给定一个可包含重复数字的序列，返回所有不重复的全排列。示例:输入: [1,1,2]输出:[ [1,1,2], [1,2,1], [2,1,1]]解题思路：使用bfs进行全排列，创建used数组检查数字的使用情况。代码实现：public class Solution { public List<List<Integer>> permuteUni...
2018-07-02 15:35:17
196
原创 Leetcode 21. Merge Two Sorted Lists 合并两个有序链表
题目：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4解题思路：创建一个新节点作为答案节点头，比较当前的l1和l2节点的大小，把小的节点作为next存入答案节点，更新答案节点。时间复杂度O(n)，空间复杂度O(1)。...
2018-07-01 23:37:09
106
原创 Leetcode 46. Permutations 全排列
题目：给定一个没有重复数字的序列，返回其所有可能的全排列。示例:输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]解题思路：回溯法，注意同一个元素不能重复选取。代码实现：class Solution { public List<List<Integer>&...
2018-07-01 23:10:57
164
原创 Leetcode 52. N-Queens II N皇后 II
题目：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。上图为 8 皇后问题的一种解法。给定一个整数 n，返回 n 皇后不同的解决方案的数量。解题思路：和Leetcode 51. N-Queens N皇后一样，都是用回溯法解决，相较于上一题的输出棋盘，这题输出合法棋盘总和相对更简单一点。空间复杂度O(n)。代码实现：class Solution { ...
2018-07-01 23:07:28
647
原创 Leetcode 51. N-Queens N皇后
题目：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。上图为 8 皇后问题的一种解法。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。示例:输入: 4输出: [ [".Q..", // 解法 1 "...Q", "Q......
2018-07-01 23:01:03
146
原创 Leetcode 784. Letter Case Permutation 字母大小写全排列
题目：给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。示例:输入: S = "a1b2"输出: ["a1b2", "a1B2", "A1b2", "A1B2"]输入: S = "3z4"输出: ["3z4", "3Z4"]输入: S = "12345"
2018-07-01 22:57:04
375
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人