数据结构及算法总结（持续更新）_数据结构常用计算公式有哪些

前言

给自己：距离蓝桥杯还有26天，准备了整整一个半月了，也没给自己太大压力。有时候
弹弹琴玩玩乐队也偶尔打打游戏，基本处于半学办玩的状态。之前的蓝桥杯真题的最最
最基础题基本都过了一遍（稍微难一点点的也做了一点点，只不过代码写的太愚蠢没
敢写到那篇笔记里），做题时常说的一句话基本可以表达做这些题后的体会：卧槽，
原来是这样做啊，我怎么没想到（我怎么想这么复杂）现在终于开始了编程题目，在
蓝桥杯里，编程题算是大头，有的题是按效率给分，所以接下来的所有题都以先做出
来为主，优化放在最后，还是先做最最基础题然后再逐步增加难度。最后，基础不牢地动山摇！
---------------------------------------------------------------------------------------------------------
2021.5.8 蓝桥杯结束两个星期了，我也已经两个星期没碰电脑了玩了两个星期hahahah，参
加的是JAVA C组（第一场），拿了一个省二，由于是第一次参加比赛虽然C组省二很垃圾 但是对自己来说还是可以的了，毕竟回想一下去年的今天，我还狗屁不会（2020.8月底才勉勉强
强能用C语言写出一个用for的从1+到n，2020.2月底才开始学怎么用for if-else因为暴力杯），
一些基本的算法了解了一些 但是在比赛中并没用到因为用的不熟练或者是没理解，算法确实
有难度，但是有价值的往往是有难度的，所以革命尚未成功，同志仍需努力
---------------------------------------------------------------------------------------------------------
2022.5 因为专升本然后裸考了蓝桥杯，然后莫名其妙省一？？？可能是比赛题改革了，2填空+8大题，没啥
签到题了，让我给捡个漏，也可能是参赛的人更水了？结果出来了也不重要了，准备专升本考试，希望专升
本考试也能让我上个岸~
---------------------------------------------------------------------------------------------------------
2023.3.21 距离蓝桥杯还有十多天，专升本勉强上了个本科蓝桥杯进B组了，指导老师一二月份就开始给我说
让我做题，然后也天天玩也没做，每次蓝桥杯都是一个多月，裸考，十多天冲刺一下混个奖，自己拖拉的毛病
到现在也没改掉，难受！现在开始把原来不会的都给补一下，看看这次抱佛脚能不能抱的住！
---------------------------------------------------------------------------------------------------------
2023.1.29 这次可能是最后一次参加蓝桥杯了，参加了一把Python组，现在距离蓝桥杯还有俩个月，准备系统整一下
数据结构与算法，一路打下来虽然没学到太多牛逼的东西，也没有改掉多少拖拉的坏毛病，但是还是有收获的，比如
获得了较强的自学能力.... 虽然临近就业，但是感觉还是准备一下这次比赛比较好！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

一、基础数学类

1.素数（质数）

特点：只能被1及其自身整除

Ⅰ.判断素数

题目：输入一个数判断该数是否为素数
1

思路:

