5 zhangzhetaojj

尚未进行身份认证

努力学习,争取BAT!

等级
TA的排名 3w+

图论系列(1)——并查集介绍

前言:最近笔试面试碰到好几道与连通图有关的题目,正好从这些题抛砖引玉,好好看看应该怎么处理这方面的问题。问题描述:假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友…),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。假如:n = 5, m = 3, r = {{1 , 2} , {2 , 3} ,{4 , 5...

2018-09-12 10:13:27

Java String专题(一)—— AbstractStringBuilder

1. 前言:最近准备面试,正好在看关于StringBuilder和StringBuffer的源码,发现它们两个类共同继承了一个抽象类AbstractStringBuilder作为它们的父类,那也就正好从这个类开始,开始整个Java String专题的解析。2. 关于AbstractStringBuilder类有一点要先说明,这个类提供的所有方法都没有加锁,所以是线程不安全的。2.1...

2018-08-29 14:59:32

2019阿里校招测评题 物流派送员最短路径问题

题目:解题思路:还是尝试用全排列先去求个解出来,把所有可能的路径都求出来,找出最短的那个。但是感觉用启发式算法效果会更好,尝试使用两元素优化求解。代码实现:全排列版本:public class Test { private static int times = 0; private static int minCost = Integer.MAX_V...

2018-08-29 13:38:45

2019阿里校招测评题 光明小学完全图最短路径问题

题目:光明小学的小朋友们要举行一年一度的接力跑大赛了,但是小朋友们却遇到了一个难题:设计接力跑大赛的线路,你能帮助他们完成这项工作么?光明小学可以抽象成一张有N个节点的图,每两点间都有一条道路相连。光明小学的每个班都有M个学生,所以你要为他们设计出一条恰好经过M条边的路径。光明小学的小朋友们希望全盘考虑所有的因素,所以你需要把任意两点间经过M条边的最短路径的距离输出出来以供参考。你需要...

2018-08-29 13:38:34

数据库锁整理

B+树在了解数据库索引之前,首先了解一下数据库索引的数据结构基础,B+treeB+tree 是一个n叉树,每个节点有多个叶子节点,一颗B+树包含根节点,内部节点,叶子节点。根节点可能是一个叶子节点,也可能是一个包含两个或两个以上叶子节点的节点。B+tree的性质:n棵子tree的节点包含n个关键字,不用来保存数据而是保存数据的索引。 所有的叶子结点中包含了全部关键字的信息,及指向...

2018-08-10 12:36:58

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

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

Leetcode 403. Frog Jump 青蛙过河

题目:一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。给定石子的位置列表(用单元格序号升序表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一个石子上)。 开始时, 青蛙默认已站在第一个石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格1跳至单元格2)。如果青蛙上一步跳跃了 k 个单...

2018-07-13 15:35:05

最小堆--原理及JAVA实现

什么是堆最小堆是一种数据结构,有着如下特点:顺序:堆顶元素永远是最小的。形状:堆是一颗完全二叉树。这两个特性保证了堆在插入和删除的过程中最大时间复杂度也是满足O(logn)的,所以是一种非常高效的数据结构格式。更新堆的方式更新堆的两种方式,分别对应了插入元素和删除堆顶元素操作:自底向上自顶向下堆的实现可以使用数组作为隐式树(因为结构是完全二叉树),不使用索引为0的元素,从1开始。如果当前元素的下标...

2018-07-12 13:57:37

Leetcode 174. Dungeon Game 地下城游戏

题目:一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房...

2018-07-09 11:25:35

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

牛客网系列--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

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

Leetcode 203. Remove Linked List Elements 删除链表中的节点

题目:解题思路:代码实现:

2018-07-06 13:40:10

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

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

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

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

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

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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!