这几天空闲时间多，做题也顺的很。有点小开心。
优美的排序
题目：假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：
第 i 位的数字能被 i 整除
i 能被第 i 位上的数字整除
现在给定一个整数 N，请问可以构造多少个优美的排列？
示例1:
输入: 2
输出: 2
解释:
第 1 个优美的排列是 [1, 2]:
第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除
第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除
第 2 个优美的排列是 [2, 1]:
第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除
第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除
说明:
N 是一个正整数，并且不会超过15。
思路：大胆的想法，n=1-15都列出来，哈哈。这种种类少的测试案例就是想钻一下空子啊。话不多说。这个题我先暴力遍历一下看看。最简单的回溯全跑一遍能有多少种组合。再分别看看这些组合能不能是优美排列。估计会超时。但是实现以后有利于找到规律或者思路。
额，回溯没有超时，居然ac了，虽然低空掠过。我把代码贴出来：
class Solution {
int res = 0;
int n;
public int countArrangement(int N) {
n =N;
List<Integer> list = new ArrayList<Integer>();
for(int i = 1;i<=N;i++) {
list.add(i);
}
dfs(list, 1);
return res;
}
//list存可选择的元素。start是当前凑成数组的位置，从1开始
public void dfs(List<Integer> list,int start) {
if(start == n+1) res++;
for(int i = 0;i<list.size();i++) {
Integer j = list.get(i);
//两个条件都不满足所以没必要递归了
if(start%j != 0 && j%start != 0) continue;
//回溯模板。数组中移除当前选中的元素。递归。放回当前元素。
list.remove(j);
dfs(list, start+1);
list.add(i, j);
}
}
}
其实这里思路还是挺清晰的。就是回溯+剪枝。当发现某个元素在这个位置上不行，直接就不往下走了。我稍微优化下试试。
class Solution {
int res = 0;
public int countArrangement(int N) {
List<Integer> list = new ArrayList<Integer>();
for(int i = 1;i<=N;i++) {
list.add(i);
}
dfs(list, 1);
return res;
}
//list存可选择的元素。start是当前凑成数组的下标
public void dfs(List<Integer> list,int start) {
int len = list.size();
if(len==0) res++;
for(int i = 0;i<len;i++) {
Integer j = list.get(i);
//两个条件都不满足所以没必要递归了
if(start%j != 0 && j%start != 0) continue;
//回溯模板。数组中移除当前选中的元素。递归。放回当前元素。
list.remove(j);
dfs(list, start+1);
list.add(i, j);
}
}
}
这里根据list中的元素判断是不是都放完了就行。没必要比较n的大小。所有可以看成是小小的简化了下代码。虽然性能并没有什么显著的提高。我觉得其实这里还有个优化点。就是不是这个list的remove和add费性能啊。我再去改一下。
class Solution {
int res = 0;
int n;
public int countArrangement(int N) {
n =N;
int[] d = new int[n];
for(int i = 0;i<n;i++) {
d[i] = i+1;
}
dfs(d, 1);
return res;
}
//list存可选择的元素。start是当前凑成数组的下标
public void dfs(int[] d,int start) {
if(start == n+1) res++;
for(int i = 0;i<d.length;i++) {
//小于0说明不能用了。两个条件都不满足所以没必要递归了
if(d[i]<0 || (start%d[i] != 0 && d[i]%start != 0)) continue;
//回溯模板。数组中移除当前选中的元素。递归。放回当前元素。
//这里优化一下，不要移除添加了，改成负数说明这个数不能用了
d[i] = -d[i];
dfs(d, start+1);
d[i] = -d[i];
}
}
}
最后一版的代码性能起码能看了，超过百分之 八十的人了。我去看看性能第一的代码:
总有抖机灵的小伙伴搞我心态。。。
性能第一的代码
下面附上正经一点的性能比较好的一版代码:
class Solution {
public int countArrangement(int N) {
int[] memeroy = new int[(1<<N)];
return dfs(N,memeroy,0,N);
}
public int dfs(int n, int[] memeroy,int state,int num)
{
if(num==0)
return 1;
if(memeroy[state]==-1)
return 0;
if(memeroy[state]!=0)
return memeroy[state];
for(int i=0;i<n;i++)
{
int a = 1<<i;
if((a&state)==0&&((i+1)%num==0||num%(i+1)==0))
{
memeroy[state]+=dfs(n,memeroy,state|a,num-1);
}
}
if(memeroy[state]==0)
{
memeroy[state]=-1;
return 0;
}
return memeroy[state];
}
}
思路本身差不多，很多都是细节处理的优化，我就不多说了，反正能理解生硬的回溯对于这个代码也很好理解的，下一题。
按权重随机选择
题目：给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。也就是说，选取下标 i 的概率为 w[i] / sum(w) 。
示例 1：
输入：
["Solution","pickIndex"]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。
示例 2：
输入：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。
由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。
提示：
1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex 将被调用不超过 10000 次
思路：永远都只有最直观的暴力法思维的我有点不知所措。我第一思路：100000乘10000.最大是十亿分之一的选择。用数组存储。然後随机获取一个看是什么值。稍微优化一点（毕竟十亿个元素的数组，空间绝对溢出）就是随机获取一个值，然後判断这个值落到哪个区间。再计算这个区间对应的元素。反正我是有思路，我去代码实现下。
ac了，代码性能不咋地。我能想到的优化的点就是二分，先贴第一版代码，我去试试优化：
class Solution {
int sum;
int[] d;
Random random = new Random();
public Solution(int[] w) {
d = new int[w.length];
for(int i=0;i<w.length;i++){
sum += w[i];
//随机数小于sum就是当前下标的值。
d[i] = sum;
}
}
public int pickIndex() {
//random可以生成0.所以要+1
int r = random.nextInt(sum)+1;
for(int i = 0;i<d.length;i++) {
if(r<=d[i]) return i;
}
return d.length-1;
}
}
这个题怎么说呢，知道优化的点懒得动手写代码。刚刚去看了性能排行第一的代码，和我想的差不多，我直接贴上来：
class Solution {
Random rand;
int[] sums;
public Solution(int[] w) {
rand = new Random();
sums = new int[w.length];
sums[0] = w[0];
for (int i =1; i < w.length; i++)
sums[i] = sums[i-1] + w[i];
}
public int pickIndex() {
int r = rand.nextInt(sums[sums.length-1])+1;
int left = 0, right = sums.length-1;
while (left < right) {
int mid = (left+right)/2;
if (sums[mid]==r)
return mid;
else if (r > sums[mid]) {
left = mid+1;
} else {
right = mid;
}
}
return right;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(w);
* int param_1 = obj.pickIndex();
*/
这个题因为没啥难度，就一个二分没必要来回说了，下一题。
扫雷游戏
题目：让我们一起来玩扫雷游戏！
给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：
如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的未挖出方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。
注意：
输入矩阵的宽和高的范围为 [1,50]。
点击的位置只能是未被挖出的方块 ('M' 或者 'E')，这也意味着面板至少包含一个可点击的方块。
输入面板不会是游戏结束的状态（即有地雷已被挖出）。
简单起见，未提及的规则在这个问题中可被忽略。例如，当游戏结束时你不需要挖出所有地雷，考虑所有你可能赢得游戏或标记方块的情况。
题目截图1
题目截图2
思路：这个题怎么说呢，因为之前没玩过扫雷。所以特意去试了下扫雷的玩法。。。然后玩了一个晚上才ac困难难度的。现在还脖子疼。。哈哈，总体而言这个题题目和扫雷规则相同。是个挺有意思的情况。分三种情况：1.点开雷。炸了。 2.点开周围没有雷的格子，递归开启好多。 3，点开上下左右对角线8个块有雷的，返回雷的个数。这个题目应该不难，也就递归那里比较复杂。我去实现下试试。
好了，代码实现了，挺有意思的一个题。有种莫名的自信。给我一个前端。我还你一个扫雷。哈哈。
class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int r = click[0];
int c = click[1];
int br = board.length;
int bc = board[0].length;
// 直接挖出地雷了。
if (board[r][c] == 'M') {
board[r][c] = 'X';
return board;
}
// 挖的点周围有地雷，这样也不需要扩散
int sum = aroundNum(board, r, c);
// 挖的这点周围有地雷，直接显示数字
if (sum != 0) {
board[r][c] = (char) (sum + '0');
return board;
} else {// 最后一种情况，周围都没地雷，可以扩散的
board[r][c] = 'B';
dfs(board, r, c);
return board;
}
}
public void dfs(char[][] board, int r, int c) {
int br = board.length;
int bc = board[0].length;
// 走到这是前提是可以扩散.所以周围直接扩散就行了
for (int i = r - 1; i <= r + 1; i++) {
for (int j = c - 1; j <= c + 1; j++) {
if (i >= 0 && i < br && j >= 0 && j < bc) {
//如果这个元素已经判断过了，没必要重复判断了
if(board[i][j] != 'E') continue;
int sum = aroundNum(board, i, j);
if(sum == 0) {//这个数还可以扩散
board[i][j] = 'B';//当前元素周围都没雷，所以B
dfs(board, i, j);
}else {//不能扩散了，当前的改成正常的
board[i][j] = (char)(sum+'0');
}
}
}
}
}
public int aroundNum(char[][] board, int r, int c) {
int br = board.length;
int bc = board[0].length;
int sum = 0;
// 判断周围的点有没有地雷。走到这里自己肯定不是地雷了
for (int i = r - 1; i <= r + 1; i++) {
for (int j = c - 1; j <= c + 1; j++) {
// i,j都没越界
if (i >= 0 && i < br && j >= 0 && j < bc) {
if(i==r&&j==c) continue;
if (board[i][j] == 'M')
sum++;
}
}
}
return sum;
}
}
这个题其实思路很简单，就是扩散那里比较麻烦。说不上难，要求细心。我反正是编译器里一遍遍debug写出来的，超级有成就感的，哈哈。感觉代码写的比较清晰，所以就不多说什么了，下一题了。
TinyURL的加密与解密
题目：TinyURL是一种URL简化服务， 比如：当你输入一个URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk.要求：设计一个 TinyURL 的加密 encode 和解密 decode 的方法。你的加密和解密算法如何设计和运作是没有限制的，你只需要保证一个URL可以被加密成一个TinyURL，并且这个TinyURL可以用解密方法恢复成原本的URL。
思路：怎么说呢，又是一道开放题。这种要思路的我就很慌怕自己做的不好也没提示。然后还要看评论去被打击。。反正这种题绝对是可以原样返回的，评论区绝对有小可爱这么做了，哈哈。我目前的想法是key-value存储。去试试
发现个问题，leetcode中没有UUID。所以我的想法就这么折腰了。。并且我直接看题解了，附上代码：
public class Codec {
Map<Integer, String> map = new HashMap<>();
public String encode(String longUrl) {
map.put(longUrl.hashCode(), longUrl);
return "http://tinyurl.com/" + longUrl.hashCode();
}
public String decode(String shortUrl) {
return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));
这个题不是我喜欢的那种题，所以也不看性能第一的代码了，下一题吧。
复数乘法
题目：给定两个表示复数的字符串。返回表示它们乘积的字符串。注意，根据定义 i2 = -1 。
示例 1:
输入: "1+1i", "1+1i"
输出: "0+2i"
解释: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i ，你需要将它转换为 0+2i 的形式。
示例 2:
输入: "1+-1i", "1+-1i"
输出: "0+-2i"
解释: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i ，你需要将它转换为 0+-2i 的形式。
注意:
输入字符串不包含额外的空格。
输入字符串将以 a+bi 的形式给出，其中整数 a 和 b 的范围均在 [-100, 100] 之间。输出也应当符合这种形式。
思路：一点不开玩笑，这个题看的我脑壳痛。。真的看不懂。我用测试案例去试试吧。不是，这个力扣找个语文好点的出题这么难么？感觉应该还有什么坑，不然这么字面量看这个题好简单啊。我去代码试试水。
题意
这个题居然真的就是字面意思，也没啥坑。一次ac。。我直接贴代码：
class Solution {
public String complexNumberMultiply(String a, String b) {
//因为确定是 a+bi的形式。所以找出a b 就行了。
//这里因为+是java中的链接符号。所以不能直接用来分割，要\\转义
String[] arr = a.split("\\+");
String[] brr = b.split("\\+");
int a1 = Integer.valueOf(arr[0]);
//最后一个是i。所以截去
int a2 = Integer.valueOf(arr[1].substring(0, arr[1].length()-1));
int b1 = Integer.valueOf(brr[0]);
int b2 = Integer.valueOf(brr[1].substring(0, brr[1].length()-1));
//最终肯定是有四个结果.数字相乘。 数字*字母（两个） 字母*字母(因为i方是-1.所以这里一起算了)
//因为i方是-1.所以这里直接取反就行了
int one = a1*b1-(a2*b2);
int two = (a1*b2)+(b1*a2);
return one+"+"+two+"i";
}
}
因为本来我是想试试坑在哪里，所以细节处理也不咋地，居然性能也还行。我尽量去改改再试试。我觉得这里性能耗费主要是字符串分割和截取了，循环一下试试。
事实证明自己写算出a和b更加性能差了。我直接去看看性能排行第一的代码吧：
class Solution {
public String complexNumberMultiply(String a, String b) {
int indexa = a.indexOf('+'), indexb = b.indexOf('+');
int a1 = Integer.valueOf(a.substring(0, indexa)), ai = Integer.valueOf(a.substring(indexa + 1, a.indexOf('i')));
int b1 = Integer.valueOf(b.substring(0, indexb)), bi = Integer.valueOf(b.substring(indexb + 1, b.indexOf('i')));
int resa = a1 * b1 - ai * bi, resb = a1 * bi + ai * b1;
StringBuffer buffer = new StringBuffer();
buffer.append(resa).append('+').append(resb).append('i');
return buffer.toString();
}
}
一样的思路，就是人家处理的更好。明明indexOf我都用过好多次了，为什么居然没想到！！！太难了。。哎，反正这个题还算好，勉强复习了个知识点不能用“+”号分割字符。下一题吧。
最小时间差
题目：给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
示例 1：
输入：timePoints = ["23:59","00:00"]
输出：1
示例 2：
输入：timePoints = ["00:00","23:59","00:00"]
输出：0
提示：
2 <= timePoints <= 2 * 104
timePoints[i] 格式为 "HH:MM"
思路：这个题怎么说呢。大胆的想法就是从0点开始，手写排序。首尾相连判断最小值。反正是有思路。我去实现下。刚刚做的时候发现不对。这样其实不怎么好。毕竟排序完了还要算时间差。还不如一开始就换成从0开始的分钟数呢。
第一版本代码，性能超过百分之八十三，我觉得还可以了。
class Solution {
public int findMinDifference(List<String> timePoints) {
List<Integer> list = new ArrayList<Integer>();
for(String s:timePoints) {
Integer i = Integer.valueOf(s.substring(0, 2))*60+Integer.valueOf(s.substring(3));
if(list.contains(i)) return 0;
list.add(i);
}
Collections.sort(list);
//绕圈的加一个
list.add(list.get(0)+1440);
int min = 1440;
for(int i=0;i<list.size()-1;i++) {
min = Math.min(list.get(i+1)-list.get(i), min);
}
return min;
}
}
气死上面的代码除了绕圈一下。第一个值换成下一天的。剩下的没啥值得说的了，挺简单的一个题目。我去看看性能第一的代码能不能有亮点：
数字获取方法改一下性能立刻上来了
这个代码也没多神气，就是获取时间数值的时候换个方法就好了，所以也就这样了，下一题吧。
有序数组中的单一元素
题目：给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: [3,3,7,7,10,11,11]
输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
思路：这个题怎么说呢，单纯的实现闭着眼都行，但是这个O（logN）的时间复杂度让这个题有了难度。首先说下不要求时间复杂度的方法：全部异或一下。最终剩下来的就是落单那个（因为相同数字异或是0）。或者遍历一下。i+2.第一个和下个不一样的是那个唯一的那个。不过因为这个题要求logN的时间复杂度。一说logN就想到二分。二分找中间那个元素。如果是偶数并和下一个一样说明唯一的在后面。如果是偶数和前面的一样说明唯一的在前面（这个很好理解，说的是下标。从0开始两个两个成对出现。0，1 /2,3看到没。如果有落单的会变成 5，6/7，8。大概的理解下意思）。一直二分到找到元素，应该是logN的时间复杂度。也不用额外的空间。我去实现了。
最近第一次一次ac性能超过百分百的，莫名自豪啊，哈哈。
class Solution {
public int singleNonDuplicate(int[] nums) {
if(nums.length == 0) return 0;
if(nums.length == 1) return nums[0];
int left = 0;
int rigth = nums.length-1;
while(left<rigth) {
int mid = (rigth-left)/2+left;//防溢出
//mid是偶数
if((mid&1)==0) {
//如果mid是偶数，并且与前一个相同。说明唯一的在前面
if(mid>0 && nums[mid]==nums[mid-1]) {
rigth = mid-1;
//如果和后一个相同，说明唯一的在后面
}else if(mid<rigth && nums[mid] == nums[mid+1]){
left = mid+1;
}else {//到这只能说mid没有与之相同的元素，答案就是mid
return nums[mid];
}
}else {//mid是奇数。
if(mid>0 && nums[mid]==nums[mid-1]) {
left = mid+1;
//如果和后一个相同，说明唯一的在前面
}else if(mid<rigth && nums[mid] == nums[mid+1]){
rigth = mid-1;
}else {//到这只能说mid没有与之相同的元素，答案就是mid
return nums[mid];
}
}
}
return nums[left];
}
}
这个思路其实简单的很，就是一个二分完美的做到了logN的时间复杂度。也就是判断要稍微复杂一点，反正这个也没啥好说的了，我的经验就是遇到logN，先想到二分。
这篇笔记就记到这里了，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！
网友评论