import java.util.Math
public class Main {
		public static void prime (int num) {
		if(num == 1 || num == 2)
			System.out.print("is Prime");
		else if (num <= 0)
			System.out.print("Error");
		else {
			for (int i = 2; i <= Math.sqrt(num);i ++) {
				if (num % i == 0)
					System.out.print("isn't Prime");
				else 
					System.out.print("is Prime");
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Ⅱ.筛选素数

题目：找出2020中所有的素数
1

思路：

1

2.约数（因数）

特点：整数a除以整数b(b≠0) 的商正好是整数而没有余数，我们就说b是a的因数（约数）。

Ⅰ.判断因数
（蓝桥杯第十一届1.）约数个数

题目：对于一个整数，能整除这个整数的数称为这个数的约数。
例如：1, 2, 3, 6 都是 6 的约数。
请问 78120 有多少个约数。
答案：96
1
2
3
4

思路：

public class Main {
	public static void main(String[] args) {
		int flag = 0;
		for (int i = 1; i <= 78120; i++) {
			if (78120%i == 0)
				flag++;
		}
		System.out.print(flag);
	}
}
1
2
3
4
5
6
7
8
9
10

Ⅱ.最大公因数
一、辗转相除法

特点：

1. m,n为自然数且m>n
2. 设r = m%n
3. 若r = 0 则n为m和n的最大公因数，反之进行下一步
4. 将m = n, n = r 重复执行(2) (3) 直到r = 0则找到最大公因数

public static int gcd (int n,int m){  //默认 m > n
	int r = m%n;
	if (r == 0)
		return n;
	else {
		while (r != 0){
			m = n;
			n = r;
			r = m%n;
		}
	}
	return n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

二、Stein算法

特点：

3.数列（高中知识）

Ⅰ.递推数列（斐波那契）

特点：如果数列{a[n]}的第n项与它前一项或几项的关系可以用一个式子来表示，那么这个公式叫做这个数列的递推公式。
典型例题：斐波那契数列
题目：求斐波那契数列的第n项

public static int Fibonacci (int n) {
		if (n == 0 || n == 1)
			return n;
		else 
			return Fibonacci (n-1) + Fibonacci (n-2);
	}
1
2
3
4
5
6

典型例题：母牛生小牛
题目：有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

public static int ox (int year) {
		if (year <= 4)
			return year;
		else 
			return ox (year-1) + ox (year-3);
	}
1
2
3
4
5
6

Ⅱ.等差数列（只牵扯到等差等比数列大多数都可以手算）

特点：后一项减前一项等于一个常数，即F(n)-F(n-1) = d (d为常数)
通项公式：F(n) = F(1) + (n-1) * d
等差中项：F(n) = (F(n+1) + F(n-1))/2
前n项和：S(n) = (F(1) + F (n)) * n/2

Ⅲ.等比数列

特点：后一项比前一项等于一个常数，即F(n)/F(n-1) = q (q为常数)
通项公式：F(n) = F(1) * pow(q,n-1)
前n项和：S(n) = F(1) * (1 - pow(q,n))/(1-q)

4.阶乘

特点：n！= 12345*…*n
递归或循环皆可：

//递归
public static int factorial (int n){
	if (n == 1)
		return 1;
	else 
		return factorial (n-1)*n;
}
//循环
int factorial (int n){
	int sum = 1;	
	for (int i = 1; i <= n; i++){
		sum = sum*i;
	}
	return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.全排列（DFS+回溯）

特点：排列注重的是顺序，即在规定所有元素内，所有不同顺序的元素排列
核心代码:

//从m-n的全排列
public static int[] num = new int [10000];
public static int[] jug = new int [100];
public static void dfs (int m,int n) {  
	if (m > n) {
		for (int i = 1;i < m;i ++) {
			System.out.print(" "+num[i]);
		}
		System.out.println();
		return ;
	}
	else {
		for (int i = 1; i <= n;i ++) {
			if (jug[i] == 0) {
			jug[i] = 1;  //如果进入过这一层则标记
			num[m] = i;
			dfs (m+1,n);  //进入下一层
			jug[i] = 0;  //回溯
			}
		}
	}	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

X.取位问题

描述：取一个数的每一位数进行操作
核心代码：

while (x != 0){
	num = x%10;
	进行需要的操作;
	x = x/10;
}
1
2
3
4
5

Ⅰ.（蓝桥杯第十一届2.）门牌制作

思路：

public class Main {
//1-2020中有多少2
	public static void main(String[] args) {
		int flag = 0;
		int num;
		for (int i = 1;i <= 2020; i ++) {
			int x = i;     // 拿x接收i  else陷入死循环
			while (x != 0) {
				num = x%10;
				if (num == 2)    //对取的每一位进行操作
					flag++;
				x = x/10;
			}
		}
		System.out.print(flag);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二、思想策略类

1.回溯算法

Ⅰ.（leetcode1688）比赛中的匹配次数

题目：给你一个整数 n ，表示比赛中的队伍数。比赛遵循一种独特的赛制：

如果当前队伍数是 偶数 ，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 
场比赛，且产生 n / 2 支队伍进入下一轮。
如果当前队伍数为 奇数 ，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总
共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。
返回在比赛中进行的配对次数，直到决出获胜队伍为止。

输入：n = 7
输出：6
解释：比赛详情：
- 第 1 轮：队伍数 = 7 ，配对次数 = 3 ，4 支队伍晋级。
- 第 2 轮：队伍数 = 4 ，配对次数 = 2 ，2 支队伍晋级。
- 第 3 轮：队伍数 = 2 ，配对次数 = 1 ，决出 1 支获胜队伍。
总配对次数 = 3 + 2 + 1 = 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

思路：第一种：根据题意进行简单的模拟（力扣题库分类是回溯算法 但是我不知道哪里体现的回溯。）

第二种:力扣大佬数学思维的答案：共有n个队伍，一个冠军，需要淘汰n-1个 队伍。每一场比赛淘汰一个队伍，因此进行了n-1场比赛。所以共有n-1个配对。

//第一种
    public static int numberOfMatches(int n) {
		int x = 0;
		while (n > 1) {
			if (n%2 == 0) {
				n = n/2;
				x = x+n;
			}
			else {
				n = (n-1)/2;
				x = x+n+1;
			}
		}
		return x;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//第二种
  	public int numberOfMatches(int n) {
       	 return n-1;
  	 }
1
2
3
4

2.贪心算法

Ⅰ.（leetcode1518）换酒问题

题目：小区便利店正在促销，用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 
numBottles 瓶酒。

如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。

请你计算最多 能喝到多少瓶酒。

输入：numBottles = 9, numExchange = 3
输出：13
解释：你可以用 3 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 9 + 3 + 1 = 13 瓶酒。
1
2
3
4
5
6
7
8
9
10
11

思路：第一种： 先把第一次的酒与第一次兑换的酒相加，再把首次可兑换的酒和剩下不够兑换的酒求出，再算出把两者相加即求出下一次兑换的酒瓶数

第二种：贪心算法，即先用res记录首次的喝的酒的数量，又numExchange个可以换一个，所以每次用numExchange个换一个都用res记录一个 ，又 numExchange个换一个之后 换的这个本身又是一个瓶子，所以下一次numExchange-1 ，每次如此循环 直到numBottles < numExchange停止（大佬指点我悟了！）

//第一种
public static int numWaterBottles(int numBottles, int numExchange) {
		int res = numBottles;
		while (numBottles >= numExchange) {
			res = res + numBottles/numExchange;
			numBottles = numBottles/numExchange + numBottles%numExchange;
		}
		return res;
    }

//第二种
public static int numWaterBottles(int numBottles, int numExchange) {
		int res = numBottles;
		while (numBottles >= numExchange) {
			numBottles = numBottles - numExchange + 1;
			res ++;
		}
		return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Ⅱ.（leetcode455）分发饼干

题目：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最
多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺
寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这
个最大数值。
输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
1
2
3
4
5
6
7
8
9
10
11
12

思路：先排序，让每一胃口值最小的孩子先吃饱然后记录最后返回该值

    public int findContentChildren(int[] g, int[] s) {
        int i = 0,j = 0; // i指向胃口值，j指向饼干尺寸
        int gl = g.length,sl = s.length;
		Arrays.sort (g);Arrays.sort(s);
		while (j < sl && i < gl){ //注意该处的逻辑关系！
			if (s[j] >= g[i]) {
				i++;
			}	
			j++;    
		}
		return i;
    }
1
2
3
4
5
6
7
8
9
10
11
12

Ⅲ.（leetcode1827）最少操作使数组递增

题目：给你一个整数数组 nums （下标从 0 开始）。每一次操作中，你可以选择数组中一个元素，并将它增加 1 。

比方说，如果 nums = [1,2,3] ，你可以选择增加 nums[1] 得到 nums = [1,3,3] 。
请你返回使 nums 严格递增 的 最少 操作次数。

我们称数组 nums 是 严格递增的 ，当它满足对于所有的 0 <= i < nums.length - 1 都
有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。

输入：nums = [1,1,1]
输出：3
解释：你可以进行如下操作：
1) 增加 nums[2] ，数组变为 [1,1,2] 。
2) 增加 nums[1] ，数组变为 [1,2,2] 。
3) 增加 nums[2] ，数组变为 [1,2,3] 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路：遍历数组，两两比较，如果不满足则相加且每加一次flag记录一次（两次循环导致效率较低）

public static int minOperations(int[] nums) {
		int i = 0,flag = 0;
		for (i = 0; i < nums.length; i++){
			while (nums[i] >= nums[i+1]){
				nums[i+1]++;
				flag++;
			}
		}
		return flag;
    }
1
2
3
4
5
6
7
8
9
10

第二种思路：两两比较，如果后一项比前一项小则相减，则把相减的数加起来并让后面的数比前面的数大1 然后return这个加数和

public static int minOperations(int[] nums) {
	int i = 0,flag = 0; 
	for(i = 0; i < nums.length-1;i ++){
    		if (nums[i] >= nums[i+1]){
    		flag = flag + (nums[i] - nums[i+1])+1;
    		nums[i+1] =nums[i]+1;
		}
	}
  return flag;
}
1
2
3
4
5
6
7
8
9
10

Ⅳ.（leetcode122）买卖股票的最佳时机 II

题目：给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 
这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 
这笔交易所能获得利润 = 6-3 = 3 。
1
2
3
4
5
6
7
8
9
10
11
12
13

思路：两两比较，永远买第二天比第一天大的那只股票

public int maxProfit(int[] prices) {
        int getMoney = 0;
		for (int i = 0; i < prices.length-1;i ++){
			if (prices[i] < prices[i+1])
				getMoney += prices[i+1] - prices[i];
		}
		return getMoney;
}
1
2
3
4
5
6
7
8

Ⅴ.（leetcode1716）计算力扣银行的钱

题目：Hercy 想要为购买第一辆车存钱。他 每天 都往力扣银行里存钱。

最开始，他在周一的时候存入 1 块钱。从周二到周日，他每天都比前一天多存入 1 块钱。在接下来每一个周一，他都会比 前一个周一 多存入 1 块钱。

给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。

示例 1：

输入：n = 4
输出：10
解释：第 4 天后，总额为 1 + 2 + 3 + 4 = 10 。
1
2
3
4
5
6
7
8
9
10
11

思路：因为n给的范围是[1,1000]所以我可以提前给他存好1001个数hahaha，然后n传入是几我就让数组的几个数相加

public int totalMoney(int n) {
    int[] bank = new int[1001];
    int week = 7,arrNum = 0,sumMoney = 0;
     for (int i = 0; i < 143; i++){
        for (int j = i+1; j < week + 1; j++ ){
            bank[arrNum] = j;
            arrNum++;
        }
        week++;
    }
    for (int i = 0; i < n; i ++){
        sumMoney += bank[i];
    }
    return sumMoney;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第二种思路：

3.分治算法

Ⅰ.（leetcode169）多数元素

题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出
现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入：[3,2,3]
输出：3
1
2
3
4
5
6

思路：第一种：力扣上叫摩尔投票，我管它叫暴力模拟！先从第一个元素开始，如果与下一个元素对比相同的话flag记录以下，如果不同从不同的那个元素开始把flag重置为1（因为它自己本身算一个 之前提交的时候就是重置为0了 怎么都没过）如果flag>nums.length那么输出这个元素

第二种：力扣官方解答，分治算法（感觉有点麻烦就没用，应该是我太菜）如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。
我们可以使用反证法来证明这个结论。假设 a 既不是左半部分的众数，也不是右半部分的众数，那么 a 出现的次数少于 l / 2 + r / 2 次，其中 l 和 r 分别是左半部分和右半部分的长度。由于 l / 2 + r / 2 <= (l + r) / 2，说明 a 也不是数组 nums 的众数，因此出现了矛盾。所以这个结论是正确的。
这样以来，我们就可以使用分治法解决这个问题：将数组分成左右两部分，分别求出左半部分的众数 a1 以及右半部分的众数 a2，随后在 a1 和 a2 中选出正确的众数。

//第一种
public int majorityElement(int[] nums) {
		int accept = nums[0];
		int nl = nums.length;
		int flag = 0,res = 0;
		for (int i = 0; i < nl; i++) {
			if (accept != nums[i]) {
				accept = nums[i];
				flag = 1;   //重置为1
			}
			else {
				flag ++;
				if (flag >= nl/2) {
					res = accept;
					break;
				}
			}
		}
		return accept;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//第二种
private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    private int majorityElementRec(int[] nums, int lo, int hi) {
        // base case; the only element in an array of size 1 is the majority
        // element.
        if (lo == hi) {
            return nums[lo];
        }

        // recurse on left and right halves of this slice.
        int mid = (hi - lo) / 2 + lo;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid + 1, hi);

        // if the two halves agree on the majority element, return it.
        if (left == right) {
            return left;
        }

        // otherwise, count each element and return the "winner".
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        return leftCount > rightCount ? left : right;
    }

    public int majorityElement(int[] nums) {
        return majorityElementRec(nums, 0, nums.length - 1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

4.剪枝(组合问题)

Ⅰ.组合问题

特点：从n个数里面选出m个数进行组合(不考虑组合里排列的顺序)
核心代码:（蓝桥杯群里大佬写的模板）

import java.util.Arrays
public static void dfs (int start,int index,int[] a,int[] b){
	if (index + (a.length - start))  // 剪枝
		return ;
	if (index == b.length){ //存满 则输出数组b
		System.out.println(b);
		return ;
	}
	for (int i = start; i <= a.length; i ++){
		b[index] = a[i];
		dfs (i + 1,index + 1,a,b);  // 进入下一层
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5.记忆化

Ⅰ.（leetcode1480）一维数组的动态和

题目:给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
1
2
3
4
5
6
7
8
9

思路：看到题目第一眼竟然想到的不是暴力… 看到解释中有与前一项重合的部分于是就直接让他的加前一项（前一项已经满足题目条件）以此类推

    public int[] runningSum(int[] nums) {
		for (int i = 1;i < nums.length; i ++){
			nums[i] = nums[i-1]+nums[i];
		}
		return nums;
    }
1
2
3
4
5
6

6.动态规划

Ⅰ.（leetcode509）斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
	
示例 1：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：
0 <= n <= 30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

思路：这题不用递归而是用动态规划的方法去解答，思路和上面的记忆化搜索一样，因为记忆化搜索的性质就是动态规划，我们可以先保存之前算出来过的值然后运算进而求出所要的结果

public static int fib(int n) {
    int[] bp = new int[n + 1];
    if (n == 0 || n == 1)
        return n;
    else {
        bp[0] = 0;
        bp[1] = 1;
        for (int i = 2; i < n + 1; i++){
            bp[i] = bp[i - 1] + bp[i - 2];
        }
    }
    return bp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

三、数据结构类

1.

Ⅰ.

四、综合类

1.高精度运算（BigInteger类、BigDecimal类）

Ⅰ.

五、数学类（感受优化）

前言

给自己：做的都是力扣里简单难度的数学题 目标就是做出来然后把代码的时间复杂度
和精简度都做到自己水平的极限 为了是感受什么是优化
1
2

Ⅰ.（leetcode1512）好数对的数目

题目：给你一个整数数组 nums 。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。

返回好数对的数目。

输入：nums = [1,2,3,1,1,3]

输出：4

解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
1
2
3
4
5
6
7
8
9
10
11

思路：冒泡排序思想

public int numIdenticalPairs(int[] nums) {
    int flag = 0;
    for (int i = 0; i < nums.length-1; i++){
        for (int j = i+1; j < nums.length; j++){
            if (nums[i] == nums[j])
                flag++;
        }
    }
    return flag;
}
1
2
3
4
5
6
7
8
9
10

优化后思路：

Ⅱ.（leetcode1822）数组元素积的符号

题目：已知函数 signFunc(x) 将会根据 x 的正负返回特定值：

如果 x 是正数，返回 1 。
如果 x 是负数，返回 -1 。
如果 x 是等于 0 ，返回 0 。
给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。

返回 signFunc(product) 。

示例 1：

输入：nums = [-1,-2,-3,-4,3,2,1]
输出：1
解释：数组中所有值的乘积是 144 ，且 signFunc(144) = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路：判断是否有0，有0直接return 0，反之判断负数的个数，负数为奇数则整体为负，反之亦然

public int arraySign(int[] nums) {
        int up = 0,down = 0,judge = 0;
        for (int num: nums){
            if (num == 0){
                judge = 0;
                break;
            }
            else if (num < 0){
                down++;
                if (down%2 == 0)
                    judge = 1;
                else
                    judge = -1;
            }
            else
                judge = 1;
        }
        return judge;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Ⅲ.（leetcode1281）整数的各位积和之差

题目：给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。

输入：n = 234
输出：15 
解释：
各位数之积 = 2 * 3 * 4 = 24 
各位数之和 = 2 + 3 + 4 = 9 
结果 = 24 - 9 = 15
1
2
3
4
5
6
7
8

思路：用while取位 求积求和最后积和相减 （第一反应写出来的代码）

public int subtractProductAndSum(int n) {
        int product = 1,sum = 0;
        int num,x = n;
        //相乘
        while (x != 0){
            num = x%10;
            product *= num;
            x = x/10;
        }
        //相加
        while (x != 0){
            num = x%10;
            sum += num;
            x = x/10;
        }
        return (product - sum);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

优化后思路：只需要一个while即可

public int subtractProductAndSum(int n) {
        int product = 1,sum = 0,num;
        while (n != 0){
            num = n%10;
            product *= num;
            sum += num;
            n = n/10;
        }
        return (product - sum);
    }
1
2
3
4
5
6
7
8
9
10

Ⅳ.（leetcode1281）6和9 组成的最大数字

给你一个仅由数字 6 和 9 组成的正整数 num。

你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。

请返回你可以得到的最大数字。

示例 1：

输入：num = 9669
输出：9969
解释：
改变第一位数字可以得到 6669 。
改变第二位数字可以得到 9969 。
改变第三位数字可以得到 9699 。
改变第四位数字可以得到 9666 。
其中最大的数字是 9969 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

思路： while取为是从低位往高位取过于麻烦 因此不考虑用while 所以从高位往低位取应转化为字符串然后第一次遇到’6’改成’9’然后break

public int maximum69Number (int num){
        StringBuilder sb = new StringBuilder(String.valueOf(num));
        for (int i = 0;i < sb.length();i ++){
            if (sb.charAt(i) != '9') {
                sb.setCharAt(i, '9');
                break;
            }
        }
        return Integer.parseInt(sb.toString());
    }
1
2
3
4
5
6
7
8
9
10

Ⅴ.（leetcode1551）使数组中所有元素相等的最小操作数

题目：存在一个长度为 n 的数组 arr ，其中 arr[i] = (2 * i) + 1 （ 0 <= i < n ）。

一次操作中，你可以选出两个下标，记作 x 和 y （ 0 <= x, y < n ）并使 arr[x] 减去 1 、arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。最终的目标是使数组中的所有元素都 相等 。题目测试用例将会 保证 ：在执行若干步操作后，数组中的所有元素最终可以全部相等。

给你一个整数 n，即数组的长度。请你返回使数组 arr 中所有元素相等所需的 最小操作数 。

示例 1：

输入：n = 3
输出：2
解释：arr = [1, 3, 5]
第一次操作选出 x = 2 和 y = 0，使数组变为 [2, 3, 4]
第二次操作继续选出 x = 2 和 y = 0，数组将会变成 [3, 3, 3]
示例 2：

输入：n = 6
输出：9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路： 列举前6项即可发现规律，当n>=2时，他的偶数项是从1+到n的前n项的偶数项的和，在n=3时，他的奇数项时从1+到n的前n项的奇数项和（比较绕）

public int minOperations(int n) {
        int res = 0,num = n/2;
        if (n == 1)
            res = 0;
        if (n%2 == 0) {
            res = num * num;
        }
        else if (n%2 != 0 && n >= 3){
            res = num*num+num;
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12

优化后思路（力扣官方）：（实在是想不到这个取整(nn-1)/4 =[nn/4]）

public int minOperations(int n) {
        return n * n / 4;
    }
1
2
3

Ⅵ.（leetcode面试题16.07）最大数值

题目：编写一个方法，找出两个数字a和b中最大的那一个。不得使用if-else或其他比较运算符。

示例：

输入： a = 1, b = 2
输出： 2
1
2
3
4
5
6

思路： 利用数学公式证明如下

public int maximum(int a, int b) {
        return (int)(((long)a+(long)b+Math.abs((long)a-(long)b))/2);
    }
1
2
3