细语呢喃

技术改变生活

0%

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:

1
2
3
4
5
6
7
Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because <b>all</b> the 0's (and 1's) are not grouped together.

Example 2:

1
2
3
Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

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 

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(object):
    def countBinarySubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s: return 0
        ans = cnt0 = cnt1 = 0
        first = s[0]
        for i, c in enumerate(s):
            if c != first:
                first = c
                if c == '1':
                    cnt1 = 0
                else:
                    cnt0 = 0
            if c == '1':
                cnt1 += 1
                if cnt1 <= cnt0:
                    ans += 1
            else:
                cnt0 += 1
                if cnt0 <= cnt1:
                    ans += 1
        return ans

 

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:

1
2
3
4
5
6
7
Input: [1, 2, 2, 3, 1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

Example 2:

1
2
Input: [1,2,2,3,1,4,2]
Output: 6

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 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def findShortestSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        d = collections.defaultdict(list)
        degree = 0
        for i, num in enumerate(nums):
            d[num].append(i)
            degree = max(degree, len(d[num]))

        ans = len(nums)
        for l in d.values():
            if len(l) == degree:
                ans = min(ans,l[-1] - l[0] + 1)
        return ans

 

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:

1
2
3
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

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 

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
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0, max = Integer.MIN_VALUE;
        for (int num : nums){
            sum += num;
            max = Math.max(max,num);
        }
        int target = sum / k;
        if (sum != target * k  max > target) return false;
        Arrays.sort(nums);
        boolean[] vis = new boolean[nums.length];
        return dfs(0, nums, k, target, vis);
    }

    private boolean dfs(int cur, int[] nums, int k, int target, boolean[] vis) {
        if (cur > target) return false;
        if (cur == target) {
            cur = 0;
            if (--k == 0) return true;
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (vis[i]  cur + nums[i] > target) continue;
            vis[i] = true;
            if (dfs(cur + nums[i], nums, k, target, vis)) return true;
            vis[i] = false;
        }
        return false;
    }
}

 

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:

1
2
3
Input: [[1, 2], [2, 3], [6, 1]]
Output: [2, 5, 5]
Explanation:

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:

1
2
3
Input: [[100, 100], [200, 100]]
Output: [100, 100]
Explanation: Adjacent squares don't get stuck prematurely - only their bottom edge can stick to surfaces.

Note:

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

题目地址：leetcode Falling Squares

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

思路

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

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

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class IntervalTree {
private:
	vector<int> maxv, setv;
	const int n;

	void pushdown(int o) {
		int lc = (o << 1) + 1, rc = lc + 1;
		if (setv[o] >= 0) {
			setv[lc] = setv[rc] = setv[o];
			setv[o] = -1;
		}
	}

	void maintain(int o, int L, int R) {
		int lc = (o << 1) + 1, rc = lc + 1;
		if (L < R) {
			maxv[o] = max(maxv[lc], maxv[rc]);
		}
		if (setv[o] >= 0) { maxv[o] = setv[o]; }
	}

	void update(int o, int L, int R, const int i, const int j, const int v) {
		if (i <= L && R <= j) {
			setv[o] = v;
		}
		else {
			pushdown(o);
			int lc = (o << 1) + 1, rc = lc + 1;
			int mid = L + ((R - L) >> 1);
			if (i <= mid) update(lc, L, mid, i, j, v); else maintain(lc, L, mid);
			if (j > mid) update(rc, mid + 1, R, i, j, v); else maintain(rc, mid + 1, R);
		}
		maintain(o, L, R);
	}

	int query(int o, int L, int R, const int i, const int j) {
		if (setv[o] >= 0) {
			return setv[o];
		}
		else if (i <= L && R <= j) {
			return maxv[o];
		}
		else {
			int _max = 0x80000000;
			int lc = (o << 1) + 1, rc = lc + 1;
			int mid = L + ((R - L) >> 1);
			if (i <= mid) _max = query(lc, L, mid, i, j);
			if (j > mid) _max = max(_max, query(rc, mid + 1, R, i, j));
			return _max;
		}
	}

public:
	IntervalTree(int n) :n(n) {
		maxv = vector<int>(n << 2, 0);
		setv = vector<int>(n << 2, -1);
	}

	int query(const int i, const int j) {
		return query(0, 0, n - 1, i, j);
	}

	void update(const int i, const int j, const int v) {
		update(0, 0, n - 1, i, j, v);
	}
};


