LeetCode刷题系列

发表于   |   分类于   |     |   阅读次数   |  

LeetCode

我们工作面试和提高自身数据结构和算法能力的时候往往需要刷刷题，我选择LeetCode是通过一个留学论坛了解的。专业，覆盖语种全面。

提前说说刷题的心得：

  • 尽量手写代码，少使用IDE的代码补全和智能提示。既然是提升和锻炼自己的代码功底，那就没有理由再犯没有IDE写代码会死症
  • 让自己去思考本身就是一件艰难的事，所以如果遇到困难，可以借鉴但切不可抄袭他人思考成果。不然刷题就没有意义了，别贪多贪快，自己思考的才是最好的

进入LeetCode官方网站，你会看到醒目的Start coding now，没有账号的同学赶快注册吧，点击此处可以进入题目分类，接着可以根据自己的实际情况，通过难易程度选择题目（PS: 带锁的需要花钱），我是先易后难，找点信心再说 😂。

选择题目后就开始刷题之旅吧，官方提供多种语言的支持，可以实时运行检测代码，也可以自己设置自定的Testcase，介绍到此，祝各位刷题愉快，学业有成，工作顺利～

LeetCode

题目预览表

由易到难排序，目前官网总共出了390+

# Title Difficulty
344 Reverse String Easy
1 Two Sum Easy
371 Sum of Two Integers Easy
7 Reverse Integer Easy
75 Sort Colors Medium
231 Power of Two Easy
232 Implement Queue using Stacks Easy
255 Implement Stack using Queues Easy
155 Min Stack Easy

344. Reverse String

Write a function that takes a string as input and returns the string reversed.

译：输入一段字符串将其倒序并返回

Example:
Given s = “hello”, return “olleh”.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public String reverseString(String s) {
        if (s == null || s.length() == 0) {
            return "";
		}
		StringBuilder sb = new StringBuilder();
        for (int index = s.length() - 1 ; index >= 0; --index ){
            char temp = s.charAt(index);
            sb.append(temp);
        }
        return sb.toString();
    }
}

问题分析

作为最简单的题，我刚开始写的时候也遇到一些坑：

  • 忽略空格、回车的存在，结果检测的时候不过关
  • 没有没有考虑性能问题，仅仅在乎结果是否正确

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

译：给定两个只有整数的数组，获取和为指定数值的两个数的索引

需要假设每个输入的值都仅有一个答案

Example:

1
2
3
4
5
6
> Given nums = [2, 7, 11, 15], target = 9,
>
> Because nums[0] + nums[1] = 2 + 7 = 9,
> return [0, 1].
>
>

>

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int[] twoSum(int[] nums, int target) {
  int[] result = new int[2];
  for (int k = 0; k < nums.length; k++) {
    for (int l = k + 1; l < nums.length; l++) {
      if (nums[k] + nums[l] == target) {
        for (int p : nums) {
          if (nums[k] == p) {
            result[0] = k;
          }
          if (nums[l] == p) {
            result[1] = l;
          }
        }
        return result;
      }
    }
  }
  return result;
}

问题分析

从问题来看，由于题目给了限制，也就是说给定的数组中肯定仅有两个数满足条件，我使用简单的冒泡挨个相加判断是否满足条件而得到答案。

  • 第一/二层通过嵌套for循环遍历数组中每个数与其他数之和
  • 取得两个数后，通过第三个增强for获取两个数在元数组中的索引

371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

译：不用+或者-符号，计算出两个数之和

Example:

Given a = 1 and b = 2, return 3.

1
2
3
4
5
public class Solution {
    public int getSum(int a, int b) {
        // todo ...
    }
}

问题分析

7. Reverse Integer

Reverse digits of an integer.

译：反转一个整数的数字

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

