leetcode

Posted on | In | | Total number of readers of this article times
Words count in article: 20.1k words | Reading time ≈ 106 minutes

前言

刷题更让我们对一门语言有更加深入的理解，也可以增进对数据结构的理解，百里无一害。

Two Sum

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, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

这也是我处女面试的第一个算法，当时想的方法是最暴力的方法，直接两个循环完事，但是时间复杂度是$O(n^{2})$，那是相当的高o(╥﹏╥)o。后来想了一下找到了一个简单的方法，当时由于太紧张写的不太好。当时的问题方法也稍微有点不同，当时要求的是找到相对应的数字，不是index。 先回顾一下当时的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int[] another(int[] nums, int target) {
    int head = 0;
    int tail = 0;

    // sort it
    Arrays.sort(nums);

    while (true) {
        int value = nums[head] + nums[tail];

        if (value == target) break;
        else if (value > target) tail -= 1;
        else head += 1;

        if (head == tail) break;
    }

    if (head != tail) return new int[] {nums[head], nums[tail]};
    return null;
}

当时想到的是两头同时遍历的方法，但是有个前提要求就是list必须是排过序的，当nums无限大时排序所消耗的时间可以忽略的，这个方法有点类似于binary search。我当时也想过用HashMap，好像处于什么原因被面试官否定了，whatever不重要的。不闲扯了，我们开始看这题的比较优化的算法，时间复杂度是O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i ++) {
        int minus = target - nums[i];
        if (map.containsKey(minus)) {
            return new int[]{map.get(minus), i};
        } else {
            map.put(nums[i], i);
        }
    }

    return null;
}

算法思路：

  1. 因为是用的HashMap所以在检测key是否contain的话使用的是hash的方法，所以复杂度是$O(1)$
  2. 第7-11行，是来判断这个HashMap是否包含这个num，如果这个num不包含在HashMap里面，然后把该num存到HashMap里面，num当做key，index当做value。这样就相当于把访问过的num和num的index存到HashMap里面，然后再遍历nums的时候得对每个数可以得到一个差值，然后判断这个差值是否存在HashMap里面，如果存在就代表得到这个结果了，如果不存在就把这个nums[i]存到HashMap。

Add Two Numbers

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

算法思想：

主要应该考虑一下边界情况：

  1. 当sum>=10
  2. 两个链表不一样长
  3. 在最后一个数字相加的时候sum>=10

第6行的while语句就是为了两条链表不一样长度。第7-8行判断如果该链表不为null就取该val，不然的话就为0（为了不影响下面的计算）。int overflow = 0是为了解决和超过10的情况，第9行把溢出的数字和v1，v2相加，然后把该结果取余就是结果。然后把overflow = sum/10 得到进位数。每次生成新的数字之后生成一个新的node没然后链接起来。主要是考虑不同的边界情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    int overflow = 0;
    if (l1 == null && l2 == null) return null;
    ListNode new_node = new ListNode();
    ListNode head = new_node;
    while (l1 != null || l2 != null) {
        int v1 = (l1 != null) ? l1.val : 0;
        int v2 = (l2 != null) ? l2.val : 0;
        int sum = v1+v2 + overflow;
        overflow = sum / 10;
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
        new_node.val = sum % 10;
        if (l1 != null || l2 != null) {
            new_node.next = new ListNode();
            new_node = new_node.next;
        }
    }
    if (overflow > 0) {
        new_node.next = new ListNode(overflow % 10);
    }
    return head;
}

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解题方法&思路：

首先说下题意，我刚开始是没理解题意来得（暴露了自己的无知╮(╯▽╰)╭），题意就是匹配到最长的子字符串，并且不能重复。比如pwwkew 可以匹配到wke 最后一个w不可以被匹配到，因为该子字符串已经包含了一个w。

算法解析：我们可以使用暴力解法：双循环（但是不推荐)。我们可以使用HashMap来解决该问题，因为HashMap查询的时候只需要$O(1)$的时间复杂度。

  1. 首先对该字符串进行遍历，如果该字符不在HashMap里面，则把该字符添加到HashMap，取max（HashMap length, ans）
  2. 如果该字符已经出现在HashMap里面，从HashMap里面去除一个字符，然后current index保持不变（会对该index进行再次遍历）
  3. 循环

有点类似于：当一个字符不在该HashMap，push进去，如果已经在了，pop出来。然后在push之后计算最大的长度是多少。（进去一个如果已经存在就pop出来一个，因为重点是长度，所以不需要关心到底是哪些字符）。

Python伪代码

1
2
3
4
5
6
7
8
9
def LongSubString(s):
4while i < len(s):
    if not s[i] in hashmap:
      hashmap[s[i]] = 0
      ans = max(len(hashmap), ans)
    else:
      del hashmap[s[d]]
      d += 1
  return ans

Java解决方法：

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
import java.util.HashMap;
import java.util.Map;

public class LongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        int remove = 0;
        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < s.length();) {
            if (!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), 0);
                ans = Math.max(map.size(), ans);
                i ++;
            } else {
                map.remove(s.charAt(remove));
                remove += 1;
            }
        }


        return ans;
    }

    public static void main(String[] args) {
        LongestSubstring lon = new LongestSubstring();
        System.out.println(lon.lengthOfLongestSubstring("abcabcbb"));
    }
}

Valid Parentheses

valid parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

1
2
Input: "()"
Output: true

Example 2:

1
2
Input: "()[]{}"
Output: true

Example 3:

1
2
Input: "(]"
Output: false

Example 4:

1
2
Input: "([)]"
Output: false

Example 5:

1
2
Input: "{[]}"
Output: true

解题思路：

这个题我使用了stack（栈）的方法来解决这个问题。stack是一种先进后出的数据结构，所以更加适合这种问题。

  1. 我们先来初始化一个HashMap来存相对应的括号
  2. 先判断该HashMap是否存在该左括号，如果存在就把左括号push到stack里面，
  3. 如果不存在先判断stack是否有数据（因为不存在的情况只有该字符是右括号的情况）
  4. 然后根据stack pop出来的结果在HashMap找到相对应的右括号，然后判断该字符和HashMap里面的右括号是否匹配。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    Map<Character, Character> map = new HashMap<>();
    map.put('[', ']');
    map.put('(', ')');
    map.put('{', '}');

    for (int i = 0; i < s.length(); i ++) {
        if (map.containsKey(s.charAt(i))) {
            stack.push(s.charAt(i));
        } else {
            if (stack.isEmpty()) return false;
            if (!map.get(stack.pop()).equals(s.charAt(i))) return false;
        }
    }

    return stack.isEmpty();
}

Reverse Integer

reverse integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

1
2
Input: 123
Output: 321

Example 2:

1
2
Input: -123
Output: -321

Example 3:

1
2
Input: 120
Output: 21

本来以为这个题很简单，使用了最简单的算法，但是呢，出现了一个整型溢出的问题o(╥﹏╥)o。

先解析一下思路吧：

  1. 首先我们可以用x%10来得到最后一个数字（因为数字不可能大于10）
  2. x/10是把最后一位数去掉
  3. reverse*10是为了整体向左移一位，比如(44, 44*10 = 440)多出一个空位，然后加上x%10的数字
1
2
3
4
5
6
7
8
9
10
11
public int reverse(int x) {
    int reverse = 0;

    while (x != 0) {
        int last_digit = x % 10;
        reverse = reverse * 10 + last_digit;
        x = x / 10;
    }

    return reverse ;
}

这样如果数字区间在$[−2^{31}, 2^{31} − 1]$的话那么就会出现溢出的问题了，大家可以使用1534236469来尝试一下。

所以这时候我们就需要来做些判断了：

当reverse > intMAX/10的时候我们基本上就可以确定他会溢出了，比如说intMAX = 2147483647，假设我们的reverse = 214748365 这时候intMAX/10 =214748364，reverse > intMAX。这时候如果reverse * 10我们不管最后一个数字是什么了，reverse已经超出了int取值范围。

正确代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
public int reverse(int x) {
    int reverse = 0;

    while (x != 0) {
        int last_digit = x % 10;
        if (reverse > Integer.MAX_VALUE / 10) return 0;
        if (reverse < Integer.MIN_VALUE / 10) return 0;
        reverse = reverse * 10 + last_digit;
        x = x / 10;
    }

    return reverse ;
}

Palindrome Number

palindrome number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

1
2
Input: 121
Output: true

Example 2:

1
2
3
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

1
2
3
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

回文数也就是说该数字等于翻转后的数字，num = reverse(num)。首先我们可以确定如果该数字是负数直接false就好了。我们可以使用上一题的思路，把数字翻转然后看是否相等。也可以把边界情况考虑进行。

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isPalindrome(int x) {
    if (x < 0) return false;

    int reverse = 0, temp = x;

    while (temp != 0) {
        int last_digit = temp % 10;
        reverse = reverse * 10 + last_digit;
        temp = temp / 10;
    }

    return reverse == x;
}

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

