剑指Offer——整数篇算法题

文章目录

- - 整数除法
  - - 题目描述
    - 解题代码
  - 二进制加法
  - - 题目描述
    - 解题代码
  - 前n个数字二进制形式中1的个数
  - - 题目描述
    - 解题代码
    - - 方法一：根据i&(i-1)求解
      - 方法二：根据i/2求解
  - 只出现一次的数字
  - - 题目描述
    - 解题代码
    - 拓展题目
    - - 题目描述
      - 解题代码
  - 单词长度最大乘积
  - - 题目描述
    - 解题代码
    - - 方法一：使用二维数组映射字符出现的情况解题
      - 方法二：使用二进制位运算解题

该系列文章主要是记录阅读《剑指Offer（专项突破版）》书籍时对其中的算法题记录。持续更新中……

整数除法题目描述

输入2个int型整数，它们进行除法计算并返回商，__要求不得使用乘号‘*’、除号‘/’以及求余符号‘%’。__当发生溢出时，返回最大的整数值。假设除数不为0。例如，输入15和2，输出15/2的结果，即7。

解题代码

package jianzhioffer;


public class Solution001 {

	public static void main(String[] args) {
		int result = new Solution001().divide(15, 2);
		System.out.println(result);
	}
	
	
	public int divide(int dividend, int divisor) {
		
		if(dividend == 0x80000000 && divisor == -1) {
			return Integer.MAX_VALUE;
		}
		int negative = 2;	//设置标志，用来判断结果是正数还是负数
		
		if(dividend > 0) {
			negative--;
			dividend = -dividend;
		}
		if(divisor > 0) {
			negative--;
			divisor = -divisor;
		}
		int result = divideCore(dividend, divisor);
		return negative==1?-result:result;
	}
	
	private int divideCore(int dividend, int divisor) {
		int result = 0;	//定义返回结果
		while(dividend <= divisor) {	//判断被除数是否小于等于除数（注意，这里是已经转为负数）,如果是小于则直接返回0
			int value = divisor;	//将除数赋值给临时变量value
			int quotient = 1;		//商值
			
			while(value >= 0xc0000000 && dividend <= value +value) {
				quotient += quotient; //累加商
				value += value;
			}
			result += quotient;
			dividend -= value;
		}
		return result;
	}
}

二进制加法题目描述

输入俩个表示二进制的字符串，请计算他们的和，并以二进制字符串形式输出。例如，输入的二进制字符串分别是“11”和“10”，则输出“101”。

解题代码

package jianzhioffer;


public class Solution002 {

	public static void main(String[] args) {
		String result = new Solution002().addBinary("11", "10");
		System.out.println(result);
	}
	
	public String addBinary(String a, String b) {
		StringBuilder result = new StringBuilder();
		int i = a.length() - 1;
		int j = b.length() - 1;
		int carry = 0;	//进1标志位
		while(i>=0 || j>=0) {	//如果a或者b的长度大于0，进入循环
			int digitA = i >=0 ? a.charAt(i--) - '0' : 0; //从右到左获取a二进制字符串的值，0或者1
			int digitB = j >=0 ? b.charAt(j--) - '0' : 0; //从右到左获取b二进制字符串的值，0或者1
			int sum = digitA + digitB + carry;	//将a和b对应位的值相加并加行进位
			carry = sum >=2 ? 1 : 0;	//如果和大于等于二就将进位赋值为1
			sum = sum >=2 ? sum - 2 : sum;	//对和进行处理
			result.append(sum);
		}
		if(carry==1) {	//如果存在进位则加一
			result.append(1);
		}
		return result.reverse().toString();	//由于添加和的时候是从右到左添加的，因此结果需要反转
	}
}

前n个数字二进制形式中1的个数题目描述

输入一个非负数n，请计算0到n之间每个数字的二进制形式中1的个数，并输出一个数组。例如，输入n为4，由于0、1、2、3、4的二进制形式中1的个数分别为0、1、1、2、1，因此输出数组[0,1,1,2,1]

解题代码方法一：根据i&(i-1)求解

package jianzhioffer;


public class Solution003 {

	public static void main(String[] args) {
		int[]result = new Solution003().countBit(4);
		for(int x : result) {
			System.out.print(x+" ");
		}
	}
	
	public int[] countBit(int n) {
		int[]result = new int[n+1];
		for(int i=1; i<=n; i++) {
			result[i] = result[i&(i-1)]+1;
		}
		return result;
	}
}

