LeetCode 240 LintCode 38 – Python 3 (Week 10 – 03)

 class Solution:
    """
    @param matrix: A list of lists of integers
    @param target: An integer you want to search in matrix
    @return: An integer indicate the total occurrence of target in the given matrix
    """
    def searchMatrix(self, matrix, target):
        # write your code here
        if matrix == [] or matrix[0] == []:
            return 0
            
        row, column = len(matrix), len(matrix[0])
        i, j = row - 1, 0
        count = 0
        while i >= 0 and j < column:
            if matrix[i][j] == target:
                count += 1
                i -= 1
                j += 1
            elif matrix[i][j] < target:
                j += 1
            elif matrix[i][j] > target:
                i -= 1
        return count

O(m+n) time and O(1) extra space.

LeetCode 74 LintCode 28 – Python 3 (Week 10 – 02)

Solution 1

 class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix: return False
         
        row, column = len(matrix), len(matrix[0])
        if not row or not column: return False 
        
        start, end = 0, row * column - 1
        
        while start + 1 < end:
            mid = int(start + (end - start) / 2)
            
            r = int(mid / column)
            c = mid % column
            
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] < target:
                start = mid
            else:
                end = mid
        
        if matrix[int(start / column)][start % column] == target or matrix[int(end / column)][end % column] == target:
            return True
        return False

Time complexity is O(log n*m). Space complexity is O(1).

Solution 2

 class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix: return False
         
        row, column = len(matrix), len(matrix[0])
        if not row or not column: return False
        
        start, end = 0, row - 1
        
        while start + 1 < end:
            mid = int(start + (end - start) / 2)
            if matrix[mid][0] == target:
                return True
            elif matrix[mid][0] < target:
                start = mid
            else:
                end = mid
                
        if matrix[start][0] > target:
            r = start - 1
        elif start < end and matrix[end][0] <= target:
            r = end
        else:
            r = start
            
        if r < 0 or r >= row: return False
        
        start, end = 0, column - 1
        
        while start + 1 < end:
            mid = int(start + (end - start) / 2)
            
            if matrix[r][mid] == target:
                return True
            elif matrix[r][mid] < target:
                start = mid
            else:
                end = mid
                
        if matrix[r][start] == target or matrix[r][end] == target:
            return True
        return False

Time complexity is O(log n + log m) = O(log n*m) . Space complexity is O(1).

LeetCode 35 LintCode 60 – Python 3 (Week 10 – 01)

class Solution:
    """
    @param A: an integer sorted array
    @param target: an integer to be inserted
    @return: An integer
    """
    def searchInsert(self, A, target):
        # write your code here
        if not A: return 0
        
        start, end = 0, len(A) - 1
        
        while start + 1 < end:
            mid = int (start + (end - start) / 2)
            if A[mid] == target:
                return mid
            if A[mid] < target:
                start = mid
            if A[mid] > target:
                end = mid
                
        if A[end] < target:
            return end + 1
        if A[start] >= target:
            return start
        return end

LintCode 637 – Java

 public class Solution {
    /**
     * @param word: a non-empty string
     * @param abbr: an abbreviation
     * @return: true if string matches with the given abbr or false
     */
    public boolean validWordAbbreviation(String word, String abbr) {
        // write your code here
        if (word == null || abbr == null) {
            return false;
        }
        
        int i = 0, j = 0;
        char[] s = word.toCharArray();
        char[] t = abbr.toCharArray();
        
        while (i < s.length && j < t.length) {
            if (Character.isDigit(t[j])) {
                if (t[j] == '0') {
                    return false;
                }
                
            int val = 0;
            while (j < t.length && Character.isDigit(t[j])) {
                    val = val * 10 + t[j] - '0';
                    j++;
                }
                
                i += val;
            } else {
                if (s[i] != t[j]) {
                    return false;
                }
                i++;
                j++;
            }    
        }
        
        return i == s.length && j == t.length;
    }
}

LintCode 60 – Java

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: interval list.
     * @return: A new interval list.
     */
    public List<Interval> merge(List<Interval> intervals) {
        // write your code here
        List<Interval> ans = new ArrayList<>();
        
        if (intervals == null) {
            return ans;
        }
        
        intervals.sort(Comparator.comparing(i -> i.start));
 //lambda 函数
        Interval last = null;
        
        for (Interval item : intervals) {
                if (last == null || last.end < item.start) {
                    ans.add(item);
                    last = item;
                } else {
                    last.end = Math.max(last.end, item.end);
                }
            }
        
         return ans;

    }
}

LeetCode 704 LintCode 14 – Python 3 (Week 09 – 08)

Basic binary search. Time complexity is O(log n). Space complexity is O(1).

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums) - 1
        
        while start + 1 < end:
            mid = int (start + (end - start) / 2)
            if nums[mid] == target:
                end = mid 
            if nums[mid] < target:
                start = mid
            if nums[mid] > target:
                end = mid
        
        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        
        return -1

LeetCode 91 LintCode 512 – Python 3 (Week 09 – 07)

Solution 1: Use dp

class Solution:
    def numDecodings(self, s: str) -> int:
        if len(s) == 0 or s[0] == '0': return 0
        if len(s) == 1: return 1
        
        w1, w2 = 1, 1
        for i in range(1, len(s)):
            w = 0
            if s[i] == '0' and not 10 <= int(s[i-1 : i+1]) <= 26:
                return 0
            if s[i] != '0':
                w = w1
            if 10 <= int(s[i-1 : i+1]) <= 26:
                w += w2
            w2 = w1
            w1 = w
            
        return w1

Time complexity is O(n). Time complexity is O(1).

LintCode 637 LeetCode 408 – Python 3 (Week 09 – 06)

 class Solution:
    """
    @param word: a non-empty string
    @param abbr: an abbreviation
    @return: true if string matches with the given abbr or false
    """
    def validWordAbbreviation(self, word, abbr):
        # write your code here
        i, j = 0, 0
        
        while i < len(word) and j < len(abbr):
                if word[i] == abbr[j]:
                    i += 1
                    j += 1
                elif abbr[j].isdigit() and abbr[j] != '0':
                    start = j
                    while j < len(abbr) and abbr[j].isdigit():
                        j += 1
                    i = i + int(abbr[start : j])
                else:
                    return False
        
        return i == len(word) and j == len(abbr)

Time complexity is O(nm). Space complexity is O(1).

Pay attention to that abbr[j] is string. The first digit should not be 0.

LintCode 1380 – Python 3 (Week 09 – 05)

class Solution:
    """
    @param logs: the logs
    @return: the log after sorting
    """
    def logSort(self, logs):
        # Write your code here
        
        type1, type2 = [], []
        for log in logs:
            i = log.index(' ')
            if log[i+1].isdigit():
                type2.append(log)
            else:
                type1.append((i, log))
        
        type1.sort(key = lambda pair: (pair[1][pair[0]+1:], pair[1][:pair[0]]))
        output = [pair[1] for pair in type1]
        
        return output + type2

Time complexity is O(nlogn). Space complexity is O(1).

LeetCode 56 LintCode 156 – Python 3 (Week 09 – 04)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ans = []
        
        for interval in sorted(intervals, key = lambda x: x[0]):
            if len(ans) == 0 or ans[-1][1] < interval[0]:
                ans.append(interval)
            else:
                ans[-1][1] = max(ans[-1][1], interval[1])
                
        return ans

Time complexity is O(nlogn): sorted(). Space complexity is O(1).

Design a site like this with WordPress.com
Get started