发表于 | 分类于

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

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.
Follow up:
What if the given array is already sorted? How would you optimize your algorithm?
What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

解法1：HashTable O(N) Space + O(N + M) Time

将其中一个构建hashtable，记录每个数字出现的次数。扫描第二个数组，每当找到一样的次数大于0的数字则加入res，加入结束以后需要将hashtable中出现次数-1
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int, int> map;
        for (int num: nums1) {
            ++map[num];
        }
        for (int num : nums2) {
            if (map[num] > 0) {
                res.emplace_back(num);
                --map[num];
            }
        }
        return res;
    }
};

Java

1

Follow up：

如果是已经排序了的数组，那么不需要用hashtable，可以用two pointers解决。简化到了O(N + M) TIME + O(1) Space
对于follow up的回答：这个blog给了挺好的答案。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
pubic：
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
      vector<int> res;
      int ptr1 =0, ptr2 = 0;
      while (ptr1 < nums1.size() && ptr2 < nums2.size()) {
        if (nums1[ptr1] < nums2[ptr2]) {
          ++ptr1;
        } else if (nums1[ptr1] > nums2[ptr2]) {
          ++ptr2;
      } else {
        res.emplace_back(nums1[ptr1]);
        ++ptr1;
        ++ptr2;
      }
    }
    return res;
}

发表于 | 分类于

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.

解法1：Hashtable

很直观的用Hashtable的题，对每一个int记录出现的次数，一但出现多余1则返回true。
C++

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int, int> map;
        for (int num: nums) {
            ++map[num];
            if (map[num] > 1) return true;
        }
        return false;
    }
};

Java

1

发表于 | 分类于

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
“abccccdd”

Output:
7

Explanation:
One longest palindrome that can be built is “dccaccd”, whose length is 7.

解法1：Hashtable

统计每个字母的出现次数：
若字母出现偶数次，则直接累加至最终结果
若字母出现奇数次，则将其值-1之后累加至最终结果
若存在出现奇数次的字母，将最终结果+1
C++

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
class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> map;
        for (char c: s) {
            ++map[c];
        }
        int res = 0;
        int maxOdd = 0;
        int oddSum = 0;
        for (auto iter = map.begin(); iter != map.end(); ++iter) {
            if (iter->second % 2 == 0) res+= iter->second;
            else {
                maxOdd = max(iter->second, maxOdd);
                oddSum += iter->second - 1;
            }
        }
        if (maxOdd > 0) {
            oddSum++;
        }
        res += oddSum;
        return 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
class Solution {
    public int longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (char ch : s.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
                int res = 0;
        boolean oddFlag = false;
        for (char key : map.keySet()) {
            if (map.get(key) % 2 == 0) {
                res += map.get(key);
            } else {
                res += map.get(key) - 1;
                oddFlag = true;
            }
        }
        return oddFlag ? res + 1 : res;        
    }
}

发表于 | 分类于

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.

解法1：抵消的思路，O(N) Time + O(1) Space

运用抵消的思路，如果有多余半数的一个数字，那么如果我们俩俩抵消不一样的数字，最后剩下来的一定是最多的那个数字。
抵消的实现用一个计数器，当两个数字不一样的时候，计数器减少1，如果归0了则更改被选答案到当前选定的数字。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int count = 1; int result = nums[0];
        for (int num: nums) {
            if (num == result) ++count;
            else count--;
            if (count == 0) {
                result = num;
                ++count;
            }
        }
        return result;
    }
};

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
class Solution {
    public int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = nums[0], count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == res) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    res = nums[i];
                    count = 1;
                }
            }
        }
        return res;
    }
}

解法2：排序 O(NlogN)

因为多数元素个数超过半数，那么排序之后，当中的元素一定是最多的元素。
这个方法也能过OA
C++

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

发表于 | 分类于

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

解法1：Sort O(NlogN)

先排序，然后看排过序的两个string是否一致。

C++

主要是掌握一下两个c++里的用法:
一个是对于字符串的排序。
std::sort(s.begin(), s.end())
另一个是比较两个字符串用s1.compare(s2)的形式，当两个字符串相等时，返回0

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isAnagram(string s, string t) {
        std::sort(s.begin(), s.end());
        std::sort(t.begin(), t.end());
        return s.compare(t) == 0;
    }
};

Java

1

解法2：Hashtable O(N) time + O(N) Space

