笔经整理3

题目来源：力扣 462/840/1006/433/112/78/784/875

力扣462. 最少移动次数使数组元素相等 II

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。

例如:

输入:
[1,2,3]

输出:
2

说明：
只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）：

[1,2,3] => [2,2,3] => [2,2,2]

思路：排序后，中位数就是所求 target，然后计算其他成员距此 target 的距离之和。

如果中位数是两个，两个都可以是 target，最终结果都一样，所以任选其一即可。

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

public class 最少移动次数使数组元素相等II {

	@Test
	public void testResult() {
		int[] nums = {1, 2, 3};
		Assert.assertEquals(2, minMoves2(nums));
	}

	public int minMoves2(int[] nums) {
		if (null == nums || nums.length < 2) {
			return 0;
		}
		Arrays.sort(nums);
		int target = nums[nums.length / 2];
		int ret = 0;
		for (int i = 0; i < nums.length; ++i) {
			ret += Math.abs(target - nums[i]);
		}
		return ret;
	}
}

---

力扣 840. 矩阵中的幻方

3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。

示例：

输入: [[4,3,8,4],
[9,5,1,9],
[2,7,6,2]]
输出: 1
解释:
下面的子矩阵是一个 3 x 3 的幻方：
438
951
276

而这一个不是：
384
519
762

总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
提示:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15

思路：

1. 这题不难，就是恶心，注意点：数值需要保证在 1~9 之前，数值需要各不相同
2. 正中心的数据就必须是 5 了（本解法未体现），但是暴力穷举的逻辑还是免不了

import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class 矩阵中的幻方 {

	@Test
	public void testResult() {
		int[][] grid = {{4, 3, 8, 4}, {9, 5, 1, 9}, {2, 7, 6, 2}};
		int ret = numMagicSquaresInside(grid);
		Assert.assertEquals(1, ret);
	}

	@Test
	public void testResult1() {
		int[][] grid = {{5, 5, 5}, {5, 5, 5}, {5, 5, 5}};
		int ret = numMagicSquaresInside(grid);
		Assert.assertEquals(0, ret);
	}

	@Test
	public void testResult2() {
		int[][] grid = {{10, 3, 5}, {1, 6, 11}, {7, 9, 2}};
		int ret = numMagicSquaresInside(grid);
		Assert.assertEquals(0, ret);
	}


	public int numMagicSquaresInside(int[][] grid) {
		int m = grid.length;
		if (m < 3) {
			return 0;
		}
		int n = grid[0].length;
		if (n < 3) {
			return 0;
		}
		int ret = 0;
		for (int i = 1; i < m - 1; ++i) {
			for (int j = 1; j < n - 1; ++j) {
				if (isGrid(grid, i, j)) {
					ret++;
				}
			}
		}
		return ret;
	}

	private boolean isGrid(int[][] grid, int x, int y) {

		boolean flag = isSameValue(grid, x, y);
		if (!flag) {
			return false;
		}
		int[] sum = new int[8];
		sum[0] = grid[x - 1][y - 1] + grid[x - 1][y] + grid[x - 1][y + 1];
		sum[1] = grid[x][y - 1] + grid[x][y] + grid[x][y + 1];
		sum[2] = grid[x + 1][y - 1] + grid[x + 1][y] + grid[x + 1][y + 1];

		sum[3] = grid[x - 1][y - 1] + grid[x][y - 1] + grid[x + 1][y - 1];
		sum[4] = grid[x - 1][y] + grid[x][y] + grid[x + 1][y];
		sum[5] = grid[x - 1][y + 1] + grid[x][y + 1] + grid[x + 1][y + 1];

		sum[6] = grid[x - 1][y - 1] + grid[x][y] + grid[x + 1][y + 1];
		sum[7] = grid[x - 1][y + 1] + grid[x][y] + grid[x + 1][y - 1];

		for (int i = 1; i < sum.length; i++) {
			flag = (sum[i - 1] == sum[i]);
			if (!flag) {
				return false;
			}
		}
		return flag;
	}

	private boolean isSameValue(int[][] grid, int x, int y) {
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = -1; i < 2; ++i) {
			for (int j = -1; j < 2; ++j) {
				int temp = grid[x + i][y + j];
				if (temp < 1 || temp > 9) {
					return false;
				}
				if (map.containsKey(temp)) {
					return false;
				} else {
					map.put(temp, 1);
				}
			}
		}
		return true;
	}
}

---

力扣 1006. 笨阶乘

通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。

例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。

另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。

示例 1：

输入：4
输出：7
解释：7 = 4 * 3 / 2 + 1
示例 2：

输入：10
输出：12
解释：12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

思路：

1. 当 N>4时，N * (N-1)/(N-2) = N + 1 始终成立，所以(N+1) - N * (N-1)/(N-2) = N + 1总是等于 0，所以可以做适当的消项