1
2
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

集体思路：

采用了垂直对比法。比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
s1 = 'flower'

s2 = 'flow'
s3 = 'flight'

我们第一层循环是表示当前string的index, i = 0;
然后得到第一个string的第i个char
第二个循环式为了和剩余的string比对，
如果i的大小等于当前string的长度也就意味着遇到了结束点，比如当i=3的时候，i = s2.length，也就意味着有结束点了。

c != strs[j].charAt(i) 这就语句是为了判断当前string的第i个char是否和第一个相等，如果不想当也就意味着可以返回i之前的数据


最后一行意味着strs[0]是最短的字符串，而且strs[0]是comm prefix
1
2
3
4
5
6
7
8
9
10
11
12
13
public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";

    for (int i = 0; i < strs[0].length(); i ++ ) {
        char c = strs[0].charAt(i);

        for (int j = 1; j < strs.length; j ++) {
            if (i == strs[j].length() || c != strs[j].charAt(i))
                return strs[0].substring(0, i);
        }
    }
    return strs[0];
}

也可以试着得到最短的string，然后进行循环，思路差不多：

这种情况其实没什么必要，因为可能没循环结束就return了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";

    int min = Integer.MAX_VALUE;
    int index = -1;

    // get the shortest string length
    for (int i = 0; i < strs.length; i ++) {
        if (strs[i].length() < min) {
            min = strs[i].length();
            index = i;
        }
    }

    for (int i  = 0; i < min; i ++) {
        char c = strs[0].charAt(i);

        for (String str : strs) {
            if (c != str.charAt(i)) return str.substring(0, i);
        }
    }

    return strs[index];
}

Merge Two Sorted Lists

Merge two sorted lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

这个好像没什么说的，就直接对比大小然后merge在一起就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode head = new ListNode();
    ListNode temp = head;

    while (l1 != null && l2 != null) {
        temp.next = new ListNode();
        temp = temp.next;

        if (l1.val <= l2.val) {
            temp.val = l1.val;
            l1 = l1.next;
        } else {
            temp.val = l2.val;
            l2 = l2.next;
        }
    }

    if (l1 != null) temp.next = l1;
    if (l2 != null) temp.next = l2;

    return head.next;
}

Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

1
2
3
4
5
Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

最获取长度的同时需要对array内部数据进行修改：

通过每次记录num，如果不相同的话，对数组的其实位置开始修改，然后curr是正在修改的index。（也会随着i增加而增加，如果所有数字都不一样）只不过是重新赋值了一次而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int dup = nums[0];
    int curr = 1;

    for (int i = 0; i < nums.length; i ++) {
        if (dup != nums[i]) {
            dup = nums[i];
            nums[curr++] = nums[i];
        }
    }

    return curr;
}

Roman to Integer

Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

1
2
Input: "III"
Output: 3

Example 2:

1
2
Input: "IV"
Output: 4

Example 3:

1
2
Input: "IX"
Output: 9

Example 4:

1
2
3
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

1
2
3
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

好像没什么好说的就是简单的字符串操作而已：

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
public int romanToInt(String s) {
    Map<Character, Integer> map = new HashMap<>();
    map.put('I', 1);
    map.put('V', 5);
    map.put('X', 10);
    map.put('L', 50);
    map.put('C', 100);
    map.put('D', 500);
    map.put('M', 1000);

    int res = 0;

    for (int i = 0; i < s.length(); i ++) {
        char c = s.charAt(i);
        if (c == 'V' || c == 'X') {
            if (i > 0) {
                if (s.charAt(i-1) == 'I') res += map.get(c) - 2;
                else res += map.get(c);
            } else res += map.get(c);
        } else if (c == 'L' || c == 'C') {
            if (i > 0) {
                if (s.charAt(i-1) == 'X') res += map.get(c) - 20;
                else res += map.get(c);
            } else res += map.get(c);
        } else if (c == 'D' || c == 'M') {
            if (i > 0) {
                if (s.charAt(i-1) == 'C') res += map.get(c) - 200;
                else res += map.get(c);
            } else res += map.get(c);
        } else {
            res += map.get(c);
        }
    }

    return res;
}

Remove Element

Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

1
2
3
4
5
Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
6
7
Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

这个和前面那个remove duplicate number是一个思路：

这个算法很简单，但是效率贼高。其实很好理解，就是当这个数字不等于val的时候，会用之前的curr（非重复的数字坐标）来替换当前的val。

1
2
3
4
5
6
7
8
9
10
3, 2, 2, 3 & val = 2
curr = 0

when i = 0, val != nums[i] num[curr++] = nums[i] -> nums[0] = nums[0] and curr = 1 now
when i = 1, val == nums[i] continue
when i = 2, val == nums[i] continue
when i = 3, val != nums[i] num[curr++] = nums[i] -> nums[1] = nums[3] and curr = 2 now

so nums = 3, 3, 2, 3 and curr = 2, we do not care index > 1 values,
so we done
1
2
3
4
5
6
7
8
9
10
11
public int removeElement(int[] nums, int val) {
    int curr = 0;

    for (int i = 0; i < nums.length; i++) {
        if (val != nums[i]) {
            nums[curr++] = nums[i];
        }
    }

    return curr;
}

Implement strStr()

Implement strStr()

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

1
2
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2
Input: haystack = "aaaaa", needle = "bba"
Output: -1

返回要求的是index，我还以为是长度一度迷茫为啥不对o(╥﹏╥)o，一个for就能解决的问题，我们先去needle的第一个字符，然后在循环haystack的时候如果里面有字符和needle的第一个字符匹配了就用substring来接取相对应的长度，然后判断是否和needle相等（需要判断index的长度是不是超过了haystack的长度）。

1
2
3
4
5
6
7
8
9
10
11
public int strStr(String haystack, String needle) {
    if (needle.length() == 0) return 0;
    char c = needle.charAt(0);
    for (int i = 0; i < haystack.length(); i ++) {
        if (haystack.charAt(i) == c) {
            if (i + needle.length() > haystack.length()) return -1;
            if (haystack.substring(i, i+needle.length()).equals(needle)) return i;
        }
    }
    return -1;
}

Search insert position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

1
2
Input: [1,3,5,6], 5
Output: 2

Example 2:

1
2
Input: [1,3,5,6], 2
Output: 1

就是找到合适的位置，然后返回相对应的index，没什么难度：

1
2
3
4
5
6
7
8
public int searchInsert(int[] nums, int target) {

    for (int i = 0; i < nums.length; i ++) {
        if (nums[i] >= target) return i;
    }

    return nums.length;
}

Median of two sorted array

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

没办法太菜了找不到合适的方法来写了，有想过分开循环，但是这样需要有很多的判断条件，晚会会再尝试的，目前就快的方法就是合并array了。

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
public double findMedianSortedArrays(int[] nums1, int[] nums2) {

    List<Integer> list = new LinkedList<>();
    int l1 = 0, l2 = 0;

    while (l1 < nums1.length && l2 < nums2.length) {
        if (nums1[l1] < nums2[l2]) {
            list.add(nums1[l1]);
            l1 += 1;
        } else {
            list.add(nums2[l2]);
            l2 += 1;
        }
    }

    // add n2
    if (l1 >= nums1.length) {
        for (int i = l2; i < nums2.length; i ++) list.add(nums2[i]);
    } else {
        for (int i = l1; i < nums1.length; i ++) list.add(nums1[i]);
    }

    int len = list.size();
    if (len % 2 != 0) return list.get(len/2);
    return (double) (list.get(len/2) + list.get(len/2-1)) / 2;
}

String to Integer (atoi)

String to Integer (atoi)

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

  • Only the space character ' ' is considered as whitespace character.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

1
2
Input: "42"
Output: 42

Example 2:

1
2
3
4
Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:

1
2
3
Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

1
2
3
4
Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

1
2
3
4
Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

这是我写LeetCode以来submit最多的次数╮(╯▽╰)╭，里面条件的限制和符号的判定太烦了。给大家写一下判断条件：

  1. 空格只能出现在最前面，一旦出现了-+0-9这些符号，之后再遇到空格就要break
  2. -+符号考虑到符号的问题
  3. 只能以数字开头的才能提取数字，如果不是就return 0
  4. 考虑到整型溢出的问题

