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

String Compression

给一个string, 求如何in-place的压缩, 返回改后数组的大小. 用双指针法, 一个指针write指向数组的写入点, 另一个read指向数组的读取点.

class Solution {
    public int compress(char[] chars) {
        int read = 0;
        int write = 0;
        char c = '!';
        while(read < chars.length){
            if(chars[read] != c){
                c = chars[read];
                chars[write++] = chars[read++];
            }
            else{
                int count = 1;
                while(read < chars.length && c == chars[read]){
                    read++;
                    count++;
                }
                for(char t : (""+count).toCharArray()){
                    chars[write++] = t;                
                } // write count to chars
            }
        }
        return write;
    }
}

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 int compress(char[] chars) {

int read = 0;

int write = 0;

char c = '!';

while(read < chars.length){

if(chars[read] != c){

c = chars[read];

chars[write++] = chars[read++];

}

else{

int count = 1;

while(read < chars.length && c == chars[read]){

read++;

count++;

}

for(char t : (""+count).toCharArray()){

chars[write++] = t;

} // write count to chars

}

return write;

}

Date February 27, 2020
Category Leetcode
Comments No Comments

One Edit Distance

给两个字符串s和t, 问s和t是不是之差一个edit distance. 先看两个的长度, 差超过2个肯定不行, 然后一样的话就看是不是都一样, 不一样(差一个) 就从前往后扫, 然后看substring.

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if(s.equals(t))
            return false;
        for (int i = 0; i < Math.min(s.length(), t.length()); i++) {
            if(s.charAt(i) != t.charAt(i)) {
                if(s.length() == t.length()){
                    if(s.substring(i+1).equals(t.substring(i+1)))
                        return true;
                    else
                        return false;
                }
                else {
                    if(s.length() > t.length()){
                        if(s.substring(i+1).equals(t.substring(i)))
                            return true;
                        else
                            return false;
                    }
                    else{
                        if(s.substring(i).equals(t.substring(i+1)))
                            return true;
                        else
                            return false;
                    }
                }
                    
            }
        }
        return Math.abs(s.length() - t.length()) <= 1;
    }
}

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

