37、数字在升序数组中出现的次数 解题思路： 题目说的在升序数组找到一个目标，然后统计这个目标出现的次数，我们要好好利用升序数组这个条件。 有了这个条件，我们就可以算出这个目标值的左边界还有右边界，然后取两者之差即可统计出这个目标出现的次数。 因为我们要找到目标值的左边界和右边界，我们很容易能想到用二分查找去求。 那么，找出左边界其实很好找，那要怎么找到右边界呢，我们可以将右边界转化为求比目标值大的数的左边界来求。 也就是说，我们如果要 求数字 4的右边界，那我们其实可以求数字5的左边界然后也就知道了4的右边界了。 代码步骤： 先定位到左边界 接着定位右边界 判断左边界是否符合规范，若超出数...

36、两个链表的第一个公共结点 解题思路： 使用两个指针N1,N2，一个从链表1的头节点开始遍历，我们记为N1，一个从链表2的头节点开始遍历，我们记为N2。 让N1和N2一起遍历，当N1先走完链表1的尽头（为null）的时候，则从链表2的头节点继续遍历，同样，如果N2先走完了链表2的尽头，则从链表1的头节点继续遍历，也就是说，N1和N2都会遍历链表1和链表2。 因为两个指针，同样的速度，走完同样长度（链表1+链表2），不管两条链表有无相同节点，都能够到达同时到达终点。 （N1最后肯定能到达链表2的终点，N2肯定能到达链表1的终点）。 所以，如何得到公共节点： 有公共节点的时候，N1和N2必会...

34、第一个只出现一次的字符 解题思路： 这道题目很好理解，就是找出第一个只出现一次的字符。做法也很简单 方法一：哈希表 1、将字符当成哈希表中的key，第一次出现时候为true，重复出现则置为false； 2、遍历数组，拿到第一个在哈希表中的value为true的字符。 来看两张动图，简单易懂理解这种做法： 先初始化哈希表 继续遍历字符数组，获取第一个在哈希表中value为true的字符 看完之后我们直接上代码： public int FirstNotRepeatingChar(String str) { HashMap<Character,Boolean> ...

33、丑数 解题思路： 我们先看到题目，把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。 有了上面的定义我们就可以知道，丑数的形式就是2x3y5z所以我们可以定义一个数组res，存储第n个丑数。因为我们要将丑数按从小到大的顺序排序，所以我们就得将对应的丑数放在对应的下标位置，小的放前面。因为最小的丑数就是1，所以我们初始化res[0]=1，那么接下来的一个丑数是什么呢？我们自己知道是2。但是我们能不能有一个格式，去将得到接下来的丑数是谁呢？这个时候上面我们的出来的丑数的格式就起作用了，丑数的形...

32、把数组排成最小的数 解题思路： 要注意题目的意思是把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 这道题目可以看成是一道排序的题目，因为要使得结果最小，那么给出的整数要怎么排列呢？其实就可以转化为 A+B 与 B+A 之间比较的问题（注意：这里的A+B并不是A加上B，而是A拼上B），当A+B小于B+A的时候，很明显A要放在B的前面，这样才能使得结果小。 举个例子： 当A = 206，B = 1 此时 A+B = 2061 B+A = 1206 我们可以看到 A+B > B+A，所以很明显B需要放在A的前面，即B+A，才能使得拼出来的数字最小。 我们在...

解题思路： 我们看到题目要求 “输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数”。其实就是求从1-n这n个数中，每一个数的计数位上出现的1的个数的总和。 所以我们只需要知道在某个计数位上面1出现次数的计算方法即可求解这道题目，下面我们分为几种情况讨论： 1、当前位上的值等于0 我们可以看到当前位为百位，即base = 100；当前位上的数为cur = 0，此时为什么需要借位呢？ 因为当cur为0的时候，后面的b即使取0-36的任何一个数，cur都不可能出现1，永远都是0。 所以需要向前借位，借位后cur才能有为1的情况，当cur借到位的时候，将cur变为1，此时我们就可以...

#给牛客的问题反馈和建议# 私信一直服务器错误

题目：给定两个有序数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n/2个数 方法一：双指针假设两个数组为一个数组，先算出上中位数的位置。我们使用双指针去遍历两个数组，并且用一个数记录走过的次数，当次数到达上中位数则返回。或者当有两个数组中的一个数组遍历完之后还没找到上中位数，这是可以确定上中位数在另外一个数组中，也可以根据已经走过的次数去定位到上中位数。 import java.util.*; public class Solution { public int find...

三种解法 分治 顺序合并 优先队列 首先做这道题，得先会一道基础的题目，没做过的可以先去做合并两个已排序的链表 分治（归并） 先分而治之，分到不能再分则合并(归并) 图解： import java.util.*; public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { return merge(lists,0,lists.size()-1); } public ListNode merge(ArrayList<ListNode...

分治 动态规划其实题目可以用动态规划做，很简单的动态规划题目，而且也是最优解先看代码: public int maxsumofSubarray (int[] arr) { int n = arr.length; if(n == 1) return arr[0]; int max = 0; for(int i = 1; i < n; i++){ arr[i] = Math.max(arr[i],arr[i]+arr[i-1]); max = Math....

前言：此类问题就是经典TopK问题快速排序的详细解析可移至博主另外一篇博文几种常见排序下面直接给出题解~常规快速排序 public int findKth(int[] a, int n, int K) { return quickSort(a,0,n-1,K); } //快速排序 public int quickSort(int[] a,int left,int right,int k){ if(left < right){ int point = partition(a,left,right); ...

刚开始犯得错误：直接将整型数组去从大到小去排序，以为就是正确结果。用例： 10，1我的输出会是101，而正确的是110，所以这很明显是错误的，考虑不周到。那么直接用整型的就不行，那就另辟蹊径，用字符串形式进行排序。但是排序的规则要如何定义呢？我们知道，两个字符串之间比较大小的是比较每一个字符的大小，遇到第一个不相等的字符则会根据其ASCII码来比较大小，我们都知道整型数字越大，ASCII码也越大，所以我们只需要比较A+B跟B+A之间的大小，将数组按照这个规则去排序，拍出来的不就是我们想要的结果了吗？ public String solve (int[] nums) { // ...

维护两个指针，一个指向奇数链表的头，一个指向偶数链表的头先将链表分为奇数链表和偶数链表，然后再进行合并。奇数位置的后面必定是偶数，偶数位置后面必定是奇数，利用这个特点即可解决这道题目~ public ListNode oddEvenList (ListNode head) { if (head == null || head.next == null) return head; ListNode odd = head; ListNode oddHead = head; ListNode even = h...