# LeetCode Range Sum Query - Mutable

LeetCode Range Sum Query - Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:

Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8


Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

class NumArray {
private:
struct Node {
int start, end, sum;
Node *left, *right;
Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {};
};
Node *root;
Node* constructTree(vector<int> &nums, int start, int end) {
Node* node = new Node(start, end);
if (start == end) {
node->sum = nums[start];
return node;
}
int mid = start + (end - start) / 2;
node->left = constructTree(nums, start, mid);
node->right = constructTree(nums, mid + 1, end);
node->sum = node->left->sum + node->right->sum;
return node;
}
int sumRange(int i, int j, Node *root) {
if (root == NULL)return 0;
if (i == root->start&&j == root->end)return root->sum;
int mid = root->start + (root->end - root->start) / 2;
if (j <= mid)return sumRange(i, j, root->left);
else if (i > mid)return sumRange(i, j, root->right);
else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right);
}
void update(int i, int val, Node *root) {
if (root->start == root->end && root->start == i) {
root->sum = val;
return;
}
int mid = root->start + (root->end - root->start) / 2;
if (i <= mid)update(i, val, root->left);
else update(i, val, root->right);
root->sum = root->left->sum + root->right->sum;
}
public:
NumArray(vector<int> nums) {
root = NULL;
if (!nums.empty())root = constructTree(nums, 0, nums.size() - 1);
}
void update(int i, int val) {
if (root == NULL)return;
update(i, val, root);
}
int sumRange(int i, int j) {
if (root == NULL)return 0;
return sumRange(i, j, root);
}
};


# LeetCode Different Ways to Add Parentheses

LeetCode Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]
Example 2
Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

class Solution {
private:
int operate(int a, int b, char c) {
switch (c) {
case '+':return a + b;
case '-':return a - b;
case '*':return a*b;
}
}
public:
vector<int> diffWaysToCompute(string input) {
int n = input.size();
vector<int> ans;
bool found = false;
for (int i = 0; i < n; ++i) {
if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
found = true;
vector<int> lefts = diffWaysToCompute(input.substr(0, i));
vector<int> rights = diffWaysToCompute(input.substr(i + 1));
for (int j = 0; j < lefts.size(); ++j) {
for (int k = 0; k < rights.size(); ++k) {
ans.push_back(operate(lefts[j], rights[k], input[i]));
}
}
}
}
if (!found)return{ atoi(input.c_str()) };
return ans;
}
};


# LeetCode Search a 2D Matrix II

LeetCode Search a 2D Matrix II
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,
Consider the following matrix:

[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]


Given target = 5, return true.
Given target = 20, return false.

LeetCode Search a 2D Matrix基础上改动了一点点，但是难度增加不少。这一次，每行和每列都是递增的，但是这一行的行首元素和上一行的行末元素没有大小关系，这种矩阵有点像从左上角递增到右下角的一个曲面，想象一下。

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0)return false;
int m = matrix.size(), n = matrix[0].size();
if (n == 0)return false;
int i = 0, j = n - 1;
while (i < m&&j >= 0) {
while (i < m&&matrix[i][j] < target)++i;
if (i >= m)return false;
while (j >= 0 && matrix[i][j] > target)--j;
if (j < 0)return false;
if (matrix[i][j] == target)return true;
}
return false;
}
};


class Solution {
public:
bool quadPart(vector<vector<int>>& matrix, int left, int top, int right, int bottom, int target) {
if (left > right || top>bottom)return false;
if (target<matrix[left][top] || target>matrix[right][bottom])return false;
int midrow = left + (right - left) / 2, midcol = top + (bottom - top) / 2;
if (target == matrix[midrow][midcol])return true;
//if (target > matrix[midrow][midcol]) { // 抛弃左上角
//	return quadPart(matrix, left, midcol + 1, midrow - 1, bottom, target) || // 右上角
//		quadPart(matrix, midrow + 1, top, right, midcol - 1, target) || // 左下角
//		quadPart(matrix, midrow, midcol, right, bottom, target); // 右下角
//}
//else {
//	return quadPart(matrix, left, midcol + 1, midrow - 1, bottom, target) || // 右上角
//		quadPart(matrix, midrow + 1, top, right, midcol - 1, target) || // 左下角
//		quadPart(matrix, left, top, midrow, midcol, target); //左上角
//}
if (target > matrix[midrow][midcol]) { // 抛弃左上角
return quadPart(matrix, left, midcol + 1, midrow, bottom, target) || // 右上角
quadPart(matrix, midrow + 1, top, right, midcol, target) || // 左下角
quadPart(matrix, midrow + 1, midcol + 1, right, bottom, target); // 右下角
}
else {
return quadPart(matrix, left, midcol, midrow - 1, bottom, target) || // 右上角
quadPart(matrix, midrow, top, right, midcol - 1, target) || // 左下角
quadPart(matrix, left, top, midrow - 1, midcol - 1, target); //左上角
}
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0)return false;
int m = matrix.size(), n = matrix[0].size();
if (n == 0)return false;
return quadPart(matrix, 0, 0, m - 1, n - 1, target);
}
};


