[[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哈希