From 41 to 60, LeetCode Problems Easy to Hard

——leetcode做题笔记

Posted by Samuel on April 24, 2017

目录

100. Same Tree

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.

/**
 * 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 && !q) return true;
        else if((!p && q) || (p && !q) || (p->val != q->val)) return false;
        else if(p->val == q->val) return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

169. Majority Element(剑指offer:面试题29)

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.

本题和 剑指offer:面试题29 一样。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int index = 0, start = 0, end = nums.size() - 1, mid = (start + end) / 2;
        index = Partition(nums, start, end);
        while(index != mid){
            if(index < mid){
                start = index + 1;    
                index = Partition(nums, start, end);
            }
            else{
                end = index - 1;
                index = Partition(nums, start, end);
            }
        }
        return nums[index];
    }
    int Partition(vector<int>& nums, int start, int end){
        int index = (start + end) / 2, small = start - 1;; 
        swap(nums[index], nums[end]);
        for(index = start; index < end; ++index)
            if(nums[index] < nums[end])
                ++small, swap(nums[index], nums[small]);
        ++small, swap(nums[small], nums[end]);
        return small;
    }
};

242. Valid Anagram

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.

方法一:先排序后比较,实现简单,代码简洁,时间复杂度为O(nlogn)

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end()), sort(t.begin(), t.end());
        return s == t ? true : false;
    }
};

方法二:利用哈希表,时间复杂度为O(n)

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;
        int counts[26] = {0};
        for (int i = 0; i < s.size(); i++) { 
            counts[s[i] - 'a']++;
            counts[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++)
            if (counts[i]) return false;
        return true;
    }
};

504. Base 7

Given an integer, return its base 7 string representation.

Example 1:
Input: 100
Output: "202"

Example 2:
Input: -7
Output: "-10"

十进制转换成七进制,需要注意的就是正负号的问题。

class Solution {
public:
    string convertToBase7(int num) {
        int x = abs(num); string res;
        do res = to_string(x % 7) + res; while(x /= 7);
        return (num >= 0 ? "" : "-") + res;
    }
};

409. Longest Palindrome

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.

Example:

Input:
"abccccdd"

Output:
7

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

用哈希表来实现

class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> hash(58, 0);
        int i = 0, res = 0, odd = 0;
        while(s[i] != '\0')
            hash[(s[i] - 'A')]++, i++;
        for(i = 0; i < hash.size(); ++i)
            hash[i] & 1 ? res += hash[i] - 1, odd = 1 : res += hash[i];
        return res + odd;
    }
};

217. 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.

思路一:用STL中count()函数,代码简洁,但时间复杂度过高,通过了17/18个用例,剩下一个超时了…

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        for(int i = 0; i < nums.size(); ++i)
            if (count(nums.begin(), nums.end(), nums[i]) > 1)
                return true;
        return false;
    }
};

思路二:巧用set

leetcode中大神解法,一行解决问题,时间复杂度为O(n)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        return set<int>(nums.begin(), nums.end()).size() < nums.size();
    }
};

13. Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

罗马字母转换成阿拉伯数字

class Solution {
public:
    int romanToInt(string s){
        unordered_map<char, int> T = { { 'I' , 1 },
                                       { 'V' , 5 },
                                       { 'X' , 10 },
                                       { 'L' , 50 },
                                       { 'C' , 100 },
                                       { 'D' , 500 },
                                       { 'M' , 1000 } };
                                       
        int sum = T[s.back()];
        for (int i = s.length() - 2; i >= 0; --i){
           if (T[s[i]] < T[s[i + 1]])
               sum -= T[s[i]];
           else
               sum += T[s[i]];
        }
        return sum;
    }
};

206. Reverse Linked List

Reverse a singly linked list.

单链表的逆置

剑指offer:面试题16

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr; 
        ListNode* cur = nullptr;
        ListNode* next = head;
        while(next != nullptr){
            pre = cur;
            cur = next;
            next = next->next;
            cur->next = pre;
        }
        return cur;
    }
};

350. Intersection of Two Arrays II

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

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

本题在multiset上继续用set_interseciton()即可

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        multiset<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end());
        vector<int> res(s1.size() + s2.size());
        auto it = set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), res.begin());
        res.resize(it - res.begin());
        return res;
    }
};

447. Number of Boomerangs

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:
Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

思路: 以每一个点为tuple第一个点, 计算所有点到这个点距离, 到这个点距离相等的任意2点就可以和这个点构成这样的tuple, 并且如果有两个点到这个点距离相等, 那么有2个答案, 如果有5个点到这个点距离相等, 那么会是这5个点的中有序取2个点的组合, 也就是一个排列组合的简单问题. 所以思路就是用hash来计算保存所有其他点到一个点的距离, 然后再遍历hash表查看距离相等的点, 累加所有的组合即可.

class Solution {  
public:  
    int numberOfBoomerangs(vector<pair<int, int>>& points) {  
        int ans = 0, len = points.size();  
        for(auto p1: points) {  
            unordered_map<double, int> hash;  
            for(auto p2: points)  
                hash[hypot(p1.first - p2.first, p1.second - p2.second)]++;  //hypot()求斜边长度<math>
            for(auto val: hash)  
                if(val.second > 1) ans += val.second * (val.second - 1);  //n中取两个
        }  
        return ans;  
    }  
};  

268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

一开始尝试用快排的Partition函数,总有case通不过,后来发现直接换就行。时间复杂度为O(n)。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int i = 0;
        while (i < nums.size()) {
            if (nums[i] != i && nums[i] < nums.size() && nums[i] != nums[nums[i]])
                swap(nums[i], nums[nums[i]]);
            else 
                ++ i;
        }
        for (i = 0; i < nums.size(); ++i) {
            if (nums[i] != i) return i;
        }
        return nums.size();
    }
};

541. Reverse String II

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.

Example:
Input: s = "abcdefg", k = 2
Output: "bacdfeg"

注意边界条件即可。

class Solution {
public:
	string reverseStr(string& s, int k) {
		if (1 == s.size()) return s;
		for (int i = 0, times = 0; i <= s.size(); i += k, ++times) {
			if (times & 1) continue; //偶数次不交换
			else swapStr(s, i, i + k - 1);
		}
		return s;
	}
	void swapStr(string& s, int begin, int end) {
		end > s.size() - 1 ? end = s.size() - 1 : end; //判断末尾边界条件
		while (begin < end)
			swap(s[begin++], s[end--]);
	}
};

leetcode上有大神写出了一行的clean code,利用reverse函数。

    每次加2 * k
    0           k           2k          3k
    |-----------|-----------|-----------|---
    +--reverse--+           +--reverse--+

class Solution {
public:

    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2*k) reverse(s.begin()+i, min(s.begin()+i+k, s.end()));
        return s;
    }
};

551. Student Attendance Record I

You are given a string representing an attendance record for a student. The record only contains the following three characters:

  1. ‘A’ : Absent.
  2. ‘L’ : Late.
  3. ‘P’ : Present.

A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:
Input: "PPALLP"
Output: True

Example 2:
Input: "PPALLL"
Output: False

按要求判断即可

class Solution {
public:
	bool checkRecord(string s) {
		int numA = 0;
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == 'A') numA++;
			if (i + 2 < s.size() && s[i] == 'L' && s[i + 1] == 'L' && s[i + 2] == 'L') return false;
		}
		return numA <= 1;
	}
};

leetcode上学会了一个记录连续字符的方法:不是就重新记录。

bool checkRecord(string s) {
    int a=0, l=0;
    for(int i=0;i<s.size();i++) {
        if(s[i]=='A') a++;
        if(s[i]=='L') l++;
        else l=0; //不是就重新记录
        if(a>=2||l>2) return false;
    }
    return true;
}

543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree 
          1
         / \
        2   3
       / \     
      4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

深度优先搜索,记录左右最远距离和。

class Solution {
public:
    int maxdiadepth = 0;

    int dfs(TreeNode* root){        
        if(root == NULL) return 0;
        
        int leftdepth = dfs(root->left);
        int rightdepth = dfs(root->right);
        
        if(leftdepth + rightdepth > maxdiadepth) maxdiadepth = leftdepth + rightdepth;
        return max(leftdepth + 1, rightdepth + 1);     
    }
    
    int diameterOfBinaryTree(TreeNode* root) {        
        dfs(root);
        
        return maxdiadepth;
    }
};

401. Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

image For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

本题学习:

使用bitset在头文件#include <bitset>中,count()函数返回的是bitset中的1的个数。

对于在容器中添加类的对象时, 相比于push_back, emplace_back可以避免额外类的复制和移动操作。

算法简单粗暴

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        for (int h = 0; h < 12; h++)
            for (int m = 0; m < 60; m++)
                if (bitset<10>(h << 6 | m).count() == num) //把小时和分或到一起,找到1的个数和num相同的
                    res.emplace_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m)); //在C++11的条件下,使用emplace_back替代push_back
        return res;
    }
};

561. Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:
Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.

让每对(ai,bi)中的最小值的和最大,所以要让小的放在一起,大的放在一起,排序之后隔一个一取即可。

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        int summin = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i += 2) {
            summin += nums[i];
        }
        
        return summin;
    }
};

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

思路:

  1. 数组最中间的元素一定为建树后的根结点
  2. 对中间元素的左边、右边,分别递归调用。
class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        if(num.size() == 0) return NULL;

        int middle = num.size() / 2;
        TreeNode* root = new TreeNode(num[middle]);
        
        vector<int> leftInts(num.begin(), num.begin() + middle);
        vector<int> rightInts(num.begin() + middle + 1, num.end());
        
        root->left = sortedArrayToBST(leftInts);
        root->right = sortedArrayToBST(rightInts);
        
        return root;
    }
};

415. Add Strings

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

  1. The length of both num1 and num2 is < 5100.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

思路:数字字符串逐位相加,由于字符串的位数是不确定的,可多可少,所以直接转换成数字是不行的,应该按照位数逐项相加,利用C++的string容器比较方便,首先将所要相加的字串翻转,依次从低位向高位相加,中间需要注意的是进位问题,预留出变量来保存对应位置的进位。代码如下:

class Solution {
public:
	string addStrings(string num1, string num2) {
    	int i = num1.size() - 1;
    	int j = num2.size() - 1;
    	int carry = 0;
    	string res = "";
    	while(i>=0 || j>=0 || carry){
    	    long sum = 0;
    	    if(i >= 0){sum += (num1[i] - '0');i--;}
    	    if(j >= 0){sum += (num2[j] - '0');j--;}
    	    sum += carry; 
    	    carry = sum / 10;
    	    sum = sum % 10;
    	    res =  res + to_string(sum);
    	}
    	reverse(res.begin(), res.end());
    	return res;
	}
};

优化一下循环,leetcode clean code如下:

class Solution {
public:
    string addStrings(string num1, string num2) {
        if (num1.size() < num2.size()) return addStrings(num2, num1); //保证第一个参数是短的数字
        int carry = 0, i = num1.size() - 1, j = num2.size() - 1;
        for (; i >= 0 && (carry || j >= 0); i--, j--, carry /= 10) //从后往前加
            num1[i] = (carry += num1[i] - '0' + (j >= 0 ? num2[j] - '0' : 0)) % 10 + '0';
        return (carry ? "1" : "") + num1;
    }
};