本题中主要运用了i&(i-1)这个运算公式，它的作用就是将i的最右边的1变为0，上面代码中for循环里的含义：因为i&(i-1)是将i的最右边的1变为0，因此正数i的二进制形式中的1的个数比i&(i-1)的二进制形式中的1的个数多1。

方法二：根据i/2求解

public class Solution003 {
	public static void main(String[]args) {
		int[]result = new Solution003().countBits(4);
		for(int x : result) {
			System.out.print(x+" ");
		}
	}

	public int[] countBits(int n) {
		int[]result = new int[n+1];
		for(int i=1; i<=n; i++){
			result[i] = result[i>>1] + (i & 1);	//i&1 是用来判断是奇数还是偶数，奇数返回1，偶数返回0
		}
		return result;
	}
}

如果正整数i是一个偶数，那么i相当于将i/2左移一位的结果，因此偶数i和i/2的二进制形式中的1的个数是相同的。如果i是奇数，那么i相当于将i/2左移一位之后再将最右边的一位设为1的结果，因此奇数i的二进制形式中1的个数比i/2的1的个数多1.

只出现一次的数字题目描述

输入一个整数数组，数组中只有一个数字出现了一次，其他数字都出现了3次。请找出那个出现了一次的数字。例如，如果输入的数组为[0,1,0,1,0,1,100]，则只出现一次的数字为100。

解题代码

package jianzhioffer;


public class Solution004 {
	
	public static void main(String[] args) {
		int[]nums = {0,1,0,1,0,1,100};
		int result = new Solution004().singleNumber(nums);
		System.out.println(result);
	}
	
	public int singleNumber(int[]nums) {
		int[]bitSums = new int[32];
		for(int num : nums) {
			for(int i=0; i<32; i++) {
				//用来得到整数num的二进制形式中从左数起第i个数位。
				bitSums[i] = (num >> (31-i)) & 1; 
			}
		}
		int result = 0;
		for(int i=0; i<32; i++) {
			//如果出现了3次的数字的位数和一定是三的倍数，因此只有出现了一次的数字bitSums[i]%3才是有值的
			result = (result << 1) + bitSums[i] % 3; 
		}
		return result;
	}

}

拓展题目题目描述

输入一个整数数组，数组中只有一个数字出现m次，其他数字都出现了n次。请找出那个唯一出现m次的数字。假设m不能被n整除。

解题代码

public int singleNumberPlus(int[]nums, int n, int m) {
		int[]bitSums = new int[32];
		for(int num : nums) {
			for(int i=0; i<32; i++) {
				bitSums[i] += (num >> (31 - i)) & 1;
			}
		}
		for(int i=0; i<32; i++) {
			System.out.print(bitSums[i]+" ");
		}
		System.out.println();
		int result = 0;
		for(int i=0; i<32; i++) {
			result = (result << 1) + bitSums[i] % n;
		}
		return result/m;
	}

上面是对出现一次的数字题目的拓展，拓展方法中n和m表示在一个数组中只有一个数字出现了m次，其余都出现了n次。这里假设m不能被n整除。

单词长度最大乘积题目描述

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。例如数组：[“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”]中"abcw", "fxyz"它们不包含相同的字符，因此返回16。

解题代码方法一：使用二维数组映射字符出现的情况解题

public int maxProduct(String[]words) {
	
	boolean[][] flags = new boolean[words.length][26];
	for(int i=0; i
		for(char c : words[i].toCharArray()) {
			flags[i][c - 'a'] = true;
		}
	}
	int result = 0;
	//进行循环对比，找出不想等的字符
	for(int i=0; i
		for(int j=i+1; j	//j = i+1 避免重复比较
			int k = 0;
			for(; k<26; k++) {
				if(flags[i][k] && flags[j][k]) {
					break;
				}
			}
			if(k==26) {	//当等于26时说明没有相等当字符
				//计算不想等字符长度的最大值
				int tempLength = words[i].length() * words[j].length();
				result = Math.max(result,tempLength);
			}
		}
	}
	return result;
}

方法二：使用二进制位运算解题

public int maxProduct2(String[]words) {
	int[]flags = new int[words.length];
	
	for(int i=0; i
		for(char c : words[i].toCharArray()) {
			flags[i] |= 1 << (c - 'a');	
		}
	}
	int result = 0;
	
	for(int i=0; i
		for(int j=i+1; j
			if((flags[i]&flags[j])==0) {
				int tempLength = words[i].length() * words[j].length();
				result = Math.max(result, tempLength);
			}
		}
	}
	return result;
}

剑指Offer——整数篇算法题

Java相关栏目本月热门文章