2. 当 N>4 时，结果分别是 N+1,N+2,N+2,N-1

import org.junit.Assert;
import org.junit.Test;

public class 笨阶乘 {

	@Test
	public void testResult1() {
		int ret = clumsy(4);
		Assert.assertEquals(7, ret);
	}

	@Test
	public void testResult2() {
		int ret = clumsy(10);
		Assert.assertEquals(12, ret);
	}

	// 当 N>3 时，N * (N-1)/(N-2) = N + 1 始终成立
	public int clumsy(int N) {
		int[] smallNum = {7, 1, 2, 6};
		int[] num = {1, 2, 2, -1};
		return N > 4 ? N + num[N % 4] : smallNum[N % 4];
	}
}

---

433. 最小基因变化

一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 “A”, “C”, “G”, “T”中的任意一个。

假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。

例如，基因序列由”AACCGGTT” 变化至 “AACCGGTA” 即发生了一次基因变化。

与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。

现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。

注意:

起始基因序列默认是合法的，但是它并不一定会出现在基因库中。
所有的目标基因序列必须是合法的。
假定起始基因序列与目标基因序列是不一样的。

思路：BFS 的经典问题，还是很简单的

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class 最小基因变化 {

	@Test
	public void testResult() {
		String start = "AACCGGTT";
		String end = "AACCGGTA";
		String[] bank = {"AACCGGTA"};
		int ret = minMutation(start, end, bank);
		Assert.assertEquals(1, ret);
	}

	@Test
	public void testResult1() {
		String start = "AACCGGTT";
		String end = "AAACGGTA";
		String[] bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
		int ret = minMutation(start, end, bank);
		Assert.assertEquals(2, ret);
	}

	@Test
	public void testResult2() {
		String start = "AAAAACCC";
		String end = "AACCCCCC";
		String[] bank = {"AAAACCCC", "AAACCCCC", "AACCCCCC"};
		int ret = minMutation(start, end, bank);
		Assert.assertEquals(3, ret);
	}

	public int minMutation(String start, String end, String[] bank) {
		List<String> bankList = new ArrayList<>(Arrays.asList(bank));
		Collections.sort(bankList);
		if (!bankList.contains(end)) {
			return -1;
		}
		List<String> stage1 = findStage1List(start, bankList);
		Queue<String> q = new LinkedList<String>() {{addAll(stage1);}};
		Map<String, Integer> visitMap = new HashMap<>();
		stage1.forEach(str -> visitMap.put(str, 1));

		while (!q.isEmpty()) {
			String top = q.poll();
			if (end.equals(top)) {
				return visitMap.get(top);
			}
			List<String> nextList = findStage1List(top, bankList);
			for (String str : nextList) {
				if (!visitMap.containsKey(str)) {
					visitMap.put(str, visitMap.get(top) + 1);
					q.add(str);
				}
			}

		}
		return -1;
	}

  // 查找相差一个字符的字符串列表
	private List<String> findStage1List(String start, List<String> bankList) {
		List<String> firstStageList = new ArrayList<>();
		for (String bank : bankList) {
			if (only1diff(start, bank)) {
				firstStageList.add(bank);
			}
		}
		return firstStageList;
	}

  // 判断是否只差一个字符
	private boolean only1diff(String str1, String str2) {
		if (null == str1 || null == str2 || str1.length() != str2.length()) {
			return false;
		}
		int count = 0;
		for (int i = 0; i < str1.length(); ++i) {
			if (str1.charAt(i) != str2.charAt(i)) {
				count++;
			}
		}
		if (count == 1) {
			return true;
		}
		return false;
	}
}

---

112. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思路：太简单了，不值一提，不过 sum 逐级减值是个不错的思路。

import org.junit.Assert;
import org.junit.Test;

public class 路径总和 {

	@Test
	public void testResult() {
		int sum = 22;

		TreeNode root1 = new TreeNode(1);
		TreeNode root7 = new TreeNode(7);
		TreeNode root2 = new TreeNode(2);
		TreeNode root11 = new TreeNode(11);
		TreeNode root13 = new TreeNode(13);
		TreeNode root4 = new TreeNode(4);
		TreeNode root4II = new TreeNode(4);
		TreeNode root8 = new TreeNode(8);
		TreeNode root5 = new TreeNode(5);
		root11.left = root7;
		root11.right = root2;
		root4.right = root1;
		root4II.left = root11;
		root8.left = root13;
		root8.right = root4;
		root5.left = root4II;
		root5.right = root8;
		boolean ret = hasPathSum(root5, sum);
		Assert.assertEquals(true, ret);
	}

	public boolean hasPathSum(TreeNode root, int sum) {
		if (root != null) {
			if (root.left == null && root.right == null && sum - root.val == 0) {
				return true;
			}
			return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
		}
		return false;
	}