就是判断条件有点麻烦，其他的还好，我写的有点乱七八糟的，讲究看下。。。如果有好的idea可以写在comment里面，我会修改的。

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
public int myAtoi(String str) {
    int res = 0;
    // + or -
    int operation = 1;
    if (str.equals(""))return 0;
    boolean whitespace = true;
    boolean sign = true;

    for (int i = 0; i < str.length(); i ++) {
        char c = str.charAt(i);
        if (whitespace && c == ' ') continue;
        if (!whitespace && c == ' ') break;
        if ((c == '-' || c == '+') && sign) {
            operation = (c == '-')?-1:1;
            sign = false;
            whitespace=false;
            continue;
        }
        if (c < '0' || c > '9') break;
        whitespace = false;
        sign=false;
        if (res*operation > Integer.MAX_VALUE/10 || res*operation < Integer.MIN_VALUE/10) {
            if (operation > 0) return Integer.MAX_VALUE;
            else return Integer.MIN_VALUE;
        }

        if (res*operation == Integer.MAX_VALUE/10) if ((int)c-48 >= Integer.MAX_VALUE %10) return Integer.MAX_VALUE;
        if (res*operation == Integer.MIN_VALUE/10) if ((int)(c-48) * -1 <= Integer.MIN_VALUE % 10) return Integer.MIN_VALUE;
        res = res * 10 + (int) c - 48;
    }
    res *= operation;
    return res;
}

Container With Most Water

Container With Most Water

本来觉得是要用动态规划，可是看了大佬的代码和idea瞬间觉得自己的思路是错的。这个题其实就是变相的求最大面积，我们可以知道长方体的面积是长*高，在遍历这个list的时候长度是一直在减小的，如果长度变小我们只有找到更大的高度才能使面积最大。那么我们可以从两头同时开始遍历，如果left < right 那么left向左移，因为我们要找到higher height，如果left >= right right向左移就行了。这样就会找到最大的area。

ps：不想想太复杂，试着从最基本的信息去推断，比如这个面积，如果一个变量变下，那另一个变量只有变大才能找到最大的。（😁学习到了）

1
2
3
4
5
6
7
8
9
10
11
12
public int maxArea(int[] height) {
    int max = 0;
    int l = 0, r = height.length-1;

    while (l < r) {
        max = Math.max(max, Math.min(height[l], height[r]) * Math.abs(r - l));
        if (height[l] < height[r]) l ++;
        else r --;
    }

    return max;
}

Merge Sorted Array

Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

1
2
3
4
5
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

这是我今天逛牛客的时候发现的一道题，然后想了一下，按照我现在的思想好像只知道直接merge然后sort。还有一种就是正序插入，但是每个element都需要后移一位，但是这样的效率太低了，看了网上的大神的idea之后就发现了新大陆。因为这个list是拍过序的，那么我们就知道了最后一个元素肯定是最大。那么我们为什么不从后面往前面循环呢，这样不需要元素以为，只需要直接赋值就好了。

1
2
3
4
5
6
7
8
9
10
11
12
public void merge(int[] nums1, int m, int[] nums2, int n) {
    // the last position of array
    int last = nums1.length - 1;
    m--; n--;
    while (m > 0 && n > 0) {
        if (nums1[m] > nums2[n]) nums1[last--] = nums1[m--];
        else nums1[last--] = nums2[n--];
    }

    while (m > 0) nums1[last--] = nums1[m--];
    while (n > 0) nums1[last--] = nums2[n--];
}

Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

1
2
Input: [2,2,1]
Output: 1

Example 2:

1
2
Input: [4,1,2,1,2]
Output: 4

庆幸一下终于可以独立思考出来一些简单的算法了。这个题其实算是还OK的，可以使用HashMap解决，因为HashMap监测key的时候的时间复杂度是$O(1)$，所以整体时间是$O(n)$。在loop里面去判断该数字是否存在HashMap里面，如果不存在就push进去，如果已经存在就删除。那么最后剩下的那个元素肯定是single（单身狗）。

1
2
3
4
5
6
7
8
9
10
11
12
public int singleNumber (int[] A) {
    // write code here
    Map<Integer, Integer> map = new HashMap<>();
    for (int value : A) {
        if (map.containsKey(value)) {
            map.remove(value);
        } else {
            map.put(value, value);
        }
    }
    return map.get(map.keySet().toArray()[0]);
}

Ps: 在discuss里面看到了一个特别骚的操作。。。真的骚操作。。。

使用了异或（exclusive OR简称xor）这个来判断的，异或的话空间复杂度只有$O(1)$。

$1\oplus0=1$

$1\oplus1=1$

$0\oplus0=0$

$0\oplus1=1$

1
2
3
4
5
6
7
public int singleNumber(int[] nums) {
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        res ^= nums[i];
    }
    return res;
}

行吧。。。牛逼。。

Remove Nth Node From End of List

Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

解析：

题意就是删除倒数第N的节点。这个可以使用一个快慢指针的方法来解决，先让快的指针移动n个node，然后慢的指针开始移动。这样当快的指针为null的时候，慢的指针刚好就是要删除的节点。

其实可以当fast.next == null的时候就停止。这样slow.next = slow.next.next是一样的，因为我的代码用了curr来判断是否为null（删除的元素是不是head）

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
public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode curr = null;
    ListNode slow = head;
    ListNode fast = head;


    while (fast != null) {
        if (n <= 0) {
            curr = slow;
            slow = slow.next;
        }
        fast = fast.next;
        n --;
    }

    // means at the head
    if(curr == null) head = head.next;
    if (curr != null) curr.next = slow.next;

    return head;
}

Maximum Subarray

Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

题意解析：找到和最大的子序列。

算法解析：

可以使用动态规划来做。初始化一个数组长度和原数组一样，如果i-1的数字小于零就表示这就不用需要进行加和，因为加负数就是在减小，然后把i就行赋值。在每次循环的时候找到最大的值就行（max,dp[i]取最大的）。dp[i]存的结果：如果dp[i-1]小于零那就是本身，不然就是dp[i-1] + num[i]加上当前数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxSubArray(int[] nums) {
    int max = nums[0];
    int[] dp = new int[nums.length];
    dp[0] = nums[0];

    for (int i = 1; i < nums.length; i ++) {
        if (dp[i-1] < 0) {
            dp[i] = nums[i];
        } else {
            dp[i] = dp[i-1] + nums[i];
        }
        max = Math.max(dp[i], max);
    }
    return max;
}

看了大佬的思路之后发现了新天地，可以节省一些内存空间，降低空间复杂度：

只需要两个空间的位置就行了，因为我们只需要i和i-1这两个参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxSubArray(int[] nums) {
    int max = nums[0];
    int[] temp = new int[2];
    temp[0] = nums[0];

    for (int i = 1; i < nums.length; i ++) {
        if (temp[(i - 1) % 2] >= 0) {
            temp[i % 2] = temp[(i-1) % 2] + nums[i];
            max = Math.max(temp[i%2], max);
        } else {
            temp[i % 2] = nums[i];
        }
    }

    return max;
}

Climbing Stairs

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

1
2
3
4
5
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

1
2
3
4
5
6
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

这是一个很经典的动态规划的问题。一次可以走一阶楼梯或者两阶楼梯。在第一层的时候肯定只能上一阶，第二层的时候可以是1+1（连续走两个一阶）或者2（直接两阶）所以是两种方法，第三层的时候可以是1+1+1, 1+2, 2+1三种方法。所以可以看出$f(n)=f(n-1)+f(n-2)$的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int[] array = new int[n];
    array[0] = 1;
    array[1] = 2;

    for (int i = 2; i < n; i ++ ){
        array[i] = array[i-1] + array[i-2];
    }

    return array[n-1];
}

Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

1
2
3
4
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

这个题的思路稍微简单一点，可以使用动态规划来找到最小的买入价格，然后我们就可以根绝在买入价格最低的日期之后，找到卖出价格最高的点，这样收益就是最大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxProfit(int[] prices) {
    if (prices.length < 2) return 0;
    int max = 0, stock = prices[0];

    for (int price : prices) {
        int receive = price - stock;
      	// 找到最大收入
        if (receive >= 0) max = Math.max(max, price-stock);
4444// 找到最新的收入
        stock = Math.min(stock, price);
    }

    return max;
}

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

算法思路：

一开始想到的是用HashMap的方式来解决这个问题，但是这样的话空间复杂度就高了很多就是$O(n)$了，然后看了一下大神们的解法，就是利用快慢指针的方法，两种我都试了一下：

  1. HashMap的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean hasCycle(ListNode head) {
    Map<ListNode, Integer> map = new HashMap<>();

    ListNode curr = head;

    while (curr != null) {
        if (map.containsKey(curr)) return true;
        else map.put(curr, 1);

        curr = curr.next;
    }

    return false;
}

  1. 快慢指针的方法

    这样效率高，内存占用少

1
2
3
4
5
6
7
8
9
10
11
12
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        
        if (slow == fast) return true;
    }
    return false;
}

Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

1
2
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

1
2
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

