LeetCode刷题--思路总结记录

LeetCode刷题--思路总结记录
23-11-08每日一题：2609.最长平衡子字符串
- 链接：2609.最长平衡子字符串
- 总体思路：
  - 平衡字符串要求“字符串前半段的0和后半段的1个数相同” ==> 分别记录0和1的计数结果，并最终取二者的最小值×2
  - 字符串必须0开头，1结束 ==> 忽略s一开头的1
  - 一个字符串记录后，怎么从上个字符串结尾的1，切换到下个字符串开头的0？
- 按普通样例“0100111”走==> 碰到’0’就给count0++，碰到‘1’就给count1++ ==> 当碰到0前面有1，就刷新一次res，并重计算count0和count1
  - ① 由于可能字符串1开头，得忽略 ==> 故“ 碰到‘1’就给count1++”就得修改成，碰到‘1’且count0≠0时
  - ② 若刷新的条件是以“碰到0前面有1”的角度，那么对于“01000111”最大的平衡字符串中“000111”之后没有0作结尾，就没法更新结果了（即只有当“0001110”时才能更新出正确答案），或者更新结果得比较繁琐 ==> 于是思考刷新的条件应修改为“1后面是0” ==> 同时由于1可能是大字符串最后一个字符，所以得并上“i+1==s.size()” ==> 故最终完善的刷新条件是 “1后面是0”或者“(i+1)=大字符串长度”
```
class Solution {
public:
   int findTheLongestBalancedSubstring(string s) {
       int count1=0,count0=0,res=0;
       for(int i=0;i
```
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 学习官方类似思路 ==> 更清晰
  - 官方刷新条件是采用“碰到0前面有1”
    - 反思：没有我当初以为会繁琐，其实和“1后面碰到0更新”一样，只是其他条件也要跟着做相对的变化
    - a. 将上方中的“(i+1)=大字符串长度”，考虑作“i为0”即可；
    - b. 将s[i] == '1'作为if最初层的条件就好
  - ① n=s.size()：把将s.size()提前提出，会快一点，不然for循环里每次都得算一遍，就慢
  - ② 每碰到“1”就更新一下res，这样即使“1”在大字符串末尾，也不担心会因为没满足“碰到0前面有1” 这个刷新条件，而错过刷新了
  - ③ 切换子字符串 – 单独拎出刷新count0和count1的情况：走到这步的前提是s[i]='0'，所以else if(i==0 || s[i-1]=='1') 表明的是
    - a. 要么s[i]='0' & i==0：'0’作为大字符串开头
    - b. 要么s[i]='0' & s[i-1]=='1'：'0’作为新子字符串开头
  - 比较自己和官方的思路：
    - 我是在切换子字符（即刷新count0和count1）时，一起更新结果 ==> 需要多考虑1在末尾的情况，而且期间有把自己绕晕的倾向
    - 官方思路是每次有1时，更新结果 ==> 无需考虑1在末尾的情况，但切换子字符串的逻辑要单独拎出来
```
class Solution {
public:
    int findTheLongestBalancedSubstring(string s) {
        int count0=0,count1=0,res=0,n=s.size()//①
        for(int i=0;i
```
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
热题100
- 链接：283. 移动零 - 力扣（LeetCode）
- 思路：left始终指向第一个0 ==> right不断向右遍历，当right指向0右侧第一个非0元素时，就交换left和right，并且两者都向右移动一位 ==> 如此right仅遍历即可实现题目要求
```
class Solution {
public:
    void moveZeroes(vector& nums) {
        int left = 0,n=nums.size();
        
		if(nums==null) { //①
			return;
		}
		
        for(int right=0;right
```

优化：
- ① 提前判断数组是否为空，直接返回
- ② 由于本题中确认是将0推到数组末尾，所以也可以将“交换”的措施，替换为采用“0”末尾覆盖的策略

23-11-08每日一题：2609.最长平衡子字符串

热题100