javaブラシ問題-ダイナミック企画

1.word-break
ソースリンク:www.nowcoder.com
テーマ記述:Given a string s and a dictionary of words dict,determine if s can be segmented into a space-separated sequence     保存先 one or more dictionary words.
For example,givens =「leetcode」,dict =［leet］「code」.
Return true because“leet code”can be segmented as“leet code”.

public boolean wordBreak(String s, Set dict) {
        int len = s.length();
        boolean[]  flag = new boolean[len+1];
        flag[0] = true;
        for (int i = 1; i <=len; i++) {
            for (int j = 0; j < i; j++) {
                if (flag[j]&&dict.contains(s.substring(j,i))){
                    flag[i] = true;
                }
            }
        }
        return flag[len];
    }

2.word-break-i
ソースリンク:www.nowcoder.com
テーマの説明:
Given a string s and a dictionary of words dict,add spaces in s トconstruct a sentence where each word is a valid dictionaryword.Return all such possible sentence.
For example,givens =「cat sandog」、dict =［cat］、「cats」、「and」、「sand」、「dog」.
A solution is[cats and dog],[cat sand dog]

import java.util.ArrayList;
import java.util.Set;

public class Solution {

    ArrayList list = new ArrayList<>();

     public ArrayList wordBreak(String s, Set dict) {
        dfs(s,s.length(),"",dict);
         return list;
    }
    
    private void dfs(String s,int index,String str,Set set){
        if (index<=0){
            if (str.length()>0){
                list.add(str.substring(0,str.length()-1));
            }
        }
        for (int i = index; i >=0 ; i--) {
            if (set.contains(s.substring(i,index))){
                dfs(s,i,s.substring(i,index)+" "+str,set);
            }
        }
    }
}

3.キャンディーを配る
先生が子供たちに飴を配ってあげたいですが、Nがあります. 子供一人が直線に立っています.先生は子供一人によって採点しておきます.
あなたは以下の要求に従って、先生がこれらの子供に飴を配ってくれるように手伝います.隣の子供の中で、採点の高い子供はもっと多くの飴をもらわなければなりません.このようにして、先生は少なくともいくつの飴を用意しなければなりませんか?
リンク:https://leetcode-cn.com/problems/candy
例 1:

  : [1,0,2]
  : 5
  :               2、1、2    。

    public class Solution {
        
        public int candy(int[] ratings) {
            int n = ratings.length;
            int[] candys = new int[n];
            //           ratings[i]>ratings[i-1]                 
            for (int i = 1; i < n; i++) {
                if (ratings[i]>ratings[i-1]){
                    candys[i] = candys[i-1]+1;
                }
            }
            /**
             *                                 ratings[i]< ratings[i-1]   
             *            ratings[i] > ratings[i+1] && candys[i]<=candys[i+1]
             */
            
            for (int i = n-2; i >=0; i--) {
                if (ratings[i]>ratings[i+1]&&candys[i]<=candys[i+1]){
                    candys[i]=candys[i+1]+1;
                }
            }
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum += candys[i];
            }
            //          
            return sum+n;
        }
    }
    

4.分割エコー-ii
文字列sを指定して、sをいくつかのサブストリングに分割して、各サブストリングがすべて回文列になります.必要に応じた最小分割回数を返します.例:
入力: 「ab」出力:1説明:一回分割すればいいです. sは「a」「b」のような二つの回文部分列に分割されます.リンク:https://leetcode-cn.com/problems/palindrome-partitioning-ii  

public class Solution {
public int minCut(String s) {
        if (s.length() <2) return 0;
        int len = s.length();
        int[] dp = new int[len];    //      
        for (int i = 1; i < len; i++) {
            //        ，       dp[i]=0，         dp[i]=1
            dp[i] = ispld(s.substring(0,i+1))?0:i;
            if (dp[i]!=0){
                /** s.substring(0,i+1)    
                 *   dp[i] = i ，      
                 *                 j->i+1
                 *     0<=j<=i        
                 */
                for (int j = i; j >0 ; j--) {
                    if (ispld(s.substring(j,i+1))){
                        //    ：0-i+1       dp[j-1]  j->i+1     1：  j->i+1         dp[i] = dp[j-1]+1
                        dp[i] = Math.min(dp[i],dp[j-1]+1);
                    }
                }
            }
        }
 
        return dp[s.length()-1];
    }
 
    //          
    private static boolean ispld(String s){
        int len = s.length();
        for (int i = 0; i < len/2; i++) {
            if (s.charAt(i)!=s.charAt(len-i-1)){
                return false;
            }
        }
        return true;
    }
 
}