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

Reverse Prefix of Word

给一个word, 给一个char, 求这个word开始到char的substring的反转后的结果.

class Solution {
    public String reversePrefix(String word, char ch) {
        char[] chs = word.toCharArray();
        int ind = word.indexOf(ch);
        if(ind == -1)
            return word;
        int i = 0;
        int j = ind;
        while(i < j){
            swap(chs, i++, j--);
        }
        return String.valueOf(chs);
    }
    public void swap(char[] c, int i, int j){
        char t = c[i];
        c[i] = c[j];
        c[j] = t;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution {

public String reversePrefix(String word, char ch) {

char[] chs = word.toCharArray();

int ind = word.indexOf(ch);

if(ind == -1)

return word;

int i = 0;

int j = ind;

while(i < j){

swap(chs, i++, j--);

}

return String.valueOf(chs);

}

public void swap(char[] c, int i, int j){

char t = c[i];

c[i] = c[j];

c[j] = t;

}

Date September 19, 2021
Category Leetcode
Comments No Comments

Count Number of Pairs With Absolute Difference K

给一个数组, 和一个数字k, 求数组中的pair的个数, 他们的绝对值差等于k.

这题就存一下数字, 然后因为数字大小范围是[1,200], 所以直接算一下这个范围可能的结果即可.

class Solution {
    public int countKDifference(int[] nums, int k) {
        int res = 0;
        Map<Integer, Integer> count = new HashMap<>();
        for(int n : nums)
            count.put(n, count.getOrDefault(n, 0) + 1);
        for(int i = 1; i <= 100 ; i++){
            int a = count.getOrDefault(i, 0);
            int b = count.getOrDefault(i + k,0);
            if(a != 0 && b != 0){
                res += a * b;
            }
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution {

public int countKDifference(int[] nums, int k) {

int res = 0;

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

for(int n : nums)

count.put(n, count.getOrDefault(n, 0) + 1);

for(int i = 1; i <= 100 ; i++){

int a = count.getOrDefault(i, 0);

int b = count.getOrDefault(i + k,0);

if(a != 0 && b != 0){

res += a * b;

}

return res;

}

Date September 19, 2021
Category Leetcode
Comments No Comments

Smallest Greater Multiple Made of Two Digits

给三个数字, k,d1,d2. 求一个数组, 大于k, 是k的倍数,并且由d1和d2组成的最小数字.

这题就是一个个搜索d1和d2可以组成的数字, 注意一下边界条件.

class Solution {
    public int findInteger(int k, int d1, int d2) {
        return find(k,d1,d2, 0);
    }
    public int find(int k, int d1, int d2, long cur){
        if(cur >= Integer.MAX_VALUE)
            return -1;
        if(cur > k && cur % k == 0)
            return (int)cur;
        int n1 = cur + d1 == 0 ? -1 : find(k, d1, d2, cur*10+d1);
        int n2 = cur + d2 == 0 ? -1 : find(k, d1, d2, cur*10+d2);
        if(n1 != -1 && n2 != -1)
            return Math.min(n1,n2);
        else if(n1 != -1)
            return n1;
        else
            return n2;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution {

public int findInteger(int k, int d1, int d2) {

return find(k,d1,d2, 0);

}

public int find(int k, int d1, int d2, long cur){

if(cur >= Integer.MAX_VALUE)

return -1;

if(cur > k && cur % k == 0)

return (int)cur;

int n1 = cur + d1 == 0 ? -1 : find(k, d1, d2, cur*10+d1);

int n2 = cur + d2 == 0 ? -1 : find(k, d1, d2, cur*10+d2);

if(n1 != -1 && n2 != -1)

return Math.min(n1,n2);

else if(n1 != -1)

return n1;

else

return n2;

}

Date September 10, 2021
Category Leetcode
Comments No Comments

Flip Game II

设定一个游戏, 翻转字符串的任意++变成–, 问开始玩的人是否一定能赢.

这题就是记忆搜索的模板题, 用一个memo存字符串改变后的状态的答案, 然后按个找结果.

class Solution {
    public boolean canWin(String s) {
        Map<String, Boolean> memo = new HashMap<>();
        find(s, memo);
        return memo.get(s);
    }
    boolean find(String s, Map<String, Boolean> memo){
        if(memo.containsKey(s))
            return memo.get(s);
        Boolean res = false;
        for(int i = 0; i < s.length(); i++) {
            if(i > 0 && s.charAt(i) == '+' && s.charAt(i - 1) == '+'){
                StringBuffer sb = new StringBuffer(s);
                sb.setCharAt(i - 1, '-');
                sb.setCharAt(i, '-');
                if(!find(sb.toString(),memo)){
                    res = true;
                    break;
                }
            }
        }
        memo.put(s, res);
        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

class Solution {

public boolean canWin(String s) {

Map<String, Boolean> memo = new HashMap<>();

find(s, memo);

return memo.get(s);

}

boolean find(String s, Map<String, Boolean> memo){

if(memo.containsKey(s))

return memo.get(s);

Boolean res = false;

for(int i = 0; i < s.length(); i++) {

if(i > 0 && s.charAt(i) == '+' && s.charAt(i - 1) == '+'){

StringBuffer sb = new StringBuffer(s);

sb.setCharAt(i - 1, '-');

sb.setCharAt(i, '-');

if(!find(sb.toString(),memo)){

res = true;

break;

}

memo.put(s, res);

return res;

}

Date September 10, 2021
Category Leetcode
Comments No Comments

Find Greatest Common Divisor of Array

给一个数组, 求里面最大值和最小值的gcd.

class Solution {
    public int findGCD(int[] nums) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int n : nums){
            max = Math.max(max, n); 
            min = Math.min(min, n);
        }
        return gcd(min, max);
    }
    public int gcd(int a, int b){
        if(a == 0)
            return b;
        return gcd(b % a, a);
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution {

public int findGCD(int[] nums) {

int max = Integer.MIN_VALUE;

int min = Integer.MAX_VALUE;

for(int n : nums){

max = Math.max(max, n);

min = Math.min(min, n);

}

return gcd(min, max);

}

public int gcd(int a, int b){

if(a == 0)

return b;

return gcd(b % a, a);

}

Date September 9, 2021
Category Leetcode
Comments No Comments

Minimum Difference Between Highest and Lowest of K Scores

给一个数组和一个数字k, 求k个数字的最大最小值的差最小.

class Solution {
    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;
        if(k == 1)
            return 0;
        for(int i = k - 1; i < nums.length; i++)
        {
            min = Math.min(min, nums[i] - nums[i - k + 1]);
        }
        return min;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution {

public int minimumDifference(int[] nums, int k) {

Arrays.sort(nums);

int min = Integer.MAX_VALUE;

if(k == 1)

return 0;

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

{

min = Math.min(min, nums[i] - nums[i - k + 1]);

}

return min;

}

Date September 9, 2021
Category Leetcode
Comments No Comments

Find the Middle Index in Array

定义middleindex是一个index的左右两边的sum都一样(不包含自己), 找到最左边的middle index.

这题就是做下presum, 然后找.

class Solution {
    public int findMiddleIndex(int[] nums) {
        int rightSum = 0;
        for(int i = 1; i < nums.length; i++)
            rightSum += nums[i];
        int leftSum = 0;
        for(int i = 0; i < nums.length; i++){
            if(leftSum == rightSum)
                return i;
            leftSum += nums[i];
            if(i < nums.length - 1)
                rightSum -= nums[i + 1];
        }
        return -1;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution {

public int findMiddleIndex(int[] nums) {

int rightSum = 0;

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

rightSum += nums[i];

int leftSum = 0;

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

if(leftSum == rightSum)

return i;

leftSum += nums[i];

if(i < nums.length - 1)

rightSum -= nums[i + 1];

}

return -1;

}

Date September 9, 2021
Category Leetcode
Comments No Comments

Count Special Quadruplets

求数组中三个数字相加等于第四个数字的组合的个数.

用map优化一维.

class Solution {
    public int countQuadruplets(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                for(int k = j + 1; k < nums.length; k++)
                {
                    res += map.getOrDefault(nums[k] - nums[j] - nums[i], 0);
                }
            }
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution {

public int countQuadruplets(int[] nums) {

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

int res = 0;

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

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

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

{

res += map.getOrDefault(nums[k] - nums[j] - nums[i], 0);

}

map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);

}

return res;

}

Date September 9, 2021
Category Leetcode
Comments No Comments

Minimize Maximum Pair Sum in Array

求最小的, 最大pair和..

这题就是先sort, 然后前后加求最大.

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        int res = 0;
        while(i < j){
            res = Math.max(res, nums[i] + nums[j]);
            i++;
            j--;
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution {

public int minPairSum(int[] nums) {

Arrays.sort(nums);

int i = 0;

int j = nums.length - 1;

int res = 0;

while(i < j){

res = Math.max(res, nums[i] + nums[j]);

i++;

j--;

}

return res;

}

Date August 21, 2021
Category Leetcode
Comments No Comments

Minimize Product Sum of Two Arrays

给两个数组, 求重新排序后, 数字的积的和最小是多少.

这题就是大*小, 所以排序一下, 然后插着乘.

class Solution {
    public int minProductSum(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int res = 0;
        for(int i = 0; i < nums1.length; i++){
            res += nums1[i] * nums2[nums2.length - 1 - i];
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

class Solution {

public int minProductSum(int[] nums1, int[] nums2) {

Arrays.sort(nums1);

Arrays.sort(nums2);

int res = 0;

for(int i = 0; i < nums1.length; i++){

res += nums1[i] * nums2[nums2.length - 1 - i];

}

return res;

}

Date August 21, 2021
Category Leetcode
Comments No Comments

Reverse Prefix of Word

Count Number of Pairs With Absolute Difference K

Smallest Greater Multiple Made of Two Digits

Flip Game II

Find Greatest Common Divisor of Array

Minimum Difference Between Highest and Lowest of K Scores

Find the Middle Index in Array

Count Special Quadruplets

Minimize Maximum Pair Sum in Array

Minimize Product Sum of Two Arrays

书脊

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

Categories

Tags