Problem solving-->Online OJ (18)

1.把数组排成最小的数(offer45)

class Solution {
    
  public static String minNumber(int[] nums) {
    
        String[] arr=new String[nums.length];
        for(int i=0;i<nums.length;i++){
    
            arr[i]=nums[i]+"";
        }
        Arrays.sort(arr,(o1,o2)->(o1+o2).compareTo(o2+o1));
        StringBuilder stringBuilder=new StringBuilder();
        for(String s:arr){
    
            stringBuilder.append(s);
        }
        return stringBuilder.toString();
    }
}

2.把数字翻译成字符串

Dynamic programming solves this problem

class Solution {
    
 public  static int translateNum(int num) {
    
        String s=num+"";
        char[] arr=s.toCharArray();
        int[] dp=new int[arr.length];
        dp[0]=1;
        int i=1;
        for(;i<arr.length;i++){
    
            dp[i]=dp[i-1];
            int ret=10*(arr[i-1]-'0')+(arr[i]-'0');
            if(ret>9 && ret<=25){
    
                if(i==1){
    
                    dp[i]=dp[i]+1;
                }else{
    
                    dp[i]=dp[i]+dp[i-2];
                }
            }
        }
        return dp[i-1];
    }
}

3.礼物的最大价值

Dynamic programming solves this problem

class Solution {
    
