Huahua's Tech Road

花花酱 LeetCode 1262. Greatest Sum Divisible by Three

By zxi on November 26, 2019

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

Constraints:

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

Solution: DP

dp[i] := max sum that has a remainder i when mod 3.

dp[(i + num) % 3] = max( dp[(i + num) % 3] , dp[i] + num)

ans: dp[0]

C++

// Author: Huahua

class Solution {

public:

int maxSumDivThree(vector<int>& nums) {

vector<int> dp(3);

for (int num : nums) {

vector<int> tmp(dp);

for (int s : tmp)

dp[(s + num) % 3] = max(dp[(s + num) % 3], s + num);

}

return dp[0];

}

};

花花酱 LeetCode 1261. Find Elements in a Contaminated Binary Tree

By zxi on November 26, 2019

Given a binary tree with the following rules:

root.val == 0
If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2

Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

You need to first recover the binary tree and then implement the FindElements class:

FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first.
bool find(int target) Return if the target value exists in the recovered binary tree.

Example 1:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output

[null,false,true]

Explanation FindElements findElements = new FindElements([-1,null,-1]); findElements.find(1); // return False findElements.find(2); // return True

Example 2:

Input
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
Output

[null,true,true,false]

Explanation FindElements findElements = new FindElements([-1,-1,-1,-1,-1]); findElements.find(1); // return True findElements.find(3); // return True findElements.find(5); // return False

Example 3:

Input
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
Output

[null,true,false,false,true]

Explanation FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]); findElements.find(2); // return True findElements.find(3); // return False findElements.find(4); // return False findElements.find(5); // return True

Constraints:

TreeNode.val == -1
The height of the binary tree is less than or equal to 20
The total number of nodes is between [1, 10^4]
Total calls of find() is between [1, 10^4]
0 <= target <= 10^6

Solutoin 1: Recursion and HashSet

Time complexity: Recover O(n), find O(1)
Space complexity: O(n)

C++

// Author: Huahua

class FindElements {

public:

FindElements(TreeNode* root) {

recover(root, 0);

}

bool find(int target) {

return s_.count(target);

}

private:

unordered_set<int> s_;

void recover(TreeNode* root, int val) {

if (!root) return;

root->val = val;

s_.insert(val);

recover(root->left, val * 2 + 1);

recover(root->right, val * 2 + 2);

}

};

Solution 2: Recursion and Binary format

The binary format of t = (target + 1) (from high bit to low bit, e.g. in reverse order) decides where to go at each node.
t % 2 == 1, go right, otherwise go left
t = t / 2 or t >>= 1

e.g. target = 13, t = 13 + 1 = 14

t = 14, t % 1 = 0, t / 2 = 7, left

t = 7, t % 1 = 1, t / 2 = 3, right

t = 3, t % 1 = 1, t / 2 = 1, right

13 => right, right, left

Time complexity: Recover O(n), find O(log|target|)
Space complexity: O(1)

C++

// Author: Huahua

class FindElements {

public:

FindElements(TreeNode* root): root_(root) {

recover(root, 0);

}

bool find(int target) {

++target;

stack<bool> right;

while (target != 1) {

right.push(target & 1);

target >>= 1;

}

TreeNode* node = root_;

while (!right.empty() && node) {

node = right.top() ? node->right : node->left;

right.pop();

}

return node;

}

private:

TreeNode* root_;

void recover(TreeNode* root, int val) {

if (!root) return;

root->val = val;

recover(root->left, val * 2 + 1);

recover(root->right, val * 2 + 2);

}

};

花花酱 LeetCode 1260. Shift 2D Grid

By zxi on November 26, 2019

Given a 2D grid of size n * m and an integer k. You need to shift the grid k times.

In one shift operation:

Element at grid[i][j] becomes at grid[i][j + 1].
Element at grid[i][m - 1] becomes at grid[i + 1][0].
Element at grid[n - 1][m - 1] becomes at grid[0][0].

Return the 2D grid after applying shift operation k times.

Example 1:

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

Example 2:

Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Example 3:

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

Constraints:

1 <= grid.length <= 50
1 <= grid[i].length <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

Solution 1: Simulation

Simulate the shift process for k times.

Time complexity: O(k*n*m)
Space complexity: O(1) in-place

C++

// Author: Huahua, 80ms, 13.5 MB

