5.10号刷题

发表于 | 分类于 | 0 comments

第一题 485 Max Consecutive Ones

算法

#####自己的
时间复杂度O(n),遍历一遍，记录下最长的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class findMaxConsecutiveOnes485 {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                if (count > max) max = count;
                count = 0;
            } else {
                count++;
            }
            if (i == nums.length - 1) {
                if (count > max) max =count;
            }
        }
        return max;
    }
}

学到的东西

当需要判断if (a > b)的时候可以用Math.max(a, b);进行替换

第二题 442 Find All Duplicates in an Array

####算法
链接主要方法是用负号记录下当前的数字。例如出现的数字是3，那么对应的index = 3-1 = 2,将nums[2]位置的数字置为负，如果之后再出现的话，发现是负数，那么说明这个数字已经出现过了。

1
2
3
4
5
6
7
8
9
10
11
public class findDuplicates442 {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] < 0) result.add(Math.abs(nums[i]));
            nums[index] = -nums[index];
        }
        return result;
    }
}

第三题 [448 Find All Numbers Disappeared in an Array Add to List

](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/#/description)

算法

我的方法

与之前题目一样，用数字和下标为负的方法记录下已经出现过的数字，如果数字为负则不用管。之后再进行一次遍历，如果某个数字是正数的话，说明其对应的数字没有出现过。返回结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class findDisappearedNumbers448 {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] < 0) continue;
            nums[index] = -nums[index];
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) result.add(i + 1);
        }
        return result;
    }
}

第四题 531 Lonely Pixel I

算法

方法是建立两个array对每行和每列出现的B点进行统计，因此需要O(n+m)的空间复杂度。之后需要遍历两遍，时间复杂度为O(2mn)。查看每行和每列中的点是否为1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class findLonelyPixel531 {
    public int findLonelyPixel(char[][] picture) {
        int row = picture.length;
        int column = picture[0].length;
        int[] row_count = new int[row];
        int[] column_count = new int[column];
        for (int i = 0; i < row; i++)
            for (int j = 0; j < column; j++) {
                if (picture[i][j] == 'B') {
                    row_count[i]++;
                    column_count[j]++;
                }
            }
        int count = 0;
        for (int i = 0; i < row; i++)
            for (int j = 0; j < column; j++) {
                if (picture[i][j] == 'B' && row_count[i] == 1 && column_count[j] == 1) count++;
            }
        return count;
    }
}

第五题 495 Teemo Attacking

算法

用一个begin 和 end记录下此刻和下一个的时间，如果时间间隔比duration 短的话，那么就直接加上begin - end。否则就加上duration.
自己的算法打败93%第一次那么高，还是挺开心的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class findPoisonedDuration495 {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int sum = 0;
        if (timeSeries.length == 0) return sum;
        for (int i = 0; i < timeSeries.length - 1; i++) {
            int begin = timeSeries[i];
            int end = timeSeries[i+1];
            if (end - begin < duration) sum += end - begin;
            else sum += duration;
        }
        return sum + duration;
    }
}