124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

给定一个二叉树，要求树中某条路径的最大和。注意路径可以不经过叶子节点，也可以不经过根节点，即树中任意一条相连的路径即可。

使用递归的思路。对于一个节点，经过它的最大和路径有如下几种情况：

• 仅包含节点本身（当左、右、父亲节点的路径和都是负数时）
• 穿过该节点，且还会往该节点的父亲上面走，说明最优路径的跟在该节点上面，该节点的左子树或右子树路径构成了最优路径的一部分
• 没有穿过该节点，即该节点为最优路径的跟，则路径的两端可能是该节点的左右孩子

完整代码如下，辅助函数maxSum的返回值即为上面的前两种情况的最大值，maxSum返回之后有可能构成父节点的最大和。ans则是全局的最大和，还包括上面列的第三种情况。

class Solution {
public:
	int maxSum(TreeNode *root, int &ans) {
		if (root == NULL)return 0;
		int left_sum = maxSum(root->left, ans), right_sum = maxSum(root->right, ans);

		// 经过root节点的子树，还得往root的父亲上面走
		int left_or_right_root = max(root->val, root->val + max(left_sum, right_sum));

		// 最后一项是以root为根，左右子树都走，即不往root的父亲上面走
		ans = max(ans, max(left_or_right_root, root->val + left_sum + right_sum));

		return left_or_right_root;
	}
	int maxPathSum(TreeNode* root) {
		int ans = INT_MIN;
		maxSum(root, ans);
		return ans;
	}
};

本代码提交AC，用时36MS。

1424. Diagonal Traverse II

Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

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

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Example 3:

Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]]
Output: [1,4,2,5,3,8,6,9,7,10,11]

Example 4:

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

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i].length <= 10^5
• 1 <= nums[i][j] <= 10^9
• There at most 10^5 elements in nums.

如上图所示，给定一个残缺矩阵，要求遍历每个对角线，输出所有元素的值。

朴素解法会TLE，特别是如果有某一行或某一列比其他行列长特别多的情况。

提示解法：观察规律发现，处于同一对角线的元素的行列下标之和相等。所以我们可以把所有元素的行列下标进行排序，如果下标和相等，则处于同一对角线，按行下标从大到小排序；如果下标和不相等，则按下标和从小到大排序。完整代码如下：

bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) {
	int sum1 = p1.first + p1.second, sum2 = p2.first + p2.second;
	if (sum1 == sum2) {
		return p1.first > p2.first;
	}
	else {
		return sum1 < sum2;
	}
}
class Solution {
public:
	vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
		vector<pair<int, int>> idxs;
		for (int i = 0; i < nums.size(); ++i) {
			for (int j = 0; j < nums[i].size(); ++j) {
				idxs.push_back(make_pair(i, j));
			}
		}
		sort(idxs.begin(), idxs.end(), cmp);
		vector<int> ans;
		for (int i = 0; i < idxs.size(); ++i) {
			ans.push_back(nums[idxs[i].first][idxs[i].second]);
		}
		return ans;
	}
};

本代码提交AC，用时500MS。

1422. Maximum Score After Splitting a String

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:

Input: s = "1111"
Output: 3

Constraints:

• 2 <= s.length <= 500
• The string s consists of characters ‘0’ and ‘1’ only.

给定一个仅包含0/1的字符串，要求把它分成两半，使得左边的0的数目加上右边的1的数目的和最大。

简单题，提前算好左边的0的数目的累加和，和右边的1的数目的累加和。完整代码如下：

class Solution {
public:
	int maxScore(string s) {
		int n = s.size();
		vector<int> zeros(n, 0), ones(n, 0);
		for (int i = 0; i < n - 1; ++i) {
			if (i == 0)zeros[i] = (s[i] == '0' ? 1 : 0);
			else zeros[i] = zeros[i - 1] + (s[i] == '0' ? 1 : 0);

			int j = n - i - 1;
			if (j == n - 1)ones[j] = (s[j] == '1' ? 1 : 0);
			else ones[j] = ones[j + 1] + (s[j] == '1' ? 1 : 0);
		}
		int ans = 0;
		for (int i = 0; i < n - 1; ++i) {
			ans = max(ans, zeros[i] + ones[i + 1]);
		}
		return ans;
	}
};

本代码提交AC，用时4MS。

LeetCode Leftmost Column with at Least a One

(This problem is an interactive problem.)

A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn’t exist, return -1.

You can’t access the Binary Matrix directly.  You may only access the matrix using a BinaryMatrix interface:

• BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed).
• BinaryMatrix.dimensions() returns a list of 2 elements [m, n], which means the matrix is m * n.

Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer.  Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes you’re given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Example 1:

Input: mat = [[0,0],[1,1]]
Output: 0

Example 2:

Input: mat = [[0,0],[0,1]]
Output: 1

Example 3:

Input: mat = [[0,0],[0,0]]
Output: -1

Example 4:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• mat[i][j] is either 0 or 1.
• mat[i] is sorted in a non-decreasing way.

给定一个0/1矩阵，且每行是升序排列的。问矩阵中至少包含一个1的列的最小列号。要求不能使用访问矩阵超过1k次，矩阵最大是100*100的。

常规解法。由于矩阵每行有序，所以在每一行中，使用二分搜索的方式找到1的最小下标，则所有行的最小下标的最小值即为答案。如果是m*n的矩阵，则时间复杂度为O(mlgn)。代码如下：

class Solution {
public:
	int LeftMost(BinaryMatrix &binaryMatrix, int row, int m, int n) {
		int l = 0, r = n - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			int midv = binaryMatrix.get(row, mid);
			if (midv == 0)l = mid + 1;
			else r = mid - 1;
		}
		return r + 1;
	}
	int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
		vector<int> dim = binaryMatrix.dimensions();
		int m = dim[0], n = dim[1];
		int ans = n;
		for (int i = 0; i < m; ++i) {
			ans = min(ans, LeftMost(binaryMatrix, i, m, n));
		}
		if (ans == n)return -1;
		else return ans;
	}
};

本代码提交AC，用时8MS。

hint还提示了另一种解法，从矩阵的右上角开始，遇到0则往下走，遇到1则往左走。因为如果是1的话，至少当前所在列是包含1的，也许还可以再往左试探一下，而如果是0的话，只能往下走了。这种方法极端情况下可能从矩阵的右上角走到左下角，时间复杂度为O(m+n)。完整代码如下：

class Solution {
public:

	int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
		vector<int> dim = binaryMatrix.dimensions();
		int m = dim[0], n = dim[1];
		int x = 0, y = n - 1;
		int ans = n;
		while (x < m&&y >= 0) {
			int val = binaryMatrix.get(x, y);
			if (val == 0)++x;
			else if (val == 1) {
				ans = y;
				if (y - 1 >= 0 && binaryMatrix.get(x, y - 1) == 1) {
					--y;
					ans = y;
				}
				else ++x;
			}
		}
		if (ans == n)return -1;
		else return ans;
	}
};

本代码提交AC，用时8MS。