Java教程

JAVA修炼秘籍番外篇第一章《这四道代码题,你真的会吗?》

本文主要是介绍JAVA修炼秘籍番外篇第一章《这四道代码题,你真的会吗?》,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

往期:
JAVA 修炼秘籍第一章:《痛苦的折磨》
JAVA 修炼秘籍第二章:《逐渐魔化》
JAVA 修炼秘籍第三章:《绝地反击》
JAVA 修炼秘籍第四章:《闭关修炼》
JAVA 修炼秘籍第五章:《卧薪尝胆》
JAVA 修炼秘籍第六章:《鏖战》


前言: 最近一直在刷题,感觉没什么可写的博客,许久未更新大家也不会想我,毕竟没人看,哈哈哈哈哈,一个人的狂欢。
———————————————————生活以痛吻我,我却报之以歌。

文章目录

  • 一、两数相除
    • 1.题目要求
    • 2.代码
    • 3.本题结语
  • 二、反转矩阵后的得分
    • 1.题目要求
    • 2.代码
    • 3.图解
  • 三、滑动窗口
    • 1.题目要求
    • 2.牛客代码
    • 3.力扣代码
  • 四、最小覆盖子串
    • 1.题目要求
    • 2.代码


在这里插入图片描述

一、两数相除

题链接:来自力扣《两数相除》

1.题目要求

给定两个数,一个除数与一个被除数。返回得到的商,要求不可以使用乘法(*),除法(\),mod(%)。

2.代码

class Solution {
    public int divide(int dividend, int divisor) {
	    //dividend =>除数。
    	//divisor =>被除数。
        long sum=0;
        //sum =>存储最后要返回的值
        long x=dividend;
        //其实这里的X与Y没有也可以,自我觉得会影响后续代码的清晰度
        long y=divisor;
        boolean bool=(x<0&&y>0)||(x>0&&y<0);
        //bool =>查看两个数是否有负数存在,对结果进行正数与负数的调整。
        if(x<0){
            x=-x;//先将负数转为正数,方便后续计算
        }
        if(y<0){
            y=-y;//先将负数转为正数,方便后续计算
        }

		//接下来采用二分查找,因为结果一定不会大于除数
		//也就是结果会在0~X之间。
        long left=0;//左指针
        long right=x;//右指针
        while(left<right){//查找范围
            long mid=left+right+1>>1;//中间值
            if(Mul(mid,y)<=x){//调用函数进行快速乘法
                left=mid;
                //相乘后返回结果小于等于X,左指针右移
            }else{
                right=mid-1;
                //相乘后返回结果大于X,右指针左移
            }
        }
        
        //将最终结果调整一下,判断是正数还是负数。
        sum=bool?-left:left;
        
        //判断是否溢出
        if(sum<Integer.MIN_VALUE||sum>Integer.MAX_VALUE){
            return Integer.MAX_VALUE;
        }
        
        //强制类型转换后返回
        return (int)sum;
    }
    
    //快速相乘方法
    public long Mul(long a,long b){
    // a => 乘数
    // b => 被乘数
    // count => 积
        long count=0;
        while(b>0){
            if((b&1)==1){
            //按位与1,最后一位为1,积加等乘数。
                count+=a;
            }
            // a+=a 等于 a=a*2;  
            a+=a;
            // b>>=1 等于 b=b/2;
            b>>=1;
        }
        return count;
    }
}

3.本题结语

所有的题解都写在了代码注释中,自己假设给定两个数值走一遍,就可以明白,主要就在于其中的二分法与快速乘法,两个基础算法。

二、反转矩阵后的得分

题链接:来自力扣《反转矩阵后的得分》

1.题目要求

给你一个二维矩阵(也就是二维数组),里面每个元素存放的不是1就是0,你可以选择任意一行元素或者一列元素进行修改,但是不可以单独选择一个元素进行修改。
修改规则为:假设选中了一行元素,那么这一行元素都要进行修改,将所有0改为1,1改为0。
在做出任意次数的移动后,将该矩阵的每一行都按照二进制数来解释,矩阵的得分就是这些数字的总和。
注意: 返回尽可能高的分数,也就是修改为总和为最高的矩阵

2.代码

