Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

describe

There is a room with n bulbs, numbered from 0 to n – 1, arranged in a row from left to right. Initially, all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the ith bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

  • Choose any bulb (index i) of your current configuration.
  • Flip each bulb from index i to index n – 1.

When any bulb is flipped it means that if it is ‘0’ it changes to ‘1’ and if it is ‘1’ it changes to ‘0’.

Return the minimum number of flips required to form target.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.
Copy the code

Example 2:

Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".
Copy the code

Example 3:

Input: target = "00000"
Output: 0
Copy the code

Example 4:

Input: target = "001011101"
Output: 5
Copy the code

Note:

1 <= target.length <= 10^5
target[i] is either '0' or '1'.
Copy the code

parsing

In the room, there is a row of light bulbs arranged from left to right. The switches are only on and off, denoted by 1 and 0. The index of these switches is 0 to N-1. We can perform an operation that requires us to press the bulbs with indexes I through N-1 once. Given the array target of a switch, how many times does it take to make the switch look like target?

In fact, this problem looks very difficult, I could not do it at first, but after reading daishen’s solution idea, I found it is really simple, it is a problem to find a rule:

  • When the initial value is 1, for example, target is 10, the change process is 00->11->10
  • If the start value is 0, for example, target is 01. The change process is 00->01
  • For example, if target is 100 at the beginning of 1, the change process is: 000->111->100
  • For example, if target is 101 at the beginning of 1, the change process is 000->111->100->101
  • When the start value is 0, for example, target is 010. The change process is 000->011->010

There’s a clear pattern:

  • We initialize result to 0 when the first letter of target is 0 and 1 when the first letter of target is 1
  • If the current character does not equal the previous character, result increments by one
  • Result is returned at the end of traversal

answer

class Solution(object): def minFlips(self, target): """ :type target: str :rtype: int """ if target[0] == '0': result = 0 elif target[0] == '1': result = 1 for i in range(1, len(target)): if target[i]! =target[i-1]: result += 1 return resultCopy the code

The results

Given in the Python online submission for Bulb Switcher IV. Memory Usage: Submissions for Python online submissions for Bulb Switcher IV.Copy the code

Original link: leetcode.com/problems/bu…

Your support is my biggest motivation