# LeetCode Pow(x, n)

LeetCode Pow(x, n)
Implement pow(x, n).

class Solution {
public:
double doPow(double x, int n) {
if (n == 0)return 1.0;
double v = doPow(x, n / 2);
if (n % 2 == 0)return v*v;
else return v*v*x;
}
double myPow(double x, int n) {
int m = n > 0 ? n : -n;
double ans = doPow(x, m);
return n > 0 ? ans : 1.0 / ans;
}
};


class Solution {
public:
double myPow(double x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
long long m = n; // 先转换为ll，否则n=INT_MIN是有问题
m = m > 0 ? m : -m;
double ans = 1;
while (m) {
if (m & 1)ans *= x;
m >>= 1;
x = x*x;
}
return n > 0 ? ans : 1 / ans;
}
};


# LeetCode Maximum Subarray

LeetCode Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
int ans = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (dp[i - 1] > 0)dp[i] = dp[i - 1] + nums[i];
else dp[i] = nums[i];
if (dp[i] > ans)ans = dp[i];
}
return ans;
}
};


class Solution {
public:
int divide(vector<int>& nums, int left, int right) {
if (left == right)return nums[left];
if (left == right - 1)return max(nums[left] + nums[right], max(nums[left], nums[right]));
int mid = (left + right) / 2;
int lmax = divide(nums, left, mid - 1);
int rmax = divide(nums, mid + 1, right);
int mmax = nums[mid], tmp = nums[mid];
for (int i = mid - 1; i >= left; i--) {
tmp += nums[i];
if (tmp > mmax)mmax = tmp;
}
tmp = mmax;
for (int i = mid + 1; i <= right; i++) {
tmp += nums[i];
if (tmp > mmax)mmax = tmp;
}
return max(mmax, max(lmax, rmax));
}
int maxSubArray(vector<int>& nums) {
return divide(nums, 0, nums.size() - 1);
}
};


# LeetCode Median of Two Sorted Arrays

LeetCode Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

int findKthSmallest(int A[], int m, int B[], int n, int k) {
assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);
int i = (int)((double)m / (m+n) * (k-1));
int j = (k-1) - i;
assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n);
// invariant: i + j = k-1
// Note: A[-1] = -INF and A[m] = +INF to maintain invariant
int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);
int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);
int Ai   = ((i == m) ? INT_MAX : A[i]);
int Bj   = ((j == n) ? INT_MAX : B[j]);
if (Bj_1 < Ai && Ai < Bj)
return Ai;
else if (Ai_1 < Bj && Bj < Ai)
return Bj;
assert((Ai > Bj && Ai_1 > Bj) ||
(Ai < Bj && Ai < Bj_1));
// if none of the cases above, then it is either:
if (Ai < Bj)
// exclude Ai and below portion
// exclude Bj and above portion
return findKthSmallest(A+i+1, m-i-1, B, j, k-i-1);
else /* Bj < Ai */
// exclude Ai and above portion
// exclude Bj and below portion
return findKthSmallest(A, i, B+j+1, n-j-1, k-j-1);
}


class Solution {
public:
double findKthSmallest(vector<int>& nums1, vector<int>& nums2, int k)//find kth smallest
{
int m = nums1.size(), n = nums2.size();
//always assume that m is equal or smaller than n
if (m > n)
return findKthSmallest(nums2, nums1, k);
if (m == 0)
return nums2[k - 1];
if (k == 1)
return min(nums1[0], nums2[0]);
//divide k into two parts
int i = (int)((double)m / (m + n)*(k - 1));
int j = (k - 1) - i;
int Ai_1 = ((i == 0) ? INT_MIN : nums1[i - 1]);
int Bj_1 = ((j == 0) ? INT_MIN : nums2[j - 1]);
int Ai = ((i == m) ? INT_MAX : nums1[i]);
int Bj = ((j == n) ? INT_MAX : nums2[j]);
if (Bj_1 < Ai && Ai < Bj)
return Ai;
else if (Ai_1 < Bj && Bj < Ai)
return Bj;
if (Ai < Bj)
{
vector<int> v1(nums1.begin() + i + 1, nums1.end());
vector<int> v2(nums2.begin(), nums2.begin() + j);
return findKthSmallest(v1, v2, k - i - 1);
}
else if (Ai > Bj)
{
vector<int> v1(nums1.begin(), nums1.begin() + i);
vector<int> v2(nums2.begin() + j + 1, nums2.end());
return findKthSmallest(v1, v2, k - j - 1);
}
else
return Ai;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int total = nums1.size() + nums2.size();
if (total & 0x01)
return findKthSmallest(nums1, nums2, total / 2 + 1);
else
return (findKthSmallest(nums1, nums2, total / 2) + findKthSmallest(nums1, nums2, total / 2 + 1)) / 2;
}
};


