解题--＞在线OJ(十八)

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.把数字翻译成字符串

动态规划解决此问题

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.礼物的最大价值

动态规划解决此问题

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();
        //去除空格之后，再次判断 此时的字符串是否为空，如果为空，返回 0
        if(str==""){
    
            return 0;
        }
        //将字符串转成字符数组
        char[] temp=str.toCharArray();
        //如果此时字符数组中，只有 + 或者 -，直接返回 0
        if(temp.length==1 && (temp[0]=='+'||temp[0]=='-')){
    
             return 0;
        }
        StringBuilder stringBuilder=new StringBuilder();
        //当字符数组长度大于1的时候，判断字符数组第一位是否是 +/-/数字。 如果不是这三项，直接返回0即可
        if(temp[0]=='+' ||temp[0]=='-' || (temp[0]>='0'&&temp[0]<='9')){
    
            list.add(temp[0]);
            stringBuilder.append(temp[0]);
        }else{
    
            return 0;
        }
        //遍历字符数组，所遍历到的字符必须得是数字，如果不是数字，就结束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;
            }
            //当stringBuilder增加足够大的时候，超过了Integer的最大值或者是最小值的时候，就直接返回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和stringBuilder中都只添加了 +,这种情况无法转换成数字，直接返回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，从题目中可以得知，每一个单独的字符都是回文字符串
       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);
               //如果截取的字符串 等于 字符串的逆置，result++即可
               if(temp.equals(stringBuilder.reverse().toString())){
    
                   result++;
               }
           }
       }
       return result;
    }
}

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

使用双层for循环来解决此题

class Solution {
    
  public static int minSubArrayLen(int target, int[] nums) {
    
        //ret记录:子数组之和 大于等于 target 的子数组最短长度
        int ret=Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
    
            int temp=target;
            //用list来记录满足的条件的数据
            List<Integer> list=new ArrayList<>();
            for(int j=i;j<nums.length;j++){
    
                //如果temp>=0,就证明需要拿temp去减数组元素
                //否则，直接退出当前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());
                }
            }
        }
        //如果没有子数组之和 大于等于 target ，此时ret的值还是初始化的值，此时，只需要返回0 即可
        if(ret==Integer.MAX_VALUE){
    
            return 0;
        }
        return ret;
    }
}

7.字符串中的变位词

class Solution {
    
    public static boolean checkInclusion(String s1, String s2) {
    
        //如果第一个字符串长度大于第二个字符串长度，直接返回false
        if(s1.length()>s2.length()){
    
            return false;
        }
        //将字符串1转化成字符数组，并且将其排序
        char[] ss1=s1.toCharArray();
        Arrays.sort(ss1);
        //排序之后，将字符数组转成字符串
        String a=new String(ss1);
        for(int i=0;i<(s2.length()-s1.length()+1);i++){
    
            //在字符串2 中截取于字符串1相等的长度
            String s=s2.substring(i,i+s1.length());
            //将其转化为字符数组，排序
            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<>();
        //将字符串转成字符数组，并且将其排序，然后再转成字符串
        char[] p1=p.toCharArray();
        Arrays.sort(p1);
        String pp=new String(p1);
        for(int i=0;i<(s.length()-p.length()+1);i++){
    
            //从s字符串中截取与p字符串相等长度的字符串，然后将其转化成字符数组，排序，再转成字符串
            String temp=s.substring(i,i+p.length());
            char[] t1=temp.toCharArray();
            Arrays.sort(t1);
            String tt=new String(t1);
            //比较两个字符串是否相等，相等，就在list当中加入其下标
            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];
           //如果累计乘积大于k的话，就把左指针往右边挪（ret除等），直到累计乘积小于k的时候，出循环
           while(left<=right && ret>=k){
    
               ret/=nums[left++];
           }
           //如果左边指针大于右边指针，直接返回0，如果左边指针小于等于右边指针，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;
    }
}