译：你仔细思考过么？写代码前需要考虑到的一些问题，比如你已经考虑到这个整数的最后一个数为0，那么我们应该输出什么呢？例如：输入10，100。你注意到反转的数可能会溢出吗？假设你输入了一个32位的整数，如1000000003反过来就会导致溢出。那你怎么处理这些情况呢？所以对于这个问题来说我们假设如果你反转的数是溢出的，那么就指定它返回0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class ReverseInteger {
    public int reverse(int x) {
        boolean isNegativeNum = false;
        if (x == 0) return 0; // 考虑到为0的情况直接返回0
        if (x < 0) {
          // 如果该数为负数，则使用标志位，并且为了去掉符号实用Math.abs()这个方法取绝对值
            isNegativeNum = true;
            x = Math.abs(x); 
        }
        String xString = String.valueOf(x);
        String result = "";
        int index = xString.length();
      	// 时间复杂度最糟为O(n)
        for (int i = index - 1; i >= 0; i--){
            result += String.valueOf(xString.charAt(i));
        }
        try{
		  // 此处投机取巧，由于反转后的数可能溢出，导致NumberFormatException，
           //所以一旦catch该异常就指定该数为0
            if (!isNegativeNum) return Integer.valueOf(result);
            else return (- Integer.parseInt(result));
        } catch (NumberFormatException e){
            e.printStackTrace();
            return 0;
        }
    }
}

问题分析

需要注意几个点：

  • 题目已经说明了，一旦有溢出的情况就返回0；
  • 如果正好为尾数为0的整数，那么反转后实际需要舍弃0；
  • 正好为0的情况需要考虑到

最近在看《剑指OFFER》，其中提到的边界问题和非法输入的处理尤为重要，所以写的时候都很小心这方面的问题

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

译： 给定一个大小为n的数组，其中包含的元素对象为红、白、蓝，将其进行毗连的排序，顺序为红、白、蓝。在此我们用0，1，2来代表红白蓝三个颜色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void sortColors(int[] nums) {
       if (nums == null) return;
       if (nums.length <= 0) return;
       ArrayList<Integer> redList = new ArrayList<>();
       ArrayList<Integer> whiteList = new ArrayList<>();
       ArrayList<Integer> blueList = new ArrayList<>();
       for (int currentColor : nums){
           if (currentColor == 0) {
               redList.add(currentColor);
           } else if (currentColor == 1) {
               whiteList.add(currentColor);
           } else if (currentColor == 2){
               blueList.add(currentColor);
           }
       }
       redList.addAll(whiteList);
       redList.addAll(blueList);
       int i = 0;
       for (int color : redList){
           nums[i] = color;
           i++;
       }
   }

问题分析

看起来越简单清晰的题，越需要谨慎的对待

首先题中已经给定了数组，虽然三种颜色是随机的，但是可以遍历出每种颜色的数量，在此我将每种颜色使用一个ArrayList存放（个人感觉这么做是最笨的办法），分成三个list后再组合成一个数组。

代码中的两个for的时间复杂度分别为N，总的为2N。

231. Power of Two

Given an integer, write a function to determine if it is a power of two.

译：给定一个整数，写一个能判断是否为2的次方的方法。

实现

1
2
3
4
5
public class Solution {
    public boolean isPowerOfTwo(int n) {
        return (n > 0) && ((n & (n - 1)) == 0);
    }
}

问题分析

一般遇到次方这种题都差不多是跟位运算相关的，写出几个2的次方数，例如：1、2、4、8、16，转换为二进制为：1、10、100、1000、10000，其实想过判断当前有多少位0或1，如果除第一位以外都是0可以得出结论，但想想一旦碰上循环的操作这时间空间复杂度都是嗷嗷的涨，所以还是老老实实别偷懒。-1后除了第一位别的就是1，两者相与则为000000000000…..

232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

  • push(x) – Push element x to the back of queue.
  • pop() – Removes the element from in front of queue.
  • peek() – Get the front element.
  • empty() – Return whether the queue is empty.

Notes:

  • You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

译：使用栈来实现一个拥有以下操作的队列：

  • push(x) – Push element x to the back of queue.
  • pop() – Removes the element from in front of queue.
  • peek() – Get the front element.
  • empty() – Return whether the queue is empty.

注意：

你必须仅仅使用标准的栈操作，意味着存在这几个可用的操作：push到栈顶，从栈顶peek/pop，size和is empty操作

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class TwoQueueUsingStacks {

    Stack<Integer> stackA = new Stack<>();
    Stack<Integer> stackB = new Stack<>();

    // Push element x to the back of queue.
    public void push(int x) {
        stackA.push(x);
    }

    // Removes the element from in front of queue.
    public void pop() {
        if (stackB.empty()) {
            while (!stackA.isEmpty()) {
                stackB.push(stackA.pop());
            }
        }
        stackB.pop();
    }

    // Get the front element.
    public int peek() {
        if (stackB.empty()) {
            while (!stackA.isEmpty()) {
                stackB.push(stackA.pop());
            }
        }
        return stackB.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return (stackA.empty()) && (stackB.empty());
    }
}