使用了一个二分查找法，头尾遍历法，不过貌似时间复杂度有点高。。没有别人那么快，花了1ms才通过。一会准备去看看大神的思路，看看有没有好的idea。第23-28行的主要作用是考虑到起始位置和结束位置在同一个地方，当其中有任何一个数字不是-1的时候，代表已经找到这个数字了，但是head==tail的时候就会结束循环了，所以会进行一个判断。

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
public int[] searchRange(int[] nums, int target) {
    if (nums.length == 0) return new int[] {-1, -1};
    if (nums.length == 1)return  (nums[0] == target) ? new int[] {0, 0}: new int[]{-1, -1};

    int head = 0, tail = nums.length - 1;
    int[] range = new int[] {-1, -1};

    while (head <= tail) {
        if (nums[head] == target) {
            range[0] = head;
            if (range[1] != -1) break;
        }

        if (nums[tail] == target) {
            range[1] = tail;
            if (range[0] != -1) break;
        }

        if (nums[head] < target) head ++;
        if (nums[tail] > target) tail --;
    }

    if (head == tail) {
        if (range[0] == -1 || range[1] == -1) {
            range[0] = Math.max(range[0], range[1]);
            range[1] = Math.max(range[0], range[1]);
        }
    }

    return range;
}

刚去看了一下discussion里面，然后发现自己写的二分查找不叫二分查找，只能算是一个两头遍历的循环。然后根据二分查找的方法写了一份：

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
public int[] searchRange(int[] nums, int target) {
    if (nums.length == 0) return new int[] {-1, -1};

    int head = 0, tail = nums.length - 1;
    int[] range = new int[] {-1, -1};

    while (head <= tail) {
        int mid = (head + tail) / 2;

        if (nums[mid] > target) {
            tail = mid - 1;
        } else if (nums[mid] < target) {
            head = mid + 1;
        } else {
            // make a loop from head to tail and tail to end
            while (head <= mid) {
                if (nums[head] == target) {
                    range[0] = head;
                    break;
                }
                head ++;
            }

            while (tail >= mid) {
                if (nums[tail] == target) {
                    range[1] = tail;
                    break;
                }
                tail --;
            }
            break;
        }
    }

    return range;
}

Pow(x, n)

Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

1
2
Input: 2.00000, 10
Output: 1024.00000

Example 2:

1
2
Input: 2.10000, 3
Output: 9.26100

Example 3:

1
2
3
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−231, 231 − 1]

这个就是简单的求一下平方，然后给保留5位小数就行了，用Python简单的写了一波

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        x = x**n
        
        x = 2**32-1 if x >= 2**32-1 else x
        x = -2**32 if x <= -2**32 else x
        
        return round(x, 5)

Intersection of Two Linked Lists

Intersection of Two Linked Lists

也算是我第一次面试的第一道题。当时想的是暴力解决，double循环哈哈哈。这次写的时候想到了一个新的方法就是使用HashMap来解决，最坏的情况是$O(n+m)$，不过也比$O(n^2)$好。先把一个LinkList全部放到HashMap里面，然后循环第二个链表，看是不是有一样的node，如果有就直接return当前的node，如果直到循环结束还没有就return null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode head = null;
    ListNode curr = headA;
    Map<ListNode, Integer> map = new HashMap<>();

    while (curr != null) {
        map.put(curr, curr.val);
        curr = curr.next;
    }

    curr = headB;
    while (curr != null) {
        if (map.containsKey(curr)) {
            head = curr;
            break;
        }
        curr = curr.next;
    }

    return head;
}

在面试的时候面试官也给我说了另一种解法，就是假设已知两条链表的长度，然后先把两条链表截取到一样的长度，然后一个循环就能找到相对应的结果。这个我觉得时间复杂度比我的要高，就没写。

Majority Element

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

1
2
Input: [3,2,3]
Output: 3

Example 2:

1
2
Input: [2,2,1,1,1,2,2]
Output: 2

看到这一类的题，最先想到的就是使用HashMap来解决这个计数的问题，当计数的结果> nums.leng/2的时候可以直接return就好了，准没错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int majorityElement(int[] nums) {
    if (nums.length <= 0) return -1;
    int len = nums.length - 1;
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i <= len; i ++) {
        if (map.containsKey(nums[i])) {
            if (map.get(nums[i]) + 1 >= nums.length/2) return nums[i];
            map.put(nums[i], map.get(nums[i]) + 1);
        } else {
            map.put(nums[i], 1);
        }
    }

    return -1;
}

然后看了一下官方的解法，就是先sort一下，如果该数字的个数大于总array长度的一般也就意味着sort完之后取中间那个数字准没错。。。那么简单的方法咋就没想到呢o(╥﹏╥)o

1
2
3
4
5
public int majorityElement(int[] nums) {
    if (nums.length == 0) return -1;
    Arrays.sort(nums);
    return nums[nums.length/2];
}

Min Stack

Min Stack(https://leetcode.com/problems/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.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

这个只需要知道stack是先进后出的原则就行。

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
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class MinStack {
    /** initialize your data structure here. */
    private List<Integer> list;
    private int lens;

    public MinStack() {
        this.list = new LinkedList<>();
        this.lens = 0;
    }

    public void push(int x) {
        this.list.add(x);
        this.lens ++;
    }

    public void pop() {
        if (this.list.size() > 0) {
            this.lens --;
            this.list.remove(this.lens);
        }
    }

    public int top() {
        if (this.list.size() > 0) {
            return this.list.get(this.lens - 1);
        }
        return -1;
    }

    public int getMin() {
        return Collections.min(this.list);
    }

    public static void main(String[] args) {
        MinStack m = new MinStack();
        m.push(-2);
        m.push(0);
        m.push(-3);
        System.out.println(m.getMin());
        m.pop();
        System.out.println(m.top());   // return 0
        System.out.println(m.getMin()); // return -2
    }
}

Reverse Linked List

Reverse a singly linked list.

Example:

1
2
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

翻转链表可以循环实现，也可以用递归实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode reverseList(ListNode head) {
      if (head == null) return null;
      ListNode curr = head;
      ListNode next = head.next;
      ListNode temp = null;
      curr.next = null;


      while (next != null) {
          temp = next.next;
          next.next = curr;
          curr = next;
          next = temp;
      }

      return curr;
}

然后递归的话就刚开始看可能不是特别好理解的。总感觉遇到递归就有点懵逼的感觉。。。

1
2
3
4
5
6
7
8
9
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode last = reverseList(head.next);

    head.next.next = head;
    head.next = null;

    return last;
}

Palindrome Linked List

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

1
2
Input: 1->2
Output: false

Example 2:

1
2
Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

思路：

本来想的是用递归的方法算一下和，如果是回文的话结果应该是一样的，想法很美好，现实很残酷。。。LeetCode官方应该也考虑到这个问题了，如果算sum的话会导致整型溢出的问题。。。。不过也算是一个思路吧。o(╥﹏╥)o

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isPalindrome(ListNode head) {
    if (head == null) return false;
    if (head.next == null) return true;
    long [] nums = new long[]{0, 0};
    recur(head,nums);

    return nums[0] == nums[1];
}

public void recur(ListNode curr, long[] nums) {
    if (curr == null) return ;

    nums[0] = nums[0]*10 + curr.val;
    recur(curr.next, nums);
    nums[1] = nums[1]*10 + curr.val;
}

最近遇到的题不是递归就是动态规划。。。看来这块有点薄弱，有时间要多练习一下。。看了discussion里面，有个大神写的也是递归的方法，类似于先把第一个指针走到结尾，第二个指针指向head，然后对比是不是一样。感觉很牛逼。。不过递归貌似花费时间有点久。

1
2
3
4
5
6
7
8
9
10
11
12
boolean flag = true;
public boolean isPalindrome(ListNode head) {
    recur(head, head);
    return flag;
}

public ListNode recur(ListNode p1, ListNode p2) {
    if (p1 == null) return p2;
    ListNode node = recur(p1.next, p2);
    if (node.val != p1.val) flag = false;
    return node.next;
}

Ps: 还有一种快慢指针的方法。。就是走到中间，然后把两条链表分开对比就行了，但是感觉有点麻烦，还是不写了。。。

Move Zeroes

Move Zeroes

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Example:

1
2
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

一开始看到这个想了一下双指针，一个从头开始一个从尾部开始，这样虽然可以把0都放到后面，但是这样就不是顺序来的了。。。看了一下大佬思路，也是双指针（方法思路没错对吧），只不过这个双指针都是从头开始的。先设置一个0的指针zero=-1因为我们一开始不知道0的位置在那，然后开始循环，如果该数字为0可以对zero进行赋值了（zero == -1），当zero != -1说明之前已经有了0的数字。然后如果该数字不等于0的时候表示可以对之前的zero的index进行替换，前提是zero != -1，然后判断zero和i的位置，如果i是zero的next说明是只有一个zero，不然的话就代表zero后面还是一个0的数字，所以这时候zero++就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void moveZeroes(int[] nums) {
    int zero = -1;

    for (int i = 0; i < nums.length; i ++) {
        if (nums[i] != 0) {
            if (zero == -1) continue;
            nums[zero] = nums[i];
            nums[i] = 0;
            zero = (zero == i + 1) ? i : zero+1;
        } else {
            if (zero != -1) continue;
            zero = i;
        }
    }
}

