刷leetCode算法题+解析（十九）

闲来无事多刷几道题。

存在重复元素

给定一个整数数组，判断是否存在重复元素。如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

思路:这个题暴力法就能解决，随随便便好几种方法。绝对不打脸的，排序然后比较，但是我觉得用这种方法肯定会有人说既然算法题别用现成的api。还可以用map。key是数值，value随意。遍历数组，有存在的key说明重了，返回true。圈遍历下来没true说明没重复的，返回false。我去撸代码了。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                return true;
            }else{
                map.put(nums[i],1);
            }
        }
        return false;
    }
}

额，这种是最简单的方式，其实这个和上片文中的一道题同构字符串差不多原理（有兴趣的可以看看同构字符串）其实应该也可以用位置来判断，我去试试。
试完回来了，理论上讲这个方法是可以的。不过在这里提交超出时间限制的（真的佩服leetcode测试案例）。所以我还是想想别的办法吧。
看了官方题解，居然是建议排序???那这个方法有什么意义了？理解不了。感觉有点欺骗感情啊。算了，下一题吧。

存在重复元素二

题目：给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = 2
输出: false

思路：这种系列题很不错啊，大多数一个通个个通。其实这个题跟上题差不多，判断是不是重复元素，区别只不过多加了一步还要判断和上个重复元素的位置差。满足要求返回true，遍历完没满足的返回false。直接上代码：

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                if(i-map.get(nums[i])>k){
                    //其实求的是相同元素最小差值，所以再之前的不用管，直接替换掉
                    map.put(nums[i],i);
                }else{
                    return true;
                }
            }else{
                map.put(nums[i],i);
            }
        }
        return false;
    }
}

因为这个性能已经很不错了，所以我直接下一题了。

用队列实现栈

题目：使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

思路：这个题怎么说呢，我做过类似的，只不过当时那个题要求是实现这些方法外还有个getMin（）获取栈中的最小值。而且并没有要求一定要用队列做。具体哪道题我有点忘了，不过这都不重要。咱们继续说这道题：其实非常简单，要求也很明确，就是简单的实现四个方法而已。一步步分析：首先这个push进去的是一个int（模板上有），所以这个队列Queue是int类型的，其次在java中队列实现类如下图，我个人决定用熟悉一点的LinkedList来实现。剩下没啥好说的，说实话，我完全没懂这个题考的啥？对java队列方法的理解？？算了，我先去撸代码。

Queue实现类
代码实现，简单粗暴到没朋友，一直怀疑我是不是审错题了。完全不懂直接调用api是干啥的。但是非要队列实现，我也不能自己写，奇了怪了就是。

class MyStack {

    private LinkedList queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.addFirst(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return (int)queue.poll(); 
    }
    
    /** Get the top element. */
    public int top() {
        return (int)queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        if(queue.peek()==null){
            return true;
        }       
        return false;
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

看了评论才看明白坑点在哪里：这个题目上说了只能使用队列的基本操作。就是往后插入，从前面获取，是否为空等。我上问用到的addFirst不能用。这一块要自己实现。其实主要就是队列的特性就是先入后出。正好相反栈的特点就是先入先出，所以
这道题的考点也就是这。用队列来实现先入先出。改进的话只要把上文的push方法改一下就行了，其实方法应该不少，我选了一个最简单的，就是整个取出来重新装一下，虽然想想性能就不能太好（数据多了肯定麻烦的要死），但是因为现在心态有点炸所以就先这样吧。直接贴代码：

class MyStack {

    private Queue queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.add(x);
        int sz = queue.size();
        while (sz > 1) {
            queue.add(queue.poll());
            sz--;
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return (int)queue.poll(); 
    }
    
    /** Get the top element. */
    public int top() {
        return (int)queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        if(queue.peek()==null){
            return true;
        }       
        return false;
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

刷题就到这了，顺便说点别的。
我一直声明我喜欢it行业敲代码是种乐趣。毕竟1就是1，0就是0.对就是对，错就是错。干净又明了。结果现在做个题看评论给我看出脾气来了！刷算法题就应该自己造轮子?那些说这道题考什么考什么的，用了什么什么就丢人了的，题目上都没写，作者指不定都没想到，你是什么玩意儿?站在道德制高点优越个鸡儿呢？mmp哦，刷算法就nb怎么不说用编程语言没意义，直接去0，1机器码写呢？
今天刷题就刷到这，我去leetCode评论喷人去了，合理的发泄有利于身心健康。如果稍微帮到你了记得点个喜欢点个关注，另外也祝大家工作顺顺利利！