current position:Home>[algorithm learning] 1221 Split balanced string (Java / C / C + + / Python / go / trust)
[algorithm learning] 1221 Split balanced string (Java / C / C + + / Python / go / trust)
2022-01-30 16:27:26 【White hat of the second leader】
- This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund .
Thank you very much for reading this article ~ welcome 【 give the thumbs-up 】【 Collection 】【 Comment on 】~ It's not hard to give up , But persistence must be cool ~ I hope all of us can make a little progress every day ~ This paper is written by The white hat of the second leader https://juejin.cn/user/2771185768884824/posts Original blog ~
1221. Split balanced string :
In a Balanced string in ,'L' and 'R' The number of characters is the same .
Give you a balanced string s, Please split it into as many balanced strings as possible .
Be careful : Each split string must be a balanced string , And the balanced string obtained by segmentation is a continuous substring of the original balanced string .
Returns a balanced string that can be split The largest number .
Examples 1
Input :
s = "RLRRLLRLRL"
Output :
4
explain :
s Can be divided into "RL"、"RRLL"、"RL"、"RL" , Each substring contains the same number of 'L' and 'R' .
Copy code
Examples 2
Input :
s = "RLLLLRRRLR"
Output :
3
explain :
s Can be divided into "RL"、"LLLRRR"、"LR" , Each substring contains the same number of 'L' and 'R' .
Copy code
Examples 3
Input :
s = "LLLLRRRR"
Output :
1
explain :
s Just keep it as it is "LLLLRRRR".
Copy code
Examples 4
Input :
s = "RLRRRLLRLL"
Output :
2
explain :
s Can be divided into "RL"、"RRRLLRLL" , Each substring contains the same number of 'L' and 'R' .
Copy code
Tips
- 1 <= s.length <= 1000
- s[i] = 'L' or 'R'
- s It's a Balance character string
analysis
- This algorithm problem if you say s If it is not a balanced string, it will be a little difficult .
- because s Itself is a balanced string , So you can use greed from left to right , The shorter it is, the more it can be divided , And the rest of the string is also a balanced string .
- We need to record the traversal process ‘L’ and ‘R’ The number of , If equal, it is a balanced string .
- Record separately ‘L’ and ‘R’ Quantity required 2 A variable , But we can record their difference , The difference is 0 It means that the quantity is equal , That is, the balanced string , In this way, only one variable is needed to record .
Answer key
java
class Solution {
public int balancedStringSplit(String s) {
int ans = 0;
// Record the difference between left and right , Left subtraction , Right plus , by 0 The left and right numbers are the same
int v = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == 'L') {
--v;
} else {
++v;
}
if (v == 0) {
++ans;
}
}
return ans;
}
}
Copy code
c
int balancedStringSplit(char * s){
int ans = 0;
// Record the difference between left and right , Left subtraction , Right plus , by 0 The left and right numbers are the same
int v = 0;
while (*s) {
*s == 'L' ? --v : ++v;
if (v == 0) {
++ans;
}
++s;
}
return ans;
}
Copy code
c++
class Solution {
public:
int balancedStringSplit(string s) {
int ans = 0;
// Record the difference between left and right , Left subtraction , Right plus , by 0 The left and right numbers are the same
int v = 0;
for (char c : s) {
c == 'L' ? --v : ++v;
if (v == 0) {
++ans;
}
}
return ans;
}
};
Copy code
python
class Solution:
def balancedStringSplit(self, s: str) -> int:
ans = 0
# Record the difference between left and right , Left subtraction , Right plus , by 0 The left and right numbers are the same
v = 0
for c in s:
if c == 'L':
v -= 1
else:
v += 1
if v == 0:
ans += 1
return ans
Copy code
go
func balancedStringSplit(s string) int {
ans := 0
// Record the difference between left and right , Left subtraction , Right plus , by 0 The left and right numbers are the same
v := 0
for _, c := range s {
if c == 'L' {
v--
} else {
v++
}
if v == 0 {
ans++
}
}
return ans
}
Copy code
rust
impl Solution {
pub fn balanced_string_split(s: String) -> i32 {
s.chars().scan(0, |v, c| {
match c {
'L' => *v -= 1,
_ => *v += 1
};
Some(*v)
}).filter(|v| { *v == 0 }).count() as i32
}
}
Copy code
Original title transmission gate :https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/
Welcome to discuss in the comment area , Nuggets officials will be in Digging force Star Program After the event , Draw... In the comment area 100 Around the Nuggets , For details of the lucky draw, see the activity article
copyright notice
author[White hat of the second leader],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201301627246581.html
The sidebar is recommended
- Python notes (6): definition and use of lists
- Python notes (V): string operation
- Python notes (IV): use of functions and modules
- Python notes (3): conditional statements and circular statements
- Python notes (II): lexical structure
- Notes on python (I): getting to know Python
- [Python data structure series] - tree and binary tree - basic knowledge - knowledge point explanation + code implementation
- [Python daily homework] Day7: how to combine two dictionaries in an expression?
- How to implement a custom list or dictionary in Python
- 15 advanced Python tips for experienced programmers
guess what you like
-
Python string method tutorial - how to use the find() and replace() functions on Python strings
-
Python computer network basics
-
Python crawler series: crawling global airport information
-
Python crawler series: crawling global port information
-
How to calculate unique values using pandas groupby
-
Application of built-in distribution of Monte Carlo simulation SciPy with Python
-
Gradient lifting method and its implementation in Python
-
Pandas: how to group and calculate by index
-
Can you create an empty pandas data frame and fill it in?
-
Python basic exercises teaching! can't? (practice makes perfect)
Random recommended
- Exploratory data analysis (EDA) in Python using SQL and Seaborn (SNS).
- Turn audio into shareable video with Python and ffmpeg
- Using rbind in python (equivalent to R)
- Pandas: how to create an empty data frame with column names
- Talk about quantifying investment using Python
- Python, image restoration in opencv - CV2 inpaint
- Python notes (14): advanced technologies such as object-oriented programming
- Python notes (13): operations such as object-oriented programming
- Python notes (12): inheritance such as object-oriented programming
- Chapter 2: Fundamentals of python-5 Boolean
- Python notes (11): encapsulation such as object-oriented programming
- Python notes (10): concepts such as object-oriented programming
- Gradient lifting method and its implementation in Python
- Van * Python | simple crawling of a site course
- Chapter 1 preliminary knowledge of pandas (list derivation and conditional assignment, anonymous function and map method, zip object and enumerate method, NP basis)
- Nanny tutorial! Build VIM into an IDE (Python)
- Fourier transform of Python OpenCV image processing, lesson 52
- Introduction to python (III) network request and analysis
- China Merchants Bank credit card number recognition project (Part I), python OpenCV image processing journey, Part 53
- Introduction to python (IV) dynamic web page analysis and capture
- Python practice - capture 58 rental information and store it in MySQL database
- leetcode 119. Pascal's Triangle II(python)
- leetcode 31. Next Permutation(python)
- [algorithm learning] 807 Maintain the city skyline (Java / C / C + + / Python / go / trust)
- The rich woman's best friend asked me to write her a Taobao double 11 rush purchase script in Python, which can only be arranged
- Glom module of Python data analysis module (1)
- Python crawler actual combat, requests module, python realizes the full set of skin to capture the glory of the king
- Summarize some common mistakes of novices in Python development
- Python libraries you may not know
- [Python crawler] detailed explanation of selenium from introduction to actual combat [2]
- This is what you should do to quickly create a list in Python
- On the 55th day of the journey, python opencv perspective transformation front knowledge contour coordinate points
- Python OpenCV image area contour mark, which can be used to frame various small notes
- How to set up an asgi Django application with Postgres, nginx and uvicorn on Ubuntu 20.04
- Initial Python tuple
- Introduction to Python urllib module
- Advanced Python Basics: from functions to advanced magic methods
- Python Foundation: data structure summary
- Python Basics: from variables to exception handling
- Python notes (22): time module and calendar module