Leetcode Contest 37

2017-06-18

第一题Maximum Distance in Arrays

给定一个包含数组的数组，每个数组都已经递增排序。我们要做的是从两个数组中各选一个数，使得这两个数的差的绝对值最大。问这个最大的值是多少？

对于第i数组中，取出最大值a，最小值b，然后将(a, i)和(b, i)放进一个数组m里。将数组m按照第一个分量排序，那么对我们有用的只是数组m前面两个元素和后面两个元素。如果第一个元素和最后一个元素来自不一样的数组（第二个分量不一样），那么答案就是这两个元素的第一个分量的差。否则，我们要比较两种情况：第一个元素与倒数第二个元素，第二个元素与最后一个元素。

class Solution(object):
    def maxDistance(self, arrays):
        """
        :type arrays: List[List[int]]
        :rtype: int
        """
        m = []
        for i, a in enumerate(arrays):
            m.append((a[0], i))
            m.append((a[-1], i))
        m.sort(key=lambda x: x[0])
        if m[0][1]!=m[-1][1]:
            return m[-1][0]-m[0][0]
        return max(m[-2][0]-m[0][0], m[-1][0]-m[1][0])

Leetcode Contest 35

2017-06-03

第一题Can Place Flowers

给定一个01数组代表一排花盆，0代表是可以种花，1代表不可以。种花的时候我们要确保左右两边的花盆是空的。问能不能种n株花。

简单的贪心。

class Solution(object):
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """
        cnt = 0
        for i in xrange(len(flowerbed)):
            if flowerbed[i] == 1:
                continue
            if i-1>=0 and flowerbed[i-1]==1:
                continue
            if i+1<len(flowerbed) and flowerbed[i+1]==1:
                continue
            flowerbed[i] = 1
            cnt += 1
        return cnt>=n

Leetcode Contest 33

2017-05-20

就着Gin的酒劲，我还能一次不WA的过了这次比赛哈哈。

第一题Longest Harmonious Subsequence

给定一个数组，找出长度最长的子数组，使得其最大值与最小值恰好相差1，返回最大长度。

既然最大值与最小值恰好相差1，那么此子数组必定恰好有两个不一样的元素。我们只要统计每个元素出现的次数，然后枚举找出相邻两个元素出现次数之和的最大值就好。

class Solution(object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cnt = {}
        for n in nums:
            cnt[n] = cnt.get(n, 0) + 1
        ans = 0
        for k, v in cnt.items():
            if k-1 in cnt:
                ans = max(ans, v+cnt[k-1])
            if k+1 in cnt:
                ans = max(ans, v+cnt[k+1])
        return ans

Leetcode Contest 32

2017-05-13

比赛链接

第一题Shortest Unsorted Continuous Subarray

给定一个数组，求其中最短的连续子数组长度，使得对该子数组排序就能完成对整个数组的排序。

首先将数组排好序，然后看排好的数组与原来的数组之间的差异。

class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sn = sorted(nums)
        i = 0
        while i < len(nums) and nums[i] == sn[i]:
            i += 1
        if i == len(nums):
            return 0
        j = len(nums) - 1
        while j >= 0 and nums[j] == sn[j]:
            j -= 1
        return j-i+1

编写Hexo插件让主页显示特定的文章

2017-05-11

今年三月份我在hostgator买的虚拟主机到期了，衡量几番二月就从wordpress迁到了Hexo。从这三个月左右的使用来看，Hexo让我挺满意的。一方面，它简洁且容易使用；另一方面它又给予用户很大的修改空间。奇怪的是，网上几乎没有编写Hexo插件的教程，以至于最近我折腾了好久才能写出可用的插件来让Hexo生成我预期的网页效果。这篇文章记录我编写Hexo插件的方法，希望对后来者有帮助。

首先描述一下我想要做的事情。最近一直参加Leetcode上面的比赛，而且每次参加之后都会写篇文章记录自己的做法，所以主页就被这些文章占领了。我希望主页只显示最新一篇关于Leetcode的文章。同时，我希望能有一个类似主页的页面，该页面是要列出所有关于Leetcode比赛的文章。总结说一下，我要做的事情是：

(I) 让主页只显示特定文章（或者说过滤掉特定文章）。

(II) 建立一个页面只显示特定文章。

Leetcode Contest 31

2017-05-06

这次比赛简单。

第一题Distribute Candies

给定一个长度为偶数的数组，将所有数分成长度一样的两堆，求其中一堆不一样数字最多的数目。

class Solution(object):
    def distributeCandies(self, candies):
        """
        :type candies: List[int]
        :rtype: int
        """
        kind = set()
        for c in candies:
            kind.add(c)
        n = len(candies)/2
        if (n<=len(kind)):
            return n
        else:
            return len(kind)

Leetcode Contest 30

2017-04-29

今晚参加了一个朋友的婚前庆祝party。看着朋友幸福也是一种幸福的享受。希望我的幸福来得更早一些 😆

今晚的比赛也一次没WA地过了。前面三题是用 C++ 写的，最后一题实在觉得 C++ 麻烦，还是换了用python写。

第一题Reshape the Matrix

题目大意：给定一个矩阵，将其变成r行c列的矩阵。如果不能转换，则返回原矩阵。

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
        int n = nums.size();
        if (n==0) return nums;
        int m = nums[0].size();
        if (m==0) return nums;
        if (n*m != r*c) return nums;
        vector<vector<int>> ans(r, vector<int>(c, 0));
        int a = 0, b = 0;
        for (auto row: nums)
            for (auto n: row) {
                ans[a][b] = n;
                b ++;
                if (b == c) {
                    b = 0;
                    a ++;
                }
            }
        return ans;
    }
};

Leetcode Contest 29

2017-04-22

今晚有鱼、豆腐和西芹。

这次比赛是久违的全一次就AC了，开心😎

第一题Binary Tree Tilt

题目大意：对于一个二叉树节点，定义它的tilt为左子树之和与右子树之和差的绝对值。给定一棵二叉树，求出所有节点tilt值之和。

感觉是简单的dfs套路。对于每个节点，递归算左右子树之和，那么它的tilt值就很容易求出来加到一个全局的变量里，然后返回当前子树之和：左子树+右子树+根节点

# 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 findTilt(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        ans = [0]

        def dfs(root):
            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            ans[0] += abs(left-right)
            return left+right+root.val

        dfs(root)
        return ans[0]

Leetcode Contest 28

2017-04-15

今晚吃的是烤鱼以及手撕鸡。

这次的比赛让我开始怀疑自己的智商了。

第一题Student Attendance Record I

题目大意：给定一个表示只含A、L和P的字符串，问字符串是否满足以下条件：不含多于1个的A或者不含有长度大于2的连续L子字符串。

简单的字符串处理。

class Solution(object):
    def checkRecord(self, s):
        """
        :type s: str
        :rtype: bool
        """
        a = 0
        for c in s:
            if c == 'A':
                a += 1
        if a > 1:
            return False
        if s.find('LLL') != -1:
            return False
        return True

Leetcode Contest 27

2017-04-08

今晚肉特别多：红烧羊肉，焖排骨，手撕鸡和罗非鱼。

第一题Reverse Words in a String III

题目大意：给定一个句子，将其中所有单词逆序。

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        lst = s.split(' ')
        for i in xrange(len(lst)):
            if lst[i] == '':
                continue
            lst[i] = ''.join(reversed(lst[i]))
        return ' '.join(lst)

Previous 1 ... 6 7 8 9 10 11 Next