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

Create Maximum Number

给两个数组, 返回一个数组大小是k, 由这两个数组的数组成最大的数, 要保持原数组的数字之间的前后关系. 这个题好难… 我就看看答案.

public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
    int n = nums1.length;
    int m = nums2.length;
    int[] ans = new int[k];        
    for (int i = Math.max(0, k - m); i <= k && i <= n; ++i) {
        int[] candidate = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
        if (greater(candidate, 0, ans, 0)) ans = candidate;
    }
    return ans;
}
public int[] maxArray(int[] nums, int k) {
    int n = nums.length;
    int[] ans = new int[k];
    for (int i = 0, j = 0; i < n; ++i) {
        while (n - i + j > k && j > 0 && ans[j - 1] < nums[i]) j--;
        if (j < k) ans[j++] = nums[i];
    }
    return ans;
}
private int[] merge(int[] nums1, int[] nums2, int k) {
    int[] ans = new int[k];
    for (int i = 0, j = 0, r = 0; r < k; ++r)
        ans[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
    return ans;
}
public boolean greater(int[] nums1, int i, int[] nums2, int j) {
    while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
        i++;
        j++;
    }
    return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
}
}

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

public class Solution {

public int[] maxNumber(int[] nums1, int[] nums2, int k) {

int n = nums1.length;

int m = nums2.length;

int[] ans = new int[k];

for (int i = Math.max(0, k - m); i <= k && i <= n; ++i) {

int[] candidate = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);

if (greater(candidate, 0, ans, 0)) ans = candidate;

}

return ans;

}

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

int n = nums.length;

int[] ans = new int[k];

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

while (n - i + j > k && j > 0 && ans[j - 1] < nums[i]) j--;

if (j < k) ans[j++] = nums[i];

}

return ans;

}

private int[] merge(int[] nums1, int[] nums2, int k) {

int[] ans = new int[k];

for (int i = 0, j = 0, r = 0; r < k; ++r)

ans[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];

return ans;

}

public boolean greater(int[] nums1, int i, int[] nums2, int j) {

while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {

i++;

j++;

}

return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);

}

Date December 5, 2019
Category Leetcode
Comments No Comments

Palindrome Pairs