Find All Numbers Disappeared in an Array

Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

题解：数组长度1-n，要判断数组里面出现的数字是不是在1-n之间，如果少了哪个数字就给补上。

比如：[2,2]数组长度1-2，那么改数组少了1。

solution 1：

刚开始考虑的是先sort一下，然后判断index在0，末尾和中间的情况进行补全，但是貌似有点浪费时间了。。所以时间复杂度有点高$O(nlog_{n} + n)$。不过也算是一种方法对吧。。。o(╥﹏╥)o

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
public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> dis = new LinkedList<>();
    if (nums.length == 0) return dis;
    Arrays.sort(nums);

    int num = nums[0];
    while (num > 1) {
        num --;
        dis.add(num);
    }

    num = nums[0];

    for (int i = 1; i < nums.length; i ++) {
        while (num + 1 != nums[i] && num != nums[i]) {
            num++;
            dis.add(num);
        }
        num = nums[i];
    }

    num = nums[nums.length-1];
    while (num != nums.length) {
        num++;
        dis.add(num);
    }
    return dis;
}

solution 2：

看了一下discussion感觉他们写的方法屌爆了。。。因为数组里面的数字是在数组长度1-n之内的，所以这个时候我们可以做一个指示器的格式，把数组里面每个数字所对应的坐标变成负数，然后再寻找一个array里面哪些是负数。很欢喜。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> dis = new LinkedList<>();
    if (nums.length == 0) return dis;

    for (int i = 0; i < nums.length; i ++) {
        int index = Math.abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }

    for (int i = 0; i < nums.length; i ++) if (nums[i] > 0) dis.add(i + 1);

    return dis;
}

Word Ladder

126 题

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

1
2
3
4
5
6
7
8
9
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

词语接龙，一个老外很喜欢的游戏，我觉得他们的test有问题。。。这个数量就很奇怪，不过我还是按照我的方法来，我不觉得我写错了，使用了一个bfs的算法，因为每次改变一个单词其中的一个字符，然后判断新生成的字符是否在wordList之间，然后再判断是不是已经visited过的。

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
import java.util.*;

public class WordLadder {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int step = 0;
        if (!wordList.contains(endWord)) return step;
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Set<String> visited = new HashSet<>();

        while (!queue.isEmpty()) {
            ++step;
            for (int x = 0; x < queue.size(); x ++) {
                String str = queue.poll();
                visited.add(str);
                if (str.equals(endWord)) return step;
                for (int i = 0; i < str.length(); i ++) {
                    char[] temp = str.toCharArray();
                    char ch = temp[i];
                    for (char c = 'a'; c <= 'z'; c ++) {
                        if (c == ch) continue;
                        temp[i] = c;
                        String t = new String(temp);
                        if (!wordList.contains(t)) continue;
                        if (visited.contains(t)) continue;
                        queue.offer(t);
                        visited.add(t);
                    }
                }
            }
        }
        return step;
    }


    public static void main(String[] args) {
        WordLadder w = new WordLadder();
        List<String> list = new ArrayList<String>(
                Arrays.asList("hot","dot","dog","lot","log","cog")
        );

        int res = w.ladderLength("hit", "cog", list);

        System.out.println(res);

    }
}

Letter Combinations of a Phone Number

Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

img

Example:

1
2
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

思路1：

每个数字代表几个相对应的数据，把这些代表的数据进行排列组合。这个第一个想到的就是loop，逐层递进，因为如果是三个数字的话，就是只组合成三个字母的string，可以先把1，2组合得到的结果去和3组合。这样就行了，还有别的算法。

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
import java.util.*;

public class LetterCombinationsofaPhoneNumber {
    private List<String> letterCombinations(String digits) {
        List<String> result = new LinkedList<>();
        HashMap<Character, String> maps = new HashMap<>();
        maps.put('2', "abc");
        maps.put('3', "def");
        maps.put('4', "ghi");
        maps.put('5', "jkl");
        maps.put('6', "mno");
        maps.put('7', "pqrs");
        maps.put('8', "tuv");
        maps.put('9', "wyxz");

        // 先实验一下相乘的办法，因为还有很多好的办法，一会慢慢看

        for (int i = 0; i < digits.length(); i ++) {
            if (!maps.containsKey(digits.charAt(i))) continue;

            String str = maps.get(digits.charAt(i));
            result = mul(result, new ArrayList<>(Arrays.asList(str.split(""))));
        }

        return result;
    }



    private List<String> mul(List<String> s1, List<String> s2) {
        if (s1.size() == 0 && s2.size() != 0) {
            return s2;
        }

        if (s1.size() != 0 && s2.size() == 0) {
            return s1;
        }

        List<String> result = new LinkedList<>();
        for (String value : s1) {
            for (String s : s2) {
                result.add(value + s);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        LetterCombinationsofaPhoneNumber l = new LetterCombinationsofaPhoneNumber();
        String str = "23";

        List<String> res = l.letterCombinations(str);

        for (String s : res) {
            System.out.println(s);
        }
    }
}

思路2：

想学习一下dfs的算法。。。学习使用dfs和递归的方法，这个算法的思路就是直接访问到最底层的str，然后遍历最底层的list，遍历完之后返回到上一层，然后对上一层进行遍历，同时还会使用到最底层的元素。。。递归有点绕。。

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
private List<String> letterCombinations(String digits) {
    List<String> result = new LinkedList<>();

    if (digits == null || digits.length() == 0) return result;

    HashMap<Character, String> maps = new HashMap<>();
    maps.put('2', "abc");
    maps.put('3', "def");
    maps.put('4', "ghi");
    maps.put('5', "jkl");
    maps.put('6', "mno");
    maps.put('7', "pqrs");
    maps.put('8', "tuv");
    maps.put('9', "wyxz");

    dfs(digits, 0, "", result, maps);

    return result;
}

public void dfs(String digits, int index, String temp, List<String> res, HashMap<Character, String> maps) {
    if (index == digits.length()) {
        res.add(temp);
        return;
    }

    String t = maps.get(digits.charAt(index));

    for (int i = 0; i < t.length(); i ++) {
        dfs(digits, index + 1, temp + t.charAt(i), res, maps);
    }

}

3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

找到三个数字和为0，这个题也是我之前就在写的一个，但是因为一些原因没做出来，然后今天下午写了一种方法，能运行，但是运行到最后一个的时候超时了，因为加了过多的sort和if的条件语句，在discussion看了一个大佬的方法之后醍醐灌顶，意识到自己少加个条件的问题。。。首先需要sort一下，然后循环遍历，在第一层循环的时候可以用sum = - num这样就只需要在剩余的numbers里面进行一个二分查找，找到相对应的和为-num的数据，当找到之后仍然需要接着二分查找，因为可能还有别的数字和为-num，但是我们需要考虑的一个最重要的因素就是数字不能重复，因为同一个数字只能找到那么多和为0的list。如果大家有更好的解决方法可以给我留言。

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
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> list = new LinkedList<>();
    if (nums.length < 3) return list;
    Arrays.sort(nums);

    // assume the list is sorted
    // then just make a loop
    for (int i = 0; i < nums.length - 1; i ++) {
      	// 避免重复循环的问题，因为每个数字只有那么几个相对应的list
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int num = -nums[i];
      	// 不需要重复的数据，所以从i+1开始
        int left = i + 1;
        int right = nums.length - 1;

        while (left <= right) {
            if (left == right) break;
            if (left == i) {
                left++;
                continue;
            }
            if (right == i) {
                right --;
                continue;
            }
            if (nums[left] + nums[right] == num) {
                // then add numbers to the list
                List<Integer> temp = new LinkedList<Integer>(
                        Arrays.asList(nums[i], nums[left], nums[right])
                );
                list.add(temp);
              	// 因为后面还有可能存在类似的list，同时要主要不能重复
                while (left < right && nums[left] == nums[left+1]) left ++;
                while (left < right && nums[right] == nums[right-1]) right--;
                left ++;
                right --;
            } else if (nums[left] + nums[right] < num) {
                left ++;
            } else {
                right --;
            }
        }
    }

    return list;
}

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

1
Given 1->2->3->4, you should return the list as 2->1->4->3.

交换node的位置，两两交换，要考虑的问题有两个，list长度为odd的时候怎么办，怎么去进行loop。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode curr = head;
    head = curr.next;
    ListNode last = null;

    while (curr != null && curr.next != null) {
        ListNode next = curr.next;
        ListNode temp = next.next;

        if (last != null) {
            last.next = curr.next;
        }
        next.next = curr;
        curr.next = null;
        last = curr;

        curr = temp;
    }

    if (curr != null && curr.next == null) last.next = curr;

