Day 52 - tree problem

The tree problem is more difficult than expected , Especially the problems involving string and dynamic programming , I feel that it is difficult to understand just the solution to the problem , In addition, I feel uneasy recently because I haven't heard anything about my own affairs due to the transfer of other colleagues , Efficiency is reduced . From tomorrow on, you should put your mind right , Improve learning efficiency , Don't affect your progress , After all, there is still a long way to go , It's also very difficult , I feel like I have entered the binary tree since I began to brush the questions , Start building websites , The whole difficulty has been greatly improved , It is no longer just a fragmented time that can be easily completed , It takes more time to concentrate , It's also easier to feel frustrated and tired , But tiredness is tiredness , Still don't want to give up .

Today's progress ：
1. Insist on brushing questions , Listen to the online class tomorrow , Although the problem is stuck , Still try to keep the progress , Can also start nginx The environment of
2. Insist to take exercise
3. Keep recording the little prince
4. Keep records

Learning notes ：
1.93. Restore IP Address
It works IP Address It's just four integers （ Each integer is located in 0 To 255 Between the composition of , And it can't contain leading 0）, Use... Between integers ‘.’ Separate .

for example ：“0.1.2.201” and “192.168.1.1” yes It works IP Address , however “0.011.255.245”、“192.168.1.312” and “[email protected]” yes Invalid IP Address .
Given a string containing only numbers s , It is used to indicate a IP Address , Returns all possible valid IP Address , These addresses can be accessed through s Insert ‘.’ To form . you You can't Reorder or delete s Any number in . You can press whatever Return the answers in order .

Input ：s = “25525511135”
Output ：[“255.255.11.135”,“255.255.111.35”]

Their thinking ： Use dfs Iterate over what happens to each combination of numbers , take IP The address is divided into four segments , Explore every possibility , If in 0-255 Within the scope of , Just add the result string , Otherwise, continue with the next recursion , If not obtained 4 individual IP Address , End the traversal ahead of time , encounter 0,0 It must be a IP Address .

class Solution {
    
    final static int IP_COUNT=4;
    List<String> res = new ArrayList<String>();
    int[] segments = new int[IP_COUNT];
    public List<String> restoreIpAddresses(String s) {
    
        dfs(s, 0, 0);
        return res;        
    }
    public void dfs(String s, int segId, int segStart){
    
        // End of traversal , get 4 individual IP Address 
        if(segId==IP_COUNT){
    
            if(segStart==s.length()){
    
                StringBuffer ipAddr = new StringBuffer();
                for(int i=0; i<IP_COUNT; i++){
    
                    ipAddr.append(segments[i]);
                    if(i!=IP_COUNT-1){
    
                        ipAddr.append(".");
                    }
                }
                res.add(ipAddr.toString());
            }
            return;
        }
        // Not obtained 4 individual IP Address , End traversal ahead of time 
        if(segStart==s.length()){
    
            return;
        }
        // encounter 0,0 It must be a IP Address 
        if(s.charAt(segStart)=='0'){
    
            segments[segId] = 0;
            dfs(s, segId+1, segStart+1);
        }
        // General situation , Go through everything 
        int addr = 0;
        for(int segEnd=segStart; segEnd<s.length(); segEnd++){
    
            addr = addr*10 + (s.charAt(segEnd)-'0');
            if(0<addr && addr<=255){
    
                segments[segId] = addr;
                dfs(s, segId+1, segEnd+1);
            }
            else{
    
                break;
            }
        }
    }
}

After this , In fact, I am even more disappointed with the company , Although I have long realized that the so-called department change is just a delaying plan for my parents not to let me change my job , There is still a big gap between the really ideal work content and the environment , Of course, there are greater requirements for strength , Don't settle for the status quo , We must work hard to refuel , Keep going tomorrow ！