代码编织梦想

我在哪?

在这里插入图片描述

二分查找以及字符串哈希,mid之后的答案都是合法的,此题寻找的是最小的K值,所以check的话 如果mid是true的话,那就把r变为mid,反之 l=mid+1,这题就是寻找最小长度下不重复的字符串,所以不等于1的时候就返回FALSE;


import java.util.*;

public class Main {
    static int n;
    static  String s;
    public static boolean check (int mid ){
        Map<String,Integer> map = new HashMap<>();
        int max=0;
        for(int i=0;i<=n-mid;i++) {
            String t = s.substring(i, mid + i);
            if(map.get(t)==null)map.put(t,1);
            else map.put(t,map.get(t)+1);
             max = Math.max(max,map.get(t));
            if(max!=1)return false;
        }
        return true;
    }

    public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            n=sc.nextInt();
            s=sc.next();
            int l =0,r=n;
            while(l<r){
                int mid = l+((r-l)>>1);
                if(check(mid))r=mid;
                else l=mid+1;

            }
        System.out.println(l);
        }
}

AcWing 3768. 字符串删减

在这里插入图片描述


import java.util.Scanner;

public class Main {
    static final int N = 110;
    static char[] s = new char[N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        s = in.next().toCharArray();
        int res = 0;
        for (int i = 0; i < n; i ++){
            if (s[i] != 'x') continue;
            int j = i + 1;
            while (j < n && s[j] == 'x') j ++;
            res += Math.max(j-i-2, 0);
            i = j;
        }
        System.out.println(res);
    }
}


截断数组

在这里插入图片描述

因为要把数组均分三份,总和一定得是3的倍数
遍历前缀和数组,边扫描边记录哪些地方可以切第一刀,哪些地方可以切第二刀。如果位置j可以切第二刀,那么它与前面第一刀进行组合,就可以切成三部分。

import java.util.*;
public class Main{
    static int N = 100010;
    static int n, m;
    static long res;
    static int[] a = new int[N];
    static int[] s = new int[N];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);

        n = scan.nextInt();
        for (int i = 1; i <= n; i ++) a[i] = scan.nextInt();
        for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];

        if (s[n] % 3 != 0 || n < 3)
        {
            System.out.println(0);
            return;
        }

        int dex = s[n] / 3;
        for (int i = 1; i < n; i ++)
        {
//不能调换这两个if判断的原因是,如果当前tot等于perSum和perSum*2时(比如0特判等),就会出现在同一位自加
        //一旦出现自加,那么可以理解为中间那个截断元素个数为0,这是不可能的
            if (s[i] == dex * 2) res += m;
            if (s[i] == dex) ++ m;
        }

        System.out.println(res);
    }
}

砖块

在这里插入图片描述

这道题为模拟。
从第一个点开始,例如想要把它全部改为黑色:
遍历从1~n的每个点,如果这个点是白色,那么把它和它后面那个反转颜色。
若遍历完后最后一个点仍然不匹配,那么全部改为黑色就是一种不可行的方案。白色同理。
如果黑色不匹配的话还可以用白色,若白色也不匹配则无解。

import java.util.*;

public class Main{

    static int n;

    public static void update(char[] s, int i){
        if (s[i] == 'B') s[i] = 'W';
        else s[i] = 'B';
    }

    public static boolean check(char[] s, char c){
        int[] res = new int[3 * n];
        char[] tem = new char[n];
        for (int i = 0; i < n; i ++) tem[i] = s[i];
        int k = 0;

        for (int i = 0; i + 1 < n; i ++){
            if (tem[i] != c){
                update(tem, i);
                update(tem, i+1);
                res[k ++] = i;
            }
        }
        if (tem[n-1] != tem[0]) return false;
        System.out.println(k);
        //砖块编号是从1开始的所以需要加一
        for (int i = 0; i < k; i ++) System.out.print((res[i]+1) + " ");
        if (k != 0) System.out.println();

        return true;
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T -- > 0){
            n = scan.nextInt();
            char[] s = scan.next().toCharArray();

            if (!check(s, 'W') && !check(s, 'B')) System.out.println(-1);
        }
    }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/crisp0530/article/details/129479927

算法刷题日志10.20_crisp制药的博客-爱代码爱编程

文章目录 二叉树的层序遍历翻转二叉树对称二叉树求正数数组的最小不可组成和星际密码 二叉树的层序遍历 用dfs搜,只不过这个dfs要添加个leave用来表示当前所在的层数 class

算法刷题日志10.21_crisp制药的博客-爱代码爱编程

