书脊 | 这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Check if All Characters Have Equal Number of Occurrences

查一个字符串是不是所有出现过的字符的字频都一样

class Solution {
    public boolean areOccurrencesEqual(String s) {
        int[] count = new int[26];
        for(char c : s.toCharArray())
            count[c - 'a']++;
        Integer j = null;
        for(int c : count)
            if(c != 0){
                if(j == null)
                    j = c;
                else
                    if(c != j)
                        return false;
            }
        return true;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution {

public boolean areOccurrencesEqual(String s) {

int[] count = new int[26];

for(char c : s.toCharArray())

count[c - 'a']++;

Integer j = null;

for(int c : count)

if(c != 0){

if(j == null)

j = c;

else

if(c != j)

return false;

}

return true;

}

Date July 26, 2021
Category Leetcode
Comments No Comments

Longest Common Subsequence Between Sorted Arrays

给一个sorted array组, 求所有的lcs.

这题都sorted了, 所以顺序不再重要, 所以就是查这几个array有几个重复的元素.

class Solution {
    public List<Integer> longestCommomSubsequence(int[][] arrays) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < arrays[0].length; i++)
        {
            set.add(arrays[0][i]);
        }
        for(int i = 1; i < arrays.length; i++)
        {
            Set<Integer> set1 = new HashSet<>(); 
            for(int j = 0; j < arrays[i].length; j++)
            {
                set1.add(arrays[i][j]);
            }
            set.retainAll(set1);
        }
        return new ArrayList<>(set);
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution {

public List<Integer> longestCommomSubsequence(int[][] arrays) {

Set<Integer> set = new HashSet<Integer>();

for(int i = 0; i < arrays[0].length; i++)

{

set.add(arrays[0][i]);

}

for(int i = 1; i < arrays.length; i++)

{

Set<Integer> set1 = new HashSet<>();

for(int j = 0; j < arrays[i].length; j++)

{

set1.add(arrays[i][j]);

}

set.retainAll(set1);

}

return new ArrayList<>(set);

}

Date July 23, 2021
Category Leetcode
Comments No Comments

Course Schedule

这个就拓扑查环,没啥说的

class Solution {
    public boolean canFinish(int n, int[][] p) {
        int[] into = new int[n];
        for(int[] pp : p)
            into[pp[0]]++;
         for(int k = 0; k < n; k++)
        {
            int i = 0;
            while(i < n)
            {
                if(into[i] == 0)
                    break;
                i++;
            }
            if(i == n)
                return false;
            into[i] = -1; //visited
            for(int[] pp : p)
                if(pp[1] == i)
                    into[pp[0]]--;
        }
        return true;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution {

public boolean canFinish(int n, int[][] p) {

int[] into = new int[n];

for(int[] pp : p)

into[pp[0]]++;

for(int k = 0; k < n; k++)

{

int i = 0;

while(i < n)

{

if(into[i] == 0)

break;

i++;

}

if(i == n)

return false;

into[i] = -1; //visited

for(int[] pp : p)

if(pp[1] == i)

into[pp[0]]--;

}

return true;

}

Date July 19, 2021
Category Leetcode
Comments No Comments

Course Schedule II

拓扑排序. 求排序后的结果.

我用的是in-degree数组做法, 一共运行n次, 每次都查找是否有in-degree为0 的点, 如果有, 标记-1(visited), 然后更新相关的边. 用一个into数组, 记录into边的数量, 即可知道是否当前访问的点的所有边都搜索过了. 这个做法简练, 而且不用dfs/bfs什么的那么多数据结构.

class Solution {
    public int[] findOrder(int n, int[][] p) {
        int[] into = new int[n];
        for(int[] pp : p)
            into[pp[0]]++;
        int[] res = new int[n];
        int k = 0;
        for(int i = 0; i < n; i++)
        {
            int j = 0; 
            while(j < n)
            {
                if(into[j] == 0)
                    break;
                j++;
            }
            if(j == n)
                return new int[0]; 
            res[k++] = j;
            into[j] = -1;
            for(int[] pp : p)
                if(pp[1] == j)
                {
                    into[pp[0]]--;
                }
            
        }
        return res;
    }
}

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

class Solution {

public int[] findOrder(int n, int[][] p) {

int[] into = new int[n];

for(int[] pp : p)

into[pp[0]]++;

int[] res = new int[n];

int k = 0;

for(int i = 0; i < n; i++)

{

int j = 0;

while(j < n)

{

if(into[j] == 0)

break;

j++;

}

if(j == n)

return new int[0];

res[k++] = j;

into[j] = -1;

for(int[] pp : p)

if(pp[1] == j)

{

into[pp[0]]--;

}

return res;

}

Date July 19, 2021
Category Leetcode
Comments No Comments

Subdomain Visit Count

给一个字符串组,由一个空格和domain组成, 求所有subdomain的count.

这题就是分割一下字符串即可. 注意用\\.分割点号

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        List<String> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for(String d : cpdomains)
        {
            String[] s = d.split(" ");
            int count = Integer.valueOf(s[0]);
            String[] ss = s[1].split("\\.");
            String tmp = "";
            for(int i = ss.length - 1; i >= 0; i--)
            {
                if(i != ss.length - 1)
                {
                    tmp = "." + tmp;
                }
                tmp = ss[i] + tmp; 
                map.put(tmp, map.getOrDefault(tmp, 0) + count);
            }
        }
        for(Map.Entry<String, Integer> entry : map.entrySet())
        {
            res.add(entry.getValue() + " " + entry.getKey());
        }
        return res;
    }
}

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

class Solution {

public List<String> subdomainVisits(String[] cpdomains) {

List<String> res = new ArrayList<>();

Map<String, Integer> map = new HashMap<>();

for(String d : cpdomains)

{

String[] s = d.split(" ");

int count = Integer.valueOf(s[0]);

String[] ss = s[1].split("\\.");

String tmp = "";

for(int i = ss.length - 1; i >= 0; i--)

{

if(i != ss.length - 1)

{

tmp = "." + tmp;

}

tmp = ss[i] + tmp;

map.put(tmp, map.getOrDefault(tmp, 0) + count);

}

for(Map.Entry<String, Integer> entry : map.entrySet())

{

res.add(entry.getValue() + " " + entry.getKey());

}

return res;

}

Date July 19, 2021
Category Leetcode
Comments No Comments

Substrings of Size Three with Distinct Characters

问长度为3的substring, 是不是都是不同字符的

class Solution {
    public int countGoodSubstrings(String s) {
        int n = s.length();
        if(n < 3)
            return 0; 
        int count = 0;
        for(int i = 0; i < n - 2; i++)
        {
            if(s.charAt(i) != s.charAt(i + 1) && s.charAt(i) != s.charAt(i + 2) && s.charAt(i + 1) != s.charAt(i + 2))
                count ++;
        }
        return count;
            
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution {

public int countGoodSubstrings(String s) {

int n = s.length();

if(n < 3)

return 0;

int count = 0;

for(int i = 0; i < n - 2; i++)

{

if(s.charAt(i) != s.charAt(i + 1) && s.charAt(i) != s.charAt(i + 2) && s.charAt(i + 1) != s.charAt(i + 2))

count ++;

}

return count;

}

Date July 16, 2021
Category Leetcode
Comments No Comments

Remove One Element to Make the Array Strictly Increasing

给一个数组, 求是否能删除一个后,让数组变成严格递增, 这个题有个陷阱, 就是示例二给的[2,3,1,2], 这个是返回false. 观察一下能看出, [2,3,1]这种, 就是不行的, 找规律发现, 不光需要比较相邻元素, 也要比较删除后的元素. 所以要用当前位置i, 记录删除后的前一个元素i-1的大小.

class Solution {
    public boolean canBeIncreasing(int[] nums) { 
        int count = 0;
        for(int i = 1; i < nums.length; i++)
        {
            if(nums[i - 1] >= nums[i])
                count++;
            if(i >= 2 && nums[i - 2] >= nums[i])
                nums[i] = nums[i - 1];
        }
        return count <= 1;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution {

public boolean canBeIncreasing(int[] nums) {

int count = 0;

for(int i = 1; i < nums.length; i++)

{

if(nums[i - 1] >= nums[i])

count++;

if(i >= 2 && nums[i - 2] >= nums[i])

nums[i] = nums[i - 1];

}

return count <= 1;

}

Date July 16, 2021
Category Leetcode
Comments No Comments

Maximum Product Difference Between Two Pairs

….太水了

class Solution {
    public int maxProductDifference(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        return (nums[n - 1] * nums[n - 2]  - (nums[0] * nums[1]));
    }
}

1

2

3

4

5

6

7

class Solution {

public int maxProductDifference(int[] nums) {

int n = nums.length;

Arrays.sort(nums);

return (nums[n - 1] * nums[n - 2] - (nums[0] * nums[1]));

}

Date July 16, 2021
Category Leetcode
Comments No Comments

Build Array from Permutation

没啥好说的

class Solution {
    public int[] buildArray(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nums[nums[i]];
        return res;
    }
}

1

2

3

4

5

6

7

8

9

class Solution {

public int[] buildArray(int[] nums) {

int n = nums.length;

int[] res = new int[n];

for(int i = 0; i < n; i++)

res[i] = nums[nums[i]];

return res;

}

Date July 15, 2021
Category Leetcode
Comments No Comments

Count Square Sum Triples

给一个数字n, 求[1,n]中有多少勾股数.

class Solution {
    public int countTriples(int n) {
        Map<Integer, Integer> m = new HashMap<>();
        int count = 0;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                int t = i*i + j*j;
                m.put(t, m.getOrDefault(t, 0) + 1);
            }
        }
        for(int i = 1; i <= n; i++)
        { 
            count += m.getOrDefault(i*i, 0);
        }
        return count;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution {

public int countTriples(int n) {

Map<Integer, Integer> m = new HashMap<>();

int count = 0;

for(int i = 1; i <= n; i++)

{

for(int j = 1; j <= n; j++)

{

int t = i*i + j*j;

m.put(t, m.getOrDefault(t, 0) + 1);

}

for(int i = 1; i <= n; i++)

{

count += m.getOrDefault(i*i, 0);

}

return count;

}

Date July 15, 2021
Category Leetcode
Comments No Comments

Check if All Characters Have Equal Number of Occurrences

Longest Common Subsequence Between Sorted Arrays

Course Schedule

Course Schedule II

Subdomain Visit Count

Substrings of Size Three with Distinct Characters

Remove One Element to Make the Array Strictly Increasing

Maximum Product Difference Between Two Pairs

Build Array from Permutation

Count Square Sum Triples

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories

Tags