	// Definition for a binary tree node.
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
}

---

78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

思路： set 去重，回溯法求解，简单

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

public class 子集 {

	@Test
	public void testResult() {
		int[] nums = {1, 2, 3};
		List<List<Integer>> result = subsets(nums);
		result.forEach(System.out::println);
	}


	public List<List<Integer>> subsets(int[] nums) {
		List<Integer> numList = Arrays.stream(nums).boxed().collect(Collectors.toList());
		Collections.sort(numList);
		Set<Set<Integer>> ret = new HashSet<>();
		Set<Integer> singleSet = new HashSet<>();
		subsets(numList, singleSet, ret);
		List<List<Integer>> result = new ArrayList<>();
		ret.forEach( set -> {
			List<Integer> list = set.stream().collect(Collectors.toList());
			result.add(list);
		});
		return result;
	}

	private void subsets(List<Integer> numList, Set<Integer> singleSet, Set<Set<Integer>> ret) {
		if (numList.size() == 0) {
			Set<Integer> tempSet = new HashSet<>(singleSet);
			ret.add(tempSet);
			return;
		}
		int firstNum = numList.get(0);
		numList.remove(0);
		singleSet.add(firstNum);
		subsets(numList,singleSet,ret);
		singleSet.remove(singleSet.remove(firstNum));
		subsets(numList,singleSet,ret);
		numList.add(0,firstNum);
	}
}

---

784. 字母大小写全排列

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例:
输入: S = “a1b2”
输出: [“a1b2”, “a1B2”, “A1b2”, “A1B2”]

输入: S = “3z4”
输出: [“3z4”, “3Z4”]

输入: S = “12345”
输出: [“12345”]
注意：

S 的长度不超过12。
S 仅由数字和字母组成。

思路：回溯法的思想。Character.isUpperCase()记得巧用

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class 字母大小写全排列 {

	@Test
	public void testResult() {
		String s = "a1b2";
		List<String> ret = letterCasePermutation(s);
		ret.forEach(System.out::println); // ["a1b2", "a1B2", "A1b2", "A1B2"]
	}
	@Test
	public void testResult2() {
		String s = "12345";
		List<String> ret = letterCasePermutation(s);
		ret.forEach(System.out::println); // ["12345"]
	}
	@Test
	public void testResult3() {
		String s = "3z4";
		List<String> ret = letterCasePermutation(s);
		ret.forEach(System.out::println); // ["3z4", "3Z4"]
	}

	public List<String> letterCasePermutation(String S) {
		List<String> ret = new ArrayList<>();
		String str = "";
		letterCasePermutation(ret, S, str, 0);
		return ret;
	}

	private void letterCasePermutation(List<String> ret, String S, String str, int index) {
		if (index == S.length()) {
			String temp = new String(str);
			ret.add(temp);
			return;
		}
		char c = S.charAt(index);
		str += c;
		letterCasePermutation(ret, S, str, index + 1);
		str = str.substring(0, str.length() - 1);
		if (Character.isAlphabetic(c)) {
			str += changeCase(c);
			letterCasePermutation(ret, S, str, index + 1);
		}
	}

  // 切换大小写
	private char changeCase(char c) {
		if (Character.isUpperCase(c)) {
			return Character.toLowerCase(c);
		} else {
			return Character.toUpperCase(c);
		}
	}
}

---

875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例 1：

输入: piles = [3,6,7,11], H = 8
输出: 4
示例 2：

输入: piles = [30,11,23,4,20], H = 5
输出: 30
示例 3：

输入: piles = [30,11,23,4,20], H = 6
输出: 23

思路：二分查找，不然容易超时

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

public class 爱吃香蕉的珂珂 {

	@Test
	public void testResult1() {
		int[] piles = {3, 6, 7, 11};
		Assert.assertEquals(4, minEatingSpeed(piles, 8));
	}

	@Test
	public void testResult2() {
		int[] piles2 = {30, 11, 23, 4, 20};
		Assert.assertEquals(30, minEatingSpeed(piles2, 5));
	}

	@Test
	public void testResult3() {
		int[] piles2 = {30, 11, 23, 4, 20};
		Assert.assertEquals(23, minEatingSpeed(piles2, 6));
	}

	public int minEatingSpeed(int[] piles, int H) {
		Arrays.sort(piles);
		int i = 1, j = piles[piles.length-1];
		while(i<j){
			int mid = (i+j)/2;
			if(canEatOver(piles,H,mid)){
				j = mid;
			}else{
				i = mid+1;
			}
		}
		return i;
	}

	private boolean canEatOver(int[] piles, int H, int i) {
		int sum = 0;
		for (int pile : piles) {
			sum += Math.ceil(1.0 * pile / i);
		}
		return sum <= H;
	}
}

---