[[5.27+5.28]刷题：字符串操作

[5.27+28] 字符串操作

一、[leetcode:6] z字形变换

（6. Z 字形变换 - 力扣（LeetCode） (leetcode-cn.com)）

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

[[5.27+5.28]刷题：字符串操作

题解一：直接用list来模拟

最开始想的是放入String，但是发现不知道怎么加，然后换成了Character，代码有点长

class Solution {
    public String convert(String s, int numRows) {
         if(numRows < 2) return s;
          List<List<Character>> temp = new ArrayList<>();
        for(int i=0;i<numRows;i++){
            temp.add(new ArrayList<Character>());
        }
        int index = 0;
        int flag = 1;
        for (int i = 0; i < s.length(); i++) {
            if (index == 0) flag = 1;
            if (flag == 1) {
                temp.get(index).add(s.charAt(i));
                index++;
            }
            else if (flag == 0) {
                temp.get(index).add(s.charAt(i));
                index--;
            }
            if (index == numRows-1) flag = 0;
        }
        //System.out.println(temp.toString());
        StringBuilder result=new StringBuilder();
        for(int i=0;i<numRows;i++){
            for(int j=0;j<temp.get(i).size();j++){
                result.append(temp.get(i).get(j));
            }
        }
        return result.toString();
    }
}

通过查看其它人的代码发现里面直接放StringBuider就可以，于是改进了一下，并且发现我的判断写的可太复杂了，可以改变一下

class Solution {
    public String convert(String s, int numRows) {
        if(numRows < 2) return s;
        List<List<Character>> temp = new ArrayList<>();
        for(int i=0;i<numRows;i++){
            temp.add(new ArrayList<Character>());
        }
        int index = 0;
        int flag = -1;
        for (int i = 0; i < s.length(); i++) {
            temp.get(index).add(s.charAt(i));
            if(index == 0 || index == numRows -1) flag = - flag;
            index += flag;
        }
        System.out.println(temp.toString());
        StringBuilder result=new StringBuilder();
        for(int i=0;i<numRows;i++){
            for(int j=0;j<temp.get(i).size();j++){
                result.append(temp.get(i).get(j));
            }
        }
        return result.toString();
    }
}

二、[leetcode:14] 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串
""

[[5.27+5.28]刷题：字符串操作

解法一：横向比较，比较每两个的公共的字串

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }
    public String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }
}

解法二：纵向比较

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

三、[leetcode:763] 划分字母区间

(763. 划分字母区间 - 力扣（LeetCode） (leetcode-cn.com))

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

[[5.27+5.28]刷题：字符串操作

题解一：贪心

每次都找都最后的位置，然后进行分配

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        int length = s.length();
        for (int i = 0; i < length; i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        List<Integer> partition = new ArrayList<Integer>();
        int start = 0, end = 0;
        for (int i = 0; i < length; i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                partition.add(end - start + 1);
                start = end + 1;
            }
        }
        return partition;
    }
}

牛客模拟笔试(百度2020校招Java研发工程师笔试卷（第三批）)

知识点：

一、线程池(资源来源)