统计其中一个字符串每个字符出现的次数，然后扫描另一个字符串来判断是否一致。
如果都是a-z的小写字母，那就只需要一个大小为26的数组记录就可，如果出现了unicode，那么还是必须要用hashtable来解决。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char,int> map;
        for (char c : s) {
            ++map[c];
        }
        for (char c: t) {
            --map[c];
            if (map[c] < 0) {
                return false;
            }
        }
        // check if there's remaining
        for (auto iter = map.begin(); iter != map.end(); ++iter) {
            if (iter->second != 0) {
                return false;
            }
        }
        return true;
    }
};

Java

1

Follw up

见解法2的讨论，主要是针对用hashtable这一种用法的follow up。

发表于 | 分类于

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

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.
Note: You may assume the string contain only lowercase letters.

解法1：HashTable

思路是将字符串建立hashtable，其中存的是每一个字符出现的位置，如果出现超过1次则位置设置为-1，然后遍历hashtable找出最小的非-1的即可。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> map;
        for (int i = 0; i < s.size(); ++i) {
            if (map.find(s[i]) != map.end()) {
                map[s[i]] = -1;
            } else {
                map[s[i]] = i;
            }
        }
        int res = s.size();
        for (auto iter = map.begin(); iter != map.end(); ++iter) {
            if (iter->second !=-1) {
                res = min(res, iter->second);
            }
        }
        if (res == s.size()) return -1;
        else return 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
class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!map.containsKey(ch)) {
                map.put(ch, new ArrayList<Integer>());
            }
            map.get(ch).add(i);
        }
        int res = Integer.MAX_VALUE;
        for (char key : map.keySet()) {
            if (map.get(key).size() == 1) {
                res = Math.min(res, map.get(key).get(0));
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

解法2：HashTable

上面的思路有点繁复，如果hashtable中存入每一个字符出现的次数，那么只需要重新扫描一遍字符串，找到第一个次数为1的就是所求的答案。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> map;
        for (char c : s) {
            ++map[c];
        }
        for (int i = 0; i < s.size(); i++) {
            if (map[s[i]] == 1) {
                return i;
            }
        }
        return -1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (map.get(ch) == 1) {
                return i;
            }
        }
        return -1;
    }
}

发表于 | 分类于

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28

解法1：O(N) 26进制到10进制转换

26进制转换为10进制的算法。关键的一句就是res = res * 26 + (s[i] - ‘A’ + 1), 从高位向低位运算。往下一位时要把之前的结果乘以26。
C++

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int titleToNumber(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); ++i) {
            res = res * 26 + (s[i] - 'A' + 1);
        }
        return res;
    }
};

Java

1

发表于 | 分类于

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

解法1：O(NlogN) Time

考察的是对custom class排序的能力，我们只需要用标准的库函数，用上自己定义的比较函数就可以了。比较的时候后一个meeting的开始时间不能早于前一个会议的结束时间。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
bool compare(Interval left, Interval right) {
        return left.start < right.start;
}
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        std::sort(intervals.begin(), intervals.end(), compare);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start < intervals[i - 1].end) {
                return false;
            }
        }
        return true;
    }
};

Java

1

发表于 | 分类于

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

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

解法1：递归 / 分治

经典的二叉树的问题，用递归很容易解决。两个树相等首先是root的值要一样，然后左子树相等，右子树相等。终结条件是如果值不一样或者有一个root为空另一个不是空则结构不同。

C++

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q != NULL) {
            return false;
        }
        if (p != NULL && q == NULL) {
            return false;
        }
        if (p == NULL && q == NULL) {
            return true;
        }
        if (p-> val != q->val) {
            return false;
        }
        bool left = isSameTree(p->left, q->left);
        if (!left) return false;
        bool right = isSameTree(p->right, q->right);
        return right;
    }
};

Java

1

发表于 | 分类于

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

解法1：O(1) Time

由于只给了当前node的指针，那么没办法得到前面一个节点的信息。只能换种思考方式。我们可以将下一个节点的数值拷贝过来然后删除下一个节点就可以。

C++

要注意的是要删除下一个节点指针对应的object，否则会造成leak

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        if (node == NULL || node-> next == NULL) {
            return;
        }
        node->val = node->next->val;
        ListNode* p = node->next;
        node->next = node->next->next;
        delete p;
    }
};

Java

1