    return head;
}

Generate Parentheses

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

这个题主要是使用了递归的方法，首先一直添加(，直到最深度n，如果超过n肯定不合法了，因为左右括号是相对应的。当左括号达到最深度的时候，开始递归右括号，同时右括号的数量应该小于左括号。伪代码:

1
2
3
4
5
6
7
8
9
def find(left, right, depth, str, res):
4if str length == depth * 2:
44res.add(str)
4
4if left < depth:
44find(left+1, right, depth, str+'(' , res)
4
4if right < left:
44find(left, right+1, depth, str+')', res)

Java代码：

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
import java.util.LinkedList;
import java.util.List;

public class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> list = new LinkedList<>();
        if (n == 0) return list;

        dfs(0,0,n,list, "");
        return list;
    }

    public void dfs(int close, int open, int depth, List<String> res, String str) {
        if (str.length() == depth * 2) {
            res.add(str);
            return;
        }

        if (open < depth) {
            dfs(close, open + 1, depth, res , str + "(");
        }

        if (close < open) {
            dfs(close + 1, open, depth, res, str + ")");
        }
    }

    public static void main(String[] args) {
        GenerateParentheses ge = new GenerateParentheses();
        List<String> res = ge.generateParenthesis(4);

        for (String str : res) {
            System.out.println(str);
        }
    }
}

Rotate Array

Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Follow up:

  • Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?

Example 1:

1
2
3
4
5
6
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

1
2
3
4
5
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

就是根据k的个数，每个element向后移动k位，超出array的话在array的开头继续。

刚开始试了好几种方法，但是都不是特别理想，看了一下discussion，学到了。这个翻转链表实际是有规律的，先把整个array reverse一下，然后再把0-kreverse，然后把k-endreverse一下就可以得到最终的结果。。。很神奇的规律。。。

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
import java.util.Arrays;

/**
 * 这个想法是在leetcode那边看到的，其工作原理就是先reverse一下
 * 然后在对前k个进行reverse，然后对k-len再reverse
 * 这样就能得到结果了
 */
public class RotateArray {
    public void rotate(int[] nums, int k) {
        if (nums.length < 2 || k < 1) return;
        // 整体反转
        reverse(0, nums.length - 1, nums);

        reverse(0, k % nums.length - 1, nums);
        reverse(k % nums.length, nums.length - 1, nums);
    }

    public void reverse(int left, int right, int[] nums) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left ++;
            right --;
        }
    }

    public static void main(String[] args) {
        RotateArray re = new RotateArray();
        int[] nums = new int[] {1,2};
        re.rotate(nums, 1);

        System.out.println(Arrays.toString(nums));
    }
}

Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

1
2
3
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

1
2
3
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

一个数学的问题，在最后面加1，然后如果大于10，那么前面的数字就需要加一。可以直接不用分类来讨论，我们可以设置一个循环index <= 0 ，index = nums.length - 1这样我们从最后面开始加1，overflow是用来判断是否溢出，在循环里面如果没有溢出，就表示前面数字加一的结果不大于10，所以可以直接break。还有一种如果循环结束了依然溢出了，这时候我们需要在array里面多加一个数字在最前面。

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
import java.util.Arrays;
import java.util.stream.IntStream;

public class PlusOne {
    public int[] plusOne(int[] digits) {
        int lens = digits.length - 1;
        int[] nums = digits.clone();
        int overflow = 0;
        nums[lens] += 1;

        while (lens != -1) {
            // every time plus one
            nums[lens] += overflow;
            overflow = nums[lens] / 10;
            if (nums[lens] > 9) nums[lens] %= 10;
            lens --;
            // 当不溢出的时候就可以break了，因为不会进位了
            if (overflow == 0) break;
        }

        // 如果循环结束还溢出，说明还需要多开辟一个内存位置。
        if (overflow != 0) {
            nums = IntStream.concat(Arrays.stream(new int[] {1}), Arrays.stream(nums)).toArray();
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] nums = new int[] {8,9};
        PlusOne p = new PlusOne();
        int[] res = p.plusOne(nums);
        System.out.println(Arrays.toString(res));
    }
}

Intersection of Two Arrays II

Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example 1:

1
2
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

1
2
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

这个题就稍微简单一点了，可以用HashMap来记录num1的元素，value来存数字出现的次数。这样在遍历num2的时候就可以直接判断了。。。刚开始想到过array的用法，但是因为key是单一的，默默被我放弃了（我就是傻逼。。。），看了一下discussion恍然大悟。。。

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
import javax.swing.*;
import java.util.*;

/**
 * Input: nums1 = [1,2,2,1], nums2 = [2,2]
 * Output: [2,2]
 * 没啥思路， 傻逼了，想着可以用hashmap但是，想到hashmap的key只能存一个value
 * 但是value可以表示数量啊
 * 傻逼
 *
 */
public class Intersection {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> maps = new HashMap<>();
        ArrayList<Integer> res = new ArrayList<Integer>();

        for (Integer num : nums1) {
            if (maps.containsKey(num)) {
                maps.put(num, maps.get(num) + 1);
            } else {
                maps.put(num, 1);
            }
        }

        for (Integer num : nums2) {
            if (maps.containsKey(num)) {
                res.add(num);
                if (maps.get(num) == 1) maps.remove(num);
                else maps.put(num, maps.get(num) - 1);
            }
        }
        int[] result = new int[res.size()];
        for (int i = 0; i < res.size(); i ++) result[i] = res.get(i);
        return result;
    }

    public static void main(String[] args) {
        int[] num1 = new int[] {1,2,2,1};
        int[] num2 = new int[] {2,2};
        Intersection i = new Intersection();
        int[] res = i.intersect(num1, num2);
        System.out.println(Arrays.toString(res));
    }
}

Happy Number

Happy Number

Write an algorithm to determine if a number n is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example: 

1
2
3
4
5
6
7
Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

输入一个数字，然后把数字分开，然后平方相加。比如19 = 1^2 + 9^2得出的数字再继续进行一样的操作，一直简化到该数字到个位数，如果该数字等于1或者7的时候，就可以return true，否则的话就return false

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
import java.util.LinkedList;
import java.util.List;

public class HappyNumber {
    public boolean isHappy(int n) {
        if (n == 1) return true;
        int sum = n;
        List<Integer> list = new LinkedList<>();

        while (true) {
            list = split(sum);
            sum = 0;
            for (Integer i : list) {
                sum += Math.pow(i, 2);
            }

            if (sum == 1 || sum == 7) {
                return true;
            }

            if (sum < 10) return false;

        }
    }

    public List<Integer> split(int n) {
        List<Integer> list = new LinkedList<>();
        while (n != 0) {
            list.add(n % 10);
            n = n / 10;
        }
        return list;
    }

    public static void main(String[] args) {
        HappyNumber hp = new HappyNumber();
        System.out.println(hp.isHappy(19));
    }
}

Contains Duplicate

Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

1
2
Input: [1,2,3,1]
Output: true

Example 2:

1
2
Input: [1,2,3,4]
Output: false

Example 3:

1
2
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

这个题用简单的HashMap做就行，或者用hashset，我这用的是hashset。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Arrays;
import java.util.HashSet;

public class ContainsDuplicate {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<Integer>();

        for (int num : nums) {
            hashSet.add(num);
        }

        return nums.length != hashSet.size();
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3, 1};
        ContainsDuplicate cd = new ContainsDuplicate();
        System.out.println(cd.containsDuplicate(nums));
    }
}

Group Anagrams

Group Anagrams

Given an array of strings, group anagrams together.

Example:

1
2
3
4
5
6
7
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

把使用同一个字符构成的string放到一起。首先确定是使用HashMap，在遍历数组的时候对每一个string先进行sort一下（或者用hash的方法，我下面有写），排过序的string当做key，如果还有相同的数据就接着添加，如果没有该key就初始化一个数组。

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
import java.util.*;

public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> list = new LinkedList<>();
        HashMap<String, List<String>> hashMap = new HashMap<>();
        for (String str : strs) {
            hash(str);
            char[] temp_char = str.toCharArray();
            Arrays.sort(temp_char);
            String key = Arrays.toString(temp_char).toString();
            if (hashMap.containsKey(key)) {
                hashMap.get(key).add(str);
            } else {
                List<String> temp = new LinkedList<>();
                temp.add(str);
                hashMap.put(key, temp);
            }
        }

        for (String key : hashMap.keySet()) {
            list.add(hashMap.get(key));
        }
        return list;
    }

    public void hash(String str) {
        int hash = 31;
        for (int i = 0; i < str.length(); i ++) {
            hash += str.charAt(i);
        }
        System.out.println(hash);
    }


    public static void main(String[] args) {
        String[] strs = new String[] {"duy","ill"};
        GroupAnagrams ga = new GroupAnagrams();
        ga.groupAnagrams(strs);
    }
}

