<commit_before>---
layout: post
comments: true
title: LeetCode菜鸟刷题
published: true
---

# Algorithm 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.

Example:

```
s = "leetcode"
return 0.

s = "loveleetcode",
return 2.
```

菜鸟Solution:

```python
class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        final_set = set()
        finalist = {}
        for i, item in enumerate(s):
            if item not in final_set:
                final_set.add(item)
                finalist[item] = i
            else:
                if item in finalist:
                    del finalist[item]
        if len(finalist) == 0:
            return -1
        else:
            index = 9223372036854775807
            for item in finalist:
                if finalist[item] < index:
                    index = finalist[item]
            return index
```

Editorial Solution:
未有


# Algorithm 226. Invert a binary tree.

Example:

```
     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1
```

菜鸟Solution:

```python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root == None:
            return root
        else:
            temp_node = root.right
            root.right = root.left
            root.left = temp_node
            self.invertTree(root.left)
            self.invertTree(root.right)
            return root
```

Editorial Solution:
还是递归来做比较优雅。

标准答案的Java版本是这样：

```java
public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode right = invertTree(root.right);
    TreeNode left = invertTree(root.left);
    root.left = right;
    root.right = left;
    return root;
}
```

感觉比我的答案还多了一次拷贝，毕竟只需要一个temp_node做中转就够了啊。。<commit_msg>algo 1<commit_after>---
layout: post
comments: true
title: LeetCode菜鸟刷题
published: true
---

# Algorithm 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.

Example:

```
s = "leetcode"
return 0.

s = "loveleetcode",
return 2.
```

菜鸟Solution:

```python
class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        final_set = set()
        finalist = {}
        for i, item in enumerate(s):
            if item not in final_set:
                final_set.add(item)
                finalist[item] = i
            else:
                if item in finalist:
                    del finalist[item]
        if len(finalist) == 0:
            return -1
        else:
            index = 9223372036854775807
            for item in finalist:
                if finalist[item] < index:
                    index = finalist[item]
            return index
```

Editorial Solution:

未有


# Algorithm 226. Invert a binary tree.

Example:

```
     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1
```

菜鸟Solution:

```python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root == None:
            return root
        else:
            temp_node = root.right
            root.right = root.left
            root.left = temp_node
            self.invertTree(root.left)
            self.invertTree(root.right)
            return root
```

Editorial Solution:

还是递归来做比较优雅。

标准答案的Java版本是这样：

```java
public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode right = invertTree(root.right);
    TreeNode left = invertTree(root.left);
    root.left = right;
    root.right = left;
    return root;
}
```

感觉比我的答案还多了一次拷贝，毕竟只需要一个temp_node做中转就够了啊。。


# Algorithm 1. Two Sum

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

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

Example:

```
Given nums = [2, 7, 11, 15], target = 9,

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

return [0, 1].
```

菜鸟Solution:

```python
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(nums)
        for i in range(length):
            for j in range(i+1,length):
                if nums[i] + nums[j] == target:
                    return [i, j]
```

Editorial Solution:

看似简单的题目，推荐答案令人深思。

我的答案计算复杂度O(n*n)，存储复杂度O(1)。

而这个答案用了Hash Table，而且只用扫一遍！计算复杂度O(n)，存储复杂度O(n)！看来还是要多思考和多使用Hash Table。

```java
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}
```

{'fraction_non_alphanumeric': 0.1122266045177483, 'fraction_numerical': 0.01918250268913589, 'mean_word_length': 1.7992975413948822, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3857305', 'n_tokens_mistral': 2038, 'n_tokens_neox': 1991, 'n_words': 525}