首页 > itarticle > topcoder – lineoff

topcoder – lineoff

admin 11月 12, 2020 0

Problem Statement

You are given a set of colored points on a straight line.

You play a game with these points. The game is a sequence of moves. In each move you have to erase two points that are adjacent and share the same color. (Two points are adjacent if there is no other point between them. Distances don’t matter.)

You are given the String points. Each character of points describes the color of one point, in the order in which they are arranged on the line at the beginning of the game. (Different letters represent different colors.) Compute and return the maximum number of moves you can make.

Definition

Class: LineOff
Method: movesToDo
Parameters: String
Returns: int
Method signature: int movesToDo(String points)
(be sure your method is public)

Constraints

  • points will contain between 1 and 50 characters, inclusive.
  • Each character in points will be a lowercase English letter (‘a’-‘z’).

Examples

  1. “abba”
    Returns: 2
    The only valid first move is to erase the two points of color ‘b’. After that move the points of color ‘a’ are now adjacent and they can be removed in our second move.

  2. “zwwwzffw”
    Returns: 2
    You can remove two ‘w’ points and two ‘f’ points with your first two moves. After that the remaining points on the line will be arranged as follows: “zwzw”. In this situation you don’t have any adjacent points that share the same color, so there are no more moves.

  3. “rrrrrrr”
    Returns: 3
    With an odd number of points, at least one of them will have no pair.

  4. “dfghj”
    Returns: 0
    All colors are different so no points can be removed.

  5. “wasitacarooracatisaw”
    Returns: 10

Analysis

  1. Consider this problem as an Online Problem, the letters arrive online one after another from left to right. An optimal solution can be maintained by a “Stack” structure, in which we stock the current optimal remained letters. Because whenever a new letter arrives, it could only impact the last letter.

C++ Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
using namespace std;
 
class LineOff {
public:
    int (string);
};
 
int LineOff::movesToDo(string points) {
    int ans = 0;
    stack<char> s;
    for (auto c : points) {
    if (!s.empty() && c == s.top()) {
        s.pop();
        ans++;
    } else {
        s.push(c);
    }
  }
  return ans;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能