Search in Rotated Sorted Array

Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

思路，先把分割点找到，就是从哪个地方来做的rotated，比如[4,5,6,7,0,1,2]那么分割点就是index = 3的时候，因为是一个递增的过程，所以想找到分割点就很简单。再根据分割点做一个binary search，先分析前半段，如果能找到结果就return，如果找不到就找后半段的内容。

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
public class SearchRotatedArray {
    public int search(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        int right = nums.length - 1;
        int num = nums[0];
        int mid = -1;

        for (int i = 1; i < nums.length; i ++) {
            if (num <= nums[i]) num = nums[i];
            else {
                mid = i - 1;
                break;
            }
        }

        if (mid == -1) mid = nums.length - 1;
        right = mid;
        int res = binary_search(left, right, nums, target);
        if (res == -1) {
            left = mid + 1; right = nums.length - 1;
            return binary_search(left, right, nums, target);
        } else {
            return res;
        }
    }

    public int binary_search(int left, int right, int[] nums, int target) {

        while (left <= right) {
            int temp_mid = left + (right - left) / 2;
            if (nums[temp_mid] == target) return temp_mid;
            else if (nums[temp_mid] > target) {
                right = temp_mid - 1;
            } else {
                left = temp_mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = new int[] {4,5,6,7,0,1,2};
        SearchRotatedArray s = new SearchRotatedArray();
        int x = s.search(nums, 0);
        System.out.println(x);
    }
}

344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

1
2
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

1
2
Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

感觉没有什么技术含量，就直接reverse就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Arrays;

public class ReverseString {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;

        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left ++;
            right --;
        }
    }

    public static void main(String[] args) {
        ReverseString re = new ReverseString();
        char[] chars = new char[] {'h', 'e', 'l', 'l', 'o'};
        re.reverseString(chars);

        System.out.println(Arrays.toString(chars));
    }
}

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

1
2
Input: 1->1->2
Output: 1->2

Example 2:

1
2
Input: 1->1->2->3->3
Output: 1->2->3

在已经sorted的链表里面去除重复的值，可以使用连个指针来完成，curr来前进，temp来链接不一样的值。当temp.val != curr.val的时候代表中间已经省略了同类项，所以直接设置temp.next = curr然后把curr赋值给temp（temp = curr）。

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
public class RemoveDuplicatesfromSortedList {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode curr = head.next;
        ListNode temp = head;

        while (curr != null) {
            if (temp.val != curr.val) {
                temp.next = curr;
                temp = curr;
            }
            curr = curr.next;
        }
        temp.next = null;

        return head;
    }


    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(1);
        ListNode l3 = new ListNode(2);

        l1.next = l2;
        l2.next = l3;
        l3.next = null;

        RemoveDuplicatesfromSortedList re = new RemoveDuplicatesfromSortedList();
        ListNode head = re.deleteDuplicates(l1);

        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }
    }

}

58. Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop from left to right) in the string.

If the last word does not exist, return 0.

Note: A word is defined as a maximal substring consisting of non-space characters only.

Example:

1
2
Input: "Hello World"
Output: 5

直接split然后取最后一个，然后直接计算length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LengthofLastWord {
    public int lengthOfLastWord(String s) {
        if (s.equals("")) return 0;
        String[] res = s.split(" ");

        if (res.length == 0) return 0;
        return res[res.length - 1].length();
    }

    public static void main(String[] args) {
        String r = "Hello world";

        LengthofLastWord l = new LengthofLastWord();
        System.out.println(l.lengthOfLastWord(r));
    }
}

387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

1
2
3
4
5
s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

使用了HashMap的方法，当字符只出现一次就设置key为当前char，value设置为index，如果出现超过一次，就标记value是MAX。筛选HashMap里面value不是MAX，并且返回就行了。

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
import java.util.Collections;
import java.util.HashMap;

public class FirstUnique {
    public int firstUniqChar(String s) {
        HashMap<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < s.length(); i ++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, Integer.MAX_VALUE);
            } else {
                map.put(c, i);
            }
        }

        int position = Integer.MAX_VALUE;
        for (Character c : map.keySet()) {
            if (map.get(c) != Integer.MAX_VALUE) {
                if (map.get(c) < position) position = map.get(c);
            }
        }
        if (position == Integer.MAX_VALUE) return -1;
        return position;
    }

    public static void main(String[] args) {
        FirstUnique f = new FirstUnique();
        String str = "loveleetcode";
        System.out.println(f.firstUniqChar(str));
    }
}

61. Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

1
2
3
4
5
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

1
2
3
4
5
6
7
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

做法稍微蠢了一点，我是通过先计算链表的长度，然后把k = k % length这样就可以得到相对链表来说的第几位。然后遍历链表，当节点的index等于k的时候开始把k之后的node放到链表的起始位置。这样就完成了rotate list。

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
65
66
67
public class RotateList {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        ListNode curr = head;

        int length = length(curr);
        k = length - (k % length);
        if(k == length) return head;

        ListNode rota = find_rota(curr, k);
        ListNode temp = rota;

        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = head;
        head = rota;


        return head;
    }

    public ListNode find_rota(ListNode curr, int k) {
        while (k > 1) {
            curr = curr.next;
            k --;
        }

        ListNode node = curr.next;
        curr.next = null;
        return node;

    }

    public int length(ListNode node) {
        int length = 0;
        while (node != null) {
            node = node.next;
            length ++;
        }

        return length;
    }
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
//        ListNode l4 = new ListNode(4);
//        ListNode l5 = new ListNode(5);

        l1.next = l2;
        l2.next = l3;
//        l3.next = l4;
//        l4.next = l5;

        RotateList r = new RotateList();
        r.rotateRight(l1, 2);
    }
}

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Return the linked list sorted as well.

Example 1:

1
2
Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

1
2
Input: 1->1->1->2->3
Output: 2->3

这个第83的进阶版。只要是有重复的node都需要删除掉。我们需要有一个node（last）来记录上一个访问的node，一个node（curr）来循环。如果curr.val == curr.next.val就代表着有重复的node了，这时候找到所有重复的node，然后得到最后一个重复node的next，然后使用last链接就行，但是last需要判断是否是null，如果是null的话需要考虑到head的情况。

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
65
public class RemoveDuplicatesfromSortedListII {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode last = null;
        ListNode curr = head;

        while (curr.next != null) {
            if (curr.val == curr.next.val) {
                ListNode node = different(curr);
                if (last == null) {
                    head = node;
                } else {
                    last.next = node;
                }
                curr = node;
                if (curr == null) break;
                continue;
            } else {
                last = curr;
            }
            curr = curr.next;
        }

        return head;
    }

    public ListNode different(ListNode node) {
        ListNode last = node;
        while (node.next != null) {
            if (node.val != node.next.val) {
                return node.next;
            }
            last = node;
            node = node.next;
        }
        // 因为是node.next != null 所以需要判断最后一个node是不是和前面的相等
        if (last.val == node.val) return null;
        return node;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(2);
        ListNode l4 = new ListNode(2);
//        ListNode l5 = new ListNode(5);

        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
//        l4.next = l5;

        RemoveDuplicatesfromSortedListII r = new RemoveDuplicatesfromSortedListII();
        r.deleteDuplicates(l1);
    }
}

48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

emmm这个题我使用了另一个double array应该是不咋对

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
import java.util.Arrays;

public class RotateImage {
    public void rotate(int[][] matrix) {
        int[][] res = new int[matrix.length][matrix[0].length];

        for (int i = 0; i < matrix[0].length; i ++) {
            int index = 0;
            for (int j = matrix.length - 1; j >= 0; j --) {
                res[i][index++] = matrix[j][i];
            }
        }

        for (int i = 0; i < res.length; i ++) {
            matrix[i] = res[i];
        }
    }

    public static void main(String[] args) {
        int[][] m = new int[][] {{1,2,3},{4,5,6},{7,8,9}};
        RotateImage ri = new RotateImage();
        ri.rotate(m);

        for (int[] ints : m) {
            System.out.println(Arrays.toString(ints));
        }
    }
}

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

1
2
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

从起始点到结束点进行reverse。首先根据curr的index遍历到m的时候记录一下该node start，然后同时记录start前面的一个node pre因为reverse结束还要把链表链接起来。当index遍历到n的时候记录该node end。然后使用递归进行reverse。

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
public class ReverseLinkedListII {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m >= n || head == null || head.next == null) return head;

        int index = 1;
        ListNode curr = head;
        ListNode start = null;
        ListNode end = null;
        ListNode pre = null;

        while (curr != null) {
            if (index == m) start = curr;
            if (index == n) end = curr;
            if (start == null) pre = curr;
            curr = curr.next;
            ++index;
        }

        if (end == null || start == null) return head;

        ListNode rest = end.next;
        end.next = null;
        reverse(start, start.next);
        // 现在endu应该是head

        if (pre == null) head = end;
        else pre.next = end;

        start.next = rest;

        return head;
    }

    public void reverse(ListNode curr, ListNode next) {
        if (next == null) return;

        reverse(next, next.next);
        next.next = curr;
        curr.next = null;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;

        ReverseLinkedListII r = new ReverseLinkedListII();
        r.reverseBetween(l1, 1, 4);
    }
}

