花花酱 LeetCode 700. Search in a Binary Search Tree

By zxi on July 12, 2018

Problem

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example,

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2

You should return this subtree:

      2     
     / \   
    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Solution: Recursion

Time complexity: O(logn ~ n)

Space complexity: O(logn ~ n)

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

TreeNode* searchBST(TreeNode* root, int val) {

if (root == nullptr) return nullptr;

if (val == root->val)

return root;

else if (val > root->val)

return searchBST(root->right, val);

return searchBST(root->left, val);

}

};

花花酱 LeetCode 704. Binary Search

By zxi on July 12, 2018

Problem

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

Note:

You may assume that all elements in nums are unique.
n will be in the range [1, 10000].
The value of each element in nums will be in the range [-9999, 9999].

Solution: Binary Search

Time complexity: O(logn)

Space complexity: O(1)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

int search(vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

int m = (r - l) / 2 + l;

if (nums[m] == target)

return m;

else if (nums[m] > target)

r = m;

else

l = m + 1;

}

return -1;

}

};

STL

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int search(vector<int>& nums, int target) {

auto it = lower_bound(nums.begin(), nums.end(), target);

if (it == nums.end() || *it != target) return -1;

return it - nums.begin();

}

};

花花酱 LeetCode 709. To Lower Case

By zxi on July 12, 2018

Problem

Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

string toLowerCase(string str) {

for (char &c : str)

if (c >= 'A' && c <= 'Z') c = c - 'A' + 'a';

return str;

}

};

Java

// Author: Huahua, 1 ms

class Solution {

public String toLowerCase(String str) {

char[] s = str.toCharArray();

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

if (s[i] >= 'A' && s[i] <= 'Z') s[i] = (char)(s[i] - 'A' + 'a');

return new String(s);

}

Python3

# Author: Huahua, 40 ms

class Solution:

def toLowerCase(self, str):

ans = ''

for c in str:

if c >= 'A' and c <= 'Z':

ans += chr(ord(c) + 32)

else:

ans += c

return ans

Python3 1-linear

# Author: Huahua, 68 ms

class Solution:

def toLowerCase(self, str):

return ''.join(chr(ord(c) + 32) if c >= 'A' and c <= 'Z' else c for c in str)

花花酱 LeetCode 840. Magic Squares In Grid

By zxi on July 8, 2018

Problem

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).

Example 1:

Input: [[4,3,8,4],
        [9,5,1,9],
        [2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15

Solution

Time complexity: O(m*n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int numMagicSquaresInside(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

int ans = 0;

for (int i = 0; i < m - 2; ++i)

for (int j = 0; j < n - 2; ++j)

ans += magic(grid, j, i);

return ans;

}

private:

int magic(const vector<vector<int>>& grid, int x, int y) {

vector<int> rows(3);

vector<int> cols(3);

vector<int> exps{15, 15, 15};

int dig = 0;

for (int i = 0; i < 3; ++i)

for (int j = 0; j < 3; ++j) {

int v = grid[y + i][x + j];

if (v <= 0 || v > 9) return 0; // must between 1 and 9

rows[i] += v;

cols[j] += v;

if (i == j) dig += v;

}

return rows == exps && cols == exps && dig == 15;

}

};

花花酱 LeetCode 867. Transpose Matrix

By zxi on July 8, 2018

Given a matrix A, return the transpose of A.

The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

Example 2:

Input: [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]

Note:

1 <= A.length <= 1000
1 <= A[0].length <= 1000

Solution: Brute Force

Time complexity: O(mn)

Space complexity: O(mn)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<vector<int>> transpose(vector<vector<int>>& A) {

int m = A.size();

int n = A[0].size();

vector<vector<int>> ans(n, vector<int>(m));

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

ans[j][i] = A[i][j];

return ans;

}

};

Posts tagged as “easy”

花花酱 LeetCode 700. Search in a Binary Search Tree

Problem

Solution: Recursion

花花酱 LeetCode 704. Binary Search

Problem

Solution: Binary Search

花花酱 LeetCode 709. To Lower Case

Problem

Solution

C++

Java

Python3

Python3 1-linear

花花酱 LeetCode 840. Magic Squares In Grid

Problem

Solution

花花酱 LeetCode 867. Transpose Matrix

Solution: Brute Force

C++