最小的K个数 牛客题霸NC119 难度：Medium 题目描述 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。 输入 [4,5,1,6,2,7,3,8],4返回值 [1,2,3,4]解决思路 使用一个容量为K的最大堆，程序如下： import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { if(k <...

二分查找 牛客题霸NC105 难度：Easy 题目描述 请实现有重复数字的有序数组的二分查找。 输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。 示例 输入 5,4,[1,2,4,4,5]返回值 3说明 输出位置从1开始计算 题目答案 很简单的二分查找，关键看三个地方就行了： low < high 还是low <= high mid是左倾还是右倾 向左收缩条件及向右收缩条件 import java.util.*; public class Solution { /** * 二分查找 * @param n ...

设计LRU缓存结构 牛客题霸NC93 难度：Medium 题目描述 设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能 set(key, value)：将记录(key, value)插入该结构 get(key)：返回key对应的value值 [要求] set和get方法的时间复杂度为O(1) 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。 若opt=1，接下来两个整数x, y，表示set(x, y)若opt=2，接下来一个整数x，表示get(x)，若x未出...

寻找第K大 牛客题霸NC88 难度：Medium 题目描述 有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。 给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。 示例1 输入 [1,3,5,2,2],5,3返回值 2题目解答 利用快排思想 通过快速排序的partion与二分思想找到第K大的数，代码如下： import java.util.*; public class Finder { public int findKth(int[] a, int n, int K) { // write code ...

跳台阶 题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 示例1 输入 1返回值 1示例2 输入 4返回值 5解决思路 就是个斐波那契数列，代码如下： public class Solution { public int JumpFloor(int target) { if(target <= 1){ return 1; } return JumpFloor(target-1) + JumpFloor(target-2); ...

实现二叉树先序中序后序遍历 牛客题霸NC45 难度：Easy 题目描述 分别按照二叉树先序，中序和后序打印所有的节点。 示例 输入 {1,2,3}返回值 [[1,2,3],[2,1,3],[2,3,1]]备注: n≤10^6题目答案 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * ...

合并有序链表 牛客题霸NC33 难度：Easy 题目描述 将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的。 输入 {1},{}返回值 {1}输入 {1},{1}返回值 {1,1}代码解决 算法入门基础题，尾插法扫描拼接即可： import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param l1 ListNode类 ...

求二叉树的层序遍历 牛客题霸NC15 难度：Medium 二叉树的层序遍历使用队列来实现，代码如下： import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型ArrayList<ArrayList&...

判断链表中是否有环 牛客题霸NC93 难度：Easy 题目描述 判断给定的链表中是否有环，你能给出空间复杂度的解法么？ 题目解答 1. Set+遍历 遍历链表，将遍历的每个节点放到一个Set里。如果遍历过程中发现Set中已经存在该节点，则代表链表存在环；如果遍历到末尾，则代表链表无环。 import java.util.*; /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * ...

title: 牛客题霸反转链表题解date: 2020.11.05categories: 算法tags: 算法 反转链表 牛客题霸NC78 难度：Easy 题目描述： 输入一个链表，反转链表后，输出新链表的表头。 示例： 输入： {1, 2, 3} 输出： {3, 2, 1}解决方法： 1.通过栈+尾插法实现 可以将所有节点入栈，然后逐个出栈，插入到链表尾部。 import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { ...

有没有比我更早的，9:20开始😂😂😂

许愿京东Offer

问的问题基本都没答上来，算法题也是别别扭扭的在提示下写出来，毫无意外的挂了 1. 什么场景下用泛型，什么场景下不用 2. java注解的原理 3. [a,b,a,c,a,b,e]输出[a1,b1,a2,c,a3,b2,e] 字节的效率真是高，第二天就流程终止了😂