- 数字操作
- 数组操作
1. 数字操作
1.1 题目分类以及常用的函数
类别：
- 遍历各位求和，或者反转求和的，这里一般会用到int的最大值和最小值，int的取值范围是从-2147483648 至2147483647
- 根据数学规律得出答案的
常用的函数：
- 判断一个char是不是数字
boolean Character.isDigit(char c);
- Character与数字进行转化的两种方法
char c;
int num = c- '0';
int num = Character.getNumericValue(c);
1.2 Leetcode实例
q7 整数反转
/**
* 反转数字:
* 就是不停的取模取余运算，把得到的余数在每次循环中*10再加上新的余数
* 在求算过程中要保证结果范围在Integer的大小范围内
*
* int的取值范围是从-2147483648 至2147483647
* @param x
* @return
*/
public int reverseTwo(int x){
int res = 0;
while (x != 0){
int residue = x % 10;
x = x/10;
//超过最大值的范围
if (res > Integer.MAX_VALUE/10 ||(res == Integer.MAX_VALUE / 10 && residue > 7)) return 0;
//超过最小值的范围
if (res < Integer.MIN_VALUE/10 || (res == Integer.MIN_VALUE / 10 && residue < -8)) return 0;
res = res*10 + residue;
}
return res;
}
q8 字符串转换整数
/**
* 这题其实也在计算数字的大小, 需要把逻辑理清楚
* 1. 首先把字符串的前面的空格都去掉
* 2. 根据首字符判断该数字是正数，负数还是不是数字需要返回0, 并且更新初始标识位
* 3. 判断好之后往后遍历得到数字结果，判断数字是否超过范围，如果超过范围返回0，若没有返回正常结果
* @param str
* @return
*/
public static int myAtoiTwo(String str){
//删除字符串首尾的空白字符
str = str.trim();
if (str.length() == 0) return 0;
char[] chars = str.toCharArray();
boolean positive = true;
int i =0;
if (chars[i] == '+'){
i++;
}else if (chars[i] == '-'){
i++;
positive = false;
}else if (!Character.isDigit(chars[i])){
return 0;
}
int res = 0;
while (i<chars.length && Character.isDigit(chars[i])){
int cur = chars[i]-'0';
if (positive){
if (res > Integer.MAX_VALUE/10 ||(res == Integer.MAX_VALUE / 10 && cur > 7))
return Integer.MAX_VALUE;
}else {
if (res > Integer.MAX_VALUE/10 || (res == Integer.MAX_VALUE / 10 && cur > 8))
return Integer.MIN_VALUE;
}
res = res*10+cur;
i++;
}
return positive?res:-res;
}
q9 回文数
/**
* 使用数字类型的解题思路:
* 反转一半数字，然后两部分比较大小
* 这里的重点是: 判断是否是反转了一半是用原本数字和新生成的数字比较大小,新生成的数字大于等于原本数字说明已经到了合适的位置
* @param x
* @return
*/
public boolean isPalindromeTwo(int x) {
if (x<0 ||(x%10==0 && x>0)) return false;
int reverse = 0;
while (reverse<x){
reverse = reverse*10 + x%10;
x = x/10;
}
return reverse == x || reverse/10 == x;
}
q43 字符串相乘
/**
* 两数字做乘法的逻辑思路:
* 两数字乘法结果的长度不会超过两个数字长度之和，所以用一个数组长度为两个数字长度之和的数组存储结果
* 然后就是考虑做乘法的规律，我们是一个数字的一位一位与另一个数字的所有位做乘法，这就需要使用双层循环
*
* 内层循环
* 然后就是每一位乘法结果应该是 （当前位置已经存储的结果 + 当前的两个位数的乘法结果 + carry） % 10 的值，
* 同理新一位的carry值是（当前位置已经存储的结果 + 当前的两个位数的乘法结果 + carry） / 10 的值
*
* 计算过一遍内层循环后就需要把最后一个carry放到外层数组指定的位置上
* 计算新的一波内层循环的时候carry需要归零进行计算
*
* @param num1
* @param num2
* @return
*/
public String multiplyTwo(String num1, String num2) {
if (num1.length() == 0 || num2.length() == 0) return "0";
int[] res = new int[num1.length()+num2.length()];
int carry;
for (int i=num1.length()-1;i>=0;i--){
carry = 0;
for (int j= num2.length()-1;j>=0;j--){
int n1 = Character.getNumericValue(num1.charAt(i));
int n2 = Character.getNumericValue(num2.charAt(j));
int mul = res[i+j+1] + (n1*n2) + carry;
res[i+j+1] = mul%10;
carry = mul/10;
}
res[i] = carry;
}
StringBuilder stringBuilder = new StringBuilder();
int k=0;
while (k<res.length){
if (res[k]>0){
break;
}
k++;
}
for (;k<res.length;k++){
stringBuilder.append(res[k]);
}
return stringBuilder.toString().length() > 0 ? stringBuilder.toString() : "0" ;
}
q172 阶乘后的零
/**
* 这道题有点考数学知识
* 形成尾部的0的条件是5*某个偶数，或者是5^n乘以2^n可以形成n个零
* @param n
* @return
*/
public int trailingZeroesTwo(int n) {
int res = 0;
while (n/5 != 0){
res += n/5;
n = n/5;
}
return res;
}
以上题目的其他解题思路请参考: https://www.jianshu.com/p/3fef17a62af4
2. 数组操作
2.1 做题思路
类别:
二维数组
二维数组的重点在于二维数组的遍历，例如根据遍历时索引坐标的变化得到结果，或者遍历数组判断哪里有零就利用第一行第一列对应的位置进行标记。一维数组
一维数组的题通常有另一个数组或者等长的String做辅助来得到结果。
想要记录的函数
- 把Integer转换成二进制字符串
String bitmap = Integer.toBinaryString(i).substring(1);
2.2 Leetcode实例
q54 螺旋矩阵
/**
* 这道题中重点在于遍历矩阵，其位置变化是有规律的
* 先是最外圈的顺时针，固定四个节点的坐标值
* 注意点:存在四个循环的前提是至少两行两列，不然的话就是一个循环
* 一次循环之后更新四个坐标值
* @param matrix
* @return
*/
public List<Integer> spiralOrderTwo(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix.length == 0)
return res;
int rl = 0, rh = matrix.length-1;
int cl = 0, ch = matrix[0].length-1;
while (rl<=rh && cl<=ch){
for (int c=cl;c<=ch;c++) res.add(matrix[rl][c]);
for (int r=rl+1;r<=rh;r++) res.add(matrix[r][ch]);
if (rl<rh && cl<ch){
for (int c = ch-1;c> cl; c--) res.add(matrix[rh][c]);
for (int r= rh;r > rl;r--) res.add(matrix[r][cl]);
}
rl++;
rh--;
cl++;
ch--;
}
return res;
}
q73 矩阵置零
/**
* 想用第一行第一列记录需要置零的元素，但是matrix[0][0]处元素的0需要特殊处理
* matrix[0][0]在一次遍历时候只能用来记录第0行或者第0列是否是0
* 所以没有被标识的行或者列需要其他标识来表示
* @param matrix
*/
public void setZeroesTwo(int[][] matrix) {
boolean isCol = false;
int R = matrix.length;
int C = matrix[0].length;
//用matrix的第一行和第一列标识当前行列是否有0，用isCol标识第一列是否有0元素
for (int i=0;i<R;i++){
if (matrix[i][0] == 0){
isCol = true;
}
for (int j=1;j<C;j++){
if (matrix[i][j] == 0){
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i=1;i<R;i++){
for (int j=1;j<C;j++){
if (matrix[i][0] == 0 || matrix[0][j] == 0){
matrix[i][j] = 0;
}
}
}
if (matrix[0][0] == 0){
for (int j = 0; j < C; j++) {
matrix[0][j] = 0;
}
}
if (isCol) {
for (int i = 0; i < R; i++) {
matrix[i][0] = 0;
}
}
}
q78 子集
/**
* 生成和nums长度一样的字符串是从0..00 到 1..11，来辅助得到答案
*
* 使用与运算来计算结果
* 生成和bitmask和字符串的长度一样，是从0..00 到 1..11
* 如果是1就加上这个字母，如果不是就不加
*/
public List<List<Integer>> subsetsTwo(int[] nums){
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
for (int i=(int)Math.pow(2,n);i<(int)Math.pow(2,n+1);i++){
//generate bitmask, from 0..00 to 1..11
//toBinaryString 是将整数转化成二进制字符串
String bitmap = Integer.toBinaryString(i).substring(1);
List<Integer> curr = new ArrayList<>();
for (int j=0;j<n;j++){
if (bitmap.charAt(j)=='1') curr.add(nums[j]);
}
res.add(curr);
}
return res;
}
q581 最短无序连续子数组
/**
* 这道题的辅助是已经有序的数组，通过有序数组和当前这个无序数组进行比较，得到最左边无序的位置和最右边无序的位置
* 从而得到结果
*
* 目标是找到无序的子集，这段数据排序之后整个数组就有序了
* 所以重点就是找到有序数组和当前这个无序数组之中最左边无序的位置和最右边无序的位置
* 最简单的找到这两个无序的位置的思路是将原数组排序，遍历两个数组，看在最左边和最右边不一致的位置分别在哪
* @param nums
* @return
*/
public int findUnsortedSubarrayTwo(int[] nums) {
//使用clone的方式复制数组
int[] initial = nums.clone();
Arrays.sort(initial);
int res =0;
int start=nums.length, end = 0;
for (int i=0;i<nums.length;i++){
if (initial[i]!=nums[i]){
start = Math.min(start,i);
end = Math.max(end,i);
}
}
return (end-start>=0 ? end-start+1 : 0);
}
另外两种找到最左端和最右端无序的位置的方法是:
- 基于排序，两个节点位置需要交换说明那两个节点都是处于无序的位置。
- 基于栈，从左往右遍历找到最左边正确的边界，然后从右往左遍历找到最右边正确的边界。
q945 使数组唯一的最小增量
/**
* 因为0 <= A.length <= 40000，因此可以尝试用一个长度够长的数组做辅助，
* 这个数组只能有0到1个元素，所以就是一个平坑填坑的过程
*
* 1. 首先先统计数组A在辅助数组的频率
* 2. 从左往右遍历，如果数组中元素大于1，就是都拿出来，所以res做相应的减法
* 3. 然后往后找到没有元素的坑了把元素加入进去，res加上相应的值
* @param A
* @return
*/
public int minIncrementForUniqueTwo(int[] A) {
int[] dirc = new int[100000];
int res = 0, token = 0;
for (int a:A){
dirc[a]++;
}
for (int i=0;i<dirc.length;i++){
if (dirc[i]>1){
token += dirc[i]-1;
res -= i*(dirc[i]-1);
} else if (token>0 && dirc[i]==0){
res += i;
token--;
}
}
return res;
}
以上题目的其他解题思路请参考:https://www.jianshu.com/p/dae13c793792
