LootCode动态数组练习（724，118，766）

LeetCode724：

这是一个返回索引的问题，并且是该索引对应元素左边所有元素之和等于右边所有元素之和，该元素不能参与运算。

思路：

      1、先对该数组判断是否为一个空数组，空的话直接返回-1。

      2、定义一个左边元素和的符号left和右边元素和的符号right，还有元素总和的符号sum。

      3、遍历获得元素总和值sum的最后结果。

      4、再次遍历，使元素开始从第一个相加进left中。这里有个关键想法，就是返回索引的位置是不相加进去的。所以需要从第二个元素的索引开始。

      5、每次左边加完元素后，记得右边元素等于总和sum减去(左边元素和对应索引元素)，然后判断左右元素是否相等，相等返回索引即可了。

class Solution {
    public int pivotIndex(int[] nums) {
        if(nums==null){            //1
            return -1;
        }
        int left=0;                //2
        int right=0;
        int sum=0;
        for(int num:nums){         //3
            sum+=num;
        }
        for(int i=0;i<nums.length;i++){ //4
            if(i==0){
                left=0;
            }else{
                left+=nums[i-1];
            }
            right=sum-left-nums[i];     //5
            if(left==right){
                return i;
            }
        }
        return -1;
    }
}

LeetCode118：

这是一道关于杨辉三角的数组题目。出题人给定一个行数，让我们输出那么多行数的杨辉三角的结果，就是每个数对应上边两个数相加之和。比如给了五行那么输出下边这样的结果。我们可以这么想，每一行相当于一个线性表，每得到一行数后，也就是一个线性表，将该线性表当成一个元素继续加入一个线性表中。

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

 

思路：

      1、根据该图可以知道每行第一个和最后一个元素都为1，其他元素为上方临近两个元素的和。并且每行元素存几个和现在为多少行有关。

      2、List<Integer>是线性表中存一个整形类，List<List<Integer>>是线性表中存一个线性表。

      3、创建一个和传入行相同的行列数组，用来存储元素便于放入线性表中。

      4、使用一个for循环，I从0~行数-1，每次都创建一个线性表变量l，因为每行存多少个元素和现在为多少行有关，所以再定义一个for循环，j从0~i，每行第一个和最后一个元素等于1，其他元素等于上一行第j个位置和j-1位置的和。看图就知道了。

      5、每行的元素存好后，将该线性表l，也就是存在变量l中的元素放入新的一个线性表就完成了。list.add(l)。

class Solution {
    public List<List<Integer>> generate(int numRows) {
       ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();
       int[][] arr = new int[numRows][numRows];
       for(int i = 0;i<numRows;i++) {
           ArrayList<Integer> l = new ArrayList<Integer>();
           for(int j = 0;j<=i;j++) {
               if(j == 0 || j == i) {
                   arr[i][j] = 1;
               }else {
                   arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
               }
               l.add(arr[i][j]);
           }
           list.add(l);
       }
       return list;
    }
}

LeetCode766：

这是一道矩阵题目，要求给定一个矩阵，只有正对角线的所有元素相等那么返回true，不相等返回false。

下边是这道题的一个思路图。

思路：

      1、由这张图可以知道，有两个路径，一个是matrix[0][0]位置向右走，另一个是向下走。向左是列数col移动，向下是行数row移动。每次都要判断正对角线上的元素是否相等，其实每个元素都是行列各加1。

待补：