   public  static int maxValue(int[][] grid) {
    
        int[][] dp=new int[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
    
            for(int j=0;j<grid[0].length;j++){
    
                if(i==0 && j==0){
    
                    dp[i][j]=grid[0][0];
                }else if(i==0 && j!=0){
    
                    dp[i][j]=grid[i][j]+dp[i][j-1];
                }else if(j==0 && i!=0){
    
                    dp[i][j]=grid[i][j]+dp[i-1][j];
                }else{
    
                    dp[i][j]=grid[i][j]+Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}

4.把字符串转换成整数

class Solution {
    
    public  static int strToInt(String str) {
    
        List<Character> list=new ArrayList<>();
        //如果字符串为空,直接返回 0
        if(str.length()==0){
    
            return 0;
        }
        //去除字符串str前面的空格
        str=str.trim();
        //去除空格之后,再次判断 Whether the string at this time is empty,如果为空,返回 0
        if(str==""){
    
            return 0;
        }
        //将字符串转成字符数组
        char[] temp=str.toCharArray();
        //If at this time in the character array,只有 + 或者 -,直接返回 0
        if(temp.length==1 && (temp[0]=='+'||temp[0]=='-')){
    
             return 0;
        }
        StringBuilder stringBuilder=new StringBuilder();
        //When the character array length is greater than 1的时候,Determines whether the first character of a character array is +/-/数字. If not these three,直接返回0即可
        if(temp[0]=='+' ||temp[0]=='-' || (temp[0]>='0'&&temp[0]<='9')){
    
            list.add(temp[0]);
            stringBuilder.append(temp[0]);
        }else{
    
            return 0;
        }
        //遍历字符数组,The traversed characters must be numbers,如果不是数字,就结束for循环
        for(int i=1;i<temp.length;i++){
    
            if(temp[i]>='0'&&temp[i]<='9'){
    
                list.add(temp[i]);
                stringBuilder.append(temp[i]);
            }else {
    
                break;
            }
            //当stringBuilderincrease when it is large enough,超过了Integermaximum or minimum value,就直接返回Integer的最大值或者最小值
            Long result=Long.parseLong(stringBuilder.toString());
            if(result<=Integer.MIN_VALUE){
    
                return Integer.MIN_VALUE;
            }else if(result>=Integer.MAX_VALUE){
    
                return Integer.MAX_VALUE;
            }
        }
        //这里是为了判断 " +-21"这种情况的,这种,list和stringBuilderare only added +,This case cannot be converted to a number,直接返回0即可.
        if(list.size()==1 && (list.get(0)=='+'|| list.get(0)=='-')){
    
            return 0;
        }
            return Integer.parseInt(stringBuilder.toString());
    }
}

5.回文子字符串的个数

class Solution {
    
    public static int countSubstrings(String s) {
    
        //如果字符串长度为1,直接返回1 即可
       if(s.length()==1){
    
           return 1;
       }
       //定义result,can be found from the title,Each individual character is a palindrome string
       int result=s.length();
       //开始遍历字符串s
       for(int i=0;i<s.length();i++){
    
           for (int j=i+1;j<s.length();j++){
    
               //开始截取字符串,从i下标开始截取,截至到j+1下标
               String temp=s.substring(i,j+1);
               StringBuilder stringBuilder=new StringBuilder(temp);
               //If the truncated string 等于 字符串的逆置,result++即可
               if(temp.equals(stringBuilder.reverse().toString())){
    
                   result++;
               }
           }
       }
       return result;
    }
}

6.和大于等于target的最短子数组

使用双层forloop to solve this problem

class Solution {
    
  public static int minSubArrayLen(int target, int[] nums) {
    
        //ret记录:子数组之和 大于等于 target The shortest length of the subarray of 
        int ret=Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
    
            int temp=target;
            //用listto record data that meets the conditions
            List<Integer> list=new ArrayList<>();
            for(int j=i;j<nums.length;j++){
    
                //如果temp>=0,Prove that you need to take ittempto subtract array elements
                //否则,直接退出当前for循环
                if(temp>=0){
    
                    temp-=nums[j];
                    list.add(nums[j]);
                }else{
    
                    break;
                }
                //验证temp是否小于等于0,如果满足条件,更新ret的值
                if(temp<=0){
    
                    ret=Math.min(ret,list.size());
                }
            }
        }
        //If there is no subarray sum 大于等于 target ,此时retThe value is still the initialized value,此时,只需要返回0 即可
        if(ret==Integer.MAX_VALUE){
    
            return 0;
        }
        return ret;
    }
}

7.字符串中的变位词

class Solution {
    
    public static boolean checkInclusion(String s1, String s2) {
    
        //If the first string length is greater than the second string length,直接返回false
        if(s1.length()>s2.length()){
    
            return false;
        }
        //将字符串1转化成字符数组,and sort it
        char[] ss1=s1.toCharArray();
        Arrays.sort(ss1);
        //排序之后,将字符数组转成字符串
        String a=new String(ss1);
        for(int i=0;i<(s2.length()-s1.length()+1);i++){
    
            //在字符串2 intercepted from the string1equal length
            String s=s2.substring(i,i+s1.length());
            //Convert it to a character array,排序
            char[] temp=s.toCharArray();
            Arrays.sort(temp);
            String ret=new String(temp);
            //如果两个字符串相等,就直接返回true
            if(a.equals(ret)){
    
                return true;
            }
        }
        //遍历完之后,如果没有返回true,返回false
        return false;
    }
}

8.字符串中的所有变位词

class Solution {
    
  public  static List<Integer> findAnagrams(String s, String p) {
    
        //定义一个list用于返回
        List<Integer> list=new ArrayList<>();
        //将字符串转成字符数组,and sort it,然后再转成字符串
        char[] p1=p.toCharArray();
        Arrays.sort(p1);
        String pp=new String(p1);
        for(int i=0;i<(s.length()-p.length()+1);i++){
    
            //从sIntercept and from the stringpStrings Strings of equal length,Then convert it into a character array,排序,再转成字符串
            String temp=s.substring(i,i+p.length());
            char[] t1=temp.toCharArray();
            Arrays.sort(t1);
            String tt=new String(t1);
            //比较两个字符串是否相等,相等,就在listAdd its subscript to it
            if(pp.equals(tt)){
    
                list.add(i);
            }
        }
        //返回list
        return list;
    }
}

9.乘积小于k的子数组

class Solution {
    
public  static int numSubarrayProductLessThanK(int[] nums, int k) {
    
        //定义左右指针
       int ret=1;
       int left=0;
       int count=0;
       for(int right=0;right<nums.length;right++){
    
           //累计乘积
           ret=ret*nums[right];
           //If the cumulative product is greater than k的话,Move the left pointer to the right（ret除等）,until the cumulative product is less than k的时候,出循环
           while(left<=right && ret>=k){
    
               ret/=nums[left++];
           }
           //If the left pointer is larger than the right pointer,直接返回0,If the left pointer is less than or equal to the right pointer,count+=right-left+1;
           count+=right>=left?(right-left+1):0;
       }
        return count;
    }
}

10.和为k的子数组

解题思路:
链接: bilibili LeetCode力扣

class Solution {
    
    public  static int subarraySum(int[] nums, int k) {
    
        HashMap<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        int pre=0;
        int count=0;
        for(int i=0;i<nums.length;i++){
    
            pre+=nums[i];
            if(map.containsKey(pre-k)){
    
                count+=map.get(pre-k);
            }
            map.put(pre,map.getOrDefault(pre,0)+1);
        }
        return count;
    }
}