携程笔试20240905

## 1

思路：前k-1位从1到k-1，剩下的倒序。

## 2
不需要修改字符串，记录修改次数，看每位修改这么多次后是否能为1，不是就增加修改次数
```java
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = 5;
    String s = "01010";
    int ans = 0;
    for(int len = 1; len <= s.length(); len+=2){
        for(int j = len;j <= s.length();j++){
            //len+1-len=1,len+1=2  1,2   0,1
            String substr = s.substring(j-len,j);
            int val = getVal(substr);
            if(val % 2 == 1)ans++;
        }
    }
    System.out.println(ans);
}

public static int getVal(String s){
    int ans = 0;
    //从后往前遍历，记录修改次数
for(int i = s.length()-1; i >= 0;i--){
        if(s.charAt(i) == '0'){
            if(ans % 2 == 0) {
                ans++;
            }
        }else{
            if(ans % 2 == 1){
                ans++;
            }
        }
    }
    return ans;
}
```

## 3

回溯，首位为0要特判

## 4

暴力过25%