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

Adding Two Negabinary Numbers

给两个以-2为base的数字, 用数字表示, 求他们的合. 这个题和adding binary number那个题一样.

class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        if (arr1.length == 0) {
            return arr2;
        }
        if (arr2.length == 0) {
            return arr1;
        }
        int i = arr1.length - 1;
        int j = arr2.length - 1;
        int carry = 0;
        List<Integer> list = new ArrayList<>();
        while (i >= 0 && j >= 0) { 
            int k = arr1[i] + arr2[j] + carry;
            list.add((k + 2) % 2);
            carry = ((k + 2) % 2 - k) / 2;
            i--;
            j--;
        } 
        while (i >= 0) {
            int k = arr1[i] + carry;
            list.add((k + 2) % 2);
            carry = ((k + 2) % 2 - k) / 2;
            i--;
        }
        while (j >= 0) {
            int k = arr2[j] + carry;
            list.add((k + 2) % 2);
            carry = ((k + 2) % 2 - k) / 2;
            j--;
        }
        while (carry != 0) {
            list.add((carry + 2) % 2);
            carry = ((carry + 2) % 2 - carry) / 2;
        }
        int m = list.size() - 1;
        while (list.get(m) == 0 && m > 0) {
            m--;
        }
        int[] result = new int[m + 1];
        while (m >= 0) {
            result[result.length - m - 1] = list.get(m);
            m--;
        }
        return result;
    }
}

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

35

36

37

38

39

40

41

42

43

44

45

46

47

class Solution {

public int[] addNegabinary(int[] arr1, int[] arr2) {

if (arr1.length == 0) {

return arr2;

}

if (arr2.length == 0) {

return arr1;

}

int i = arr1.length - 1;

int j = arr2.length - 1;

int carry = 0;

List<Integer> list = new ArrayList<>();

while (i >= 0 && j >= 0) {

int k = arr1[i] + arr2[j] + carry;

list.add((k + 2) % 2);

carry = ((k + 2) % 2 - k) / 2;

i--;

j--;

}

while (i >= 0) {

int k = arr1[i] + carry;

list.add((k + 2) % 2);

carry = ((k + 2) % 2 - k) / 2;

i--;

}

while (j >= 0) {

int k = arr2[j] + carry;

list.add((k + 2) % 2);

carry = ((k + 2) % 2 - k) / 2;

j--;

}

while (carry != 0) {

list.add((carry + 2) % 2);

carry = ((carry + 2) % 2 - carry) / 2;

}

int m = list.size() - 1;

while (list.get(m) == 0 && m > 0) {

m--;

}

int[] result = new int[m + 1];

while (m >= 0) {

result[result.length - m - 1] = list.get(m);

m--;

}

return result;

}

Date January 21, 2020
Category Leetcode
Comments No Comments

给一个数组, 里面是完成一个任务需要的技能, 另一个数组是每个人有的技能, 求完成任务的最少人的数组. 这个题是一个set cover问题, 因为set cover的k决定性问题是NPC, 但是set cover本身不是, 所以这个题应该可以在多项式时间内解决. 首先hints中提示了要做bit编码, 那么就用过反转index,找到每个skill对应的数字, 然后通过左移(<<)标记在int中. 然后就是算法部分. 通过hint2得知, 这题是类似于背包问题的dp问题, 所以我们用一个loop扫描每个人, 然后用一个数组装所有可能的需要完成任务的技能的combination, 比如n个需要的技能, 那么就是 1 << 个位置. 所以我们的答案就在all[(1<<n) – 1]这个位置上.我们比较每个可能技能下的需要的人数, 就可以得知这种组合下的人的最优解(人数最少).

最后要解决的问题是, 如何匹配组合的技能和人的技能.int comb = k | pSkill; k遍历所有的技能, 然后通过与运算和pSkill进行匹配. 对技能的编码如下: {"java":0,"nodejs":1,"reactjs":2} ,

而pSkill的编码比如people: [["java","nodejs","reactjs"]] 编码为111. 即表示这个人会所有技能, 那么如果是 people: [["java","reactjs"]], 编码为101,

k则从1一直遍历到1 << 3,也就是7(111), 这样可以覆盖所有可能的组合, 我们通过k一直update每个人的技能与当前team的匹配结果, 最后得出答案.

class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int n = req_skills.length;
        int m = people.size();
        List<Integer>[] all = new ArrayList[1 << n];
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            map.put(req_skills[i], i); // build reverse index
        }
        for(int i = 0 ; i < all.length; i++) {
            all[i] = new ArrayList<>();
        }
        for(int p = 0; p < m; p++) {
            int pSkill = 0; // one person's skill
            for(String s : people.get(p))
                pSkill |= 1 << (map.get(s));
            for(int k = 0; k < all.length; k++) {
                if(k != 0 && all[k].size() == 0) // haven't visited yet
                    continue;
                List<Integer> cur = all[k];
                int comb = k | pSkill;
                if(comb == k) // in this case, pSkill is same to k
                    continue;
                int size = all[comb].size();
                if(size == 0 || size > cur.size() + 1) {
                    List<Integer> newList = new ArrayList<>(cur);
                    newList.add(p);
                    all[comb] = newList;
                }
            }
        }
        
        int[] res = new int[all[(1 << n) - 1].size()];
        for(int i = 0 ; i < all[(1<<n) - 1].size(); i++) {
            res[i] = all[(1<<n) - 1].get(i);
        }
        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

