周末周末，今天的目标五道题就好~~~加油！
数组的度
题目：给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
示例 1:
输入: [1, 2, 2, 3, 1]
输出: 2
解释:
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.
示例 2:
输入: [1,2,2,3,1,4,2]
输出: 6
注意:
nums.length 在1到50,000区间范围内。
nums[i] 是一个在0到49,999范围内的整数。
思路：讲真，我现在觉得难的不是题目本身或者思路，而且阅读理解的水平。读了两遍题目大概觉得所谓的数组的度：就是数组中最多元素的个数。这道题我理解的就是找到数组中包含最多元素个数的子串。比如 1 1 1 1 2 3 4 5 这个子串就是前面四个1.再比如1 01 2 1 3 1 4 1这个子串就是全串。我不知道我说明白没有，反正我自己明白了。我去尝试写代码了。
说一下思路：最笨的就是先获取出现次数最多的元素值。然后判断第一次出现和最后一次出现的位置，然后截取字串。但是我目前的想要是要借助map来判断。尝试去写了。
写完回来了，首先这道题我的思路没问题，但是真写出来有点麻烦。其次性能超过百分之八十多，没达到我心里预期。但是我已经想好改进的办法了，一会儿去试试，先把第一版本的代码贴上来：
class Solution {
public int findShortestSubArray(int[] nums) {
Map<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>>();
int n = 0;
int[] val = new int[nums.length];
int index = 0;
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
List<Integer> list = map.get(nums[i]);
list.add(i);
map.put(nums[i],list);
if(n<list.size()){
n = list.size();
index = 0;
val[index] = nums[i];
index++;
}else if(n == list.size()){
val[index] = nums[i];
index++;
}
}else{
List<Integer> list = new ArrayList<Integer>();
list.add(i);
map.put(nums[i],list);
}
}
//数组中没有重复元素，每一个子串都是度
if(index==0) return 1;
int res = 50001;
for(int x = 0;x<index;x++){
List<Integer> list = map.get(val[x]);
//最后一次出现的下标减去第一次出现的下标+1就是字串的长度
int temp = list.get(list.size()-1)-list.get(0)+1;
res = res<temp?res:temp;
}
return res;
}
}
写的比较墨迹，我改进一下的。改进完了性能和消耗都更好了我能说什么？我也很绝望啊！！！
看了第一的代码，不能不说这些数据结构中，数组是最简单方便快捷的处理方式了，性能不行用数组快成为真理了。这个性能第一的代码用的数组处理。我这里map的key是数字本身，value是list，用list的长度判断次数，用list中的int记录下标。而人家是用了三个数组，下标代表元素来处理的！
说不会有点过了，但是处理起来比较绕。而且没有我上面的直观，可是性能真的是好太多！我执行下来31ms，人家用2ms。也不是很难，只不过一来是我没想到那么做而已。接下来附上代码：
class Solution {
public int findShortestSubArray(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
int max = 0;
for (int i : nums) {
max = Math.max(i, max);
}
int[] temp = new int[max + 1];
int[] first = new int[max + 1];
int[] last = new int[max + 1];
int maxTime = 1;
for (int i = 0; i < nums.length; i++) {
temp[nums[i]]++;
//这里如果这个元素第一次出现则在first数组中存储，是第一次出现的下标
if (temp[nums[i]] == 1) {
first[nums[i]] = i;
}
//肯定是越往后数字越大， 所以这个last中不断替换，存储的就是最后一次出现的下标
last[nums[i]] = i;
//这个遍历是记录出现次数最多的次数个数
maxTime = Math.max(maxTime, temp[nums[i]]);
}
int result = nums.length;
for (int i = 0; i < max + 1; i++) {
//只有本身是次数最多的元素才有必要判断，
if (temp[i] == maxTime) {
result = Math.min(result, last[i] - first[i] + 1);
}
}
return result;
}
}
好了，我自己理了一遍思路，想法都写在注释上了，这道题其实不难，感觉考点是性能，下一题吧。
二叉搜索树中的搜索
题目：给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
思路：这道理怎么说呢，感觉简单的离谱啊？？是我想简单了么？因为是二叉搜索树，所以遵循左小右大的原则，我现在的理解就是根据条件遍历。。我去试试有没有坑吧。
试完了，完全没坑，三分钟搞定，性能超过百分百，确定他就是一道小白题！直接上代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root==null) return null;
if(root.val==val) return root;
if(root.val>val) return searchBST(root.left,val);
if(root.val<val) return searchBST(root.right,val);
return null;
}
}
哈哈，我都是顺序刷的简单的题目，知道我周末不太愿意刷题所以给我凑题数的么？希望接下来的几道题都这么简单~~~
数据流中的第K大元素
题目：设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。
示例:
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
说明:
你可以假设 nums 的长度≥ k-1 且k ≥ 1。
思路：先说题目，看了两遍，认真看了给的demo，才算是明白了是什么意思。首先这个add不是一次性操作，而是add一次同一个对象的数组里就一直多这么一个元素了。其实这个题我感觉是实现简单，但是性能好的实现比较难，不然一个Arrays.sort就搞定了没什么意义了。我去尝试写代码了。
咳咳，反正第一版代码我用贼无脑的形式实现了，起码先实现再优化，哈哈
class KthLargest {
private int k;
private List<Integer> list;
public KthLargest(int k, int[] nums) {
this.k = k;
list = new ArrayList<Integer>();
for(int i:nums){
list.add(i);
}
}
public int add(int val) {
list.add(val);
Collections.sort(list);
return list.get(list.size()-k);
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
不出所料的性能，只超过百分之七的人。其实优化点很多，我这个版本也是为了测试我对题目的理解对不对。接下来我去真的实现了。
好了，进化版出来了，依然排名二三十而已，完全数组实现了，直接贴代码：
class KthLargest {
private int[] arr;
public KthLargest(int k, int[] nums) {
arr = new int[k];
Arrays.sort(nums);
int j = k-1;
int i = nums.length-1;
if(j>i) arr[0] = Integer.MIN_VALUE;
while(i>=0 && j>=0){
arr[j] = nums[i];
i--;
j--;
}
}
public int add(int val) {
if(val<=arr[0]) return arr[0];
for(int i=arr.length-1;i>=0;i--){
if(val>arr[i]){
int temp = arr[i];
arr[i] = val;
val =temp;
}
}
return arr[0];
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLarges>t(k, nums);
* int param_1 = obj.add(val);
*/
感觉唯一可能拖性能的也就是那个排序了，可是总不能我自己实现吧？真的是脑壳痛，我放弃优化了，直接看人家性能好的怎么写的吧。
看到了一个数据结构：PriorityQueue。
这个类厉害了，自带比较大小的队列。
PriorityQueue使用跟普通队列一样，唯一区别是PriorityQueue会根据排序规则决定谁在队头，谁在队尾。
有了这个属性就不用自己比较了，虽然还没看源码不知道人家怎么封装的，但是看别人代码用了这个类几乎就是一次搞定，我去写出来：
class KthLargest {
private PriorityQueue<Integer> q;
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
q = new PriorityQueue<Integer>(k);
for(int i:nums){
add(i);
}
}
public int add(int val) {
//如果还没被填满就顺序往里填充元素
//这种情况要么正在初始化，要么第一次调用add往里填充元素
if(q.size() < k) {
q.offer(val);
//如果已经满了，判断第一个元素和val大小，如果val较大才需要操作不谈直接返回第一个就行
}else if(q.peek() < val) {
q.poll();
q.offer(val);
}
return q.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLarges>t(k, nums);
* int param_1 = obj.add(val);
*/
顺便看了一些 PriorityQueue类的知识，不过因为在家所以没看源码。先记下有空去看。觉得还是知道的少，早知道这个数据结构还用废那么久时间自己实现么~~
二分查找
题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
思路：这个题怕不是出错地方了吧？要是刚刚接触算法可能还要想想，现在都用烂了好不好~~我去直接实现了。
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]>target){
right = mid-1;
}else{
left = mid+1;
}
}
return -1;
}
}
就这样了，反正也没啥亮点，唯一算是坑的就是可能只有一个元素，所以left是可以等于right的。就是一个普通的二分法。
设计哈希集合
题目：不使用任何内建的哈希表库设计一个哈希集合。具体地说，你的设计应该包含以下的功能
add(value)：向哈希集合中插入一个值。
contains(value) ：返回哈希集合中是否存在这个值。
remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
示例:
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);
hashSet.add(2);
hashSet.contains(1); // 返回 true
hashSet.contains(3); // 返回 false (未找到)
hashSet.add(2);
hashSet.contains(2); // 返回 true
hashSet.remove(2);
hashSet.contains(2); // 返回 false (已经被删除)
注意：
所有的值都在 [0, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希集合库。
思路:这道题怎么说呢，我只能说实现的方式很多，但是性能是主要考虑因素。不然暴力实现感觉就跟投机取巧了似的。其实我觉得就是实现一个Set。我先想想怎么提高效率。灵机一动，我决定用数组！！去写代码了！
我现在爱死了我自己的灵机一动。用数组实现了，数组下标代表数字，贴代码：
class MyHashSet {
private int[] n;
/** Initialize your data structure here. */
public MyHashSet() {
n = new int[1000001];
n[0] = -1;
}
public void add(int key) {
n[key] = key;
}
public void remove(int key) {
n[key] = (key==0?-1:0);
}
/** Returns true if this set contains the specified element */
public boolean contains(int key) {
return n[key]==key;
}
}
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet obj = new MyHashSet();
* obj.add(key);
* obj.remove(key);
* boolean param_3 = obj.contains(key);
*/
其实每个方法就是几行代码，非要说缺点应该就是每个set都要初始一个大容量的数组吧？我去看看排第一的代码是怎么实现的。
emmmmmmm....我们是一样的思路，只不过我这是用数字代表有没有，人家是Boolean值代表的。我直接贴代码：
class MyHashSet {
boolean[] hash = new boolean[1000001];
/** Initialize your data structure here. */
public MyHashSet() {
}
public void add(int key) {
hash[key] = true;
}
public void remove(int key) {
hash[key] = false;;
}
/** Returns true if this set contains the specified element */
public boolean contains(int key) {
return hash[key];
}
}
思路一样，大同小异而已~~~这道题就这么过！
虽然今天的目标是五道题，但是讲真这几道都是送分题，时间还早，再做一两道。
设计哈希映射
题目：不使用任何内建的哈希表库设计一个哈希映射.具体地说，你的设计应该包含以下的功能
put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
remove(key)：如果映射中存在这个键，删除这个数值对。
示例：
MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // 返回 1
hashMap.get(3); // 返回 -1 (未找到)
hashMap.put(2, 1); // 更新已有的值
hashMap.get(2); // 返回 1
hashMap.remove(2); // 删除键为2的数据
hashMap.get(2); // 返回 -1 (未找到)
注意：
所有的值都在 [1, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希库。
思路：刚刚差点以为是进错题了。仔细一看跟上面那道题不一样。这道题是key-val对的存储。但是我不慌啊，思路可以直接复制，甚至我上一个用数字代表元素比人家用boolean代表元素的还要好用，而且我看题目这次的值在1-1000000之间，不就是为了避开0省的挨个赋值嘛？嘿嘿，给我五分钟去实现。
不是，这个题玩赖啊？？？？？都说好了所有的值都在1-1000000之间，怎么还能put 0 呢？过分了吧?太过分了！本来想直接返回的，看这样还是处理一下吧。
好了，实现了：
class MyHashMap {
private int[] num = new int[1000001];
/** Initialize your data structure here. */
public MyHashMap() {
}
/** value will always be non-negative. */
public void put(int key, int value) {
num[key] = key+value;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
public int get(int key) {
return num[key]==0?-1:num[key]-key;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
num[key] = 0;
}
}
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap obj = new MyHashMap();
* obj.put(key,value);
* int param_2 = obj.get(key);
* obj.remove(key);
*/
还是老思路:数组下标代表key，val本来想直接存的，但是因为可以put 0 的骚操作，所以我这里存key+val的和。这样可以知道这个key到底有没有。至于获取val用存的数字减去key就行了。
性能不是很理想，我去看看被人怎么实现的。。
卧槽，大佬用的链表实现的，，厉害了，，，有点懵，这么简单的题生生做的贼复杂。。。算了算了，我还是不求甚解点吧。直接下一题吧。
转换成小写字母
题目：实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。
示例 1：
输入: "Hello"
输出: "hello"
示例 2：
输入: "here"
输出: "here"
示例 3：
输入: "LOVELY"
输出: "lovely"
思路：这个题第一思路绝对是用char判断，如果超过了a-z的数字范围就处理成对应小写的char.我还得去查查char对应的数字是多少
大写变小写+32。我去实现啦：
!!!这个题有毒吧，既然字符串中可能有不是字母的元素为啥示例不弄一个出来？？？示例都是字母，结果提交了测试案例给我出特殊符号了？合适么?
行了，做出来了，直接性能超过百分百，一道送分题。一开始我以为不是大写就是小写，所以只判断小于'a'就行了，后来发现还有乱七八糟的符号，所以判断变成了大于'A'小于'Z'。
class Solution {
public String toLowerCase(String str) {
char[] res = str.toCharArray();
for(int i=0;i<res.length;i++){
if(res[i]>='A'&& res[i]<='Z') res[i] = (char) (res[i]+32);
}
return new String(res);
}
}
嗯嗯，这道题教会我代码要严谨（个鬼！）。。有进步有进步。继续下一题。
1比特与2比特字符
题目：有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。
示例 1:
输入:
bits = [1, 0, 0]
输出: True
解释:
唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。
示例 2:
输入:
bits = [1, 1, 1, 0]
输出: False
解释:
唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。
注意:
1 <= len(bits) <= 1000.
bits[i] 总是0 或 1.
思路:哎，这就不太好了啊，越是寻思做几道就去玩游戏越是遇到简单的题几分钟刷一道。沉迷刷题不可自拔~~~~这道题感觉只需要判断最后0前面是什么，如果是0则肯定是true。如果是1则判断有几个1.单数1说明是false，双数1说明是true。我去试试。感觉应该就这么简单。
直接贴代码：
class Solution {
public boolean isOneBitCharacter(int[] bits) {
int count = 0;
for(int i=bits.length-2;i>=0;i--){
if(bits[i]==1){
count++;
}else{
break;
}
}
return count%2==0;
}
}
比较简单，只要明白怎么计算就行了。下一题。
字典中最长的单词
题目：给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
示例 1:
输入:
words = ["w","wo","wor","worl", "world"]
输出: "world"
解释:
单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。
示例 2:
输入:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出: "apple"
解释:
"apply"和"apple"都能由词典中的单词组成。但是"apple"得字典序小于"apply"。
注意:
所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。
思路：很好，又遇到题目比较复杂的题了。理解了半天，才看明白示例而的banana就是捣乱的，因为没有从第一个单词开始逐步添加一个字母组成。所以不用考虑。然后可能有多个可行的方案，所以从最长的开始挨个判断一时间也没想出好的办法。。首先分析这个若无答案返回空串。因为这个单词到底是不是真的也不用考虑，所以哪怕有一个单词也算是答案啊，除非数组是空的，但是他都说了数组长度范围1-1000。奇了怪了,真的会有返回空的时候？哈哈，好了，先不吐槽了，继续做题。
做完了，思路清晰明了简单快捷，就是性能略微差点：
class Solution {
public String longestWord(String[] words) {
Arrays.sort(words);
Set<String> set = new HashSet<>();
String res = "";
for (String s : words) {
//一个字母是一个单词，但是不见得是最长单词，不过可能是别的单词的底子，所以存进set
//如果是两个单词一定要保证第一个单词是有的，三个要保证前两个单词是有的
if (s.length() == 1 || set.contains(s.substring(0, s.length() - 1))) {
//这有个坑，本来我觉得后面的一定比前面的长，直接赋值res的
//后来报错了。因为也会等于。而等于要取前面的值
res = s.length() > res.length() ? s : res;
//添加进set
set.add(s);
}
}
return res;
}
}
中间关于赋值的坑我特意写了注释，千万要注意。第一遍提交我是res=s，然后错了！剩下的优化。。其实我觉得我性能可能差在1.数组的排序。 2.一直用contains判断。。。但是怎么优化没思路。我直接看排行第一的代码吧：
我不知道是不是我又没理解题意或者说什么，排行前几的代码！都复杂的不行！创建内部类，外部类，递归加递归，循环加循环的。。。
大佬们为了这个题写了几十上百行代码，我有点心虚啊。。。是不是一个解题方式啊？？
真的思路NB，完全是字典的模式，每一个单词26种选择，然后到第二个字母又是26种情况。。以此类推，我只能说set的contains性能是真的差！！！！这种判断都比不过。。。我甚至隐隐有冲动有数组型数组型数组型....数组来存储了！哎，算了算了，大佬解法真的有点复杂，我还是静静的当一个用现成api的咸鱼吧。。。这道题也就到这里。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注！也祝大家周末愉快，工作顺顺利利！每天进步一点点，唯有努力不欺人~~！
