leetcode contest 54 solution

本次题解包括

  • 696. Count Binary Substrings
  • 697. Degree of an Array
  • 698. Partition to K Equal Sum Subsets
  • 699. Falling Squares

696. Count Binary Substrings

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Example 2:

Note:

  • s.length will be between 1 and 50,000.
  • s will only consist of “0” or “1” characters.

题目地址:leetcode Count Binary Substrings

题目大意:给定只由0和1组成的字符串,求有多少个子串满足子串的连续的0和1的个数相等。

思路

我是区分0和1的区间,进行计数。如果当前的是1,cnt1<=cnt0说明可以满足,ans++,当前是0同理。

Python

 

 


 

697. Degree of an Array

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Example 2:

Note:

  • nums.length will be between 1 and 50,000.
  • nums[i] will be an integer between 0 and 49,999.

题目地址:leetcode Degree of an Array

题目大意:一个数组的degree定义为元素出现最多的次数。求最短的字数组,使得子数组的degree等于原数组的degree

思路:

我直接Hash表水了。。

Python

 

 


 

698. Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into knon-empty subsets whose sums are all equal.

Example 1:

Note:

  • 1 <= k <= len(nums) <= 16.
  • 0 < nums[i] < 10000.

题目地址:leetcode Partition to K Equal Sum Subsets

题目大意:给定一个数组nums和数字k,求数组能否被分为k个子数组,使得k个子数组的和相等?

思路:

首先判断是否可以:即总和能被k整除,并且数组中元素的最大值<= sum /k。

然后DFS即可。

Java

 

 


 

699. Falling Squares

On an infinite number line (x-axis), we drop given squares in the order they are given.

The i-th square dropped (positions[i] = (left, side_length)) is a square with the left-most point being positions[i][0] and sidelength positions[i][1].

The square is dropped with the bottom edge parallel to the number line, and from a higher height than all currently landed squares. We wait for each square to stick before dropping the next.

The squares are infinitely sticky on their bottom edge, and will remain fixed to any positive length surface they touch (either the number line or another square). Squares dropped adjacent to each other will not stick together prematurely.

Return a list ans of heights. Each height ans[i] represents the current highest height of any square we have dropped, after dropping squares represented by positions[0], positions[1], ..., positions[i].

Example 1:

After the first drop of positions[0] = [1, 2]:
_aa
_aa
-------
The maximum height of any square is 2.

After the second drop of positions[1] = [2, 3]:
__aaa
_
_aaa
_
_aaa
_
aa__
_aa__
--------------

The maximum height of any square is 5. The larger square stays on top of the smaller square despite where its center of gravity is, because squares are infinitely sticky on their bottom edge.

After the third drop of positions[1] = [6, 1]:
__aaa
_
_aaa
_
_aaa
_
aa
_aa___a
--------------

The maximum height of any square is still 5. Thus, we return an answer of [2, 5, 5].

Example 2:

Note:

  • 1 <= positions.length <= 1000.
  • 1 <= positions[0] <= 10^8.
  • 1 <= positions[1] <= 10^6.

题目地址:leetcode Falling Squares

题目大意:给定一些正方形的起始位置和长度,每次从空中掉落。如果正方形和之前的正方形重合,那么会叠加变高。求每次正方形掉落后的最大高度

思路

一看就是线段树的模板题而已。。

RMQ问题,并且是设置值的RMQ。

C++

Python

 

 

本文是leetcode如下的题解

  • 696. Count Binary Substrings
  • 697. Degree of an Array
  • 698. Partition to K Equal Sum Subsets
  • 699. Falling Squares

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode contest 54 solution
本文地址:https://www.hrwhisper.me/leetcode-contest-54-solution/

听说帅的人已经打赏了

Leetcode , . permalink.

One thought on “leetcode contest 54 solution

  1. 强大的楼主
    求加一个linkedin
    从你的blog里面学到了很多东西
    特别感谢楼主的分享
    希望楼主继续更新下去

Leave a Reply

Your email address will not be published. Required fields are marked *