Jianzhi offer 43.47.46.48 dynamic planning (medium)

Always right " Dynamic programming " Have a superficial knowledge of , This time, , Hope you can understand , I want to find some popular explanations .(20 A private letter / 80 Bar message ) How to understand dynamic programming ？ - You know (zhihu.com)https://www.zhihu.com/question/39948290/answer/883302989

This is very simple , I am a preschooler who can get To . Then we started to do the problem .

42. subject

The finger of the sword Offer 42. The maximum sum of successive subarrays https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

idea :

1. Violence optimization , A two-tier cycle : Fix the right end first , Let's assume the left end , Get the values of each sub array in turn , And we get max.

2.DP Fix the left end , Calculate the maximum value of the subarray at this time for each beginning .

        f(i)=max( f(i-1)+a(i) , a(i) ) When the former f(i-1)<0 The latter is the opposite , a(i) Current value .

Code :

// Violence law optimization , Time complexity O(n2), Overtime .
class Solution {
    public int maxSubArray(int[] nums) {
        int max=Integer.MIN_VALUE;
        for(int i=nums.length-1;i>=0;i--){
            int sum=0;
            for(int j=i;j>=0;j--){
                sum+=nums[j];
                if(sum>max)
                    max=sum;
            }
        }
        return max;
    }
}
//DP Law ,
class Solution {
    public int maxSubArray(int[] nums) {
        int max=nums[0];
        int sum=nums[0];
        for(int i=1;i<nums.length;i++){
            sum=sum>0?sum+nums[i]:nums[i];
            if(sum>max)
                max=sum;
        }
        return max;
    }
}

result :

 

47. subject :

The finger of the sword Offer 47. The greatest value of gifts https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/

 

idea : The value of reaching each point and It's on the left / The higher value and Add the current point value It can be traversed in turn

Code :

class Solution {
    public int maxValue(int[][] grid) {
        int m=grid.length;// Row number 
        int n=grid[0].length;// Number of columns 
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0)
                    continue;
                else if(i==0)
                    grid[i][j]+=grid[i][j-1];
                else if(j==0)
                    grid[i][j]+=grid[i-1][j];
                else 
                    grid[i][j]+=Math.max(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }
}

result :

46. subject :

The finger of the sword Offer 46. Translate numbers into strings

Idea one : First, convert numbers into character arrays , Every backward movement of a number , Calculate the number of different translation methods of the current substring , add The number of mantissa of the previous substring .( Note that only translatable two digit numbers are 10-25)

Code 1 :

class Solution {
    public int translateNum(int num) {
        char[] nums=(num+"").toCharArray();
        int tail=nums[0]-48;// Record the last mantissa 
        int count=1;// Record the number of different translation methods 
        int countTail=1;// Record the number of mantissa 
        for (int i = 1; i < nums.length; i++) {
            int tmp=count;// Number of single mantissa   It is the number of translation methods counted last time 
            if(tail==1||(tail==2 && nums[i]-48<=5)){
                // If mantissa is 1  You can add 0-9
                // If mantissa is 2  You can only add 0-5
                count+=countTail;
            }
            countTail=tmp;// Record the number of single mantissa of this statistics 
            tail=nums[i]-48;// Record the mantissa of this statistics 
        }
        return count;
    }
}

Idea 2 : Reference resources jyd( Method 1 )
link ：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/mian-shi-ti-46-ba-shu-zi-fan-yi-cheng-zi-fu-chua-6/

Code 2 :

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1;//a=f(0)=1,b=f(1)=1
        for(int i = 2; i <= s.length(); i++) {
            String tmp = s.substring(i - 2, i);// When i=2 when , The substring is shown in the following table 0-1 String 
            // When two digits are translatable ,f(i)=f(i-1)+f(i-2)
            // When two digits are untranslatable ,f(i)=f(i-1)
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : b;
            // Pointer backward 
            a = b;
            b = c;
        }
        return b;
    }
}

result :

 

48. subject :

The finger of the sword Offer 48. The longest substring without repeating characters

 

  idea : Use a hash table to store characters and corresponding subscripts , Traverse in turn , If the character does not exist , The current longest substring length tmp+1, If there is , Then judge tmp and i-j( Length of new substring after de duplication ) Who is big , Make tmp+1 or tmp=i-j; Then take each... In the loop tmp The maximum value of .

Code :

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int res = 0, tmp = 0;
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);// Take out the characters in turn 
            int j=map.getOrDefault(c,-1);// If it exists in the hash table , Returns the subscript in the character array , Otherwise return to -1
            map.put(c,i);// Store the characters and corresponding subscripts in the hash table 
            if(j==-1){// non-existent 
                tmp+=1;// This can be omitted , because j=-1 when , Let's judge tmp<i+1( This is certain because tmp It's the length of the string ,i Is the total length of the current string )
            }else{
                tmp = tmp < i - j ? tmp + 1 : i - j; // dp[j - 1]  deduction  dp[j]
            }
             res = Math.max(res, tmp);// max(dp[j - 1], dp[j])
        }
        return res;
    }
}

result :