平衡二叉树 递归的方式判断,因为是判断高度,因此我们需要从底至上进行判断。左右子树如果高度差大于1则说明不平衡。 class Solution { public boolean isBalanced(

算法刷题日志——二叉树_crisp制药的博客-爱代码爱编程

文章目录 合并二叉树二叉搜索树中的搜索[ 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/)二叉搜索树的最小绝对差

算法刷题日志——二叉树_crisp制药的博客-爱代码爱编程

文章目录 删除二叉搜索树中的节点修剪二叉搜索树将有序数组转换为二叉搜索树](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tre

算法刷题日志——回溯算法_crisp制药的博客-爱代码爱编程

文章目录 组合总和[组合总和 II](https://leetcode.cn/problems/combination-sum-ii/)[ 组合总和 III](https://leetcode.cn/problems

算法刷题日志——贪心_crisp制药的博客-爱代码爱编程

文章目录 跳跃游戏[跳跃游戏 II](https://leetcode.cn/problems/jump-game-ii/description/)用最少数量的箭引爆气球 跳跃游戏 如果某一个作

算法刷题日志——dp-爱代码爱编程

文章目录 最长递增子序列 最长公共子序列 最长递增子序列 dp[i] 的值代表 nums 以 nums[i] 结尾的最长子序列长度。 class Solution { pub

什么是输入和输出?-爱代码爱编程

本文首发自「慕课网」,想了解更多IT干货内容,程序员圈内热闻,欢迎关注! 作者| 慕课网精英讲师 ColorfulC 本篇文章将会介绍基本输入输出的 Java 标准类,你将了解到什么是输入和输入,什么是流;输入输出流的应用场景,File类的使用,什么是文件,Java 提供的输入输出流相关 API 等内容。 1. 什么是输入和输出(I / O) 1.

【数据结构】哈希表-爱代码爱编程

文章目录 哈希表的定义常见的哈希结构setmap leetcode242.有效的字母异位词leetcode383.赎金信leetcode349.两个数组的交集leetcode350.两个数组的交集Ⅱleetcod

【leetcode每日一题】——783.二叉搜索树节点最小距离-爱代码爱编程

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【解题思路】七【题目提示】八【题目注意】九【时间频度】十【代码实现】十一【提交结果】 一【题目类别】 深度优先搜索 二【题目

扩展欧几里得算法及其应用-爱代码爱编程

前言 由于数论的板子真的很抽象,也很难背,所以特此记录扩展欧几里得算法的板子和它的用途 本篇文章只涉及应用,不涉及证明,如需理解证明还请各位移步其他优秀的讲解! 扩展欧几里得算法  先粘一下板子的代码 typedef long long LL ; LL exgcd(LL a, LL b, LL &x, LL &am

图论学习(一)-爱代码爱编程

图的定义 一个图G定义为一个有序对(V,E),记为G=(V,E),其中 V是一个非空集合,称为顶点集或点集,其元素称为顶点或点。E是由V中的点组成的无序点对构成的集合,称为边集,其元素称为边,且同一点对在E中可出现多次。

【c语言】指针的深度理解(一)-爱代码爱编程

前言  我们已经了解了指针的概念,一是指针变量是用来存放地址的,每个地址都对应着唯一的内存空间。二是指针的大小是固定的4或8个字节(取决于操作系统,32位的占4个字节,64位的占8个字节)。三是指针是有类型的,不同的类型决定了指针的访问权限,同时决定了指针加减整数的步长。 字符指针 形式 我们将形如 char* 的指针称为字符指针

蓝桥杯之二分-爱代码爱编程

蓝桥杯之二分 区间移位扫地机器人 但是左端点的更新也要自己找规律,扫地机器人是根据当前遍历到的机器人的位置和左端点L的位置的前后不同更新L,区间移位是根据L和当前遍历到的区间最大能移到L的左边还是右边,以及

代码随想录动态规划 || 198 213 337-爱代码爱编程

Day41 198.打家劫舍 力扣题目链接 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 示例

推荐系统-基于领域的协同过滤算法选择(一文足矣)-爱代码爱编程

1、基于用户的协同过滤算法(UserCF) 1.1、 基本思想 该算法主要用于计算两个用户之间的相似度,这里的相似度指的是两个用户之间的兴趣相似度。假设存在用户u和用户v,N(u)和N(v)分别是他们曾经有过正反馈的物品

移动通信(16)信号检测_信号检测csdn-爱代码爱编程

常见的信号检测算法一般包括以下几类检测算法:最优、线性和非线性。 最优检测算法:最大似然算法 线性检测算法:迫零检测算法和最小均方误差检测算法 非线性检测算法:串行干扰消除检测算法 球形译码检测算法属于一种次优检测算法(运算量远小于最大似然检测算法) 作为一种性能接近ML的次优算法,球形译码(SD)可以大大降低检测的复杂度。简单来

一篇文章教你彻底理解threadlocal_threadlocal存放数据-爱代码爱编程

文章目录 ThreadLocal是什么?ThreadLocal如何使用?特别注意 ThreadLocal数据存储存取 ThreadLocal原理解析Thread.threadLocals原理