class Solution {
    public int matrixScore(int[][] grid) {
        int m=grid.length;//m为矩阵有几行
        int n=grid[0].length;//n为矩阵有几列
        int res=0;//矩阵修改后的得分
        
        for(int i=0;i<m;i++){
        //把每行第一个为0的行进行修改,此行为会让此行的二进制一定比修改前大
        //比如:0111 => 7 修改后为 1000 => 8 所以修改第一位很关键
            if(grid[i][0]==0){
                for(int j=0;j<n;j++){
                //此行全部反转,1-0=1,1-1=0;
                //也可以写成 grid[i][j]^=1;
                    grid[i][j]=1-grid[i][j];
                }
            }
        }
        
        //现在进项每一列的检查
        //这里检查后没有修改原数组而是直接计算了。
        for(int j=0;j<n;j++){
            int count=0;
            
            //count保留每一列有几个1。
            for(int i=0;i<m;i++){
                count+=grid[i][j];
            }
            
            //如果此列中0比1多就进行反转,但是此处没有反转,而是直接取值了
            //有点小偷鸡,也无伤大雅
            //调用max方法,此行1的个数乘以当前位置的1在二进制中的十进制数字。
            res+=Math.max(count,m-count)*(1<<(n-j-1));
        }
        return res;
    }
}

3.图解

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

三、滑动窗口

力扣原题链接:点击进入。
牛客原题链接:点击进入。

1.题目要求

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回值:返回滑动窗口中的最大值。

2.牛客代码

这道题会给出两个代码,一个是我在牛客上可以通过,而力扣无法通过的,另一个是两个网站都可以通过的。

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] nums, int k) {
    
        //len保存数组长度,后续清晰度
        int len=nums.length;
        
        //max保留每个窗口最大值
        int max=0;
        
        //arr储存每个窗口最大值
        ArrayList<Integer> arr=new ArrayList<Integer>();
        
        //判断如果K==0直接结束
        if(k==0){
            return arr;
        }
        
        //循环遍历数组
        for(int i=0;i<=len-k;i++){
        
        	//将max制空
            max=0;
            
            //查找当前窗口的最大值
            for(int j=i;j<k+i;j++){
                max=Math.max(max,nums[j]);
            }
            
            //储存每个窗口最大值
            arr.add(max);
        }
        
        //返回
        return arr;
    }
}

这个方法非常简单,不需要过多的解释。

3.力扣代码

分块+预处理方法

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
    
    	//len储存输入数组长度
        int len=nums.length;

		//储存前缀最大值
        int[] arr1=new int[len];

		//储存后缀最大值
        int[] arr2=new int[len];

		//保留原数组中以i结尾的前缀最大值
        for(int i=0;i<len;i++){

			//如果i是k的倍数,那么nums[i]到nums[i+k-1]恰好是一个分组
            if(i%k==0){
                arr1[i]=nums[i];
            }else{
                arr1[i]=Math.max(arr1[i-1],nums[i]);
            }
        }

		//保留原数组中以i开始的后缀最大值
        for(int i=len-1;i>=0;i--){
            if(i==len-1||(i+1)%k==0){
                arr2[i]=nums[i];
            }else{
                arr2[i]=Math.max(arr2[i+1],nums[i]);
            }
        }
        
        //arr1[i]和arr2[i+k-1]都等于分组中的最大值,
        //因此无论窗口属于哪一种情况,都为答案
        int[] arr=new int[len+1-k];
        for(int i=0;i<=len-k;i++){
            arr[i]=Math.max(arr1[i+k-1],arr2[i]);
        }
        return arr;
    }
}

这里一般容易出错在后缀的最大值的位置,一定要看好判断条件,防止越界。

四、最小覆盖子串

力扣原题链接:点击进入。
牛客原题链接:点击进入

1.题目要求

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。

2.代码

class Solution {
    public String minWindow(String s, String t) {
    
    	//储存t中每个元素出现的次数
        int[] amp=new int[128];
        for(int i=0;i<t.length();i++){
            amp[t.charAt(i)]++;
        }

		//begin与end存储窗口的首位,
		//d存储窗口的长度, 
		//count储存t中还有几个字符没被窗口包含
        int count=t.length();
        int len=s.length();
        int end=0;
        int head=0;
        int d=Integer.MAX_VALUE;
        int begin=0;

		//循环遍历	
        while(end<len){

			// amp[] > 0 说明该字符在t中出现,
			//count-- 表示对应的字符被包含在了窗口,
			//如果s中的字符没有在t中出现,
			//则amp[]中对应的字符变为负值
            if((amp[s.charAt(end++)]--) > 0){
                count--;
            }

			//count为0了,这个时候证明窗口中已经完全包含了t中的所有元素
            while(count==0){
                if(end-begin<d){
                    d=end-begin;
                    head=begin;
                }

				// begin开始后移,继续向后寻找。
				//如果begin后移后指向的字符在map中==0,表示是在T中出现的,如果没有出现,map[]中的值会是负值。
				// 在T中的某个字符从窗口中移除,所以counter++。
                if(amp[s.charAt(begin++)]++ == 0){
                    count++;
                }
            }
        }
        return  d == Integer.MAX_VALUE ? "" : s.substring(head,head+d);
    }
}

谢谢观看。再见!
在这里插入图片描述

这篇关于JAVA修炼秘籍番外篇第一章《这四道代码题,你真的会吗?》的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!