142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

首先想到的就是HashMap哈哈哈哈，然后他要求说不用额外的空间，在不实用额外的空间的情况下想到了递归+循环的方法，但是时间复杂度比较高。在循环的过程中每个node都进行一个检查环的操作，并且判断在环里面是不是等于该数字，如果不等于的话就代表不是环的一个node，当出现第一个node并且是在环里面的node就代表是环的第一个节点。感觉牺牲了时间换来了空间的优化。。。。。

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
65
import java.util.HashMap;

public class LinkedListCycleII {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    // hashmap的解决方法
//    public ListNode detectCycle(ListNode head) {
//        HashMap<ListNode, Integer> map = new HashMap<>();
//
//        ListNode curr = head;
//        while (curr != null) {
//            if (map.containsKey(curr)) {
//                return curr;
//            } else {
//                map.put(curr, 1);
//            }
//            curr = curr.next;
//        }
//
//        return null;
//    }

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode curr = head;

        while (curr.next != null) {
            ListNode temp = loop(curr.next, curr.next.next, curr);
            if (temp != null) return curr;
            curr = curr.next;
        }

        return null;
    }

    public ListNode loop(ListNode slow, ListNode fast, ListNode node) {
        if (slow == null || fast == null || slow.next == null || fast.next == null
                || fast.next.next == null) return null;
        if (slow == fast && slow == node) return slow;
        if (slow == fast) return null;
        return loop(slow.next, fast.next.next, node);
    }


    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);

        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
//        l4.next = l2;

        LinkedListCycleII l = new LinkedListCycleII();
        l.detectCycle(l1);
    }
}

219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

1
2
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

1
2
Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

1
2
Input: nums = [1,2,3,1,2,3], k = 2
Output: false

本来想的是直接用for循环，根据当前数字然后向后走k位，看k位以内有没有和nums[i]相同的数字，但是貌似bug有点多，放弃了。。改用HashMap了，key存nums[i]，value存相对应的index。如果HashMap已经有该key则可以计算HashMap里面存的index和当前i的差值，如果小于等于K就可以直接返回了。

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
import java.util.HashMap;
import java.util.Map;

public class ContainsDuplicateII {
    // 放弃了我使用hashmap来写好吧。。。
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i ++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) return true;
            }

            map.put(nums[i], i);
        }

        return false;
    }

    public static void main(String[] args) {
        ContainsDuplicateII c = new ContainsDuplicateII();
        int[] nums = new int[] {1,2,3,1,2,3};

        System.out.println(c.containsNearbyDuplicate(nums, 2));
    }
}

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

1
2
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

1
2
Input: nums = [1], k = 1
Output: [1]

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
  • It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
  • You can return the answer in any order.

用HashMap可以解决，但是因为Java对HashMap有点点不太友善，我改成Python了，因为可以自定义sort 字典，这样可以根据结果排序了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def topKFrequent(self, nums, k):
        frequence = {}

        for value in nums:
            if value in frequence:
                frequence[value] += 1
            else:
                frequence[value] = 1

        frequence = sorted(frequence.items(), key=lambda x: x[1], reverse=True)
        index = 0
        res = []

        for t in frequence:
            index += 1
            res.append(t[0])
            if index == k:
                break

        return res

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its minimum depth = 2.

关于tree的算法可以去看我另一篇文章https://shunyangli.github.io/2020/05/03/Algorithm/#more

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class MinimumDepthofBinaryTree {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;

        int left = minDepth(root.left);
        int right = minDepth(root.right);

        if (root.left == null) return 1 + right;
        if (root.right == null) return 1 + left;

        return Math.min(left, right) + 1;
    }
}

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

1
2
3
4
5
6
7
8
9
10
11
public class PathSum {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return root.val == sum;

        boolean left = hasPathSum(root.left, sum - root.val);
        boolean right = hasPathSum(root.right, sum - root.val);

        return left | right;
    }
}

100. Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

1
2
3
4
5
6
7
Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

思路就是左右两边的node都一样。

1
2
3
4
5
6
7
8
9
10
11
public class SameTree {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;

        boolean left = isSameTree(p.left, q.left);
        boolean right = isSameTree(p.right, q.right);

        return p.val == q.val && (left && right);
    }
}

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

其实是和上面那道题一个相反的思路，上面是左右相等，这个是left = right, right = left。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class SymmetricTree {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return mirror(root.left, root.right);
    }
    // 判断左右是否一样
    public boolean mirror(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;

        boolean left = mirror(p.left, q.right);
        boolean right = mirror(p.right, q.left);

        return p.val == q.val && (left && right);
    }
}

144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

就是一个前序的遍历：根左右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.LinkedList;
import java.util.List;

public class BinaryTreePreorderTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();

        traversal(root, res);
        return res;

    }

    public void traversal(TreeNode root, List<Integer> res) {
        if (root == null) return;

        res.add(root.val);
        traversal(root.left, res);
        traversal(root.right, res);
    }
}

162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

1
2
3
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

1
2
3
4
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Follow up: Your solution should be in logarithmic complexity.

可以采用一个二分查找的方法来处理这个问题，因为已知peak number是 nums[i] > nums[i+1]也就是说如果在array里面出现一个降序就代表着是peak number。这样的话可以使用二分查找，如果nums[mid] > nums[mid+1]就代表该数字就是peak number，但是之前的可以还有相对应的peak number，所以就是search(nums, left, mid)。

ps: 也有一种O(n)的方法来查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class FindPeakElement {
//    public int findPeakElement(int[] nums) {
//        for (int i = 0; i < nums.length - 1; i ++) {
//            if (nums[i] > nums[i+1]) return i;
//        }
//
//        return nums.length-1;
//    }

    public int findPeakElement(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }

    public int search(int[] nums, int left, int right) {
        if (left == right) return left;

        int mid = (left + right) / 2;
        if (nums[mid] > nums[mid+1]) return search(nums, left, mid);

        return search(nums, mid+1, right);
    }
}

39. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

1
2
3
4
5
6
7
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

这个可以使用到回溯算法的思想，从i - nums.length，每个都会重复，比如当i=0的时候：

1
2
3
4
5
6
7
8
9
10
2,2,2,2
2,2,2,3
2,2,2,6
2,2,2,7
2,2,3
2,2,6
2,2,7
2,2
2,3
....

这样的一个规律。

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
import java.util.*;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new LinkedList<>();
        back_tracking(res, new ArrayList<>(), target, candidates, 0);
        return res;
    }

    // 回溯算法
    public void back_tracking(List<List<Integer>> res, List<Integer> temp, int target, int[] nums, int index) {
        if (target < 0) return;
        else if (target == 0) res.add(new ArrayList<>(temp));
        else {
            for (int i = index; i < nums.length; i ++) {
                temp.add(nums[i]);
                back_tracking(res, temp, target - nums[i], nums, i);
                temp.remove(temp.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        CombinationSum cs = new CombinationSum();
        int[] nums = new int[] {2,3,6,7};
        List<List<Integer>> res = cs.combinationSum(nums, 7);

        for (List<Integer> l : res) {
            System.out.println(Arrays.toString(l.toArray()));
        }
    }
}

46. Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

也是一个回溯算法，需要加一个额外的条件，不能重复，不过也是回溯算法的一个套路。伪代码：

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(path, select_list):
    if condition:
        result.add(path)
        return

    for list in select_list:
        make a select
        backtrack(path, select_list)
        drawback select
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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;


public class Permutations {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();

        back_track(res, new ArrayList<>(), nums);
        return res;
    }


    public void back_track(List<List<Integer>> res, List<Integer> temp, int[] nums) {
        if (temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }

        for (int i = 0; i < nums.length; i ++) {
            // 避免重复项
            if (temp.contains(nums[i])) continue;
            temp.add(nums[i]);
            back_track(res, temp, nums);
            temp.remove(temp.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[] {1,2,3};

        Permutations p = new Permutations();
        List<List<Integer>> res = p.permute(nums);

        for (List<Integer> l : res) {
            System.out.println(Arrays.toString(l.toArray()));
        }
    }
}

704. Binary Search

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Example 1:

1
2
3
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

1
2
3
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

标准的二分查找法（只能用在排过序的list里面）。有一个算法讲解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class BinarySearch {
    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;
    }

    public static void main(String[] args) {
        int[] nums = new int[] {-1,0,3,5,9,12};
        BinarySearch bs = new BinarySearch();
        int res = bs.search(nums, 9);
        System.out.println(res);
    }
}
----- End Thanks for reading-----