O(lgn+lgm)的解法。假设arr1和arr2的中位数分别是arr1[mid1]和arr2[mid2]，如果mid1+mid2arr2[mid2]的情况类似。

class Solution {
private:
int findKth(vector<int>& nums1, int s1, int e1, vector<int>& nums2, int s2, int e2, int k) {
int len1 = e1 - s1 + 1, len2 = e2 - s2 + 1;
if(len1 > len2)
return findKth(nums2, s2, e2, nums1, s1, e1, k);
if(len1 == 0)
return nums2[s2 + k - 1];
if(k == 1)
return min(nums1[s1], nums2[s2]);
int i = s1 + min(k / 2, len1) - 1, j = s2 + min(k / 2, len2) - 1;
if(nums1[i] > nums2[j])
return findKth(nums1, s1, e1, nums2, j + 1, e2, k - (j - s2 + 1));
else
return findKth(nums1, i + 1, e1, nums2, s2, e2, k - (i - s1 + 1));
}
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if((m + n) % 2) {
return findKth(nums1, 0, m - 1, nums2, 0, n - 1, (m + n) / 2 + 1);
} else {
return (findKth(nums1, 0, m - 1, nums2, 0, n - 1, (m + n) / 2) + findKth(nums1, 0, m - 1, nums2, 0, n - 1, (m + n) / 2 + 1)) / 2.0;
}
}
};


# hihoCoder 1139-二分·二分答案

hihoCoder 1139-二分·二分答案
#1139 : 二分·二分答案

5 6 2 5
1 2 3
1 3 2
1 4 4
2 5 2
3 5 5
4 5 3

3

f(x)可以使用广度优先搜索实现。实现的时候注意不能使用邻接矩阵保存图，有可能TLE或MLE，使用邻接表更好。完整代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int kMaxN = 10005, kINF = 0x3f, kMaxW = 1000005;
vector<vector<int>> path;
vector<vector<int>> powers;
vector<bool> visit;
int n, m, k, t;
bool BFS(int power)
{
visit.clear();
visit.resize(n + 1, false);
queue<int> Q;
int u, v, len = 0;;
Q.push(1);
visit[1] = true;
Q.push(-1);
while (!Q.empty()&&len<k)
{
u = Q.front();
Q.pop();
if (u == -1)
{
if (Q.empty())
return false;
else
{
len++;
Q.push(-1);
continue;
}
}
for (int i = 0; i < path[u].size(); i++)
{
v = path[u][i];
if (!visit[v]&&powers[u][i] <= power)
{
if (v == t)
return true;
visit[v] = true;
Q.push(v);
}
}
}
return false;
}
int main()
{
freopen("input.txt", "r", stdin);
scanf("%d %d %d %d", &n, &m, &k, &t);
path.resize(n + 1);
powers.resize(n + 1);
int u, v, w, low = kMaxW, high = 0;
for (int i = 0; i < m; i++)
{
scanf("%d %d %d", &u, &v, &w);
low = min(low, w);
high = max(high, w);
path[u].push_back(v);
path[v].push_back(u);
powers[u].push_back(w);
powers[v].push_back(w);
}
while (low+1 < high)
{
int mid = (low + high) / 2;
if (BFS(mid))
high = mid;
else
low = mid;
}
printf("%d\n", high);
return 0;
}


# hihoCoder 1133-二分·二分查找之k小数

hihoCoder 1133-二分·二分查找之k小数
#1133 : 二分·二分查找之k小数

10 4
1732 4176 2602 6176 1303 6207 3125 1 1011 6600

1732

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n, k;
vector<int> a;
int GetNumberK(int p, int q)
{
int m = a[p], i = p, j = q;
while (i < j)
{
while (i < j&&a[j] > m)
j--;
a[i] = a[j];
while (i < j&&a[i] < m)
i++;
a[j] = a[i];
}
if (k == i + 1)//(1)
return m;
else if (k < i + 1)
return GetNumberK(p, i - 1);
else
{
//k = k - (i - p + 1);//(2)，因为(1)处判等的时候i取p，但分割之后p并没有从0开始，所以k还是k
return GetNumberK(i + 1, q);
}
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &k);
a.resize(n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]); if (k > n||k < 1)
printf("-1\n");
else
printf("%d\n", GetNumberK(0, n - 1));
return 0;
}


# hihoCoder 1128-二分·二分查找

