寻找数组的中心索引
题目:给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
示例 1:
输入:
nums = [1, 7, 3, 6, 5, 6]
输出: 3
解释:
索引3 (nums[3] = 6) 的左侧数之和(1 + 7 + 3 = 11)，与右侧数之和(5 + 6 = 11)相等。
同时, 3 也是第一个符合要求的中心索引。
示例 2:
输入:
nums = [1, 2, 3]
输出: -1
解释:
数组中不存在满足此条件的中心索引。
说明:
nums 的长度范围为 [0, 10000]。
任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。
思路：隐隐想用双指针。。。累加判断左右相等，，，但是这个如果有多个中心索引的情景暂时想象不到，我先尝试实现看看。
想法被证实不行!因为我预计的是左右那个小哪个往上+。但是发现可能是负数，越加越错！换个思路，尝试一下累加什么的，我先理理思路。
不是，这个测试案例真的绝了！！！左边没元素右边有元素也可以？？？？我继续修改代码。
好了，改完了，性能超过百分之九十八，这道题应该可以ac了。直接贴代码:
class Solution {
public int pivotIndex(int[] nums) {
int r = nums.length-1;
if(r<1) return r;
int sum = 0;
for(int i : nums){
sum += i;
}
int n = 0;
for(int i=0;i<=r;i++){
if(sum-nums[i]-n*2==0){
return i;
}else{
n += nums[i];
}
}
return -1;
}
}
这里用到的一个思维方式就是：如果左右相等，那么总和减去当前元素值，结果应该就是左边+右边。左右相等的话，结果就是两个左边。其实这个可以稍微优化一点点，因为之前的关于length的判断就没必要了，我去了这两个判断试试。
自除数
题目：自除数 是指可以被它包含的每一位数除尽的数。例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。还有，自除数不允许包含 0 。给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。
示例 1：
输入：
上边界left = 1, 下边界right = 22
输出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
注意：
每个输入参数的边界满足 1 <= left <= right <= 10000。
思路：我目前的想法就是暴力法：实现一个判断是否是自除数的方法。然后从left开始一直判断到right。但是我总觉得应该是有技巧的。毕竟这么无脑暴力可能不是考点。。不管怎么说先去实现一次再说吧。
有点意思啊，我以为这个题不能这么无脑的解，但是事实上按照我刚刚的思路居然通过不说，性能还超过百分之九十九的人?看这个架势这个题就是这么无脑啊。
其实这个就是一个循环判断是否能被每一位数整除的方法。但是题中包含0就肯定不是。比如10，就不是自除数， 20，30等等都不是，数位种包含0就自动去除。直接贴代码:
class Solution {
private List<Integer> list;
public List<Integer> selfDividingNumbers(int left, int right) {
list = new ArrayList<Integer>();
for(int i = left;i<=right;i++){
isSelf(i,i);
}
return list;
}
public void isSelf(int n,int nn){
while(n>0){
int d = n%10;
if(d==0 || nn%d!=0) return;
n = n/10;
}
list.add(nn);
}
}
感觉性能也就这样了，所以直接下一题吧。
图像渲染
题目：有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。最后返回经过上色渲染后的图像。
示例 1:
输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析:
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。
注意:
image 和 image[0] 的长度在范围 [1, 50] 内。
给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。
思路：这道题题意我反正是自己照着示例画了图才理解的。如图，因为一开始初值是1，扩散值也只会扩散1的元素。右下角的1没有被扩散到。至于这道题的解题思路，我个人有点想递归。其实我们可以把每一个点的扩散都看做是一个完整的过程。不过这是第一想法，具体怎么做要结合代码一点点实现，我去尝试写代码了。
好了，用的递归实现了，性能超过百分百。
具体一点说思路:其实就是一个点可以扩散上下左右四个点（要元素值是初始扩散点的值的），递归扩散就行了。不过要判断一下是不是有上下左右（突然想起之前那个四层for循环的图片平滑器了，但是因为这个只有四个点可以判断，所以没用什么花板子，直接一个个写的）。然后每一个被扩散的点还要递归扩散。
这里提交的时候有一个坑，就是如果新改的元素和以前的元素一样。相当于没变，一定要直接返回。不然就会栈溢出。其实可以理解：左边的扩散右边的，右边的回来扩散左边的，然后死循环了。差不多就是这个意思，直接贴代码:
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int n = image[sr][sc];
if(newColor==n) return image;
image[sr][sc] = newColor;
spread(image,sr,sc,newColor,n);
return image;
}
//一个点扩散到上下左右四个点
public void spread(int[][] image, int sr, int sc, int newColor,int oldColor){
if(sr>0 && image[sr-1][sc]==oldColor) {
image[sr-1][sc] = newColor;
spread(image,sr-1,sc,newColor,oldColor);
}
if(sr<image.length-1 && image[sr+1][sc]==oldColor) {
image[sr+1][sc] = newColor;
spread(image,sr+1,sc,newColor,oldColor);
}
if(sc>0 && image[sr][sc-1] == oldColor) {
image[sr][sc-1] = newColor;
spread(image,sr,sc-1,newColor,oldColor);
}
if(sc<image[0].length-1 && image[sr][sc+1]==oldColor){
image[sr][sc+1] = newColor;
spread(image,sr,sc+1,newColor,oldColor);
}
}
}
因为性能超过百分百了，所以我直接下一题了。
寻找比目标字母大的最小字母
题目：给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。数组里字母的顺序是循环的。举个例子，如果目标字母target = 'z' 并且有序数组为 letters = ['a', 'b']，则答案返回 'a'。
示例:
输入:
letters = ["c", "f", "j"]
target = "a"
输出: "c"
输入:
letters = ["c", "f", "j"]
target = "c"
输出: "f"
输入:
letters = ["c", "f", "j"]
target = "d"
输出: "f"
输入:
letters = ["c", "f", "j"]
target = "g"
输出: "j"
输入:
letters = ["c", "f", "j"]
target = "j"
输出: "c"
输入:
letters = ["c", "f", "j"]
target = "k"
输出: "c"
注:
letters长度范围在[2, 10000]区间内。
letters 仅由小写字母组成，最少包含两个不同的字母。
目标字母target 是一个小写字母。
思路：这个题似曾相似啊。除了字符串比较麻烦比较之外也没啥了，这个题的实现方式很容易，但是考点应该是性能吧。我去先实现了。目前是思路用数组下标表示数字！不对！！！我之前所以用下标表示数字是因为因为这是一个字符串数组！！你看示例上都是双引号，但是看了题目代码模板。参数是char数组！那么直接处理就行了啊！我去实现了。
第一版本实现了，就是性能可怜点：
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
char min = (char)123;
char min1 = (char)123;
for(char i : letters){
//最小的字母
min1 = min1>i?i:min1;
if(i>target){
//比给定字母大的最小字母
min = min>i?i:min;
}
}
return min==123?min1:min;
}
}
如图就是两个判断，一个是比给定大的最小字母。一个是本身的最小字母。如果没用比给定大的说明需要从a开始再循环。
感觉挺简洁清晰明了的，性能只超过百分之三十多的人，，，
好吧，我知道我为什么错了！！！题目说了是给定顺序的数组！也就是说本身是排好序的，所以就不用遍历一遍了，其实用二分法查找就行了！不过我觉得这道题真的没必要重新做一遍，就这样吧，直接下一题了。
使用最小花费爬楼梯
题目：数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
注意：
cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。
思路：刚刚的一瞬间我想起的是第一次接触动态规划的爬楼梯这个题目！不过看了下，还是有点差别的。这道题不知道是我现在有一定的思维经验了还是本来就简单，反正我觉得很好做。我记得以前做过类似的题目，反正动态规划是没跑了！
emmmm...怎么说呢，做出来了，据说是典型递归，可是我只能根据公式一点点测试做出来。
class Solution {
public int minCostClimbingStairs(int[] cost) {
int f1 = 0, f2 = 0;
for (int i = cost.length - 1; i >= 0; --i) {
int f0 = cost[i] + Math.min(f1, f2);
f2 = f1;
f1 = f0;
}
return Math.min(f1, f2);
}
}
我记得是打家劫舍那道题，不能连着偷，跟这个一样一样的，只不过那个是取最大值，这个是取最小值。前n个元素的最小值，然后判断是取n+1还是n+2。我早就说过我动态规划这块属于能勉强对付着一次次测试ac题目。但是我自己的理解也是一知半解的。
反正这道题就是很典型，而且我是根据打家劫舍一点点套的。
今天的学习笔记就到这里了,我要去继续看那个讲解动态规划是视频了。如果本章的思路和知识点稍微帮到你了记得点个喜欢点个关注，也祝大家周末愉快！工作顺顺利利！明天周一有个好的开始！
