Leetcode_350

给定两个数组，求他们的交集
给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

题解：
python (主要使用字典)

class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        dict1 = dict()
        dict2 = dict()
        for num in nums1:
            dict1[num] = dict1.get(num,0)+1
        for num in nums2:
            dict2[num] = dict2.get(num,0)+1
        return [x for x in dict2 for j in range(min(dict2.get(x,0),dict1.get(x,0)))]

C++ （使用map容器）

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        map<int,int> record;
    for(int i = 0; i<nums1.size();i++)
        record[nums1[i]]++;
    vector<int> v;
    for(int i=0; i<nums2.size();i++)
    {
        if(record[nums2[i]]>0)
        {
            v.push_back(nums2[i]);
            record[nums2[i]]--;
        }
    }
    return v;        
    }
};

Leetcode_202

判断一个数字是不是幸福数，题目实在是太绕了，直接给出示例

1.png

这里的19就是一个happynum，如果最终结果不是1的话，那么它就不是一个happynum。
C++

#include <iostream>
#include <map>
using namespace std;
bool isHappy(int n)
{
    map<int, int> m;
    while(true)
    {
        int sum = 0;
        while(n)
        {
            sum += (n%10)*(n%10);
            n = n/10;
        }
        if(sum == 1) return true;
        else
        {
            n = sum;
            m[sum]++;
        }
        
        if(m[sum]==2) return false;
    }
}
int main()
{
    int a = 19;
    if(isHappy(12))
        cout<<"end";
    return 0;
}

Leetcode_242

判断两个字符串是不是含有相同的字母，顺序可以不一样

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <typeinfo>
using namespace std;
bool isAnagram(string s, string t)
{
    map<char,int> v1;
    map<char,int> v2;
    for(int i = 0; i<s.size(); i++)
        v1[s[i]]++;
    for(int i = 0; i<t.size();i++)
        v2[t[i]]++;
    if (v1 == v2)
        return true;
    else
        return false;
}
int main()
{
    string a = "abcd";
    string b = "bacd";
    if(isAnagram(a,b))
        cout<<"end";
    return 0;
}

Leetcode_290

主要需要匹配pattern和str他们是否属于同一类，看下面的样例你就会明白啦
pattern = “abba”, str = “dog cat cat dog” should return true.
pattern = “abba”, str = “dog cat cat fish” should return false.
pattern = “aaaa”, str = “dog cat cat dog” should return false.
pattern = “abba”, str = “dog dog dog dog” should return false.

这边放出两个思路的代码
python
思路1：体验一下python的简洁吧

def wordPattern(pattern,str):
    words = str.split(' ')
    if len(words) != len(pattern):
        return False
    return len(set(pattern)) == len(set(words)) == len(set(zip(pattern, words)))
if __name__ == '__main__':
    a = "abba"
    b = "dog cat cat dog"
    c = wordPattern(a,b)
    print(c)

思路2：主要是建立pattern和str的映射关系，同时还要保证映射的独立。pattern是我们的key值，不同的key不能映射到相同的str上

class Solution(object):
    def wordPattern(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        words = str.split(' ')
        if len(words) != len(pattern):
            return False
        hashmap = {}
        mapval = {}
        for i in xrange(len(pattern)):
            if pattern[i] in hashmap:
                if hashmap[pattern[i]] != words[i]:
                    return False
            else:
                if words[i] in mapval:
                    return False
                hashmap[pattern[i]] = words[i]
                mapval[words[i]] = True
        return True

Leetcode_205

几乎和290是一样的模型，还是判断两个输入的模式是否一样，注意看下面的样例
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

这里我就放出最常规的解法
python

def isIsomorphic(s, t):
    if len(s)!=len(t):
        return False

    hashmap = {}
    val = {}
    for i in range(len(s)):
        if s[i] in hashmap:
            if hashmap[s[i]] != t[i]:
                return False
        else:
            if t[i] in val:
                return False #防止不同的key映射到同一个value上#
            hashmap[s[i]] = t[i]
            val[t[i]] = True

    return True

Leetcode_451

按照字母出现的频率逆序排序，请看具体的示例
Example 1:
Input:
"tree"
Output:
"eert"
Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:
Input:
"cccaaa"
Output:
"cccaaa"
Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:
Input:
"Aabb"
Output:
"bbAa"
Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

python 再次感叹python的简洁和强大

import collections
def frequencySort(s):
    count = collections.Counter(s).most_common()
    res =''
    for c,v in count:
        res += c*v
    return res

if __name__ == '__main__':
    a = "abbcd"
    s = frequencySort(a)
    print(s)

注意我们这边都是以真实环境能够跑的代码呈现为主的，提交的时候需要去掉一些导入和main函数

Leetcode_01_two_sum

找出数组里面的两个数字，使得他们的和等于我们的目标数，返回我们找到的两个数的下标

#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target)
{
    map<int,int> record;
    for(int i = 0; i<nums.size(); i++)
    {
        int temp = target-nums[i];
        if(record.find(temp)!=record.end())
        {
            int res[2] = {i,record[temp]};
            return vector<int> (res,res+2);
        }
        record[nums[i]] = i;
    }
}
int main()
{
    vector<int> v = {2,7,11,15};    
    vector<int> a = twoSum(v,9);
    for(int i = 0; i<a.size(); i++)
    {
        cout<<a[i]<<" ";
    }

}

Leetcode_15_3_sum

从数组中选择三个元素和为零

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

/// Using Hash Table to store all the numbers
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        unordered_map<int, int> counter;
        for(int i = 0 ; i < nums.size() ; i ++)
            counter[nums[i]] ++;

        vector<vector<int>> res;

        if(counter[0] >= 3)
            res.push_back({0, 0, 0});

        // Remove duplication
        sort(nums.begin(), nums.end());
        vector<int>::iterator iter = unique(nums.begin(), nums.end());
        nums.erase(iter, nums.end());

        for(int i = 0 ; i < nums.size() ; i ++)
            for(int j = i + 1 ; j < nums.size() ; j ++){

                if(nums[i] * 2 + nums[j] == 0 && counter[nums[i]] >= 2)
                    res.push_back({nums[i], nums[i], nums[j]});

                if(nums[i] + nums[j] * 2 == 0 && counter[nums[j]] >= 2)
                    res.push_back({nums[i], nums[j], nums[j]});

                int c = 0 - nums[i] - nums[j];
                if(c > nums[j] && counter[c] != 0)
                    res.push_back({nums[i], nums[j], c});
            }

        return res;
    }
};

