My Personal Blog

Leetcode Q10

I tried to use non-deterministic state machine first, but the code seems too slow that the Time Limit was reached :(

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
class Solution {
Character repchar = null;
Character stopchar = null;
int maxlen = 0;
int i = 0;
String p = null;
String s = null;
int j = 0;

void compile(){
if(j >= p.length()){
repchar = null;
return;
}
repchar = p.charAt(j++);
if(j < p.length()){
if(p.charAt(j) == '*'){
stopchar = j < s.length() -1 ? p.charAt(++j) : null;
maxlen = 0;
}else{
stopchar = p.charAt(j);
maxlen = 1;
}
}else{
stopchar = null;
maxlen = 1;
}

}

public boolean isMatch(String s, String p) {
this.p = p;
this.s = s;
compile();
while( i < s.length()){
char c = s.charAt(i);
if(repchar == null)
return false;

if(maxlen == 1 || (stopchar != null && c != stopchar)){
if(repchar == '.' || repchar == c){
i++;
}else{
return false;
}
}
if((stopchar != null &&c == stopchar) || maxlen == 1)
compile();

}
if(repchar != null)
return false;
return true;
}
}

Leetcode Q8

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
static inline bool is_char(char c){
return '0' <= c && c <= '9';
}

int myAtoi(char* str) {
long ret = 0;
int sign = 1;
if(!str)
return ret;
while(*str == ' ')
str++;
if(*str && *str == '-'){
sign = -1;
str++;
}else if(*str && *str == '+')
str++;

while(*str && is_char(*str)){
ret = ret * 10 + (*str - '0');
if(ret * sign < (1 << 31))
return 1 << 31;
if(ret * sign > ~(1 << 31))
return ~(1 << 31);

str++;
}
return ret * sign;
}

Leetcode Q7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public int reverse(int x) {
long i = 0;
int l = String.valueOf(Math.abs(x)).length();
int count = 1;
for(;l>1;l--){
count *= 10;
}

while(x!=0){
i += ((long)x%10) * (long)count;
count /= 10;
x /= 10;
}
if(i>Integer.MAX_VALUE || i<Integer.MIN_VALUE){
return 0;
}
if(x<0) i*= -1;
return (int)i;
}
}

Leetcode Q32

First attempt was a naive solution with Time Complexity O(n^2)

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 longestValidParentheses(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int[] ends = new int[s.length()+1];
int longest = 0;
for(int i=s.length() - 1; i >= 0; i--){
for(int j = i; j < s.length(); j++){
if(s.charAt(i) == '(' && s.charAt(j) == ')'
&& (j - i == 1 || dp[i + 1][j - 1])){
dp[i][j] = true;
ends[i] = j;
int nexthop = j + 1;
while(ends[nexthop] != 0){
ends[i] = ends[nexthop];
int end = ends[i];
nexthop = end + 1;
dp[i][end] = true;
}
longest = Math.max(longest, ends[i] - i + 1);
// System.out.println(i + " " + j + " " + longest);
}
}
}
return longest;
}
}

Leetcode Q5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public String longestPalindrome(String s) {
if(s.length() <= 2)
return s;
int lo = 0, len = 0;
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i= s.length() - 2; i >= 0; i--){
for(int j=i+1; j < s.length(); j++){
if(s.charAt(i) == s.charAt(j) &&
(j - i < 3 || dp[i + 1][j - 1])){
dp[i][j] = true;
int tlen = j - i;
if(tlen > len){
len = tlen;
lo = i;
}
}
}
}
return s.substring(lo,lo + len + 1);
}
}

Leetcode Q3

There are basically two options here

  1. O(n^3), loop through every possibility to find the longest substring
  2. Use a hashmap to indicate the position of each character. If a replicate character is encountered, and is contained in the current substring, current substring will be updated such that it will start from one character next to the previous one, curr count will be updated accordingly.
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 lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int longest = 0;
int curr = 0;
int prev = 0;
for(int i=0; i < s.length(); i++){
char c = s.charAt(i);
if(map.get(c) != null && map.get(c) >= prev){
prev = map.get(c);
map.put(c, i);
longest = Math.max(curr, longest);
curr = i - prev;
prev++;
}else{
map.put(c, i);
curr++;
}
}
longest = Math.max(curr, longest);
return longest;
}
}

leetcode Q2

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
int carry = 0;

while( l1 != null || l2 != null){
int l1i = l1 != null ? l1.val : 0;
int l2i = l2 != null ? l2.val : 0;
int combine = (l1i + l2i) + carry;
int newval = combine % 10;
carry = combine / 10;

ListNode tmp = new ListNode(newval);

curr.next = tmp;
curr = tmp;
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}

if(carry != 0){
curr.next = new ListNode(carry);
}

return dummy.next;
}
}

Leetcode Q1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
int[] res = new int[2];

for(int i=0; i < nums.length; i++){
int remaining = target - nums[i];
if(map.get(remaining) == null){
map.put(nums[i], i);
}else{
res[0] = map.get(remaining);
res[1] = i;
return res;
}
}
return res;
}
}

Leetcode Q9

https://leetcode.com/problems/palindrome-number/description/

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 boolean isPalindrome(int x) {
if(x == 0)
return true;
if(x < 0)
return false;
long rev = 0;
int val = x;
int count = 0;
while( val!= 0){
rev = rev * 10 + val % 10;
val /= 10;
count++;
if( rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE)
return false;
}
int irev = (int)rev;
while(x != irev){
int shift = count * 10;
int left = irev / shift;
int right = x % 10;
if( left != right)
return false;
x/= 10;
irev /= shift;
count--;
}
return true;
}
}