问题分析

先画图，画分解图一步步的通过入栈出栈LIFO的特性就能反推出链表FIFO的行为，例如存在两个栈A 、B，将一组元素{a, b, c, d, e, f, g, h} 进行各种链表操作，只要遵循FIFO的行为就不难理解。

225. Implement Stack using Queues

Implement the following operations of a stack using queues.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • empty() – Return whether the stack is empty.

Notes:

  • You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
  • Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
  • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

译：使用队列来实现以下栈的操作：

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • empty() – Return whether the stack is empty.

实现

方法一：队列A负责入栈，队列B负责中转A中的元素

以下实现方式有个不足之处就是每次B不为空时，都需要将B中的所有元素遍历一遍传给A后在A中进行相关操作，导致效率低下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class MyStack {
    
    LinkedList<Integer> queueA = new LinkedList<>();
    LinkedList<Integer> queueB = new LinkedList<>();
    
    // Push element x onto stack.
    public void push(int x) {
        if (queueB.isEmpty()) {
            queueA.add(x);
        } else {
            queueB.add(x);
        }
    }

    // Removes the element on top of the stack.
    public void pop() {
        if (queueA.isEmpty() && queueB.isEmpty()) {
            return;
        }
        if (queueB.isEmpty()) {
            while(queueA.size() > 1) {
                queueB.add(queueA.remove());
            }
            if (queueA.size() > 0) {
                queueA.remove();
            }
        } else {
             while(queueB.size() > 1) {
                queueA.add(queueB.remove());
             }
            if (queueB.size() > 0) {
                queueB.remove();
            }
        }
    }

    // Get the top element.
    public int top() {
        if(queueA.isEmpty() && queueB.isEmpty()) {
            return 0;
        }

        if (queueB.isEmpty()) {
            while(queueA.size() > 1) {
                queueB.add(queueA.remove());
            }
            int lastElement = queueA.peek();
            queueB.add(queueA.remove());
            return lastElement;
        } else {
            while(queueB.size() > 1) {
                queueA.add(queueB.remove());
            }
            int lastElement = queueB.peek();
            queueA.add(queueB.remove());
            return lastElement;
        }
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return (queueA.isEmpty() && queueB.isEmpty());
    }
}

问题分析

关于栈和队列的相互实现，主要考察的是两者的概念和原理的清晰度，并且在队列实现中，需要了解相关语言的知识点，例如Java中实现队列结构的类有LinkedList，那么LinkedList中的哪些方法符合条件，就可以去看看Java源码。这里给出LeetCode中对这次的总结，各类操作的时间复杂度都分析明确，值得仔细看看：implement-stack-using-queues

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.

译：设计一个支持push / pop / top操作的栈，能够在常量时间取得最小值

Example:

1
2
3
4
5
6
7
8
9
> MinStack minStack = new MinStack();
> minStack.push(-2);
> minStack.push(0);
> minStack.push(-3);
> minStack.getMin();   --> Returns -3.
> minStack.pop();
> minStack.top();      --> Returns 0.
> minStack.getMin();   --> Returns -2.
>

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class MinStack {

    Stack<Integer> minValueStack = new Stack<>();
    Stack<Integer> mStack = new Stack<>();

    public void push(int x) {
        mStack.push(x);
        if (minValueStack.isEmpty() || minValueStack.peek() >= x) {
            minValueStack.push(x);
        }
    }

    public void pop() {
        if (mStack.isEmpty()) return;
        else {
            if (!minValueStack.isEmpty()) {
                if (mStack.peek().equals(minValueStack.peek())) {
                    minValueStack.pop();
                }
            }
            mStack.pop();
        }
    }

    public int top() {
        if (!mStack.isEmpty()) {
            return mStack.peek();
        } else return 0;
    }

    public int getMin() {
        if (minValueStack.isEmpty()) return 0;
        else return minValueStack.peek();
    }
}

问题分析

题中为了取当前栈mStack中最小值，一开始想的是用常量来做一个缓存，但发现最小值是根据栈mStack的内容动态变化的，这就意味着需要一个额外的栈minValueStack进行缓存。别的就是正常的栈操作，注意边界和空栈的情况即可。不过发现一个问题，如果原始栈一直处于递减状态，那么栈minValueStack会一直递增花费更多的空间，而一旦题目对空间的要求比较苛刻，这种方式就不再适用。