Leetcode 学习记录 数组与字符串

基础不牢，地动山摇。这句话就是描述我现在的阶段，虽然这些天在csdn的练习上进展还比较顺利，但是内心还是没有底的。实话说，csdn的练习题和leetcode上的比起来，还是真的相差很远。可能是不和口味吧。我还是比较喜欢Leetcode，Leetcode唯一的缺点就是会员比较贵，其他的暂时还没有找到，我很喜欢那种深入浅出的讲解。

于是，继上次近乎捐赠了一年的会员后，我又入坑了。今天还是复习基础，还真的很有意思。

数组的pivot index

用嵌套循环实现

pivot index，翻译成中文是，中心索引。就是这个索引左边和右边的数字和是相等的，我注意到题目描述用到了stricly left/right，就是不包含中心索引自己哦，严格意义上的左边和右边。

说起来倒是不难，很快实现了一个版本，但是如图所示，内存消耗和用时都不理想。

class Solution {
    public int pivotIndex(int[] nums) {

        int i = 0;
        int index = 0, sumLeft = 0, sumRight = 0;

        while( i < nums.length){

            for( int j = i + 1; j < nums.length; j++){
                sumRight += nums[j];
            }

            if( i >= 1){
                sumLeft += nums[i-1];
            }

            if( sumLeft == sumRight){
                index = i;
                return index;
            }else{
                i ++;
                sumRight = 0;
            }

        }

        return index = -1;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

如上面的代码，我使用了嵌套循环，于是用时就很糟糕。

独立的两个循环的实现

嵌套循环的实现方法中，内部的循环的目的是计算sumRight。这里确实有更好的处理方式，可以放在while循环之外。在一开始计算出最初的sumRight，随后在while循环里逐步调整sumRight的值。具体代码如下：

class Solution {
    public int pivotIndex(int[] nums) {

        int i = 0;
        int index = 0, sumLeft = 0, sumRight = 0;

        for( int j = i + 1; j < nums.length; j++){
                sumRight += nums[j];
            }

        while( i < nums.length){

            if( i >= 1){
                sumLeft += nums[i-1];
            }

            if( sumLeft == sumRight){
                index = i;
                return index;
            }else if( i < nums.length - 1){
                sumRight -= nums[i+1];
                
            }
            i ++;

        }

        return index = -1;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

优化后的代码用时减少了很多，但是内存消耗还是很大。

优化变量

上面的代码中，可以优化掉一个dummy变量，index纯粹是为了好理解出现的，减少变量有助于减少内存消耗。

修改了代码后，内存消耗减少了0.3MB。其实也想过，循环要不要考虑一下精简，但是不想牺牲可理解性，现在这样很好理解。

最终的代码，虽然不尽完美，但是经过自己的思考，过程还是很有趣的。

class Solution {
    public int pivotIndex(int[] nums) {

        int i = 0;
        int sumLeft = 0, sumRight = 0;

        for( int j = i + 1; j < nums.length; j++){
                sumRight += nums[j];
            }

        while( i < nums.length){

            if( i >= 1){
                sumLeft += nums[i-1];
            }

            if( sumLeft == sumRight){
                
                return i;
            }else if( i < nums.length - 1){
                sumRight -= nums[i+1];
                
            }

            i ++;

        }

        return -1;



    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34