int main() {

    vector<int> nums1 = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> res = Solution().threeSum(nums1);
    for( int i = 0 ; i < res.size() ; i ++ ){
        for( int j = 0 ; j < res[i].size() ; j ++ )
            cout<<res[i][j]<<" ";
        cout<<endl;
    }

    return 0;
}

这里也提供一个简单的Python思路，使用对撞指针来做

def threeSum(nums):
    res = []
    nums.sort()
    for i in range(len(nums)-2):
        if i>0 and nums[i]==nums[i-1]:
            continue
        l,r = i+1, len(nums)-1
        while l<r:
            s = nums[i]+nums[l]+nums[r]
            if s<0:
                l += 1
            elif s>0:
                r-=1
            else:
                res.append((nums[i],nums[l],nums[r]))
                while l<r and nums[l] == nums[l+1]:
                    l = l+1
                while l<r and nums[r] == nums[r-1]:
                    r-=1
                l+=1
                r-=1
    return res

if __name__ == '__main__':
    a = [1,2,3,-1,0,-2,-3,4]
    print(threeSum(a))

Leetcode_18_4sum

vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> total;
        int n = nums.size();
        if(n<4)  return total;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-3;i++)
        {
            if(i>0&&nums[i]==nums[i-1]) continue;
            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
            if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
            for(int j=i+1;j<n-2;j++)
            {
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
                if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
                int left=j+1,right=n-1;
                while(left<right){
                    int sum=nums[left]+nums[right]+nums[i]+nums[j];
                    if(sum<target) left++;
                    else if(sum>target) right--;
                    else{
                        total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
                        do{left++;}while(nums[left]==nums[left-1]&&left<right);
                        do{right--;}while(nums[right]==nums[right+1]&&left<right);
                    }
                }
            }
        }
        return total;
    }

Leetcode_454

四个数组，abcd，求abcd四个数组元素和为0的个数

#include <iostream>
#include <map>
#include <vector>
using namespace std;


int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D)
{
    map<int,int> rec;
    for(int i = 0; i<C.size(); i++)
        for(int j = 0; j<D.size();j++)
            rec[C[i]+D[j]]++;

    int res = 0;

    for(int i = 0;i<A.size();i++)
        for(int j = 0;j<B.size();j++)
            if(rec.find(-A[i]-B[j])!=rec.end())
                res += rec[-A[i]-B[j]];
    return res;
}

leetcode_447

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int dis(const pair<int,int> &pa, const pair<int,int> &pb)
{
    return (pa.first-pb.first)*(pa.first-pb.first) + (pa.second-pb.second)*(pa.second-pb.second);

}

int numberOfBoomerangs(vector<pair<int, int>>& points)
{
    int res = 0;
    for(int i = 0; i<points.size();i++)
    {
        map<int, int> rec;
        for(int j = 0; j<points.size();j++)
            if(j!=i)
                rec[dis(points[i],points[j])]++;
        for(map<int,int>::iterator iter = rec.begin(); iter != rec.end(); iter++)
            res += (iter->second)*(iter->second-1);

    }
    return res;
}

leetcode_219

bool containsNearbyDuplicate(vector<int>& nums, int k)
{
    set<int> rec;
    for(int i = 0; i<nums.size();i++)
    {
        if(rec.find(nums[i])!=rec.end())
            return true;
        rec.insert(nums[i]);
        if(rec.size()==k+1)
            rec.erase(nums[i-k]);
    }
    return false;
}

Leetcode_206

反转链表

#include <iostream>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x): val(x),next(NULL) {}
    
};

ListNode* reverseList(ListNode* head)
{
    ListNode *pre = NULL;
    ListNode *cur = head;
    //ListNode *next = head->next;
    while(cur!=NULL)
    {
        ListNode *next = cur->next;
        cur ->next= pre ;
        pre = cur;
        cur = next;
        //next = next->next;

    }
    return pre;
}