没有感情的刷题机器

原创 LEETCODE ALL IN ONE PYTHON

LEETCODE ALL IN ONE PYTHON题号 题目 标签 备注 1 2 3 无重复字符的最长子串 滑动窗口 剑指offer、字节跳动 4 寻找两个有序数组的中位数 二分 5 6 ...

原创 MapReduce案例Java版本

MapReduce

原创 dfs 求二叉树节点最大深度/创建一颗二叉树

def dfs(m_root, deep): if not m_root: return val_depth_map[m_root.val] = max(val_depth_map.get(m_root.val, 0), deep) dfs(m_root.left, deep + 1) dfs(m_root.right, deep + 1)dfs(root, 1)def create_tree(root, array, i): if i &.

原创 leetcode373. 查找和最小的K对数字

1.题目描述给定两个以升序排列的整数数组 nums1 和 nums2,以及一个整数 k。定义一对值(u,v)，其中第一个元素来自nums1，第二个元素来自 nums2。请找到和最小的 k个数对(u1,v1), (u2,v2) ... (uk,vk)。示例 1:输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3输出: [1,2],[1,4],[1,6]解释: 返回序列中的前 3 对数： [1,2],[1,4]...

原创 Python实现二分查找lower_bound和upper_bound

使用前提条件：数组是有序不递减数组内置函数：lower_bound：返回数组中大于等于target的第一个索引：index = bisect.bisect_left(nums, target)如果返回等于数组长度或者对应位置索引不等于目标值,那么说明没有找到upper_bound：返回数组中大于target的第一个索引：index = bisect.bisect_right(nums, target)该函数返回的是第一个大于目标值的索引, 如果返回0或者该索引前一个位置的值不是目

原创 leetcode1712.将数组分成三个子数组的方案数

1.题目描述1712. 将数组分成三个子数组的方案数我们称一个分割整数数组的方案是好的，当它满足：数组被分成三个非空连续子数组，从左至右分别命名为left，mid，right。 left中元素和小于等于mid中元素和，mid中元素和小于等于right中元素和。给你一个非负整数数组nums，请你返回好的分割nums方案数目。由于答案可能会很大，请你将结果对109+ 7取余后返回。示例 1：输入：nums = [1,1,1]...

原创 leetcode1094. 拼车「差分」、leetcode1109. 航班预定统计「差分」

1.题目描述假设你是一位顺风车司机，车上最初有capacity个空座位可以用来载客。由于道路的限制，车只能向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。这儿有一份乘客行程计划表trips[][]，其中trips[i] = [num_passengers, start_location, end_location]包含了第 i 组乘客的行程信息：必须接送的乘客数量；乘客的上车地点；以及乘客的下车地点。这些给出的地点位置是从你的初始出发位置向前...

原创 “差分“的介绍与使用方法

"差分"的介绍与使用方法_哔哩哔哩_bilibili差分数组：前缀和的逆运算。适用于数组一段区间反复修改。eg.对下面这一全0数组的3~5区间的每个元素+21.差分数组：对下标起始位置元素+2，对下标结束位置的下一个位置元素-2（取反）2.前缀和求解：见红色部分由O(n)降到了O(1)如果有多次数组的修改，复杂度由由O(n^2)降到了O(n)(因为还有求前缀和的操作)eg.对下面这一非全0数组的两个区间分别+3、-21.求解差分数组：第一位直接落，接下来的用这一位

原创 leetcode503. 下一个更大元素 II「单调栈」

1.题目描述给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。示例 1:输入: [1,2,1]输出: [2,-1,2]解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。注意: 输入数组的长度不会超过 10000.

原创 SQL中只要用到聚合函数就一定要用到group by 吗？

原创 leetcode509.斐波那契数

1.题目描述斐波那契数，通常用F(n) 表示，形成的序列称为 斐波那契数列 。该数列由0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0，F(1)= 1F(n) = F(n - 1) + F(n - 2)，其中 n > 1给你 n ，请计算 F(n) 。示例 1：输入：2输出：1解释：F(2) = F(1) + F(0) = 1 + 0 = 1示例 2：输入：3输出：2解释：F(3) = F(2) + F(1) = 1 + 1 ...

