Posted Updated LeetCode / Easy / 复习2 minutes read (About 299 words)

290. Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

先将s分割成数组。
如果words的长度和pattern的长度不同则返回false。
用长度为26的数组储存pattern的字符。
同时遍历words和pattern，将pattern的字符换算成数字作为index，将words[i]填入数组。
如果数组中已经有word存在，则检查新的word和数组内的word是否相等。
如果不相等，则返回false。

最后遍历数组，比对各个字符中对应的word是否相等，如果有相等的，则返回false。由于数组长度固定，因此这个操作的时间复杂度是O(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
33
34
35
class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        String[] alphabet = new String[26];
        
        if(words.length != pattern.length()){
            return false;
        }
        
        for(int i = 0; i < pattern.length(); i++){
            
            if( alphabet[pattern.charAt(i) - 'a'] != null){
                if(!alphabet[pattern.charAt(i) - 'a'].equals(words[i])){
                    return false;
                }
            }
            else{
                alphabet[pattern.charAt(i) - 'a']  = words[i];
            }
        }
        
        for(int i = 0; i < alphabet.length; i++){
            for(int j = i+1; j < alphabet.length; j++){
                if(alphabet[i] == null || alphabet[j] == null){
                    continue;
                }
                if(alphabet[i].equals(alphabet[j])){
                    return false;
                }
            }
        }
        
        return true;
    }
}
Posted Updated LeetCode / Easya minute read (About 159 words)

415. Add Strings

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

按照正常加法计算方法即可。
先将指针设置在两个String的末尾。
每次计算位置上加和的结果。
最后需要将字符串翻转过来。

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 String addStrings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;
        
        StringBuffer ans = new StringBuffer();
        
        while( i >= 0 || j >= 0 || carry > 0){
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + carry;
            
            ans.append(result % 10);
            carry = result / 10;
            
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 210 words)

409. Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, “Aa” is not considered a palindrome here.

回文字符串除了中心一个元素，其他的字符必须成对出现。因此可以直接统计字符串里有几组成对的字符。

用数组记录字符出现的次数。
如果数组中某个字符出现了两次，则可以将其归零。然后可以组成的最长回文数字加2。
如果字符串还剩下其他字符未选择，则最长回文数可以加一。

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 longestPalindrome(String s) {
        int[] alphabet = new int['z' - 'A' + 1];
        int count = 0;
        int total = s.length();
        
        for(int i = 0; i < s.length(); i++){
            int index = s.charAt(i) - 'A';
            alphabet[index]+=1;
            if( alphabet[index] == 2 ){
                total -= 2;
                count += 2;
                alphabet[index] = 0;
            }
        }
        
        if(total != 0){
            count++;
        }

        return count;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 194 words)

547. Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

DFS搜索，当map[i][i] = 1时加入搜索。
搜索时将map[i][i]设为0。遍历并递归其数列。
当map[i][i]等于0时，返回。

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 Solution {
    int[][] map;
    public int findCircleNum(int[][] isConnected) {
        map = isConnected;
        int count = 0;
        
        for(int i = 0; i < isConnected.length; i++){
            if(map[i][i] == 1){
                count++;
                dfs(i);
            }
        }
        return count;
    }
    
    private void dfs(int i){
        if(map[i][i] == 0){
            return;
        }
        map[i][i] = 0;
        for(int j = 0; j < map[0].length; j++){
            if(map[i][j] == 1){
                dfs(j);
            }
        }
    }
}
Posted Updated LeetCode / Easya minute read (About 181 words)

705. Design HashSet

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

  • void add(key) Inserts the value key into the HashSet.
  • bool contains(key) Returns whether the value key exists in the HashSet or not.
  • void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

计算哈希值，使用数组实现Hash Set。

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
class MyHashSet {
    int PRIME = 1009;
    List<Integer>[] data;
    
    public MyHashSet() {
        data = new List[PRIME];
        for(int i = 0; i < PRIME; i++){
            data[i] = new LinkedList<Integer>();
        }
    }
    
    public void add(int key) {
        if(!contains(key)){
            int h = getHash(key);
            data[h].add(key);
        }
    }
    
    public void remove(int key) {
        int h = getHash(key);
        data[h].remove(new Integer(key));
    }
    
    public boolean contains(int key) {
        int h = getHash(key);
        for( int num : data[h] ){
            if( num == key ){
                return true;
            }
        }
        return false;
    }
    
    private int getHash(int o){
        return o % PRIME;
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */
Follow

Recents

Archives

Links

×