hihoCoder 1128-二分·二分查找
#1128 : 二分·二分查找

Nettle最近在玩《艦これ》，因此Nettle收集了很多很多的船(这里我们假设Nettle氪了很多金，开了无数个船位)。去除掉重复的船之后，还剩下N(1≤N≤1,000,000)种不同的船。每一艘船有一个稀有值，任意两艘船的稀有值都不相同，稀有值越小的船越稀有，价值也就越高。
Nettle现在通过大建又造出了一艘船，他想知道这艘船是不是重复的。如果是重复的，那么这艘船在Nettle所有的船里面稀有值排多少位。

Nettle已经先把自己所有船按照稀有值从小到大排列好了(a[1..N])，我们要做的是看看新得到的船(假设稀有值为K)是否在这个序列中，且有对应的a[i]=K时，i为多少？

10 5180
2970 663 5480 4192 4949 1 1387 4428 5180 2761

9

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> a;
int n, k;
int main()
{
scanf("%d %d", &n, &k);
a.resize(n);
bool is_exist = false;
int ans = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
if (a[i] == k)
is_exist = true;
if (a[i] < k)
ans++;
}
if (!is_exist)
printf("-1\n");
else
printf("%d\n", ans + 1);
return 0;
}


#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> a;
int n, k;
int GetOrder(int p, int q)
{
int m = a[p];
int i = p, j = q;
while (i < j)
{
while (i < j&&a[j] > m)
j--;
a[i] = a[j];
while (i < j&&a[i] < m)
i++;
a[j] = a[i];
}
if (k == m)
return i;
else if (k < m)
return GetOrder(p, i - 1);
else
return GetOrder(i + 1, q);
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &k);
a.resize(n);
bool is_exist = false;
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
if (a[i] == k)
is_exist = true;
}
if (!is_exist)
printf("-1\n");
else
printf("%d\n", GetOrder(0, n - 1) + 1);
return 0;
}


# hihoCoder 1070-RMQ问题再临

hihoCoder 1070-RMQ问题再临
#1070 : RMQ问题再临

10
618 5122 1923 8934 2518 6024 5406 1020 8291 2647
6
0 3 6
1 2 2009
0 2 2
0 2 10
1 1 5284
0 2 5

1923
2009
1020
1923

#include<iostream>
using namespace std;
const int MAX_N=1e4+2;
int w[MAX_N];//每个商品重量
int n,m;
int seg_tree[MAX_N][MAX_N];//seg_tree[i][j]：起点为i，长度为j的区间的最小值
inline int get_min(int a,int b)
{
return a<b?a:b;
}
//深度优先遍历以构造线段树
void dfs(int left,int length)
{
if(length==1)
{
seg_tree[left][1]=w[left];
return;
}
dfs(left,length/2);
dfs(left+length/2,length-length/2);
seg_tree[left][length]=get_min(seg_tree[left][length/2],seg_tree[left+length/2][length-length/2]);//取最小值
}
//在区间[s_left,s_len]搜索区间[left,length]的最小值
int search_min(int s_left,int s_len,int left,int length)
{
if((s_left==left)&&(s_len==length))
return seg_tree[s_left][s_len];
if((left+length-1)<(s_left+s_len/2))//全在左半部分
{
return search_min(s_left,s_len/2,left,length);
}
else if(left>=(s_left+s_len/2))//全在右半部分
{
return search_min(s_left+s_len/2,s_len-s_len/2,left,length);
}
else//左右分开搜索
{
int left_len=s_left+s_len/2-left;
int right_len=length-left_len;
int min_left=search_min(s_left,s_len/2,left,left_len);
int min_right=search_min(s_left+s_len/2,s_len-s_len/2,s_left+s_len/2,right_len);
return get_min(min_left,min_right);
}
}
//从区间[s_left,s_len]开始更新下标pos的值为value
void update(int s_left,int s_len,int pos,int value)
{
if((s_left==pos)&&(s_len==1))
{
seg_tree[s_left][1]=value;
return ;
}
int mid=s_left+s_len/2;
if(pos<mid)
update(s_left,s_len/2,pos,value);
else
update(mid,s_len-s_len/2,pos,value);
seg_tree[s_left][s_len]=get_min(seg_tree[s_left][s_len/2],seg_tree[mid][s_len-s_len/2]);//更新父节点
}
int main()
{
//freopen("input.txt","r",stdin);
cin>>n;
for(int i=1;i<=n;i++)
cin>>w[i];
dfs(1,n);
cin>>m;
int p,l,r;
for(int i=0;i<m;i++)
{
cin>>p>>l>>r;
if(p==0)//查询
{
cout<<search_min(1,n,l,r-l+1)<<endl;
}
else//修改
{
update(1,n,l,r);
}
}
return 0;
}