[leetcode] [KMP] KMP

ABCDABD...

ABCDABF...

簡單的說, 傳統解兩字串匹配部分

可能會來個雙迴圈, 哀個比對, 當不匹配的時候, 會將下方列再後移1位

然後不匹配再後移

然而

如果像上放已經有4個屬於匹配的字串, 她就應該直接往後移四位來匹配, 而不是只移動1位

隱藏的思維是, 當已知匹配的, 就已知完全不能匹配的部分, 而這部分應該合理的跳過

而當它既是前墜又是後墜的時候, 可能前面就都相同可以跳過

直接開始比開始不同的地方

後贅數組定義, 是整個kmp算法根基

dp[i]: the max length k s.t. s[0:k-1] = s[i-k+1:i]

[x x x] x [x x i]

中心思想, 是得到一個next數組 類似[-1, -1, 0, 1]

當該數位置對應的數字找不到匹配時, 可往前跳向下標位置再進行比對

(網路上有不同解法有跳往下標, 或是前一個下標, 會反應在j的初始值-1或是0)

public static boolean repeatedSubstringPattern(String s) {

    if(s.equals(""))return false;

    int len = s.length();
    int[] temp = new int[len];
    int[] next=getNext(temp,s, len);
    // 比對表最後一欄位置不為-1 且 長度能被最大重複組除盡
    if (next[len-1] != -1 && len % (len - (next[len-1]+1)) == 0) {
        return true;
    }

    return false;
}

public static int[] getNext(int[]next, String s, int len){
    // 1 初始化賦予-1值
    next[0] = -1;
    int j = -1;
    char[] chars = s.toCharArray();

    for(int i = 1; i<len; i++){
        // 2 前後綴不相等時, 往前跳到指定位置再進行下迴圈(比對)
        while(j>=0&&chars[i]!=chars[j+1]){
            j = next[j];
        }
        // 3 前後綴相等, j++, 並將值放到next表中
        if(chars[i]==chars[j+1]){
            j++;
        }
        next[i]=j;
    }
    return next;
}

參考: https://www.youtube.com/watch?v=t6xa2p6fFS8&t=918s

[leetcode] [eazy] Q1002

public class Q1002 {
    public static void main(String[] args) {
        String[] words = {"bella","label","roller"};
        commonChars(words);
    }
    public static List<String> commonChars(String[] words) {
        List<String>ans = new ArrayList<>();
        int[] count = new int[26];
        Arrays.fill(count, Integer.MAX_VALUE);
        for(String str: words){
            int []cnt = new int[26];
            str.chars().forEach(c->++cnt[c-'a']);
            for(int i= 0; i<26; i++){
                count[i] = Math.min(cnt[i], count[i]);
            }
        }
        for(char c='a'; c<='z';c++){
            while(count[c-'a']-->0){
                ans.add("" + c);
            }
        }
        return ans;
    }
}

1 Arrays.fill方法沒用過, 可以用來產生空陣列

2 統計文出現次數可以用int[]count = new int[26]]

3 str.chars().forEach(c->++cnt[c-'a'])

可以用來把cnt陣列中出現的文母次數做一個統計

4 for(char c=='a';c<='z';c++){

while(count[c-'a']-->0){

ans.add(""+c);

}

}

能將陣列中出現的字母, 在轉換放進List答案中

eazy這麼難...

 

在分支上測試時遇到dev已經更新太多

 在分支上測試時遇到dev已經更新太多

可能會導致專案已經跑不起來

不得不在分支上會需要dev更新的部分

本來預計就直接把分支併回dev做測試

而今天學到一個方法

就是在分支上pull

將dev pull近來

這樣就能解決dev已經更新很多的問題

網關 gateway

關於網關的存在，是為了解決目前遇到的問題

解決綁定絕對路徑綁死同一機台問題

如上圖為絕對路徑，在微服務架構下， 可能一個服務有多台(多實例)，他服務對接並不適合綁定某一機台，應讓不同的實例都能處理此請求才是

如上圖在中間增設網關，這樣在前端的代碼中只需要指定每個接口的相對路徑， 

在前端代碼的一個固定的地方在接口地址前統一加網關的地址，每個請求統一到網關，由網關將請求轉發到具體的微服務。

有了網關就可以對請求進行路由，路由到具體的微服務，減少外界對接微服務的成本，比如：400電話，路由的試可以根據請求路徑進行路由、根據host地址進行路由等， 當微服務有多個實例時可以通過負載均衡算法進行路由

同時，這個結構也解決前端需要寫死API-URL的問題, 由網關來解決對應URL問題即可

以spring cloud gateway結構 流程如下：

1、微服務啟動，將自己注冊到Nacos，Nacos記錄了各微服務實例的地址。

2、網關從Nacos讀取服務列表，包括服務名稱、服務地址等。

3、請求到達網關，網關將請求路由到具體的微服務。

LeetCode策略

目前順序:

數組-> 鏈表-> 哈希表->字符串->棧與隊列->樹->回溯->貪心->動態規劃->圖論->高級數據結構

參考: https://github.com/youngyangyang04/leetcode-master/blob/master/README.md

規劃: 

1 刷1題

2 隔天再刷同一題, 並寫當題的bigO, 將答案和思路貼到專案中

3 完成第二種解法

4 重寫第二種解法, 寫第二種bigO, 並將答案和思路貼到專案中, 並在excel表紀錄

excel表紀錄參考: https://www.youtube.com/watch?v=NdWYxz3izH4&t=5s