(

通过 Executor 框架的工具类 Executors 来实现：（三类）

FixedThreadPool ：该方法返回一个固定线程数量的线程池。该线程池中的线程数量始终不变。当有一个新的任务提交时，线程池中若有空闲线程，则立即执行。若没有，则新的任务会被暂存在一个任务队列中，待有线程空闲时，便处理在任务队列中的任务。
SingleThreadExecutor：方法返回一个只有一个线程的线程池。若多余一个任务被提交到该线程池，任务会被保存在一个任务队列中，待线程空闲，按先入先出的顺序执行队列中的任务。
CachedThreadPool：该方法返回一个可根据实际情况调整线程数量的线程池。线程池的线程数量不确定，但若有空闲线程可以复用，则会优先使用可复用的线程。若所有线程均在工作，又有新的任务提交，则会创建新的线程处理任务。所有线程在当前任务执行完毕后，将返回线程池进行复用。

3、线程池的原理：

[[5.27+5.28]刷题：字符串操作

四、线程池的拒绝策略（饱和策略）（四种）

如果当前同时运行的线程数量达到最大线程数量并且队列也已经被放满了任时，

ThreadPoolTaskExecutor

定义一些策略:

ThreadPoolExecutor.AbortPolicy ：抛出 RejectedExecutionException 来拒绝新任务的处理。线程池默认拒绝策略；
ThreadPoolExecutor.CallerRunsPolicy ：调用执行自己的线程运行任务，也就是直接在调用 execute 方法的线程中运行( run )被拒绝的任务，如果执行程序已关闭，则会丢弃该任务。因此这种策略会降低对于新任务提交速度，影响程序的整体性能。如果您的应用程序可以承受此延迟并且你要求任何一个任务请求都要被执行的话，你可以选择这个策略。由调用的线程处理该任务，谁调用谁的线程处理。
ThreadPoolExecutor.DiscardPolicy ：不处理新任务，直接丢弃掉。不抛出异常；
ThreadPoolExecutor.DiscardOldestPolicy ：此策略将丢弃最早的未处理的任务请求。丢弃队列最前面的任务，然后重新提交被拒绝的任务；

二、贪心算法

老板给度度熊n个数，每一次从中取出一个最大的减去[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传，其他的n-1个数加上1，一直重复直到最大数小于n的执行次数记为k。

老板想知道最少执行多少次操作使得个数都小于n呢？

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        long[] nums=new long[N];
        long sum=0;
        for (int i = 0; i < N; i++) {
            nums[i]=s.nextLong();
        }
        while(!valiable(nums,N)){
            long max=0;
            int index=0;
            for (int i = 0; i < nums.length; i++) {
                if(max<nums[i]){
                    max=nums[i];
                    index=i;
                }
            }
            sum+=max/N;
            for (int i = 0; i <N ; i++) {
                nums[i]+=max/N;
            }
            nums[index]=max%N;
        }
        System.out.println(sum);
    }
    public static boolean valiable(long[] nums,int target){
        for(long i:nums){
            if(i>=target) return false;
        }
        return true;
    }
}

三、关于图的路径的长度的一个dfs

[[5.27+5.28]刷题：字符串操作

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main{
    static int max=0;
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int N=s.nextInt();
        int[] nums=new int[N+1];
        for (int i = 1; i < N+1; i++) {
            nums[i]=s.nextInt();
        }
        List<Integer>[] graph=new ArrayList[N+1];
        for(int i=0;i<graph.length;i++){
            graph[i]=new ArrayList<>();
        }
        for (int i = 0; i <N-1 ; i++) {
            int l=s.nextInt();
            int r=s.nextInt();
            graph[l].add(r);
            graph[r].add(l);
        }
        for (int i = 1; i <N ; i++) {
            dfs(graph,nums,i,0);
        }
        System.out.println(max);
 
    }
    public static void dfs(List<Integer>[] graph,int[] nums,int now,int len){
        len+=1;
        max=Math.max(max,len);
        List<Integer> nexts=graph[now];
        for (int next:nexts ) {
            if(nums[next]>nums[now]){
                dfs(graph,nums,next,len);
            }
        }
    }
}

[[5.27+5.28]刷题：字符串操作

[5.27+28] 字符串操作

一、[leetcode:6] z字形变换

题解一：直接用list来模拟

二、[leetcode:14] 最长公共前缀

解法一：横向比较，比较每两个的公共的字串

解法二：纵向比较

三、[leetcode:763] 划分字母区间

题解一：贪心

牛客模拟笔试(百度2020校招Java研发工程师笔试卷（第三批）)

知识点：

一、线程池(资源来源)

二、贪心算法

三、关于图的路径的长度的一个dfs

继续阅读

Codeforces 1417 D. Make Them Equal(思维+构造)

查找算法之二分查找查找算法之二分查找

查找算法学习之二分查找（Python版本）——BinarySearch

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

hdu7108哈希