class Solution {

public:

vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {

const int n = grid.size();

const int m = grid[0].size();

while (k--) {

int last = grid[n - 1][m - 1];

for (int i = n - 1; i >= 0; --i)

for (int j = m - 1; j >= 0; --j) {

if (i == 0 && j == 0)

grid[i][j] = last;

else if (j == 0)

grid[i][j] = grid[i - 1][m - 1];

else

grid[i][j] = grid[i][j - 1];

}

return grid;

}

};

Solution 2: Rotate

Shift k times is equivalent to flatten the matrix and rotate by -k or (m*n – k % (m * n)).

Time complexity: O(m*n)
Space complexity: O(m*n)

C++

// Author: Huahua, 68 ms, 14.4 MB

class Solution {

public:

vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {

const int n = grid.size();

const int m = grid[0].size();

k = m * n - k % (m*n);

vector<int> g;

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

g.insert(end(g), begin(grid[i]), end(grid[i]));

rotate(begin(g), begin(g) + k, end(g));

auto it = begin(g);

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

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

grid[i][j] = *it++;

return grid;

}

};

O(1) space in-place rotation

C++

// Author: Huahua， 68 ms, 13.6 MB

class MatrixIterator {

public:

MatrixIterator(vector<vector<int>>& data, int index = 0) :

data_(data),

index_(index) {}

MatrixIterator& operator++() {

++index_;

return *this;

}

MatrixIterator& operator--() {

--index_;

return *this;

}

MatrixIterator operator +(int dis) const {

return MatrixIterator(data_, index_ + dis);

}

MatrixIterator operator -(int dis) const {

return MatrixIterator(data_, index_ - dis);

}

bool operator==(const MatrixIterator& o) const {

return data_ == o.data_ && index_ == o.index_;

}

bool operator!=(const MatrixIterator& o) const {

return data_ != o.data_ || index_ != o.index_;

}

ptrdiff_t operator-(const MatrixIterator& o) const {

return index_ - o.index_;

}

MatrixIterator& operator=(const MatrixIterator& o) {

data_ = o.data_;

index_ = o.index_;

return *this;

}

int& operator*() {

if (index_ <= 0) {

return data_[0][0];

} else if (index_ >= m() * n()) {

return data_.back().back();

} else {

return data_[index_ / m()][index_ % m()];

}

private:

int n() const { return data_.size(); }

int m() const { return n() == 0 ? 0 : data_[0].size(); }

vector<vector<int>>& data_;

int index_;

};

namespace std {

template<>

struct iterator_traits<MatrixIterator> {

typedef ptrdiff_t difference_type;

typedef int value_type;

typedef int* pointer;

typedef int& reference;

typedef random_access_iterator_tag iterator_category;

};

}

class Solution {

public:

vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {

const int n = grid.size();

const int m = grid[0].size();

k = m * n - k % (m*n);

MatrixIterator it(grid);

rotate(it, it + k, it + m * n);

return grid;

}

};

Python中的整型占多少个字节？

By zxi on November 24, 2019

说到计算机中的整型，相信很多人都会联想到32位整型（或者int），是程序员日常生活中用的最多的一种类型。32位整型顾名思义，占用32个位也就是4个字节，取值范围−2,147,483,648~ 2,147,483,647 。C/C++中是4个字节，Java中也是4个字节，但是Python中呢？

我们知道Python中也有int类，而且非常好用，原生支持高精度计算。但是Python中的一个整型到底占用多少字节呢？我相信绝大多数的Python程序员从未想过这一点，越是习以为常的东西越是不会在意它的存在。

在Python中，如果想要知道一个对象所占用的内存大小，只需要使用sys.getsizeof这个API就可以了。那就让我们来试一下不同的整数

print(sys.getsizeof(0)) # 24

print(sys.getsizeof(1)) # 28

print(sys.getsizeof(2)) # 28

print(sys.getsizeof(2**15)) # 28

print(sys.getsizeof(2**30)) # 32

print(sys.getsizeof(2**128)) # 44

从上面的小实验可以看出，一个整型最少要占24字节(0)，1开始就要占用28个字节，到了2的30次方开始要占用32个字节，而2的128次方则要占用44个字节。我们可以得到两点规律，1. 字节数随着数字增大而增大。2. 每次的增量是4个字节。好像至此已经回答了我们的题目中的问题：Python中的整型占多少个字节？答案是：变长的（相对于int32的定长），而且最少24个字节。

你以为本文到这里就结束了吗？那你就图样图森破了。一个整型数2，居然要占用28个字节！这完全了颠覆了我的认知，我一定搞清楚为什么。在哥们的帮助下，我找到了Python的源码。 https://github.com/python/cpython

Python的官方实现是C语言，所以叫cpython。这也就意味着只要Python还在，C就会不消失。其他实现还有jython(Java), IronPython (.Net), PyPy (Python)。

第一件事情要搞清楚的是Python中int类型在cpython的名字是什么？看了半天，在 longobject.h 中发现了一个叫 PyLongObject 的结构体。然而它只是一个马甲，是 _longobject的别名。在longintrepr.h中找到了 _longobject 的定义如下：

struct _longobject {

PyObject_VAR_HEAD

digit ob_digit[1];

};

在文件的开头就看到了typedef uint32_t digit;，digit就是unit32_t, 每个元素占4个字节。但PyObject_VAR_HEAD又是什么鬼？在object.h中发现了它是个宏，上面的注释倒是挺有意思的。

/* PyObject_VAR_HEAD defines the initial segment of all variable-size

container objects. These end with a declaration of an array with 1

element, but enough space is malloc'ed so that the array actually

has room for ob_size elements. Note that ob_size is an element count,

not necessarily a byte count.

define PyObject_VAR_HEAD PyVarObject ob_base;

等一下，PyVarObject又是什么？还好定义就在下面。

typedef struct {

PyObject ob_base;

Py_ssize_t ob_size; /* Number of items in variable part */

} PyVarObject;

又一层嵌套，是不是已经晕了，继续查看PyObject的定义，这次反而在上面了。

typedef struct _object {

_PyObject_HEAD_EXTRA

Py_ssize_t ob_refcnt;

struct _typeobject *ob_type;

} PyObject;

有完没完啊？_PyObject_HEAD_EXTRA又是什么？看了一下发现它只在debug build中有定义，这里就不展开了。Py_ssize_t等于ssize_t如果有定义的话， ssize_t在64位的机器上就是long。_typeobject又是什么？感觉应该非常大，不然就不会用指针了。不过话说回来，既然用了指针，我又何必去关心它是什么呢？反正就是8个字节而已，指向一个内存地址。至此真相大了一个白，如果我们把structs flatten, PyLongObject 定义如下：

struct PyLongObject {

long ob_refcnt; // 8 bytes

struct _typeobject *ob_type; // 8 bytes

long ob_size; // 8 bytes

unsigned int ob_digit[1]; // 4 bytes * abs(ob_size)

};

ob_refcnt引用计数 8个字节，ob_type类型信息 8个字节（指针），ob_size变长部分元素的个数，8个字节。ob_digit变长的数据部分，字节数为4*abs(ob_size)，ob_size可以为0，所以最少8+8+8=24字节，每次增量都是4 (unsigned int) 的倍数。这和我们之前观察到的实验结果吻合。

以上都是基于64位的Python，对于32位的版本，定义如下：

struct PyLongObject {

int ob_refcnt; // 4 bytes

struct _typeobject *ob_type; // 4 bytes

int ob_size; // 4 bytes

unsigned short ob_digit[1]; // 2 bytes * abs(ob_size)

};

32位就要比64位小很多了，最少12个字节，增量为2个字节。

好了，今天就写到这里。相信你对整型数或者Python有了一个新的认识。下面一篇我们会将会介绍整型数在Python中的表示和计算。

花花酱 LeetCode 1269. Number of Ways to Stay in the Same Place After Some Steps

By zxi on November 24, 2019

You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

Example 2:

Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

Example 3:

Input: steps = 4, arrLen = 2
Output: 8

Constraints:

1 <= steps <= 500
1 <= arrLen <= 10^6

Solution: DP

Since we can move at most steps, we can reduce the arrLen to min(arrLen, steps + 1).

dp[i][j] = dp[i-1][j – 1] + dp[i-1][j] + dp[i-1][j+1] // sum of right, stay, left

Time complexity: O(steps * steps)
Space complexity: O(steps)

C++

// Author: Huahua

class Solution {

public:

int numWays(int steps, int arrLen) {

const int kMod = 1e9 + 7;

arrLen = min(steps + 1, arrLen);

vector<int> dp(arrLen);

dp[0] = 1;

for (int i = 0; i < steps; ++i) {

vector<int> tmp(dp.size());

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

tmp[j] = dp[j];

if (j > 0) tmp[j] = (tmp[j] + dp[j - 1]) % kMod;

if (j < arrLen - 1) tmp[j] = (tmp[j] + dp[j + 1]) % kMod;

}

swap(dp, tmp);

}

return dp[0];

}

};