给一个字符串数组, 返回通过链接其中的两个字符串, 能组成的回文的pairs. 这个就是dfs加剪枝

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ret = new ArrayList<>(); 
        if (words == null || words.length < 2) return ret;
        Map<String, Integer> map = new HashMap<>();
        for (int i=0; i<words.length; i++) {
            map.put(words[i], i);
        }
        for (int i=0; i<words.length; i++) {
            for (int j=0; j<=words[i].length(); j++) { // notice it should be "j <= words[i].length()"
                String str1 = words[i].substring(0, j);
                String str2 = words[i].substring(j);
                if (isPalindrome(str1)) {
                    String str2rvs = new StringBuilder(str2).reverse().toString();
                    if (map.getOrDefault(str2rvs, i) != i) {
                        ret.add(Arrays.asList(map.get(str2rvs), i));
                    }
                }
                if (isPalindrome(str2) && str2.length() != 0) {
                    String str1rvs = new StringBuilder(str1).reverse().toString();
                    // check "str.length() != 0" to avoid duplicates
                    if (map.getOrDefault(str1rvs, i) != i) { 
                        ret.add(Arrays.asList(i, map.get(str1rvs)));
                    }
                }
            }
        }
        return ret;
    }

    private boolean isPalindrome(String str) {
        for (int l = 0, r = str.length() - 1; l <= r; l ++, r --) {
            if (str.charAt(l) != str.charAt(r)) {
                return false;
            }
        }
        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

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

public class Solution {

public List<List<Integer>> palindromePairs(String[] words) {

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

if (words == null || words.length < 2) return ret;

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

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

map.put(words[i], i);

}

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

for (int j=0; j<=words[i].length(); j++) { // notice it should be "j <= words[i].length()"

String str1 = words[i].substring(0, j);

String str2 = words[i].substring(j);

if (isPalindrome(str1)) {

String str2rvs = new StringBuilder(str2).reverse().toString();

if (map.getOrDefault(str2rvs, i) != i) {

ret.add(Arrays.asList(map.get(str2rvs), i));

}

if (isPalindrome(str2) && str2.length() != 0) {

String str1rvs = new StringBuilder(str1).reverse().toString();

// check "str.length() != 0" to avoid duplicates

if (map.getOrDefault(str1rvs, i) != i) {

ret.add(Arrays.asList(i, map.get(str1rvs)));

}

return ret;

}

private boolean isPalindrome(String str) {

for (int l = 0, r = str.length() - 1; l <= r; l ++, r --) {

if (str.charAt(l) != str.charAt(r)) {

return false;

}

return true;

}

Date December 5, 2019
Category Leetcode
Comments No Comments

Data Stream as Disjoint Intervals

给一个intervals的stream, 求写一个API. 这个要利用java treemap的内建方法.

public class SummaryRanges {
    TreeMap<Integer, Interval> tree;

    public SummaryRanges() {
        tree = new TreeMap<>();
    }

    public void addNum(int val) {
        if(tree.containsKey(val)) return;
        Integer l = tree.lowerKey(val);
        Integer h = tree.higherKey(val);
        if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) {
            tree.get(l).end = tree.get(h).end;
            tree.remove(h);
        } else if(l != null && tree.get(l).end + 1 >= val) {
            tree.get(l).end = Math.max(tree.get(l).end, val);
        } else if(h != null && h == val + 1) {
            tree.put(val, new Interval(val, tree.get(h).end));
            tree.remove(h);
        } else {
            tree.put(val, new Interval(val, val));
        }
    }

    public List<Interval> getIntervals() {
        return new ArrayList<>(tree.values());
    }
}

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

public class SummaryRanges {

TreeMap<Integer, Interval> tree;

public SummaryRanges() {

tree = new TreeMap<>();

}

public void addNum(int val) {

if(tree.containsKey(val)) return;

Integer l = tree.lowerKey(val);

Integer h = tree.higherKey(val);

if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) {

tree.get(l).end = tree.get(h).end;

tree.remove(h);

} else if(l != null && tree.get(l).end + 1 >= val) {

tree.get(l).end = Math.max(tree.get(l).end, val);

} else if(h != null && h == val + 1) {

tree.put(val, new Interval(val, tree.get(h).end));

tree.remove(h);

} else {

tree.put(val, new Interval(val, val));

}

public List<Interval> getIntervals() {

return new ArrayList<>(tree.values());

}

Date December 5, 2019
Category Leetcode
Comments No Comments

All O`one Data Structure

写一个全是O(1)的数据结构

public class AllOne {class Tuple{
    String key;
    int val;
    Tuple(String s, int v){
        key=s;
        val=v;
    }
}

Map<String, Integer> map; //store key-> index of the following list
List<Tuple> list; //store all (key,value) in reversing sorted value order [(a,3),(b,3),(c,2),(d,1)]
Map<Integer, Integer> indexMap; //start index for each value, using above example (3->0),(2->2),(1,3)

/** Initialize your data structure here. */
public AllOne() {
    map = new HashMap<>();
    list = new ArrayList<>();
    indexMap = new HashMap<>();
}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
public void inc(String key) {
    if(map.containsKey(key)){
        //swap curr with the first element which val equals curr.val
        int i = map.get(key);
        Tuple curr = list.get(i);
        int first=indexMap.get(curr.val);
        Tuple exchange =list.get(first);
        list.set(i, exchange);
        list.set(first, curr);
        map.put(key, first);
        map.put(exchange.key, i);
        
        //update curr val index
        indexMap.put(curr.val, first+1);
        
        //increase val, if it is a new val, put 0 in index map
        curr.val++;
        if(!indexMap.containsKey(curr.val)) indexMap.put(curr.val, 0);
    }else{
        //if a new key, add to the last of list
        Tuple t = new Tuple(key, 1);
        list.add(t);
        map.put(key, list.size()-1);
        indexMap.putIfAbsent(1,0);
    }
}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
public void dec(String key) {
    if(map.containsKey(key)){
        int i=map.get(key);
        Tuple curr = list.get(i);
        if(curr.val==1){
            Tuple last = list.get(list.size()-1);
            list.set(i, last);
            list.remove(list.size()-1);
            map.put(last.key, i);
            map.remove(key);
        }else{
            //swap curr with the last element which val equals curr.val
            int index = indexMap.get(curr.val-1)-1;
            Tuple exchange = list.get(index);
            list.set(i, exchange);
            list.set(index, curr);
            map.put(key, index);
            map.put(exchange.key, i);
            if(index==0) indexMap.remove(curr.val);
            curr.val--;
            indexMap.put(curr.val, index);
        }
    }
}

/** Returns one of the keys with maximal value. */
public String getMaxKey() {
    if(!list.isEmpty()) return list.get(0).key;
    return "";
}

/** Returns one of the keys with Minimal value. */
public String getMinKey() {
    if(!list.isEmpty()) return list.get(list.size()-1).key;
    return "";
}
}

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */

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

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

public class AllOne {class Tuple{

String key;

int val;

Tuple(String s, int v){

key=s;

val=v;

}

Map<String, Integer> map; //store key-> index of the following list

List<Tuple> list; //store all (key,value) in reversing sorted value order [(a,3),(b,3),(c,2),(d,1)]

Map<Integer, Integer> indexMap; //start index for each value, using above example (3->0),(2->2),(1,3)

/** Initialize your data structure here. */

public AllOne() {

map = new HashMap<>();

list = new ArrayList<>();

indexMap = new HashMap<>();

}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */

public void inc(String key) {

if(map.containsKey(key)){

//swap curr with the first element which val equals curr.val

int i = map.get(key);

Tuple curr = list.get(i);

int first=indexMap.get(curr.val);

Tuple exchange =list.get(first);

list.set(i, exchange);

list.set(first, curr);

map.put(key, first);

map.put(exchange.key, i);

//update curr val index

indexMap.put(curr.val, first+1);

//increase val, if it is a new val, put 0 in index map

curr.val++;

if(!indexMap.containsKey(curr.val)) indexMap.put(curr.val, 0);

}else{

//if a new key, add to the last of list

Tuple t = new Tuple(key, 1);

list.add(t);

map.put(key, list.size()-1);

indexMap.putIfAbsent(1,0);

}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */

public void dec(String key) {

if(map.containsKey(key)){

int i=map.get(key);

Tuple curr = list.get(i);

if(curr.val==1){

Tuple last = list.get(list.size()-1);

list.set(i, last);

list.remove(list.size()-1);

map.put(last.key, i);

map.remove(key);

}else{

//swap curr with the last element which val equals curr.val

int index = indexMap.get(curr.val-1)-1;

Tuple exchange = list.get(index);

list.set(i, exchange);

list.set(index, curr);

map.put(key, index);

map.put(exchange.key, i);

if(index==0) indexMap.remove(curr.val);

curr.val--;

indexMap.put(curr.val, index);

}

/** Returns one of the keys with maximal value. */

public String getMaxKey() {

if(!list.isEmpty()) return list.get(0).key;

return "";

}

/** Returns one of the keys with Minimal value. */

public String getMinKey() {

if(!list.isEmpty()) return list.get(list.size()-1).key;

return "";

}

/**

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

* AllOne obj = new AllOne();

* obj.inc(key);

* obj.dec(key);

* String param_3 = obj.getMaxKey();

* String param_4 = obj.getMinKey();

*/

Date December 5, 2019
Category Leetcode
Comments No Comments

Concatenated Words

给一个字符串组, 返回所有在里面的由两个以上字符串拼接组成的字符串. 这个题主要考察剪枝, 首先要查重, 用一个set重新装一下数组, 然后按照字典序排序, 然后逐个看是不是答案, 验证的时候, 每个substring都要看一下, 用一个dp当memo, 记录已经看过的字符串.

public class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> result = new ArrayList<>();
        Set<String> preWords = new HashSet<>();
        Arrays.sort(words, new Comparator<String>() {
            public int compare (String s1, String s2) {
                return s1.length() - s2.length();
            }
        });
        for(int i = 0 ; i < words.length; i++) {
            if(canForm(words[i],preWords))
                result.add(words[i]);
            preWords.add(words[i]);
        }
        return result;
    }
    
    public boolean canForm(String word, Set<String> dict) {
        boolean[] dp = new boolean[word.length() + 1];
        dp[0] = true;
        if(dict.isEmpty())
            return false;
        for(int i = 1;  i <= word.length(); i++) {
            for(int j = 0 ; j < i; j++){
                if(dp[j]&&dict.contains(word.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[word.length()];
    }
}

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

public class Solution {

public List<String> findAllConcatenatedWordsInADict(String[] words) {

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

Set<String> preWords = new HashSet<>();

Arrays.sort(words, new Comparator<String>() {

public int compare (String s1, String s2) {

return s1.length() - s2.length();

}

});

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

if(canForm(words[i],preWords))

result.add(words[i]);

preWords.add(words[i]);

}

return result;

}

public boolean canForm(String word, Set<String> dict) {

boolean[] dp = new boolean[word.length() + 1];

dp[0] = true;

if(dict.isEmpty())

return false;

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

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

if(dp[j]&&dict.contains(word.substring(j,i))){

dp[i] = true;

break;

}

return dp[word.length()];

}

Date December 5, 2019
Category Leetcode
Comments No Comments

Sum of Square Numbers

给一个数字, 问能不能有两个平方数组成. 这个题嘛…费马定理.可以做, 就是是否有偶数个4k+3这种形式的数字在里面. 然后最后还要判断一下, 是否这个数本身就是质数,

class Solution {
    public boolean judgeSquareSum(int c) {
        for(int i = 2; i * i <= c; i++) {
            int count = 0;
            if(c % i == 0) { // if i is a factor
                while(c % i == 0) { // remove all i from c
                    count ++;
                    c /= i;
                }
                if (i % 4 == 3 && count % 2 != 0) { // if 4k+3 and count is odd
                    return false;
                }
            }
        }
        if(c % 4 == 3) // in this case, c is a prime number
            return false; // return false, since the count of 4k+3 is 1 in this case
        else
            return true; // return true, since the count of 4k+3 is 0 (even)
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution {

public boolean judgeSquareSum(int c) {

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

int count = 0;

if(c % i == 0) { // if i is a factor

while(c % i == 0) { // remove all i from c

count ++;

c /= i;

}

if (i % 4 == 3 && count % 2 != 0) { // if 4k+3 and count is odd

return false;

}

if(c % 4 == 3) // in this case, c is a prime number

return false; // return false, since the count of 4k+3 is 1 in this case

else

return true; // return true, since the count of 4k+3 is 0 (even)

}

Date December 5, 2019
Category Leetcode
Comments No Comments

Construct String from Binary Tree

给一个数组, 返回有括号表示后的pre order traversing..

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public String tree2str(TreeNode t) {
        if(t == null)
            return "";
        String right = tree2str(t.right);
        String left = tree2str(t.left);
        String res = t.val+"";
        if(right.equals("") && left.equals(""))
            return res;
        else if(right.equals("")){
            return res + "(" + left + ")";
        }
        else 
            return res + "(" + left + ")" + "(" + right + ")";
    }
}

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

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

public String tree2str(TreeNode t) {

if(t == null)

return "";

String right = tree2str(t.right);

String left = tree2str(t.left);

String res = t.val+"";

if(right.equals("") && left.equals(""))

return res;

else if(right.equals("")){

return res + "(" + left + ")";

}

else

return res + "(" + left + ")" + "(" + right + ")";

}

Date December 5, 2019
Category Leetcode
Comments No Comments

Contiguous Array

给一个0,1数组, 返回最长的0和1相等的子数组. 这个直接count也能做, 但是我看讨论中有一个解法更巧妙. 先把0变成-1, 以为n个0和1个0想加是没有区别的, 所以变成-1就可以知道有几个-1了, 然后只需要找相同的sum就可以找到-1和1的相同的位置, 只需要记录最多的个数就可以.

public class Solution {
    public int findMaxLength(int[] nums) {
        for(int i = 0 ; i < nums.length; i++){
            if(nums[i] == 0)
                nums[i] = -1;
        }
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0,-1);
        int sum = 0;
        int max = 0;
        for(int i = 0 ; i < nums.length; i++){
            sum += nums[i];
            if(map.containsKey(sum))
                max = Math.max(max, i - map.get(sum));
            else
                map.put(sum,i);
        }
        return max;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

public class Solution {

public int findMaxLength(int[] nums) {

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

if(nums[i] == 0)

nums[i] = -1;

}

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

map.put(0,-1);

int sum = 0;

int max = 0;

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

sum += nums[i];

if(map.containsKey(sum))

max = Math.max(max, i - map.get(sum));

else

map.put(sum,i);

}

return max;

}

Date December 5, 2019
Category Leetcode
Comments No Comments

Number of Segments in a String

给一个字符串, 问有几个组成.

public class Solution {
    public int countSegments(String s) {
        int res = 0;
        for(int i = 0 ; i < s.length(); i++) {
            if(s.charAt(i) != ' ' && (i == 0 || s.charAt(i-1) == ' '))
                res++;
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

public class Solution {

public int countSegments(String s) {

int res = 0;

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

if(s.charAt(i) != ' ' && (i == 0 || s.charAt(i-1) == ' '))

res++;

}

return res;

}

Date December 5, 2019
Category Leetcode
Comments No Comments

Queue Reconstruction by Height

给一个2d数组, 里面是一个数字和不小于(大于等于)它的数字个数. 求一个sorted数组. 这个直接sort就可以.

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>(){
            public int compare(int[] o1, int[] o2){
                if(o1[0] != o2[0])
                    return o2[0] - o1[0];
                else
                    return o1[1] - o2[1];
            }
        });
        List<int[]> res = new LinkedList<>();
        for(int[] cur : people){
            res.add(cur[1],cur);
        }
        return res.toArray(new int[people.length][]);
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

public class Solution {

public int[][] reconstructQueue(int[][] people) {

Arrays.sort(people, new Comparator<int[]>(){

public int compare(int[] o1, int[] o2){

if(o1[0] != o2[0])

return o2[0] - o1[0];

else

return o1[1] - o2[1];

}

});

List<int[]> res = new LinkedList<>();

for(int[] cur : people){

res.add(cur[1],cur);

}

return res.toArray(new int[people.length][]);

}

Date December 5, 2019
Category Leetcode
Comments No Comments

Create Maximum Number

Palindrome Pairs

Data Stream as Disjoint Intervals

All O`one Data Structure

Concatenated Words

Sum of Square Numbers

Construct String from Binary Tree

Contiguous Array

Number of Segments in a String

Queue Reconstruction by Height

书脊

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

Categories

Tags

Links

December 2019
M	T	W	T	F	S	S
« Nov
						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