class Solution {

public boolean isOneEditDistance(String s, String t) {

if(s.equals(t))

return false;

for (int i = 0; i < Math.min(s.length(), t.length()); i++) {

if(s.charAt(i) != t.charAt(i)) {

if(s.length() == t.length()){

if(s.substring(i+1).equals(t.substring(i+1)))

return true;

else

return false;

}

else {

if(s.length() > t.length()){

if(s.substring(i+1).equals(t.substring(i)))

return true;

else

return false;

}

else{

if(s.substring(i).equals(t.substring(i+1)))

return true;

else

return false;

}

return Math.abs(s.length() - t.length()) <= 1;

}

Date February 26, 2020
Category Leetcode
Comments No Comments

License Key Formatting

给一个字符串, 和一个k, 要求重新编辑字符串, 让每隔k个夹一个-.

class Solution {
    public String licenseKeyFormatting(String S, int K) {
        int cur = 0;
        StringBuilder sb = new StringBuilder();
        for(int j = S.length() -1 ; j >= 0; j--){
            char c = Character.toUpperCase(S.charAt(j));
            if(c != '-'){
                if(cur == K){
                    sb.append('-');
                    cur = 0; //reset
                }
                sb.append(c);
                cur++;
            }
        }
        return sb.reverse().toString();
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution {

public String licenseKeyFormatting(String S, int K) {

int cur = 0;

StringBuilder sb = new StringBuilder();

for(int j = S.length() -1 ; j >= 0; j--){

char c = Character.toUpperCase(S.charAt(j));

if(c != '-'){

if(cur == K){

sb.append('-');

cur = 0; //reset

}

sb.append(c);

cur++;

}

return sb.reverse().toString();

}

Date February 26, 2020
Category Leetcode
Comments No Comments

Valid Word Square

给一个list, 里面是字符串, 问是不是横竖都是同一个字符串. 这个题就按照题意查就行了, 注意边界.

class Solution {
    public boolean validWordSquare(List<String> words) {
        for(int i = 0; i < words.size(); i++) {
            for(int j = 0; j < words.get(i).length(); j++) {
                if(j >= words.size()) // out bound
                    return false;
                if(i >= words.get(j).length())// out bound
                    return false;
                if(words.get(j).charAt(i) != words.get(i).charAt(j))
                    return false;
            }
        }
        return true;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution {

public boolean validWordSquare(List<String> words) {

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

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

if(j >= words.size()) // out bound

return false;

if(i >= words.get(j).length())// out bound

return false;

if(words.get(j).charAt(i) != words.get(i).charAt(j))

return false;

}

return true;

}

Date February 26, 2020
Category Leetcode
Comments No Comments

Longest Uncommon Subsequence I

这题真是瞎了眼.

class Solution {
    public int findLUSlength(String a, String b) {
            return a.equals(b) ? -1 : Math.max(a.length(), b.length());
    }
}

1

2

3

4

5

class Solution {

public int findLUSlength(String a, String b) {

return a.equals(b) ? -1 : Math.max(a.length(), b.length());

}

Date February 26, 2020
Category Leetcode
Comments No Comments

Sort Integers by The Number of 1 Bits

给一组数,按照里面二进制1的个数排序.

class Solution {
    public int[] sortByBits(int[] arr) {
        return  Arrays.stream(arr).boxed().sorted((a,b) -> (countBit(a) == countBit(b)) ? a-b : countBit(a) - countBit(b)).mapToInt(i -> i).toArray();
    }
    
    private int countBit(int n) {
        int res = 0;
        for(int i = 0 ; i < 32; i++) {
            if((n & (1 << i)) != 0)
                res++;
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution {

public int[] sortByBits(int[] arr) {

return Arrays.stream(arr).boxed().sorted((a,b) -> (countBit(a) == countBit(b)) ? a-b : countBit(a) - countBit(b)).mapToInt(i -> i).toArray();

}

private int countBit(int n) {

int res = 0;

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

if((n & (1 << i)) != 0)

res++;

}

return res;

}

Date February 25, 2020
Category Leetcode
Comments No Comments

Count Negative Numbers in a Sorted Matrix

给一个已经sorted的2d matrix, 求里面负数的个数. 这个题sorted肯定是要用二叉搜索的. 但是为了速度, 应该考虑两个情况,一个是里面全是负数, 一个数里面没有负数. 第一个情况是在第一个数就是负数的情况下, 第二个求你高考是在最后一个数是负数的情况下.

class Solution {
    public int countNegatives(int[][] grid) {
        int res = 0;
        for(int[] g : grid){
            res += find(g);
        }
        return res;
    }
    
    private int find(int[] nums) {
        int left = 0 ;
        int right = nums.length  - 1;
        if(nums[right] >= 0)
            return 0;
        if(nums[left] < 0)
            return nums.length;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < 0)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return nums.length - left;
    }
}

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

class Solution {

public int countNegatives(int[][] grid) {

int res = 0;

for(int[] g : grid){

res += find(g);

}

return res;

}

private int find(int[] nums) {

int left = 0 ;

int right = nums.length - 1;

if(nums[right] >= 0)

return 0;

if(nums[left] < 0)

return nums.length;

while(left <= right) {

int mid = left + (right - left) / 2;

if(nums[mid] < 0)

right = mid - 1;

else

left = mid + 1;

}

return nums.length - left;

}

Date February 25, 2020
Category Leetcode
Comments No Comments

Valid Word Abbreviation

给一个abbr和一个word, 问abbr是不是word的缩写. 这个题太傻逼了, 各种corner cases. 而且还有’01’ ‘a’ 这种带leading 0的.

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        if(abbr.length() > word.length())
            return false;
        int cur = 0;
        for(int i = 0; i < abbr.length();) {
            if(abbr.charAt(i) >= 'a' && abbr.charAt(i) <='z') {
                if(cur < word.length() && abbr.charAt(i) != word.charAt(cur))
                    return false;
                else{ 
                    cur++;
                    i++;
                }
            }else if(abbr.charAt(i) > '0' && abbr.charAt(i) <= '9') {
                int right = i;
                while(right < abbr.length() && abbr.charAt(right) >= '0' && abbr.charAt(right) <= '9'){
                    right++;
                }
                cur += Integer.valueOf(abbr.substring(i, right));
                i = right;
            }else
                return false;
        }
        return cur == 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

class Solution {

public boolean validWordAbbreviation(String word, String abbr) {

if(abbr.length() > word.length())

return false;

int cur = 0;

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

if(abbr.charAt(i) >= 'a' && abbr.charAt(i) <='z') {

if(cur < word.length() && abbr.charAt(i) != word.charAt(cur))

return false;

else{

cur++;

i++;

}

}else if(abbr.charAt(i) > '0' && abbr.charAt(i) <= '9') {

int right = i;

while(right < abbr.length() && abbr.charAt(right) >= '0' && abbr.charAt(right) <= '9'){

right++;

}

cur += Integer.valueOf(abbr.substring(i, right));

i = right;

}else

return false;

}

return cur == word.length();

}

Date February 25, 2020
Category Leetcode
Comments No Comments

Logger Rate Limiter

做一个简单的rate limiter, 要求10秒内不能有重复的message. 直接用map做.

class Logger {
    Map<String, Integer> m;
    /** Initialize your data structure here. */
    public Logger() {
       m = new HashMap<>(); 
    }
    
    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    public boolean shouldPrintMessage(int timestamp, String message) {
        if(!m.containsKey(message)) {
            m.put(message, timestamp);
            return true;
        } else {
            if(timestamp - m.get(message) >= 10) {   
                m.put(message, timestamp);
                return true;
            }
            else {
                return false;
            }
        }
    }
}

/**
 * Your Logger object will be instantiated and called as such:
 * Logger obj = new Logger();
 * boolean param_1 = obj.shouldPrintMessage(timestamp,message);
 */

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

Map<String, Integer> m;

/** Initialize your data structure here. */

public Logger() {

m = new HashMap<>();

}

/** Returns true if the message should be printed in the given timestamp, otherwise returns false.

If this method returns false, the message will not be printed.

The timestamp is in seconds granularity. */

public boolean shouldPrintMessage(int timestamp, String message) {

if(!m.containsKey(message)) {

m.put(message, timestamp);

return true;

} else {

if(timestamp - m.get(message) >= 10) {

m.put(message, timestamp);

return true;

}

else {

return false;

}

/**

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

* Logger obj = new Logger();

* boolean param_1 = obj.shouldPrintMessage(timestamp,message);

*/

Date February 25, 2020
Category Leetcode
Comments No Comments

Is Subsequence

给一个s和一个t, 问s是不是t的子序列. 这个题有个follow up, 需要二叉才能过.

class Solution {
    public boolean isSubsequence(String s, String t) {
        int cur = 0;
        if(s.length() == 0)
            return true;
        for(int i = 0; i < t.length(); i++) {
            if(s.charAt(cur) == t.charAt(i))
                cur++;
            if(cur == s.length())
                return true;
        }
        return cur == s.length();
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution {

public boolean isSubsequence(String s, String t) {

int cur = 0;

if(s.length() == 0)

return true;

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

if(s.charAt(cur) == t.charAt(i))

cur++;

if(cur == s.length())

return true;

}

return cur == s.length();

}

Date February 25, 2020
Category Leetcode
Comments No Comments

String Compression

One Edit Distance

License Key Formatting

Valid Word Square

Longest Uncommon Subsequence I

Sort Integers by The Number of 1 Bits

Count Negative Numbers in a Sorted Matrix

Valid Word Abbreviation

Logger Rate Limiter

Is Subsequence

书脊

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

Categories

Tags

Links

February 2020
M	T	W	T	F	S	S
« Jan
					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