31

32

33

34

35

36

37

38

39

40

class Solution {

public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {

int n = req_skills.length;

int m = people.size();

List<Integer>[] all = new ArrayList[1 << n];

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

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

map.put(req_skills[i], i); // build reverse index

}

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

all[i] = new ArrayList<>();

}

for(int p = 0; p < m; p++) {

int pSkill = 0; // one person's skill

for(String s : people.get(p))

pSkill |= 1 << (map.get(s));

for(int k = 0; k < all.length; k++) {

if(k != 0 && all[k].size() == 0) // haven't visited yet

continue;

List<Integer> cur = all[k];

int comb = k | pSkill;

if(comb == k) // in this case, pSkill is same to k

continue;

int size = all[comb].size();

if(size == 0 || size > cur.size() + 1) {

List<Integer> newList = new ArrayList<>(cur);

newList.add(p);

all[comb] = newList;

}

int[] res = new int[all[(1 << n) - 1].size()];

for(int i = 0 ; i < all[(1<<n) - 1].size(); i++) {

res[i] = all[(1<<n) - 1].get(i);

}

return res;

}

Date January 21, 2020
Category Leetcode
Comments No Comments

Building H2O

多线程的题, 给两个方法, 一边是h一边是o, 问如何即时返回水(h2o). 通过观察可以看到, 水是两个h一个o, 那么当一个o出现的时候, 我们就检查是否有两个h. 当h不够2的时候, 就等h够2再继续运行. 所以一个互斥锁即可.

class H2O {
    private AtomicInteger water;
    public H2O() {
        water = new AtomicInteger();
    }

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
	    synchronized(water){
            while(water.get() == 2)
                water.wait();
            water.addAndGet(1);
            releaseHydrogen.run();
            water.notifyAll();
        }
        // releaseHydrogen.run() outputs "H". Do not change or remove this line.
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        synchronized(water){
            while(water.get() < 0)
                water.wait();
            water.addAndGet(-2);
            releaseOxygen.run();
            water.notifyAll();
        }
    }
}

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 H2O {

private AtomicInteger water;

public H2O() {

water = new AtomicInteger();

}

public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {

synchronized(water){

while(water.get() == 2)

water.wait();

water.addAndGet(1);

releaseHydrogen.run();

water.notifyAll();

}

// releaseHydrogen.run() outputs "H". Do not change or remove this line.

}

public void oxygen(Runnable releaseOxygen) throws InterruptedException {

synchronized(water){

while(water.get() < 0)

water.wait();

water.addAndGet(-2);

releaseOxygen.run();

water.notifyAll();

}

Date January 18, 2020
Category Leetcode
Comments No Comments

Check If It Is a Straight Line

给一个数组, 里面是点, 问这些点在不在一个直线上. 这个题要用斜率公式算, y=ax+b, where (x,y) from array. 先用一组算出a, 然后再算b.

class Solution {
    public boolean checkStraightLine(int[][] c) {
        double s = (double)(c[1][1] - c[0][1]) / (c[1][0] - c[0][0]);
        double m = c[0][1] - s*c[0][0];
        for(int i = 2; i < c.length; i++) {
            int t = (int)(s * c[i][0] + m);
            if(t != c[i][1])
                return false;
        }
        return true;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

class Solution {

public boolean checkStraightLine(int[][] c) {

double s = (double)(c[1][1] - c[0][1]) / (c[1][0] - c[0][0]);

double m = c[0][1] - s*c[0][0];

for(int i = 2; i < c.length; i++) {

int t = (int)(s * c[i][0] + m);

if(t != c[i][1])

return false;

}

return true;

}

Date January 17, 2020
Category Leetcode
Comments No Comments

Remove Covered Intervals

给一个数组, 里面是intervals, 求移除所有重叠的intervals后, 数组里面元素的个数. 这个题先排序一下, 然后比较intervals的end值即可.

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if(a[0] != b[0]){
                return a[0] - b[0];
            }
            else{
                return b[1] - a[1];
            }
        });
        int pre = 0;
        int count = 0;
        for(int i = 1; i < intervals.length; i++) {
            if(intervals[i][1] <= intervals[pre][1]){
                count++;
            }
            else {
                pre = i;
            }
        }
        return intervals.length - count;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution {

public int removeCoveredIntervals(int[][] intervals) {

Arrays.sort(intervals, (a, b) -> {

if(a[0] != b[0]){

return a[0] - b[0];

}

else{

return b[1] - a[1];

}

});

int pre = 0;

int count = 0;

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

if(intervals[i][1] <= intervals[pre][1]){

count++;

}

else {

pre = i;

}

return intervals.length - count;

}

Date January 16, 2020
Category Leetcode
Comments No Comments

Find Numbers with Even Number of Digits

给一个数组, 找到里面位数为偶数的数字的个数.

class Solution {
    public int findNumbers(int[] nums) {
        int count = 0;
        for(int n : nums) {
            if(check(n)) {
                count++;
            }
        }
        return count;
    }
    
    private boolean check(int n) {
        int count = 0;
        while(n != 0) {
            count++;
            n /= 10;
        }
        return count % 2 == 0;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution {

public int findNumbers(int[] nums) {

int count = 0;

for(int n : nums) {

if(check(n)) {

count++;

}

return count;

}

private boolean check(int n) {

int count = 0;

while(n != 0) {

count++;

n /= 10;

}

return count % 2 == 0;

}

Date January 16, 2020
Category Leetcode
Comments No Comments

Iterator for Combination

写一个Iterator遍历长度为k的n个字符的组合. 这个题就是把Combination写成api. 所以先算出k个n的comb, 然后就直接输出

class CombinationIterator {
    List<String> q = new ArrayList<>();
    public CombinationIterator(String characters, int combinationLength) {
        pre(q, characters.toCharArray(), new StringBuilder(),combinationLength,0);
    }
    private void pre(List<String> q, char[] c, StringBuilder sb,int k, int pos) {
        if(sb.length() == k) {
            q.add(sb.toString());
            return;
        }
        for(int i = pos; i < c.length; i++) {
            sb.append(c[i]);
            pre(q, c, sb, k, i+1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    public String next() {
        return q.remove(0);
    }
    
    public boolean hasNext() {
        return q.size() > 0;
    }
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * String param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

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

class CombinationIterator {

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

public CombinationIterator(String characters, int combinationLength) {

pre(q, characters.toCharArray(), new StringBuilder(),combinationLength,0);

}

private void pre(List<String> q, char[] c, StringBuilder sb,int k, int pos) {

if(sb.length() == k) {

q.add(sb.toString());

return;

}

for(int i = pos; i < c.length; i++) {

sb.append(c[i]);

pre(q, c, sb, k, i+1);

sb.deleteCharAt(sb.length() - 1);

}

public String next() {

return q.remove(0);

}

public boolean hasNext() {

return q.size() > 0;

}

/**

* Your CombinationIterator object will be instantiated and called as such:

* CombinationIterator obj = new CombinationIterator(characters, combinationLength);

* String param_1 = obj.next();

* boolean param_2 = obj.hasNext();

*/

Date January 15, 2020
Category Leetcode
Comments No Comments

Sum of Mutated Array Closest to Target

给一个数组和一个target, 求一个数字n, 把数组中所有大于n的数字都替换成n以后, 数组的和与target最接近. 这个题是找最接近target的一个数字n, 那么用二叉搜索找即可, 设lo是0, hi是target, 那么mid就是中间假设的答案, 这个答案可以通过题意的改变数组后, 找到和target的差值, 因为我们知道mid是单调递增的, 所以可以用二叉搜索.

class Solution {
    public int findBestValue(int[] arr, int target) {
        int lo = 0;
        int hi = target;
        while(lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int tmp = sum(arr, mid);
            if(tmp == target)
                return mid;
            else if(tmp > target)
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        if(Math.abs(sum(arr, lo) - target) >=  Math.abs(sum(arr, lo-1) - target))
            return lo-1;
        else
            return lo;
    }
    
    private int sum(int[] arr, int n) {
        int sum = 0;
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] > n) {
                sum += n;
            }
            else {
                sum += arr[i];
            }
        }
        return sum;
    }
}

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

class Solution {

public int findBestValue(int[] arr, int target) {

int lo = 0;

int hi = target;

while(lo <= hi) {

int mid = lo + (hi - lo) / 2;

int tmp = sum(arr, mid);

if(tmp == target)

return mid;

else if(tmp > target)

hi = mid - 1;

else

lo = mid + 1;

}

if(Math.abs(sum(arr, lo) - target) >= Math.abs(sum(arr, lo-1) - target))

return lo-1;

else

return lo;

}

private int sum(int[] arr, int n) {

int sum = 0;

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

if(arr[i] > n) {

sum += n;

}

else {

sum += arr[i];

}

return sum;

}

Date January 15, 2020
Category Leetcode
Comments No Comments

Decompress Run-Length Encoded List

给一个数组, 里面是一对对的数, 偶数位的数字表示频率, 奇数位的数字表示前一个偶数位的值. 求原始数组.

class Solution {
    public int[] decompressRLElist(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < nums.length; i+=2) {
            for(int j = 0; j < nums[i]; j++) {
                list.add(nums[i+1]);
            }
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution {

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

List<Integer> list = new ArrayList<>();

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

for(int j = 0; j < nums[i]; j++) {

list.add(nums[i+1]);

}

int[] res = new int[list.size()];

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

res[i] = list.get(i);

}

return res;

}

Date January 15, 2020
Category Leetcode
Comments No Comments

Matrix Block Sum

给一个2d数组和一个k, 求k的范围内的和. 这个题和range sum的那个一样的结构, 只是query部分稍加改动. 附上一个答案里很简练的做法.

class Solution {
     public int[][] matrixBlockSum(int[][] mat, int K) {
        int m = mat.length, n = mat[0].length;
        int[][] sum = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + mat[i][j];
        int[][] ans = new int[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                int r1 = Math.max(0, i - K);
                int c1 = Math.max(0, j - K);
                int r2 = Math.min(m, i + K + 1);
                int c2 = Math.min(n, j + K + 1);
                ans[i][j] = sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];
            }
        return ans;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution {

public int[][] matrixBlockSum(int[][] mat, int K) {

int m = mat.length, n = mat[0].length;

int[][] sum = new int[m + 1][n + 1];

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

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

sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + mat[i][j];

int[][] ans = new int[m][n];

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

for (int j = 0; j < n; j++) {

int r1 = Math.max(0, i - K);

int c1 = Math.max(0, j - K);

int r2 = Math.min(m, i + K + 1);

int c2 = Math.min(n, j + K + 1);

ans[i][j] = sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];

}

return ans;

}

Date January 15, 2020
Category Leetcode
Comments No Comments

Adding Two Negabinary Numbers

Smallest Sufficient Team

Building H2O

Check If It Is a Straight Line

Remove Covered Intervals

Find Numbers with Even Number of Digits

Iterator for Combination

Sum of Mutated Array Closest to Target

Decompress Run-Length Encoded List

Matrix Block Sum

书脊

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

Categories

Tags

Links

January 2020
M	T	W	T	F	S	S
« Dec
		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