ຄະແນນສູງສຸດຫຼັງຈາກທີ່ແບ່ງປັນວິທີແກ້ໄຂແບບ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ກູໂກ
string

ຄະແນນສູງສຸດຂອງບັນຫາຫລັງຈາກແຍກເປັນກ string Leetcode Solution ໄດ້ໃຫ້ພວກເຮົາດ້ວຍເຊືອກ. ສະຕິງທີ່ໃຫ້ໄວ້ມີພຽງແຕ່ 0 ແລະ 1. ດັ່ງນັ້ນຄົນ ໜຶ່ງ ຍັງສາມາດພິຈາລະນາມັນເປັນ ລຳ ດັບຄູ່. ບັນຫາຫຼັງຈາກນັ້ນໄດ້ຮ້ອງຂໍໃຫ້ພວກເຮົາຊອກຫາຄະແນນສູງສຸດທີ່ສາມາດບັນລຸໄດ້ຫຼັງຈາກແຍກສາຍ. ຫລັງຈາກແຍກສາຍ, ຄະແນນຈະຖືກປະເມີນເປັນເລກ 0 ໃນສ່ວນເບື້ອງຊ້າຍແລະເລກ 1 ໃນເຄິ່ງຂວາ. ສະນັ້ນຕາມປົກກະຕິ, ກ່ອນທີ່ຈະ ດຳ ນ້ ຳ ໃນການແກ້ໄຂ. ຂໍໃຫ້ເຮົາພິຈາລະນາບາງຕົວຢ່າງ.

s = "011101"
5

ຄໍາອະທິບາຍ: ຄົນເຮົາສາມາດເຫັນໄດ້ວ່າຄະແນນສູງສຸດທີ່ເຮົາສາມາດບັນລຸໄດ້ຖ້າເຮົາແຍກສາຍຫຼັງຈາກດັດສະນີທໍາອິດ. ວິທີນັ້ນພວກເຮົາມີ 1 0s ໃນເຄິ່ງຂວາແລະ XNUMX ດຽວໃນເຄິ່ງຊ້າຍ.

ຄະແນນສູງສຸດຫຼັງຈາກທີ່ແບ່ງປັນວິທີແກ້ໄຂແບບ Leetcode

s = "00111"
5

ຄຳ ອະທິບາຍ: ຄົນເຮົາສາມາດຄິດອອກໄດ້ຢ່າງງ່າຍດາຍວ່າຖ້າພວກເຮົາແຍກສາຍເຊັ່່ນທີ່ເບື້ອງຊ້າຍມີທັງ ໝົດ 0s ແລະອີກເຄິ່ງ ໜຶ່ງ ບັນຈຸ 1s ທັງ ໝົດ ວິທີນັ້ນພວກເຮົາຈະໄດ້ຮັບຄະແນນສູງສຸດ. ດັ່ງນັ້ນ, ມັນງ່າຍທີ່ຈະເຫັນວ່າຈຸດຂອງການແບ່ງປັນຄວນຢູ່ໃນດັດຊະນີ 2.

ວິທີການເພື່ອໃຫ້ໄດ້ຄະແນນສູງສຸດຫຼັງຈາກທີ່ແບ່ງປັນວິທີແກ້ໄຂ Leetcode

ຄະແນນສູງສຸດທີ່ມີປັນຫາພາຍຫຼັງທີ່ແຍກໂຊ Stet Leetcode Solution ໄດ້ກ່າວມາຂ້າງເທິງແລ້ວໃນ ຄຳ ອະທິບາຍບັນຫາ. ສະຫລຸບໂດຍຫຍໍ້, ບັນຫາໄດ້ຂໍໃຫ້ພວກເຮົາຊອກຫາຄະແນນສູງສຸດທີ່ສາມາດບັນລຸໄດ້ຖ້າພວກເຮົາແບ່ງສາຍເຊືອກອອກເປັນສອງສ່ວນ. ຄະແນນຈະຖືກປະເມີນຕາມ ຈຳ ນວນ 0 ໃນເຄິ່ງຊ້າຍແລະ 1 ໃນເຄິ່ງສິດ. ດັ່ງນັ້ນ, ທຳ ອິດ, ພວກເຮົາຄິດໄລ່ ຈຳ ນວນເລກສູນແລະຕົວເລກທັງ ໝົດ ໃນສາຍທີ່ຖືກລະບຸ. ໃນຮອບທີສອງ, ພວກເຮົາສືບຕໍ່ຄິດໄລ່ເລກ 0f 0 ທີ່ພົບມາຮອດປະຈຸບັນ.

ພວກເຮົາ ກຳ ລັງໃຊ້ວົງຈອນນີ້ເພື່ອ ຈຳ ລອງຂັ້ນຕອນຂອງການແບ່ງສາຍ. ພວກເຮົາເກັບຮັກສາສູນແລະຄົນທີ່ປະສົບມາຮອດປະຈຸບັນ. ຜູ້ທີ່ຢູ່ໃນເຄິ່ງຂວາສາມາດຄິດໄລ່ໄດ້ງ່າຍໂດຍການຫັກເລກ 1 ໃນເຄິ່ງຊ້າຍ. ພວກເຮົາສືບຕໍ່ປັບປຸງ ຄຳ ຕອບດ້ວຍມູນຄ່າສູງສຸດທີ່ສາມາດບັນລຸໄດ້.

ລະຫັດ ສຳ ລັບຄະແນນສູງສຸດຫຼັງຈາກທີ່ແບ່ງປັນວິທີແກ້ໄຂ Leetcode

ລະຫັດ C ++

#include <bits/stdc++.h>
using namespace std;

int maxScore(string s) {
    int zero = 0, one = 0;
    for(int i=0;i<s.size();i++)
        (s[i] == '0') ? zero++ : one++;
    int curZero = (s[0] == '0'), curOne = (s[0] == '1');
    int ans = curZero + one - curOne;
    for(int i=1;i<s.size()-1;i++){
        (s[i] == '0') ? curZero++ : curOne++;
        ans = max(ans, curZero + one - curOne);
    }
    return ans;
}

int main(){
    cout<<maxScore("00111");
}
5

ລະຫັດ Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int maxScore(String s) {
        int one = 0, zero = 0;
        for(int i=0;i<s.length();i++)
            if(s.charAt(i) == '0')
                zero++;
            else
                one++;
        int curZero = (s.charAt(0) == '0' ? 1 : 0), curOne = (s.charAt(0) == '1' ? 1 : 0);
        int ans = curZero + one - curOne;
        for(int i=1;i<s.length()-1;i++){
            if(s.charAt(i) == '0')curZero++;
            else curOne++;
            ans = Math.max(ans, curZero + one-curOne);
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    System.out.print(maxScore("00111"));
  }
}
5

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (N), ເຖິງແມ່ນວ່າວິທີການດັ່ງກ່າວແມ່ນຜ່ານໄປສອງຄັ້ງ, ຄວາມສັບສົນຂອງເວລາກໍ່ຍັງຄົງເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (1), ເນື່ອງຈາກວ່າພື້ນທີ່ຄົງທີ່ຖືກ ນຳ ໃຊ້ໃນສູດການຄິດໄລ່.