每周寫篇日誌做些調整

2024新年新目標

工程師目前, 大約是四年半

想說立一些今年要達成的目標, 來給自己完成

長久的目標

1 進入外企寫程式

2 英文母語化

3 成為程式資深開發者

4 減肥or使身材更優, 體力更好, 睡眠正常, 頭髮長回來, 美顏

5 年薪突破140, 資產突破300

以往目標或許太遠或是太抽象, 就開始散漫過開心生活去, 天天玩那種

稍微讓目標具體點

我希望今年能完成

1 兩個月做一個專案 包含redis, Elasticsearch, kafka

2 leetcode 一個月 easy 8題 medium 4題

3 一周健身3次, 跑步3次

4 擦皮膚保養品

5 每天10:00洗澡, 11:30準備睡覺, 早上6:30起床

6 平日5天讀英文?!

大概是說關於devops, 上雲相關明年再來專注弄, 今年開始練code, 部分技術

設計模式是真的頗容易忘, 現在有點不知道怎辦, 想說弄幾個專案起來後面再看看

畢竟code刷不過, 面試後面連談的機會都沒有

那, 每次寫完一題, 就寫一點點的解題思路作筆記, 讓自己日後複習能快點

看起來6:30起床, 運動到7:00, 洗澡到7:20, 讀英文到8:20的話, 兩年就會很有進步

他目前的實力並不足以支持他的野心

JSR-303 Bean Validation

 在以往Bean Validation通常會在service的function寫上好長一段判斷如下

//合法性校驗
  if (StringUtils.isBlank(dto.getName())) {
   throw new XueChengPlusException("課程名稱為空");
  }

  if (StringUtils.isBlank(dto.getMt())) {
   throw new XueChengPlusException("課程分類為空");
  }

  if (StringUtils.isBlank(dto.getSt())) {
   throw new XueChengPlusException("課程分類為空");
  }

  if (StringUtils.isBlank(dto.getGrade())) {
   throw new XueChengPlusException("課程等級為空");
  }

然而當欄位多起來的時候，code看起來就會變得冗長

且如果不同的function都要來一段這個，這些也有許多重複的程式碼其實也有改進空間

而在JavaEE6規範中就定義了參數校驗的規範

它就是JSR-303，它定義了Bean Validation，即對bean屬性進行校驗

SpringBoot提供了JSR-303的支持，它就是spring-boot-starter-validation，它的底層使用Hibernate Validator，Hibernate Validator是Bean Validation 的參考實現。

所以，我們準備在Controller層使用spring-boot-starter-validation完成對請求參數的基本合法性進行校驗。

以下的組合是可以讓不同的controller使用不同組的校驗文字

我們在專案中的exception包定出GlobalExceptionHandler和ValidationGroups

GlobalExceptionHandler

@Slf4j
@ControllerAdvice
public class GlobalExceptionHandler {
    @ResponseBody
    @ExceptionHandler(XueChengPlusException.class)
    @ResponseStatus(HttpStatus.INTERNAL_SERVER_ERROR)
    public RestErrorResponse customException(XueChengPlusException e) {
        log.error("【系統異常】{}",e.getErrMessage(),e);
        return new RestErrorResponse(e.getErrMessage());

    }

    @ResponseBody
    @ExceptionHandler(Exception.class)
    @ResponseStatus(HttpStatus.INTERNAL_SERVER_ERROR)
    public RestErrorResponse exception(Exception e) {

        log.error("【系統異常】{}",e.getMessage(),e);

        return new RestErrorResponse(CommonError.UNKOWN_ERROR.getErrMessage());

    }

    @ResponseBody
    @ExceptionHandler(MethodArgumentNotValidException.class)
    @ResponseStatus(HttpStatus.INTERNAL_SERVER_ERROR)
    public RestErrorResponse methodArgumentNotValidException(MethodArgumentNotValidException e) {

        BindingResult bindingResult = e.getBindingResult();
        List msgList = new ArrayList<>();
        bindingResult.getFieldErrors().stream().forEach(item->{
            msgList.add(item.getDefaultMessage());
        });
        String msg = StringUtils.join(msgList, ",");
        log.error("【系統異常】{}",msg);
        return new RestErrorResponse(msg);

    }
}

ValidationGroups

public class ValidationGroups {
    public interface Insert{};
    public interface Update{};
    public interface Delete{};
}

目前將ValidationGroups分成新增, 更新, 刪除三個類別

在bean上設置的檢核訊息如下

@Data
@ApiModel(value="AddCourseDto", description="新增課程基本信息")
public class AddCourseDto {

 @NotEmpty(groups = {ValidationGroups.Insert.class},message = "新增課程名稱不能為空")
 @NotEmpty(groups = {ValidationGroups.Update.class},message = "修改課程名稱不能為空")
 @ApiModelProperty(value = "課程名稱", required = true)
 private String name;
 ...
 }

然後使用上, 我們在controller就可以這樣寫, 比方說我們此類為新增 就使用Insert @Validated({ValidationGroups.Insert.class})

    @ApiOperation("新增課程基礎信息")
    @PostMapping("/course")
    public CourseBaseInfoDto createCourseBase(@RequestBody @Validated({ValidationGroups.Insert.class}) AddCourseDto addCourseDto){
        //獲取到用戶所屬機構id
        Long companyId = 1232141425L;
        return courseBaseInfoService.createCourseBase(companyId,addCourseDto);
    }