原创 剑指offer10- II. 青蛙跳台阶问题

1.题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。示例 1：输入：n = 2输出：2示例 2：输入：n = 7输出：21示例 3：输入：n = 0输出：1提示：0 <= n <= 100注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbi.

转载 搜索系统简介

搜索系统简介一个基本的搜索引擎系统主要由离线（建库）和在线（检索）两部分构成，离线侧主要完成“网页获取——网页分析——建倒排索引库”的过程，在线侧主要完成“query获取——query处理——与doc进行相关性匹配”的过程。首先给出一个全貌图：搜索系统概览网页获取做过爬虫的人都知道，网页获取实际上就是一个spider的过程，spider通过“抓取网页——分析页面——进网页库——提取链接——抓取网页”的循环过程从互联网上源源不断的获取网页，评价一个spider的优劣主要从“覆盖率”、“时效..

原创 leetcode103. 二叉树的锯齿形层次遍历

1.题目描述给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。例如：给定二叉树[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回锯齿形层次遍历如下：[ [3], [20,9], [15,7]]来源：力扣（Le...

原创 leetcode167. 两数之和 II - 输入有序数组

1.题目描述给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1必须小于index2。说明:返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。示例:输入: numbers = [2, 7, 1...

原创 leetcode445. 两数相加 II

1.题目描述给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。进阶:如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。示例:输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 ...

原创 leetcode2. 两数相加

1.题目描述给出两个非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0开头。示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -...

原创 字节跳动面试题.如何等概率地大小为n的数组中选取m个整数(python)

题目描述：随机的从大小为n的数组中选取m个整数，要求每个元素被选中的概率相等。分析与解答：首先从有N个元素的数组中随机选出一个元素，然后把这个选中的数字与数组中第一个元素交换，接着从数组后面N-1个数字中选出1个元素与数组中第二个元素交换，以此类推，直到选出m个数字为止，数组前m个数字就是随机选出来的m个数字，且他们被选中的概率相同。————————————————版权声明：本文为CS...

原创 leetcode460.LFU缓存「2020-0405」

1.题目描述设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get和put。get(key)- 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。put(key, value)- 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最...

原创 剑指offer／leetcode21. 合并两个有序链表

1.题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/merge-two-sorted-...

原创 leetcode128.最长连续序列

1.题目描述给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为O(n)。示例:输入:[100, 4, 200, 1, 3, 2]输出: 4解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。2.解题思路这些数字用一个 HashSet 保存（或者用 Python 里的 Set），实现 O(1)时间的查询，同时，我们只对 当前数字...

原创 剑指offer.左旋转字符串Python「字节跳动」

1.题目描述汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！2.解题思路就是将原数组，分为两个部分，分别将这两个部分逆序，然后再将合并后的字符...

原创 字节跳动面试题.使用固定长度的数组实现队列

/** * 固定长度数组实现队列 */public class ArrayQueue { private int[] data; private int start; private int end; private int size; public ArrayQueue(int capacity) { if (capacity &...

原创 leetcode41.缺失的第一个正数

1.题目描述给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。示例1:输入: [1,2,0]输出: 3示例2:输入: [3,4,-1,1]输出: 2示例3:输入: [7,8,9,11,12]输出: 1提示：你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。来源：力扣（LeetCode）链接：https://l...

原创 leetcode160.相交链表

1.题目描述编写一个程序，找到两个单链表相交的起始节点。如下面的两个链表：在节点 c1 开始相交。示例 1：输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出：Reference of the node with value = 8输入解释：...

原创 leetcode567.字符串的排列

1.题目描述给定两个字符串s1和s2，写一个函数来判断 s2 是否包含 s1的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。示例1:输入: s1 = "ab" s2 = "eidbaooo"输出: True解释: s2 包含 s1 的排列之一 ("ba").示例2:输入: s1= "ab" s2 = "eidboaoo"输出: False...

原创 leetcode8. 字符串转换整数 (atoi)「2020-0403」

1.题目描述请你来实现一个atoi函数，使其能将字符串转换成整数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。该字符串在有效的整数部分之...

原创 字节跳动面试题.二叉排序树的合并

1.题目描述试编写程序，将两棵二叉排序树合并为一棵二叉排序树。2.解题思路将第二棵树的节点合并到第一棵树上，然后中序遍历第一棵树递归中序遍历第二棵树的节点，再将节点插入到第一棵树中3.代码实现class TreeNode(object): def __init__(self, x): self.val = x self.left...

原创 归并排序

def merge(arr,l,m,r): lenA=m-l+1 lenB=r-m A=[0]*lenA B=[0]*lenB for i in range(lenA): A[i]=arr[l+i] for i in range(lenB): B[i]=arr[m+1+i] i=0 j=0 ...

原创 leetcode1111. 有效括号的嵌套深度「2020-0401」

1.题目描述有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。详情参见题末「有效括号字符串」部分。嵌套深度 depth 定义：即有效括号字符串嵌套的层数，depth(A) 表示有效括号字符串 A 的嵌套深度。详情参见题末「嵌套深度」部分。有效括号字符串类型与对应的嵌套深度计算方法如下图所示：给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有...

原创 如何使用简单的SQL查询在MySQL中计算中位数

https://forum.huawei.com/enterprise/zh/thread-424163-1-1.html

原创 字节跳动面试题.个人玩抛硬币的游戏，谁先抛到正面就获胜。那么先抛的人获胜概率为？

第一次：正第三次：反反正第五次：反反反反正.......第N次：反反。。。。正p=1/2+(1/2)^3+(1/2)^5+······+（1/2）^(2n+1)=1/2*(1+1/4+(1/4)^2+……+(1/4)^n)当公比不为1时，等比数列的求和公式为：Sn=[a1(1-q^n)]/(1-q)对于一个无穷递降数列，数列的公比小于1,当上式得n趋向于正无穷大时，分子括号中的...

原创 leetcode950.按递增顺序显示卡牌

1.题目描述牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。最初，这些卡牌在牌组里是正面朝下的（即，未显示状态）。现在，重复执行以下步骤，直到显示所有卡牌为止：从牌组顶部抽一张牌，显示它，然后将其从牌组中移出。如果牌组中仍有牌，则将下一张处于牌组顶部的牌放在牌组的底部。如果仍有未显示的牌，那么返回步骤 1。否则，停止行动。返回能以递增顺序显示...

原创 leetcode7.整数反转

1.题目描述给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例1:输入: 123输出: 321示例 2:输入: -123输出: -321示例 3:输入: 120输出: 21注意:假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为[−231,231− 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。...

原创 字节跳动面试题.1条直线把平面分成2部分，2条直线最多把平面分成4部分，那么3条直线最多把平面分成几部分？n条呢？

原创 字节跳动面试题.无序数组求最大值

1.对于无序数组a，求a[i]-a[j]的最大值，其中i<j参考：https://www.cnblogs.com/freedom-wangyb/p/4192611.htmlpackage test;import java.util.Arrays;public class FindMax { public static void main(String[] args)...

原创 leetcode215. 数组中的第K个最大元素

1.题目描述在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1:输入: [3,2,1,5,6,4] 和 k = 2输出: 5示例2:输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4说明:你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。来源：力扣（...

原创 剑指offer27. 二叉树的镜像／leetcode226. 翻转二叉树

1.题目描述翻转一棵二叉树。示例：输入： 4 / \ 2 7/ \ / \1 3 6 9输出： 4 / \ 7 2/ \ / \9 6 3 1来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/invert-b...

原创 字节跳动面试题.二叉树最左下节点、二叉树最左节点、二叉树每行最左边节点

二叉树最左下节点、二叉树最左节点：二叉树每行最左边节点方法一：# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self....

原创 leetcode409.最长回文串「2020-0319」

1.题目描述给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如"Aa"不能当做一个回文字符串。注意:假设字符串的长度不会超过 1010。示例 1:输入:"abccccdd"输出:7解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。2.解题思路如果一个字母出现的次...