Posted Updated LeetCode / Easya minute read (About 132 words)

876. Middle of the Linked List

问题
Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

快慢指针，两个指针不同速度遍历链表。当快指针达到链表尾部时候，慢指针正好在中间。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        
        ListNode slowNode = head;
        ListNode fastNode = head;
        
        while( fastNode != null ){
            fastNode = fastNode.next;
            if (fastNode == null){
                return slowNode;
            }
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }
        return slowNode;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 216 words)

74. Search a 2D Matrix

问题
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

二分搜索，以整个数组尺寸作为搜索范围。
每次搜索中间值，如等于target则返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0;
        int right = (matrix.length * matrix[0].length) - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            int row = mid / matrix[0].length;
            int col = mid % matrix[0].length;
            if(matrix[row][col] == target){
                return true;
            }
            else if(matrix[row][col] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return false;
    }
}

双指针，先搜索到合适的行。
再搜索到合适的列。

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
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        int j = 0;
        
        while(i < matrix.length){
            if(matrix[i][0] == target){
                return true;
            }
            else if(matrix[i][0] < target){
                i++;
            }
            else{
                break;
            }
        }
        if( i == 0 ){
            return false;
        }
        i--;
        while(j < matrix[0].length){
            if(matrix[i][j] == target){
                return true;
            }
            j++;
        }
        return false;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 239 words)

36. Valid Sudoku

问题
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.

遍历并创建三组不同的哈希表，每个表内包含一组哈希集合。
如果访问的元素已在哈希集合内，则返回false

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
class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashMap<Integer,HashSet<Character>> rowMap = new HashMap<Integer,HashSet<Character>>();
        HashMap<Integer,HashSet<Character>> colMap = new HashMap<Integer,HashSet<Character>>();
        HashMap<Integer,HashSet<Character>> blockMap = new HashMap<Integer,HashSet<Character>>();

        for (int i = 0; i < board[0].length; i++ ){
            for (int j = 0; j < board.length; j++ ){
                char curChar = board[i][j];
                if (curChar == '.'){
                    continue;
                }
                if (!rowMap.containsKey(i)){
                    rowMap.put(i, new HashSet<Character>());
                }
                if (!colMap.containsKey(j)){
                    colMap.put(j, new HashSet<Character>());
                }
                if (!blockMap.containsKey(j/3*3+i/3)){
                    blockMap.put(j/3*3+i/3, new HashSet<Character>());
                }
                HashSet<Character> curRow = rowMap.get(i);
                HashSet<Character> curCol = colMap.get(j);
                HashSet<Character> curBlock = blockMap.get(j/3*3+i/3);
                
                if ( !curRow.contains(curChar) && !curCol.contains(curChar) && !curBlock.contains(curChar) ){
                    curRow.add(curChar);
                    curCol.add(curChar);
                    curBlock.add(curChar);
                }
                else{
                    return false;
                }   
            }
        }
        return true;
    }
}

Posted Updated LeetCode / Medium / 复习2 minutes read (About 264 words)

923. 3Sum With Multiplicity

Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 109 + 7.

首先遍历元素，根据元素的值和出现次数建立哈希表。
然后再哈希表中选择三个元素，如果和等于target，则计算三个元素出现次数的乘积。
最后除以重复计算的次数。
由于数值较大，因此中途计算应该采用长整型long。

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 {
    public int threeSumMulti(int[] arr, int target) {
        //enumberate every element and put them into the map
        HashMap<Integer, Long> map = new HashMap<Integer, Long>();
        long count = 0;
        
        for ( int num : arr ){
            if (!map.containsKey(num)){
                map.put(num, (long)1);
            }
            else{
                map.put(num, map.get(num)+1);
            }
        }
        
        //traverse whole elements and select three numbers
        
        for ( int a : map.keySet() ){
            long totalA = map.get(a);
            for (int b : map.keySet()){
                long totalB = map.get(b);
                if ( a == b ){
                    if (totalB < 2){
                        continue;
                    }
                    totalB = totalB - 1;
                }

                int c = target - a - b;
                if ( map.containsKey(c) ){
                    long totalC = map.get(c);
                    long total = 0;
                    if ( a == b && b == c ){
                        total = totalA * totalB * ( totalC - 2 ) ;
                    }
                    else if ( b == c || a == c ){
                        total = totalA * totalB * ( totalC - 1 ) ;
                    }
                    else{
                        total = totalA * totalB * totalC;
                    }
                    if ( total > 0 ){
                        count += total;
                    }

                }
            }
        }
        count/=6;
        int ans = (int) (count % 1000000007);
            
        return ans;
    }
}

242. Valid Anagram
Posted Updated LeetCode / Easya minute read (About 163 words)

242. Valid Anagram

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Solution

两数组相等时，直接遍历两个数组并记录各个字符出现的数量。
一个数组遍历时用做加法，另一个做减法。
如果最后每个字符出现的数量均为0，则返回真。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length()!=t.length()){
            return false;
        }
        int[] dic = new int[26];
        for (int i = 0; i < s.length(); i++){
            dic[s.charAt(i)-'a']++;
            dic[t.charAt(i)-'a']--;
        }
        
        for(int num : dic){
            if ( num != 0 ){
                return false;
            }
        }
        return true;
    }
}
Follow

Recents

Archives

Links

×