二维网格迁移
题目：给你一个 n 行 m 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。每次「迁移」操作将会引发下述活动：
位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
位于 grid[m - 1][ - 1] 的元素将会移动到 grid[0][0]。
请你返回 k 次迁移操作后最终得到的 二维网格。提示：
1 <= grid.length <= 50
1 <= grid[i].length <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100
思路：感觉这个题很简单啊，其实数组会觉得很麻烦，但是如果用list表示，只不过是把最后一个元素删除，把这个值addFirst插入到第一个元素就ok了。最后再把这个list按照行列分开就行了，我去实现了。
咳咳，想法很丰满，现实略骨感。。完成是完成了，性能就一言难尽了，，我先贴代码吧：
class Solution {
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
LinkedList<Integer> list = new LinkedList<Integer>();
for(int[] i : grid){
for(int n : i){
list.add(n);
}
}
for(int i = 0;i<k;i++){
int n = list.get(list.size()-1);
list.removeLast();
list.addFirst(n);
}
List<List<Integer>> res = new ArrayList<List<Integer>>();
int idx = 0;
for(int i = 0;i<grid.length;i++){
List<Integer> sub = new ArrayList<Integer>();
for(int j = 0; j<grid[0].length;j++){
sub.add(list.get(idx++));
}
res.add(sub);
}
return res;
}
}
接下来用常规的办法去做了。
class Solution {
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
int m=grid.length,n=grid[0].length;
List<List<Integer>> list=new ArrayList();
int l=n*m;
int idx=(l-k%l)%l;
for(int i=0;i<m;i++){
List<Integer> alist=new ArrayList<>();
for(int j=0;j<n;j++){
alist.add(grid[idx/n][idx%n]);
idx=(idx+1)%l;
}
list.add(alist);
}
return list;
}
}
这个方法其实比我刚刚的还好，判断第一个元素应该是哪个位置的第几个，然后顺序往下一个个填充，最后填完了从第一个开始再填。然后这到题就这样吧。
访问所有点的最小时间
题目：平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi]。请你计算访问所有这些点需要的最小时间（以秒为单位）。
你可以按照下面的规则在平面上移动：
- 每一秒沿水平或者竖直方向移动一个单位长度，或者跨过对角线（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
- 必须按照数组中出现的顺序来访问这些点。
提示：
points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000
思路：这个题就这样，其实仔细看看就能看到两点间最短距离的公式，就是能斜着先斜着走，最后不能斜着了再走直线（横着走竖着走看xy大小）反正情况就是这样，也可以自己找点带入试试。也就是两个点的最小距离是经纬度差较大的那个。剩下的没难度了，一点点加吧。我去实现了。
emmmm...思路没问题，性能也没翻车，一次过，性能超过百分百。我直接上代码：
class Solution {
public int minTimeToVisitAllPoints(int[][] points) {
int res = 0;
for(int i = 0 ;i< points.length-1;i++){
res += Math.max(Math.abs(points[i][0]-points[i+1][0]),Math.abs(points[i][1]-points[i+1][1]));
}
return res;
}
}
找出井字棋的获胜者
题目：A 和 B 在一个 3 x 3 的网格上玩井字棋。井字棋游戏的规则如下：
玩家轮流将棋子放在空方格 (" ") 上。
第一个玩家 A 总是用 "X" 作为棋子，而第二个玩家 B 总是用 "O" 作为棋子。
"X" 和 "O" 只能放在空方格中，而不能放在已经被占用的方格上。
只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。
如果所有方块都放满棋子（不为空），游戏也会结束。
游戏结束后，棋子无法再进行任何移动。
给你一个数组 moves，其中每个元素是大小为 2 的另一个数组（元素分别对应网格的行和列），它按照 A 和 B 的行动顺序（先 A 后 B）记录了两人各自的棋子位置。如果游戏存在获胜者（A 或 B），就返回该游戏的获胜者；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。你可以假设 moves 都 有效（遵循井字棋规则），网格最初是空的，A 将先行动。
思路：剩下的就不画了，反正没结束的一种是不足5步，因为必然一人一次，不足五步凑不出来三次，所以没完成。。剩下都要判断。目前思路是先把数组填完了，再创建一个方法专门判断填完的数组是否有胜利者，还是没下完还是平局。我去实现了。
好了，做出来了，我自己都没想到又性能超过百分百了。其实因为这个是3乘3的格子，所以可以直接字面量写，而且我在方法中也没用双层循环而是手动+1，+2的，不推荐和我学啊。我直接贴代码：
class Solution {
public String tictactoe(int[][] moves) {
if(moves.length<5) return "Pending";
int[][] d = new int[3][3];
//a下棋填1 ， b下棋填-1
for(int i=0;i<moves.length;i++){
if((i&1)==0) {
d[moves[i][0]][moves[i][1]] = 1;
}else{
d[moves[i][0]][moves[i][1]] = -1;
}
}
return tool(d);
}
public String tool(int[][] d){
for(int i = 0;i<3;i++){
if(d[i][0]+d[i][1]+d[i][2]==3) return "A";
if(d[i][0]+d[i][1]+d[i][2]==-3) return "B";
if(d[0][i]+d[1][i]+d[2][i]==3) return "A";
if(d[0][i]+d[1][i]+d[2][i]==-3) return "B";
}
if(d[0][0]+d[1][1]+d[2][2]==3) return "A";
if(d[0][0]+d[1][1]+d[2][2]==-3) return "B";
if(d[2][0]+d[1][1]+d[0][2]==3) return "A";
if(d[2][0]+d[1][1]+d[0][2]==-3) return "B";
int n = 0;
for(int i = 0; i<3;i++){
for(int j = 0;j<3;j++){
if(d[i][j]==0) n++;
}
}
//走到这说明没3个连上的，只要判断是没下完还是平局就行了
return n==0?"Draw":"Pending";
}
}
其实直到现在为止我都觉得我的笔记做的越来越不好了。因为刚刚刷算法题的时候我自己确实觉得很难，很费解。所以把思路，遇到的坑和注意的点都一一罗列。而现在我感觉大多数都是一次过，都不知道要注意什么了（真的不是在炫耀和吹嘘，感觉都是基本知识）如果亲们看了以后觉得我写的不够明确看的不是很明白可以私聊我或者评论，我看到了一定回。
好了，这道题就这么过，下一题了。
整数的各位积和之差
题目：给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
示例 1：
输入：n = 234
输出：15
解释：
各位数之积 = 2 * 3 * 4 = 24
各位数之和 = 2 + 3 + 4 = 9
结果 = 24 - 9 = 15
示例 2：
输入：n = 4421
输出：21
解释：
各位数之积 = 4 * 4 * 2 * 1 = 32
各位数之和 = 4 + 4 + 2 + 1 = 11
结果 = 32 - 11 = 21
提示：
1 <= n <= 10^5
思路：简直又是送分题，思路求出各个位数，直接相加和相乘，一次遍历。我去实现了。
额，做是做出来，我不知道为啥性能1ms，只超过百分之40的人，先贴代码再优化:
class Solution {
public int subtractProductAndSum(int n) {
int h = 0;
int j = 1;
while(n>0){
int x = n%10;
h += x;
j *= x;
n = n/10;
}
return j-h;
}
}
感觉优化点应该在细节。我再去看看。好了，没有优化点，只能看脸，一样的代码二次提交超过百分百了：
有序数组中出现次数超过百分之二十五的元素
题目：给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。请你找到并返回这个整数
示例：
输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6
提示：
1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5
思路：这个题怎么说呢，肯定是做过！然后目前两种思路：一种是数组下标代替值，然后数组值超过百分之25直接返回。另一种就是一次遍历，直接遍历到计数超过百分之二十五的返回，感觉这个直接遍历就行了。我去实现了。
第一版本代码，性能超过百分之七十。直接贴：
class Solution {
public int findSpecialInteger(int[] arr) {
if(arr.length==1) return arr[0];
int count = 1;
int n = arr.length/4;
for(int i = 0; i< arr.length-1;i++){
if(arr[i]==arr[i+1]){
count++;
if(count>n) return arr[i];
}else{
count = 1;
}
}
return -1;
}
}
接下来去尝试优化了。看了性能排行第一的代码，确实很优雅，我直接贴出来吧，一看就懂，自己想不出来：
class Solution {
public int findSpecialInteger(int[] arr) {
int limit = arr.length/4;
for(int i=0;i<arr.length-limit;i++){
if(arr[i] == arr[i+limit]) {
return arr[i];
}
}
return arr[0];
}
}
二进制链表转整数
题目：给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值 。
示例 1：
输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)
示例 2：
输入：head = [0]
输出：0
示例 3：
输入：head = [1]
输出：1
示例 4：
输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880
示例 5：
输入：head = [0,0]
输出：0
提示：
链表不为空。
链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。
思路：这个题似曾相识又简单的多的多。主要是性能吧。我现在的思路是随着追加随着算。原数乘2加上追加的数。我去实现了。
直接贴代码，性能超过百分百，感觉这种题很简单啊
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int getDecimalValue(ListNode head) {
int res = 0;
while(head!=null){
res = res*2 +head.val;
head = head.next;
}
return res;
}
}
统计位数为偶数的数字个数
题目：给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。
示例 1：
输入：nums = [12,345,2,6,7896]
输出：2
解释：
12 是 2 位数字（位数为偶数）
345 是 3 位数字（位数为奇数）
2 是 1 位数字（位数为奇数）
6 是 1 位数字 位数为奇数）
7896 是 4 位数字（位数为偶数）
因此只有 12 和 7896 是位数为偶数的数字
示例 2：
输入：nums = [555,901,482,1771]
输出：1
解释：
只有 1771 是位数为偶数的数字。
提示：
1 <= nums.length <= 500
1 <= nums[i] <= 10^5
思路：感觉这个直接算就行啊，每一个元素判断是奇数位偶数位。目前打算用数值范围确定，反正最大100000.我去实现了。
又是一次过，性能超过百分百，我直接贴出来，没什么技术含量：
class Solution {
public int findNumbers(int[] nums) {
int res = 0;
for(int i : nums){
if((i>=10 && i<100) || (i>=1000 && i<10000) || i==100000){
res++;
}
}
return res;
}
}
将每个元素替换为右侧最大元素
题目：给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。完成所有替换操作后，请你返回这个数组。
示例：
输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]
提示：
1 <= arr.length <= 10^4
1 <= arr[i] <= 10^5
思路：这个题怎么说呢，感觉比前两个题稍微复杂点，目前的想法就是从右往前取最大值，替换给前一个元素，我去实现下。
好的吧，我夸早了，也是一次过。我直接贴代码：
class Solution {
public int[] replaceElements(int[] arr) {
int max = -1;
for(int i = arr.length-1;i>0;i--){
int n = arr[i];
arr[i] = max;
max = Math.max(max,n);
}
arr[0] = max;
return arr;
}
}
性能2ms，我感觉可以微调一下，我去试试怎么提升性能。
好了，就调整一下，把Math.max换成三目运算就1ms，超过百分百了，我贴出来下一题了：
class Solution {
public int[] replaceElements(int[] arr) {
int max = -1;
for(int i = arr.length-1;i>0;i--){
int n = arr[i];
arr[i] = max;
max = max>n?max:n;
}
arr[0] = max;
return arr;
}
}
和为0的N个唯一整数
题目：给你一个整数 n，请你返回 任意 一个由 n 个 各不相同 的整数组成的数组，并且这 n 个数相加和为 0 。
示例 1：
输入：n = 5
输出：[-7,-1,1,3,4]
解释：这些数组也是正确的 [-5,-1,1,2,3]，[-3,-1,2,-2,4]。
示例 2：
输入：n = 3
输出：[-1,0,1]
示例 3：
输入：n = 1
输出：[0]
提示：
1 <= n <= 1000
思路：还有三道题所有简单的都刷完了，有点小激动啊~继续说这个题，首先能正能负就几乎没难度了，正n，负n，正n-1，负n-1...一点点往后找呗。。单数的话中间是0，双数没中间数。就这个思路，我去代码实现了。
emmmm...刚刚群里看半天吵架才开始做题，笑死我了，java技术交流群吵哲学问题。。。
言归正传，这个题我思路没问题，直接贴代码然后下一题了：
class Solution {
public int[] sumZero(int n) {
int[] res = new int[n];
int idx = 0;
//奇数
if((n&1)==1){
res[idx] = 0;
idx++;
}
int x = 1;
while(idx<n){
res[idx] = x;
idx++;
res[idx] = -x;
idx++;
x++;
}
return res;
}
}
解码字母到整数硬设
题目:给你一个字符串 s，它由数字（'0' - '9'）和 '#' 组成。我们希望按下述规则将 s 映射为一些小写英文字符：
字符（'a' - 'i'）分别用（'1' - '9'）表示。
字符（'j' - 'z'）分别用（'10#' - '26#'）表示。
返回映射之后形成的新字符串。题目数据保证映射始终唯一。
示例 1：
输入：s = "10#11#12"
输出："jkab"
解释："j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".
示例 2：
输入：s = "1326#"
输出："acz"
示例 3：
输入：s = "25#"
输出："y"
示例 4：
输入：s = "12345678910#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#"
输出："abcdefghijklmnopqrstuvwxyz"
提示：
1 <= s.length <= 1000
s[i] 只包含数字（'0'-'9'）和 '#' 字符。
s 是映射始终存在的有效字符串。
思路：这个题，主要是看后 两个字符是不是#，是#这这是一整个串，不是#则自己是一个串，然后从前往后遍历。到倒数第三个元素。最后的几个会下标越界所以单独判断，好了，我去实现了。
第一版本出来了，我直接贴代码：
class Solution {
public String freqAlphabets(String s) {
char[] c = s.toCharArray();
StringBuffer sb = new StringBuffer();
for(int i = 0; i<c.length-2;i++){
if(c[i+2]=='#'){
sb.append(getC(c[i]+""+c[i+1]));
i= i+2;
}else{
sb.append(getC(c[i]+""));
}
}
int last = c.length-1;
if(c[last]!='#' && c[last-1]!='#'){
sb.append(getC(c[last-1]+""));
sb.append(getC(c[last]+""));
}else if(c[last]!='#'){
sb.append(getC(c[last]+""));
}
return sb.toString();
}
public char getC(String s) {
int i = Integer.valueOf(s) + 96;
return (char)i;
}
}
做的比较麻烦，而且性能大大的不行，我先去优化。
好了，改完回来了，其实上面的代码性能低就是因为字符串来回来去转，当时做是为了快，简单。现在知道思路是对的自然优化这点就ok了，改成直接char操作就好了，我先贴代码：
class Solution {
public String freqAlphabets(String s) {
char[] c = s.toCharArray();
StringBuffer sb = new StringBuffer();
for(int i = 0; i<c.length-2;i++){
if(c[i+2]=='#'){
sb.append(getC(c[i],c[i+1]));
i= i+2;
}else{
sb.append(getC(c[i]));
}
}
int last = c.length-1;
if(c[last]!='#' && c[last-1]!='#'){
sb.append(getC(c[last-1]));
sb.append(getC(c[last]));
}else if(c[last]!='#'){
sb.append(getC(c[last]));
}
return sb.toString();
}
public char getC(char i , char c ) {
int res = (i-'0')*10 +(c-'0')+96;
return (char)res;
}
public char getC(char i){
return (char)(i-'0'+96);
}
}
上面的代码超过了百分之九十八的人，这个题关于整数，string，char来回来去处理还挺有意思，我看看排名第一的代码怎么做的
好的，看完了，确实更优雅点，就是更简洁，但是思路是一样的，感觉我的代码的最终版也会是这样，我直接贴上来
class Solution {
public String freqAlphabets(String s) {
StringBuilder sb = new StringBuilder();
char[] cs = s.toCharArray();
for (int i = 0; i < cs.length; i++) {
if (i < cs.length - 2 && cs[i + 2] == '#') {
sb.append((char)('j' + (cs[i] - '1') * 10 + cs[i + 1] - '0'));
i += 2;
} else {
sb.append((char)('a' + (cs[i] - '1')));
}
}
return sb.toString();
}
}
解压缩编码列表
题目：给你一个以行程长度编码压缩的整数列表 nums 。考虑每相邻两个元素 [a, b] = [nums[2i], nums[2i+1]] （其中 i >= 0 ），每一对都表示解压后有 a 个值为 b 的元素。请你返回解压后的列表。
示例：
输入：nums = [1,2,3,4]
输出：[2,4,4,4]
提示：
2 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100
思路：这个题目有点类似于之前的报数，只不过比那个简单多了。就是两个一对，单个下标数是元素个数，双下标数是元素值。然后遍历往新数组加，因为不知道数组长所以一开始用最大长度，后来再导就好了，我去实现了。
喏，2ms，超过性能百分百，一次过的。直接贴代码：
class Solution {
public int[] decompressRLElist(int[] nums) {
int[] temp = new int[10001];
int idx = 0;
for(int i = 0; i<nums.length;i=i+2){
while(nums[i]>0){
temp[idx] = nums[i+1];
idx++;
nums[i]--;
}
}
int[] res = new int[idx];
for(int i = 0;i<idx;i++){
res[i] = temp[i];
}
return res;
}
}
将整数转化为两个无0整数的和
题目：「无零整数」是十进制表示中 不含任何 0 的正整数。给你一个整数 n，请你返回一个 由两个整数组成的列表 [A, B]，满足：
A 和 B 都是无零整数
A + B = n
题目数据保证至少有一个有效的解决方案。如果存在多个有效解决方案，你可以返回其中任意一个。
示例 1：
输入：n = 2
输出：[1,1]
解释：A = 1, B = 1. A + B = n 并且 A 和 B 的十进制表示形式都不包含任何 0 。
示例 2：
输入：n = 11
输出：[2,9]
示例 3：
输入：n = 10000
输出：[1,9999]
示例 4：
输入：n = 69
输出：[1,68]
示例 5：
输入：n = 1010
输出：[11,999]
提示：
2 <= n <= 10^4
思路：这道题印象比较深刻，因为这道题是上周日的周赛题，是我当时做出来的，简单的题目。就是麻烦点按位数比较，创建数组，我直接贴代码吧
class Solution {
public int[] getNoZeroIntegers(int n) {
//最大1万。所以如果五位数只能是1万，不然就是四位数
if(n/10000==1) return new int[]{1,9999};
if(n<10) return new int[]{1,n-1};
int[] ar;
if(n>1000){
ar = new int[]{(n/1000)%10,(n/100)%10,(n/10)%10,n%10};
}else if(n>100){
ar = new int[]{(n/100)%10,(n/10)%10,n%10};
}else {
ar = new int[]{(n/10)%10,n%10};
}
int[] ar1 = new int[ar.length];
for(int i = ar.length-1;i>0;i--){
if(ar[i]<2){
ar[i-1]--;
ar1[i] = 5;
ar[i] = ar[i]+5;
}else{
ar[i]--;
ar1[i] = 1;
}
}
int res1 = 0;
int res2 = 0;
for(int i=0;i<ar.length;i++){
res1 = res1*10 + ar[i];
res2 = res2*10 + ar1[i];
}
return new int[]{res1,res2};
}
}
就是我写的比较蠢，而且当时是 真的慌（考试紧张）。但是刚刚看了运行性能还是不错了，超过百分百了。其实应该还有别的方法我去看看。
这个题是新的，所以没有执行时间图，但是可以看到评论，，话不多说直接看图吧，这个方法我觉得我不喜欢，所以也不这么做了。
猜数字
题目：小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3。
示例 1：
输入：guess = [1,2,3], answer = [1,2,3]
输出：3
解释：小A 每次都猜对了。
示例 2：
输入：guess = [2,2,3], answer = [3,2,1]
输出：1
解释：小A 只猜对了第二次。
限制：
guess的长度 = 3
answer的长度 = 3
guess的元素取值为 {1, 2, 3} 之一。
answer的元素取值为 {1, 2, 3} 之一。
思路：我是不是可以理解，再两个数组中，下标相同值相同就是一次？感觉题目就是这样啊，我先按照这个思路去做了。
一次过，这个纯送分题：
class Solution {
public int game(int[] guess, int[] answer) {
int res = 0;
for(int i = 0; i<guess.length;i++){
if(guess[i]==answer[i]) res++;
}
return res;
}
}
分式化简
题目：连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。输入的cont代表连分数的系数（cont[0]代表上图的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。
示例 1：
输入：cont = [3, 2, 0, 2]
输出：[13, 4]
解释：原连分数等价于3 + (1 / (2 + (1 / (0 + 1 / 2))))。注意[26, 8], [-13, -4]都不是正确答案。
示例 2：
输入：cont = [0, 0, 3]
输出：[3, 1]
解释：如果答案是整数，令分母为1即可。
限制：
cont[i] >= 0
1 <= cont的长度 <= 10
cont最后一个元素不等于0
答案的n, m的取值都能被32位int整型存下（即不超过2 ^ 31 - 1）。
题目截图
思路：这个题其实不复杂，就是来回来去分子分母除来除去比较麻烦，我去试着写代码。
额，写完了，第一次有个误区，就是这个除数不能为0.而java中正数相除还是整数，这样没法计算，其实本质上的1/那么多 就似乎分子分母呼唤，所以用乘法来算就好了，我直接贴代码:
class Solution {
public int[] fraction(int[] cont) {
int[] res = new int[2];
res[0] = 1;
res[1] = 0;
for(int i = cont.length - 1; i >= 0; i--){
int temp1 = res[1];
res[1] = res[0];
res[0] = cont[i] * res[1] + temp1;
}
return res;
}
}
今天的笔记就记到这里，另外目前为止终于把leetocde中的所有没锁的简单的题目都刷完了~~明天开始要刷中等的了。一转眼记了53篇笔记了，真的挺快的，感觉开始刷leetcode是前不久的事呢！只能说坚持就是胜利吧
如果这篇文章对你稍微有点帮助记得点个喜欢点个关注，也祝大家工作顺顺利利！