class Solution {
public:
	vector<int> fallingSquares(vector<pair<int, int>>& positions) {
		vector<int> points;
		unordered_map<int, int> index;

		for (pair<int, int>& cur : positions) {
			points.push_back(cur.first);
			points.push_back(cur.first + cur.second - 1);
		}
		sort(points.begin(), points.end());
		int n = 0;
		for (int p : points)
			if (index.find(p) == index.end())
				index[p] = n++;

		vector<int> ans;
		IntervalTree tree(n);
		int maxv = 0;
		for (pair<int, int>& cur : positions) {
			int s = index[cur.first], side = cur.second, e = index[cur.first + cur.second - 1];
			int h = tree.query(s, e) + side;
			tree.update(s, e, h);
			ans.push_back(maxv = maxv < h ? h : maxv);
		}
		return ans;
	}
};

Python

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class IntervalTree(object):
    def __init__(self, n):
        self._n = n
        t = 1
        while t < n: t <<= 1
        t <<= 1
        self.maxv = [0] * t
        self.setv = [-1] * t

    def _pushdown(self, o):
        if self.setv[o] != -1:
            lc, rc = (o << 1) + 1, (o << 1) + 2
            self.setv[lc] = self.setv[rc] = self.setv[o]
            self.setv[o] = -1

    def _maintain(self, o, L, R):
        if L < R:
            lc, rc = (o << 1) + 1, (o << 1) + 2
            self.maxv[o] = max(self.maxv[lc], self.maxv[rc])
        if self.setv[o] != -1:
            self.maxv[o] = self.setv[o]

    def _query(self, o, L, R, i, j):
        if self.setv[o] != -1:
            return self.setv[o]

        if i <= L and R <= j:
            return self.maxv[o]

        lc, rc = (o << 1) + 1, (o << 1) + 2
        mid = (L + R) >> 1
        _max = -1
        if i <= mid:
            _max = self._query(lc, L, mid, i, j)
        if j > mid:
            _max = max(_max, self._query(rc, mid + 1, R, i, j))
        return _max

    def _update(self, o, L, R, i, j, v):
        if i <= L and R <= j:
            self.setv[o] = v
        else:
            self._pushdown(o)
            mid = (L + R) >> 1
            if i <= mid:
                self._update((o << 1) + 1, L, mid, i, j, v)
            else:
                self._maintain((o << 1) + 1, L, mid)
            if j > mid:
                self._update((o << 1) + 2, mid + 1, R, i, j, v)
            else:
                self._maintain((o << 1) + 2, mid + 1, R)
        self._maintain(o, L, R)

    def query(self, i, j):
        return self._query(0, 0, self._n - 1, i, j)

    def update(self, i, j, v):
        self._update(0, 0, self._n - 1, i, j, v)

class Solution(object):
    def fallingSquares(self, positions):
        """
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        points = set()
        for x, side in positions:
            points.add(x)
            points.add(x + side - 1)

        index = {x: i for i, x in enumerate(sorted(points))}
        ans = []
        _max = -1
        tree = IntervalTree(len(index))
        for x, side in positions:
            s, e = index[x], index[x + side - 1]
            h = tree.query(s, e) + side
            _max = max(_max, h)
            tree.update(s, e, h)
            ans.append(_max)
        return ans

 

本文是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/

请我喝杯咖啡吧~