Weekly Contest 149

Posted on 2019-09-26 | In leetcode , Weekly-Contest |

Words count in article: 804 | Reading time ≈ 5

Day of the Year

Given a string date representing a Gregorian calendar date formatted as YYYY-MM-DD, return the day number of the year.

class Solution {
public:
    int dayOfYear(string data){
        int mm[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        int year = 0;
        int month = 0;
        int day = 0;
        year = (data[0]-'0') * 1000 + (data[1]-'0') * 100 +(data[2]-'0') * 10 +(data[3]-'0'); 
        month = (data[5]-'0') * 10 + (data[6]-'0');
        day = (data[8]-'0') * 10 + (data[9]-'0');
        int ret = 0;
        if(year % 100 != 0 && year % 4 == 0 || year % 400 == 0){
            for(int i=0; i<month-1; i++){
                ret += mm[i];
            }
            ret += day;
            if(month > 2){
                ret++;
            }
        }
        else
        {
            for(int i=0; i<month-1; i++){
                ret += mm[i];
            }
            ret += day;
        }
        return ret;
    }
};

Number of Dice Rolls With Target Sum

You have d dice, and each die has f faces numbered 1, 2, …, f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

class Solution {
public:
    vector<vector<int>> dpp = vector<vector<int>>(35, vector<int>(1005, -1));
    int helper(int d, int f, int target, int ans){
        if(dpp[d][target] > -1)
            return dpp[d][target];
        if(d == 0)
            return dpp[d][target] = static_cast<int>(target == 0);
        for(int i=1; i<=f; i++)
        {
            if(target-i >= 0)
                ans = (ans + helper(d-1, f, target-i, 0)) % static_cast<int>(1e9+7);
        }
        return dpp[d][target] = ans;
    }
    int numRollsToTarget(int d, int f, int target){
        return helper(d, f, target, 0);
    }
};

Swap For Longest Repeated Character Substring

Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.

class Solution {
public:
    int maxRepOpt1(string text) {
        int ans = 1;
        int n = text.size();
        int cur = 0;
        vector<int> count(26, 0);
        for(int i=0; i<n; i++)
        {
        	count[text[i]-'a']++;
        }

        vector<int> left(n, 1);
        vector<int> right(n, 1);

        cur = 1;

        for(int i=1; i<n; i++)
        {
        	if(text[i] == text[i-1])
        		cur++;
        	else
        		cur = 1;

        	left[i] = max(cur, left[i]);
        	ans = max(cur, ans);
        }

        cur = 1;

        for(int i=n-2; i>=0; i--)
        {
        	if(text[i] == text[i+1])
        		cur++;
        	else
        		cur = 1;
        	right[i] = max(cur, right[i]);
        	ans = max(cur, ans);
        }

        for(int i=1; i<n-1; i++)
        {
        	if(count[text[i-1]-'a'] > left[i-1])
        		ans = max(ans, left[i-1] + 1);
        	if(count[text[i+1]-'a'] > right[i+1])
        		ans = max(ans, right[i+1] + 1);
        	if( text[i-1] == text[i+1] && text[i-1] != text[i])
        		if(count[text[i-1]-'a'] > (left[i-1] + right[i+1]))
        			ans = max(ans, left[i-1] + right[i+1] + 1);
        		else
        			ans = max(ans, left[i-1] + right[i+1]);
        }
        return ans;
    }
};

Online Majority Element In Subarray

Implementing the class MajorityChecker, which has the following API:

MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
int query(int left, int right, int threshold) has arguments such that:
- 0 <= left <= right < arr.length representing a subarray of arr;
- 2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray

Each query(…) returns the element in arr[left], arr[left+1], …, arr[right] that occurs at least threshold times, or -1 if no such element exists.

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

class MajorityChecker {
public:
    unordered_map<int, vector<int>> idx;
    MajorityChecker(vector<int>& arr) {
        for(int i=0; i<arr.size(); i++)
        {
            idx[arr[i]].push_back(i);
        }
    }
    
    int query(int left, int right, int threshold) {
        for(auto &i: idx)
        {
            if(i.second.size() < threshold)
                continue;
            auto t1 = lower_bound(i.second.begin(), i.second.end(), left);
            auto t2 = upper_bound(i.second.begin(), i.second.end(), right);
            if(t2 - t1 >= threshold)
                return i.first;
        }
        return -1;
    }
};

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * MajorityChecker* obj = new MajorityChecker(arr);
 * int param_1 = obj->query(left,right,threshold);
 */

二叉树

Posted on 2019-09-23 | In C++ , 数据结构 |

Words count in article: 3k | Reading time ≈ 16

// BinNode.h
// 二叉树的基本组陈实体是二叉树节点，而边则对应于节点之间的相互关系
#include <iostream>
#define BinNodePosi(T) BinNode<T>* //节点位置
#define stature(p)  ((p) ? (p)->height : -1)// 节点高度，约定空树高度为-1

//BinNode 状态与性质的判断：
#define IsRoot(x) ( !( (x).parent ) )
#define IsLChild(x) ( ! IsRoot(x) && ( &(x) == (x).parent->lc ) )
#define IsRChild(x) ( ! IsRoot(x) && ( &(x) == (x).parent->rc ) )
#define HasParent(x) ( ! IsRoot(x) )
#define HasLChild(x) ( (x).lc )
#define HasRChild(x) ( (x).rc )
#define HasChild(x) ( HasLChild(x) || HasRChild(x) )
#define HasBothChild(x) ( HasLChild(x) && HasRChild(x) )
#define IsLeaf(x) ( ! HasChild(x) )

// 与BinNode具有特定关系的节点以及指针:
#define sibling(p) ( IsLChild(*(p)) ? (p)->parent->rc: (p)->parent->lc ) //兄弟
#define uncle(x) ( IsLChild(*((x)->parent)) ? (x)->parent->parent->rc: (x)->parent->parent->lc ) //叔叔
#define FromParentTo(x) /*来自父亲的引用*/ ( IsRoot(x) ? _root: ( IsLChild(x) ? (x).parent->lc : (x).parent->rc ) ) //含有父指针的二叉树结点，一般会定义这样的一个宏（获取从父节点指向自己的指针）


typedef enum { RE_RED, RB_BLACK} RBColor; //节点颜色

template <typename T> struct BinNode{ //二叉树节点模板类
// 成员
	T data;
	BinNodePosi(T) parent; BinNodePosi(T) lc; BinNodePosi(T) rc; // 父节点以及左右孩子
	int height; //高度
	int npl; //Null Path Length (左式堆， 也可以用height代替)
	RBColor color; //颜色 红黑树
// 构造函数
	BinNode(): parent(NULL), lc(NULL), rc(NULL), height(0), npl(1), color(RE_RED) {}
	BinNode(T e, BinNodePosi(T) p = NULL, BinNodePosi(T) lc = NULL, BinNodePosi(T) rc = NULL, int h = 0, int l = 1, RBColor c = RE_RED): data(e), parent(p), lc(lc), rc(rc), height(h), npl(l), color(c){}
// 操作接口
	int size(); // 统计当前节点后代总数，亦即以其为根的子树的规模
	BinNodePosi(T) insertAsLC( T const& ); // 作为当前节点的左孩子插入新节点
	BinNodePosi(T) insertAsRC( T const& ); // 作为当前节点的右孩子插入新节点
	BinNodePosi(T) succ(); //取当前节点的直接后继
	template <typename VST> void travLevel( VST& ); //子树层次遍历
	template <typename VST> void travPre( VST& ); //子树先序遍历
	template <typename VST> void travIn( VST& ); //子树中序遍历
	template <typename VST> void travPost( VST& ); //子树后序遍历
// 比较器、判等器 
	bool operator< (BinNode const& bn) { return data < bn.data; }
	bool operator== (BinNode const& bn) { return data == bn.data; }
	bool operator> (BinNode const& bn) { return data > bn.data; }
	bool operator<= (BinNode const& bn) { return data <= bn.data; }
	bool operator>= (BinNode const& bn) { return data >= bn.data; }
	bool operator!= (BinNode const& bn) { return data != bn.data; }
};

// 插入儿子节点： 约定插入新节点之前，当前节点尚无左/右孩子
template <typename T> BinNodePosi(T) BinNode<T>::insertAsLC( T const& e)
{
	return lc = new BinNode( e, this );
	/* 相当于：
		this->lc = new BinNode(e, this);
		return this->lc;
	*/
}

template <typename T> BinNodePosi(T) BinNode<T>::insertAsRC( T const& e)
{
	return rc = new BinNode( e, this );
}

// BinTree.h
#include "BinNode.h"
#include <queue>
template <typename T> class BinTree{
protected:
	int _size; //规模
	BinNodePosi(T) _root; //根节点
	virtual int updateHeight ( BinNodePosi(T) x ); //更新节点x的高度
	void updateHeightAbove ( BinNodePosi(T) x ); //更新节点x及其祖先的高度
public:
	BinTree(): _size(0), _root(NULL) {}
	~BinTree() {
		if(0 < _size)
			remove( _root );
	}
	int size() const { return _size; }
	bool empty() const { return !_root; }
	BinNodePosi(T) root() const { return _root; }
	BinNodePosi(T) insertAsRoot ( T const& e );
	BinNodePosi(T) insertAsLC ( BinNodePosi(T) x, T const& e);
	BinNodePosi(T) insertAsRC ( BinNodePosi(T) x, T const& e);
	BinNodePosi(T) attachAsLC ( BinNodePosi(T) x, BinTree<T>* &S);//T作为x左子树插入
	BinNodePosi(T) attachAsRC ( BinNodePosi(T) x, BinTree<T>* &S);
	int remove ( BinNodePosi(T) x); //删除以位置x处节点为根的子树，返回该子树原先的规模
	BinTree<T>* secede ( BinNodePosi(T) x ); // 将子树x从当前树中摘除，并将其转换为一颗独立的子树
	template <typename VST> void travLevel( VST& visit) { if(_root) _root->travLevel(visit); } // 层次遍历
	template <typename VST> void travPre (VST& visit) { if(_root) _root->travPre(visit); }
	template <typename VST> void travIn (VST& visit) { if(_root) _root->travIn(visit); }
	template <typename VST> void travPost (VST& visit) { if(_root) _root->travPost(visit); }
	bool operator< (BinTree<T> const& t) { return _root && t._root && (_root->data < t._root->data); }
	bool operator== (BinTree<T> const& t) { return _root && t._root && (_root->data == t._root->data); }
	bool operator!= (BinTree<T> const& t) { return _root && t._root && (_root->data != t._root->data); }
	bool operator> (BinTree<T> const& t) { return _root && t._root && (_root->data > t._root->data); }
	bool operator<= (BinTree<T> const& t) { return _root && t._root && (_root->data <= t._root->data); }
	bool operator>= (BinTree<T> const& t) { return _root && t._root && (_root->data >= t._root->data); }
};

// 一旦有节点加入/离开二叉树，则更新其所有祖先的高度
int max(int a,int b)
{
	return a > b ? a : b;
}

template <typename T> int BinTree<T>::updateHeight(BinNodePosi(T) x)
{
	return x->height = 1 + max(stature(x->lc), stature(x->rc));
}

template <typename T> void BinTree<T>::updateHeightAbove(BinNodePosi(T) x)
{
	while(x)
	{
		updateHeight(x); 
		x = x->parent;
	}
} // 在某些种类的二叉树（红黑树）中，高度的定义有所不同，因此这里updateHeight()定义为保护级的虚函数，以便派生类在必要时重写(override)

//节点插入：
template <typename T> BinNodePosi(T) BinTree<T>::insertAsRoot( T const& e){
	_size = 1;
	return _root = new BinNode<T>(e);
}

template <typename T> BinNodePosi(T) BinTree<T>::insertAsLC(  BinNodePosi(T) x, T const& e){
	_size++;
	x->insertAsLC(e);
	updateHeightAbove(x);
	return x->lc;
}

template <typename T> BinNodePosi(T) BinTree<T>::insertAsRC(  BinNodePosi(T) x, T const& e){
	_size++;
	x->insertAsRC(e);
	updateHeightAbove(x);
	return x->lc;
}

//子树接入：
//指针是一个存放地址的变量，而指针引用指的是这个变量的引用，众所周知C++中如果参数不是引用的话会调用参数对象的拷贝构造函数，所以如果有需求想改变指针所指的对象（换句话说，就是要改变指针里面存的地址），就要使用指针引用
template <typename T>
BinNodePosi(T) BinTree<T>::attachAsLC( BinNodePosi(T) x, BinTree<T>* &S){
	if(x->lc = S->_root) x->lc->parent = x;
	_size += S->_size;
	updateHeightAbove(x);
	S->root = NULL;
	S->_size = 0;
	release( S );
	S = NULL;
	return x;
}

template <typename T>
BinNodePosi(T) BinTree<T>::attachAsRC( BinNodePosi(T) x, BinTree<T>* &S){
	if(x->rc = S->_root) x->rc->parent = x;
	_size += S->_size;
	updateHeightAbove(x);
	S->root = NULL;
	S->_size = 0;
	release( S );
	S = NULL;
	return x;
}

//子树删除
template <typename T>
int BinTree<T>::remove( BinNodePosi(T) x )
{
	FromParentTo(*x) = NULL; //切断来自父节点的指针
	updateHeightAbove(x->parent);//更新祖先高度
	int n = removeAt(x);
	_size -= n;
	return n; // 删除子树x，更新规模，返回删除节点总数
}

template <typename T> 
static int removeAt( BinNodePosi(T) x )
{
	if( !x ) return 0;
	int n = 1 + removeAt( x->lc ) + removeAt( x->rc );
//	release( x->data );
//	release( x );
	delete x;
	return n;  
}

// 子树分离
template <typename T>
BinTree<T>* BinTree<T>::secede( BinNodePosi(T) x ){
	FromParentTo ( *x ) = NULL;
	updateHeightAbove( x->parent );
	BinTree<T>* S = new BinTree<T>;
	S->root = x;
	x->parent = NULL;
	S->_size = x->size();
	_size -= S->_size;
	return S;
}

// 遍历：
template <typename T, typename VST>
void travPre ( BinNodePosi(T) x, VST& visit ){
	if( !x ) return;
	visit (x->data);
	travPre (x->lc, visit);
	travPre (x->rc, visit);
} 

template <typename T, typename VST>
void travPost ( BinNodePosi(T) x, VST& visit ){
	if( !x ) return;
	travPre (x->lc, visit);
	travPre (x->rc, visit);
	visit (x->data);
} 

template <typename T, typename VST>
void travIn ( BinNodePosi(T) x, VST& visit ){
	if( !x ) return;
	travPre (x->lc, visit);
	visit (x->data);
	travPre (x->rc, visit);
} 

// 直接后继及其定位 (中序遍历)
template <typename T> BinNodePosi(T) BinNode<T>::succ(){
	BinNodePosi(T) s = this;
	if(rc) //若有右孩子，则直接后继必在右子树中
	{
		s = rc;
		while(HasLChild(*s)) s = s->lc;
	}
	else // 否则，直接后继应是“将当前节点包含于其左子树中的最低祖先”
	{
		while(IsRChild(*s)) s = s->parent;
		s = s->parent;
	}
	return s;
}

// 层次遍历
template <typename T> template <typename VST>
void BinNode<T>::travLevel(VST& visit)
{
	std::queue<BinNodePosi(T)> Q;
	Q.push (this);
	while( !Q.empty() ){
		BinNodePosi(T) x = Q.front(); Q.pop(); visit(x->data);
		if(HasLChild(*x)) Q.push(x->lc);
		if(HasRChild(*x)) Q.push(x->rc);
	}
}

//test.cpp
#include <iostream>
#include "BinTree.h"
using namespace std;

int main()
{
	BinTree<int> test;
	test.insertAsRoot(1);
	cout << test.size();
	return 0;
}

#include <iostream>
#include <queue>
using namespace std;

template < typename T >
struct TreeNode
{
	TreeNode(T s): data(s), left(NULL), right(NULL) {}
	T data;
	TreeNode* left;
	TreeNode* right;
};

template < typename T >
class Tree {
private:
	int size;
	TreeNode<T>* root;
public:
	Tree(): size(0), root(NULL){};
	Tree( T x ){
		size = 1;
		root = new TreeNode<T>(x);
	}
	~Tree(){
		if(size > 0){
			queue<TreeNode<T>*> delq;
			delq.push(root);
			while(!delq.empty()){
				TreeNode<T>* x = delq.front();
				delq.pop();
				if(x->left) delq.push(x->left);
				if(x->right) delq.push(x->right);
				delete( x );
			}
		}
	}
	Tree<T>& operator= (Tree<T>& t){
		if(this->root != t.root)
		{
			this->root = t.root;
		}
		return *this;
	}
	int getsize()const { return this->size; }
	TreeNode<T>* getroot() const { return this->root; }
	TreeNode<T>* insertasleft( TreeNode<T>* x, T data ){
		x->left = new TreeNode<T>(data);
		size++;
		return x;
	}
	TreeNode<T>* insertasright( TreeNode<T>* x, T data ){
		x->right = new TreeNode<T>(data);
		size++;
		return x;
	}
	void preorder( TreeNode<T>* root){
		cout << root->data << " ";
		if(root->left) preorder(root->left);
		if(root->right) preorder(root->right);
	}
	void inorder( TreeNode<T>* root){
		if(root->left) inorder(root->left);
		cout << root->data << " ";
		if(root->right) inorder(root->right);
	}
	void postorder( TreeNode<T>* root){
		if(root->left) postorder(root->left);
		if(root->right) postorder(root->right);
		cout << root->data << " ";
	}
	void levelorder( TreeNode<T>* root){
		queue<TreeNode<T>*> Q;
		Q.push(root);
		int levelcur = 0;
		while(!Q.empty())
		{
			levelcur ++;
			cout << "level " << levelcur << " : ";
			queue<TreeNode<T>*> rem;
			while(!Q.empty())
			{
				TreeNode<T>* x = Q.front();
				Q.pop();
				if(x->left) rem.push(x->left);
				if(x->right) rem.push(x->right);
				cout << x->data << " ";
			}
			queue<TreeNode<T>*> temp = Q;
			Q = rem;
			rem = temp;
			cout << endl;
		}
	}
	int find_leaf_size( TreeNode<T>* leaf ){
		if( !leaf ) return 0;
		if( leaf->left == NULL && leaf->right == NULL ) return 1;
		return find_leaf_size( leaf->left ) + find_leaf_size( leaf->right );
	}
	int find_leaf_depth( TreeNode<T>* leaf){
		if(!leaf) return 0;
		int size_left = find_leaf_depth( leaf->left );
		int size_right = find_leaf_depth( leaf->right );
		if( size_left > size_right )
			return size_left + 1;
		else
			return size_right + 1;
	}
	TreeNode<T>* find_x_leaf( TreeNode<T>* root, const T& x){
		if( !root ) return NULL;
		if( root->data == x )  return root;
		TreeNode<T>* find_left = find_x_leaf ( root->left, x );
		if( find_left )
			return find_left;
		else
			return find_x_leaf ( root->right, x );
	}
	int find_x_level_size( TreeNode<T>* root, const T& x){
		if( !root ) return 0;
		if( x == 1 ) return 1;
		else return find_x_level_size( root->left, x-1 ) +  find_x_level_size( root->right, x-1 );
	} 
};


int main(){
	Tree<int> test(1);
	cout << "getsize: " << test.getsize() << endl;
	test.insertasleft( test.getroot(), 2);
	test.insertasright( test.getroot(), 3);
	cout << "getsize: " << test.getsize() << endl;
	cout << "preorder: ";
	test.preorder( test.getroot() );
	cout << endl;
	cout << "inorder: ";
	test.inorder( test.getroot() );
	cout << endl;
	cout << "postorder: ";
	test.postorder( test.getroot() );
	cout << endl;
	Tree<int> test1;
	test1 = test;
	cout << "test1 after = : test1.root->data = " << test.getroot()->data << endl;
	cout << "leveltravel: " << endl;
	test.levelorder( test.getroot() );
	cout << endl;
	cout << "find_leaf_size : " << endl;
	cout << " test.root : " << test.find_leaf_size( test.getroot() ) << endl;
	cout << " test.root->left : " << test.find_leaf_size( test.getroot()->left ) << endl;
	cout << " test.root->right : " << test.find_leaf_size( test.getroot()->right ) << endl;
	cout << "find_leaf_depth : " << endl;
	cout << " test.root : " << test.find_leaf_depth( test.getroot() ) << endl;
	cout << " test.root->left : " << test.find_leaf_depth( test.getroot()->left ) << endl;
	cout << " test.root->right : " << test.find_leaf_depth( test.getroot()->right ) << endl;
	cout << "find_x_leaf : " << endl;
	cout << " 1 : " << test.find_x_leaf( test.getroot(), 1 )->data << endl;
	cout << "find_x_level_size : " << endl;
	cout << " level-2 : " << test.find_x_level_size( test.getroot(), 2 ) << endl;
	return 0;
}

double Week Contest 9

Posted on 2019-09-22 | In leetcode , Weekly-Contest |

Words count in article: 1.1k | Reading time ≈ 4

最多可以买到的苹果数量

楼下水果店正在促销，你打算买些苹果，arr[i] 表示第 i 个苹果的单位重量。

你有一个购物袋，最多可以装 5000 单位重量的东西，算一算，最多可以往购物袋里装入多少苹果。

class Solution {
public:
    int maxNumberOfApples(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int ret = 0 ;
        int sum = 0;
        for(int i=0; i<arr.size(); i++)
        {
            sum += arr[i];
            if(sum > 5000)
                return ret;
            ret++;
        }
        return ret;
    }
};

进击的骑士

一个坐标可以从 -infinity 延伸到 +infinity 的无限大的棋盘上，你的骑士驻扎在坐标为 [0, 0] 的方格里。

骑士的走法和中国象棋中的马相似，走 “日” 字：即先向左（或右）走 1 格，再向上（或下）走 2 格；或先向左（或右）走 2 格，再向上（或下）走 1 格。

每次移动，他都可以按图示八个方向之一前进。

现在，骑士需要前去征服坐标为 [x, y] 的部落，请你为他规划路线。

最后返回所需的最小移动次数即可。本题确保答案是一定存在的。

class Solution {
public:
  int minKnightMoves(int x, int y) {
    vector<vector<int>> M(800, vector<int>(800, -1));
    M[300][300] = 0;
    queue<pair<int, int>> Q;
    Q.push({0, 0});
    int dx[] = {1, 1, 2, 2, -1, -1, -2, -2};
    int dy[] = {2, -2,1, -1, 2, -2, 1, -1};
    while (!Q.empty() && M[x+300][y+300] == -1) {
      auto [sx, sy] = Q.front(); Q.pop();
      for (int i = 0; i < 8; i++) {
        int tx = sx + dx[i];
        int ty = sy + dy[i];
        if (abs(tx) + abs(ty) > 300) continue;
        if (M[tx+300][ty+300] != -1) continue;
        M[tx+300][ty+300] = M[sx+300][sy+300] + 1;
        Q.push({tx, ty});
      }
    }
    return M[x+300][y+300];
  }
};

找出所有行中最小公共元素

给你一个矩阵 mat，其中每一行的元素都已经按递增顺序排好了。请你帮忙找出在所有这些行中最小的公共元素。

如果矩阵中没有这样的公共元素，就请返回 -1。

class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        for(int i=0; i<mat[0].size(); i++)
        {
            int tmp = mat[0][i];
            int flag = 1;
            for(int j=1; j<mat.size(); j++)
            {
                int z;
                for(z=0; z<mat[j].size(); z++)
                {
                    if(mat[j][z] == tmp)
                        break;
                }
                if(z == mat[j].size())
                {
                    flag = 0;
                    break;
                }
            }
            if(flag == 1)
                return tmp;
            else
                continue;
        }
        return -1;
    }
};

建造街区的最短时间

你是个城市规划工作者，手里负责管辖一系列的街区。在这个街区列表中 blocks[i] = t 意味着第 i 个街区需要 t 个单位的时间来建造。

由于一个街区只能由一个工人来完成建造。

所以，一个工人要么需要再召唤一个工人（工人数增加 1）；要么建造完一个街区后回家。这两个决定都需要花费一定的时间。

一个工人再召唤一个工人所花费的时间由整数 split 给出。

注意：如果两个工人同时召唤别的工人，那么他们的行为是并行的，所以时间花费仍然是 split。

最开始的时候只有一个工人，请你最后输出建造完所有街区所需要的最少时间。

示例 1：

输入：blocks = [1], split = 1
输出：1
解释：我们使用 1 个工人在 1 个时间单位内来建完 1 个街区。
示例 2：

输入：blocks = [1,2], split = 5
输出：7
解释：我们用 5 个时间单位将这个工人分裂为 2 个工人，然后指派每个工人分别去建造街区，从而时间花费为 5 + max(1, 2) = 7
示例 3：

输入：blocks = [1,2,3], split = 1
输出：4
解释：
将 1 个工人分裂为 2 个工人，然后指派第一个工人去建造最后一个街区，并将第二个工人分裂为 2 个工人。
然后，用这两个未分派的工人分别去建造前两个街区。
时间花费为 1 + max(3, 1 + max(1, 2)) = 4

提示：

1 <= blocks.length <= 1000
1 <= blocks[i] <= 10^5
1 <= split <= 100

//
//贪婪: 挑最小的两个合并(取大值+split)成新节点

class Solution {
public:
    int minBuildTime(vector<int>& blocks, int split) {
        multiset<int> vals(blocks.begin(), blocks.end());

        while (vals.size() > 1)
        {
            int minVal = *vals.begin();
            vals.erase(vals.begin());
            int minVal2 = *vals.begin();  //这个一定比前一个大或相等
            vals.erase(vals.begin());
            vals.insert(minVal2 + split);
        }

        return *vals.begin();
    }
};

Weekly Contest 155

Posted on 2019-09-22 | In leetcode , Weekly-Contest |

Words count in article: 1.2k | Reading time ≈ 7

Minimum Absolute Difference

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr

1 2	Input: arr = [3,8,-10,23,19,-4,-14,27] Output: [[-14,-10],[19,23],[23,27]]

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
		vector<vector<int>> ret;
		int min = INT_MAX;
		sort(arr.begin(), arr.end());
        for(int i=0; i<arr.size()-1; i++)
        {
            if(abs(arr[i]-arr[i+1]) < min)
                min = abs(arr[i]-arr[i+1]);
        }
        for(int i=0; i<arr.size()-1; i++)
        {
            if(abs(arr[i]-arr[i+1]) == min)
            {
                vector<int> cur;
                cur.push_back(arr[i]);
                cur.push_back(arr[i+1]);
                ret.push_back(cur);
            }
        }
		return ret;        
    }
};

Ugly Number III

Write a program to find the n-th ugly number.

Ugly numbers are positive integers which are divisible by a or b or c.

容斥加二分

class Solution {
public:
    long long ab, ac, bc, abc;
    long long gcd(long long a, long long b)
    {
        if(b == 0) return a;
        else
            return gcd(b, a%b);
    }
    long long lcd(long long a, long long b)
    {
        return a*b/gcd(a,b);
    }
    long long rongchi(long long N, long long a, long long b, long long c)
    {
        return N/a + N/b + N/c - N/ab - N/ac - N/bc + N/abc;
    }
    int nthUglyNumber(int n, int a, int b, int c) {
        ab = lcd(a, b);
        ac = lcd(a, c);
        bc = lcd(b, c);
        abc = lcd(ab, c);
        
        int left = 1;
        int right = 2000000001;
        
        while(left < right)
        {
            long long mid = left + (right - left)/2;
            long long num = rongchi(mid, a, b, c);
            if(num < n) left = mid+1;
            else if(num >= n) right = mid;
        }
        return left;
        
    }
};

Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

class Solution {
public:
    map<int, vector<int>> mm;
    vector<int> have;
    
    void dfs(int index, vector<int>& indexset)
    {
        if(have[index]) return;
        indexset.push_back(index);
        have[index] = 1;
        for(auto m: mm[index])
        {
            dfs(m, indexset);
        }
    }
    
    
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        for(auto& p: pairs)
        {
            mm[p[0]].push_back(p[1]);
            mm[p[1]].push_back(p[0]);
        }
        
        have.resize(s.length(), 0);
        
        
        for(int i=0; i<s.length(); i++)
        {
            if(have[i]) continue;
            
            string tmp;
            vector<int> indexset;
            
            dfs(i, indexset);
            
            sort(indexset.begin(), indexset.end());
            
            for(auto aa: indexset)
            {
                tmp.push_back(s[aa]);
            }
            
            sort(tmp.begin(), tmp.end());
            
            for(int j=0; j<tmp.size(); j++)
            {
                s[indexset[j]] = tmp[j];
            }
        }
        return s;
    }
};

1203. Sort Items by Groups Respecting Dependencies

拓扑排序

There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it’s equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.

Return a sorted list of the items such that:

The items that belong to the same group are next to each other in the sorted list.
There are some relations between these items where beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item).

Return any solution if there is more than one solution and return an empty list if there is no solution.

第一步，构造小组的依赖关系和组内项目的依赖关系。
第二步，判断小组间是否有冲突，没冲突计算出小组的拓扑排序。
第三步：判断每个小组内项目是否有冲突，没冲突计算出小组内项目的拓扑排序。

class Solution {
    map<int, set<int>> group2item; //组织架构，没有小组的项目会分配一个唯一的小组
    
    map<int, int> groupInNum;       //每个小组的入度
    map<int, set<int>> groupDir;   //小组的依赖图
    map<int, int> itemInNum;       //组内每个成员的入度
    map<int, set<int>> itemDir;    //组内的依赖图

    
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        int minGroup = m;
        
        for(int i=0;i<group.size();i++){
            if(group[i] == -1){
                group[i] = minGroup++;
            }
            group2item[group[i]].insert(i);
        }
        for(int to = 0; to < beforeItems.size(); to++){
            int toGroup = group[to];
            for(auto from: beforeItems[to]){
                int fromGroup = group[from];
                
                if(toGroup == fromGroup){
                    itemDir[from].insert(to);
                    itemInNum[to]++; //入度加一
                }else{
                    if(groupDir[fromGroup].count(toGroup) == 0){
                        groupDir[fromGroup].insert(toGroup);
                        groupInNum[toGroup]++; //入度加一
                    }
                }
            }
        }
        
        //第一步检查小组间是否有冲突
        queue<int> que;
        vector<int> groupAns;
        for(int to = 0; to < minGroup; to++){
            if(groupInNum[to] == 0){
                que.push(to);
                groupAns.push_back(to);
            }
        }
        
        while(!que.empty()){
            int from = que.front();
            que.pop();
            for(auto to: groupDir[from]){
                groupInNum[to]--;
                if(groupInNum[to] == 0){
                    que.push(to);
                    groupAns.push_back(to);
                }
            }
        }
        if(groupAns.size() != minGroup){
            return {};
        }
        
        //第二部检查小组内的项目是否有冲突
        vector<int> ans;
        
        
        for(auto id: groupAns){
            auto& items = group2item[id];
            
            int num = 0;
            for(auto to: items){
                if(itemInNum[to] == 0){
                    que.push(to);
                    ans.push_back(to);
                    num++;
                }
            }
            
            while(!que.empty()){
                int from = que.front();
                que.pop();
                for(auto to: itemDir[from]){
                    itemInNum[to]--;
                    if(itemInNum[to] == 0){
                        que.push(to);
                        ans.push_back(to);
                        num++;
                    }
                }
            }
            
            if(num != items.size()){
                return {};
            } 
        }
        return ans;
        
    }
};

Weekly Contest 151

Posted on 2019-09-20 | In leetcode , Weekly-Contest |

Words count in article: 2.4k | Reading time ≈ 14

Invalid Transactions

A transaction is possibly invalid if:

the amount exceeds $1000, or;

if it occurs within (and including) 60 minutes of another transaction with the same name in a different city.

Each transaction string transactions[i] consists of comma separated values representing the name, time (in minutes), amount, and city of the transaction.

Given a list of transactions, return a list of transactions that are possibly invalid. You may return the answer in any order.

1
2
3

Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
Output: ["alice,20,800,mtv","alice,50,100,beijing"]
Explanation: The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city. Similarly the second one is invalid too.

1 2	Input: transactions = ["alice,20,800,mtv","alice,50,1200,mtv"] Output: ["alice,50,1200,mtv"]

1 2	Input: transactions = ["alice,20,800,mtv","bob,50,1200,mtv"] Output: ["bob,50,1200,mtv"]

暴力

class Solution {
public:
    vector<string> invalidTransactions(vector<string>& t) {
        unordered_map<string, vector<string>> mp;
        for(int i=0; i<t.size(); i++)
        {
            vector<string> v;
            string s = "";
            for(int j=0; j<t[i].size(); j++)
            {
                if(t[i][j] == ',')
                {
                    v.push_back(s);
                    s = "";
                }
                else
                    s += t[i][j];
            }
            v.push_back(s);
            bool f = false;
            for(auto it = mp.begin(); it != mp.end(); it++)
            {
                vector<string> c = it->second;
                if(c[0] == v[0] && c[3] != v[3] && abs(stoi(c[1])-stoi(v[1])) <= 60)
                {
                    if((it->second).back() != "-1")
                        (it->second).push_back("-1");
                    f = true;
                }
            }
            if(stoi(v[2]) > 1000 || f)
            {
                v.push_back("-1");
            }
            mp[t[i]] = v;
        }
        vector<string> ret;
        for(auto it = mp.begin(); it != mp.end(); it++)
        {
            if((it->second).back() == "-1")
                ret.push_back(it->first);
        }
        return ret;
    }
};

Compare Strings by Frequency of the Smallest Character

Let’s define a function f(s) over a non-empty string s, which calculates the frequency of the smallest character in s. For example, if s = “dcce” then f(s) = 2 because the smallest character is “c” and its frequency is 2.

Now, given string arrays queries and words, return an integer array answer, where each answer[i] is the number of words such that f(queries[i]) < f(W), where W is a word in words.

Example 1:

Input: queries = ["cbd"], words = ["zaaaz"]
Output: [1]
Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").
Example 2:

Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
Output: [1,2]
Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").

class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        map<int, int> freq; // map会自动排序
        for(int i=0; i<words.size(); i++) freq[f(words[i])]++;
        int cur = 0;
        for(auto p = freq.end(); p != freq.begin(); p--)
        {
            p->second += cur;
            cur = p->second;
        }
        vector<int> res;
        for(int i=0; i<queries.size(); i++)
        {
            int q = f(queries[i]);
            auto p = freq.upper_bound(q);
            if(p == freq.end()) res.push_back(0);
            else  res.push_back(p->second);
        }
        //lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。

        //upper_bound(起始地址，结束地址，要查找的数值) 返回的是数值 最后一个 出现的位置。

        //binary_search(起始地址，结束地址，要查找的数值)  返回的是是否存在这么一个数，是一个bool值。
        return res;
    }
    
    int f(string s)
    {
        vector<int> freq(26, 0);
        for(int i=0; i<s.size(); i++) freq[s[i]-'a']++;
        for(int i=0; i<26; i++)
        {
            if(freq[i] != 0) return freq[i];
        }
        return 0;
    }
};

Remove Zero Sum Consecutive Nodes from Linked List

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.
Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]
Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        auto d = new ListNode(-1);
        d->next = head;
        auto p = d;
        
        while(p)
        {
            int sum = 0;
            bool flag = false;
            auto q = p->next;
            
            while(q)
            {
                sum += q->val;
                if(sum == 0)
                {
                    p->next = q->next;
                    flag = true;
                    break;
                }
                q = q->next;
            }
            if(!flag)
                p = p->next;
        }
        return d->next;
    }
};

Dinner Plate Stacks

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.

Implement the DinnerPlates class:

DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks.
void push(int val) pushes the given positive integer val into the leftmost stack with size less than capacity.
int pop() returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all stacks are empty.
int popAtStack(int index) returns the value at the top of the stack with the given index and removes it from that stack, and returns -1 if the stack with that given index is empty.

Input: 
["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
Output: 
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

Explanation: 
DinnerPlates D = DinnerPlates(2);  // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
                                                       1  3  5
                                                       ﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
                                                        1  3  5
                                                        ﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
                                                        1  3  5
                                                        ﹈ ﹈ ﹈ 
D.pop()            // Returns 5.  The stacks are now:      4
                                                        1  3 
                                                        ﹈ ﹈  
D.pop()            // Returns 4.  The stacks are now:   1  3 
                                                        ﹈ ﹈   
D.pop()            // Returns 3.  The stacks are now:   1 
                                                        ﹈   
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.

class DinnerPlates 
{
public:
    set<int> s_aval;
    vector<stack<int>> vs;
    int cap = 0;
    
    DinnerPlates(int capacity) { cap = capacity; }
    
    void push(int val) {
      if (s_aval.empty()) {
        vs.push_back(stack<int>());
        s_aval.insert(vs.size() - 1);
      }
      auto idx = *s_aval.begin();
      vs[idx].push(val);
      if (vs[idx].size() == cap) s_aval.erase(s_aval.begin());
    }
    
    int pop() {
      if (vs.empty()) return -1;
      auto res = vs.back().top(); vs.back().pop();
      while (!vs.empty() && vs.back().empty()) {
        s_aval.erase(vs.size() - 1);
        vs.pop_back();
      }
      if (!vs.empty() && vs.back().size() < cap) s_aval.insert(vs.size() - 1);
      return res;
    }
    int popAtStack(int index) {
      if (vs.size() <= index || vs[index].empty()) return -1;
      if (vs.size() - 1 == index) return pop();
      auto res = vs[index].top(); vs[index].pop();
      s_aval.insert(index);
      return res;
    }
};

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates* obj = new DinnerPlates(capacity);
 * obj->push_back(val);
 * int param_2 = obj->pop_back();
 * int param_3 = obj->pop_backAtStack(index);
 */

Maximum Level Sum of a Binary Tree

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level X such that the sum of all the values of nodes at level X is maximal.

Input: [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        if(!root)
            return 0;
        int cur_level = 0;
        queue<TreeNode* > q;
        q.push(root);
        int mx_sum = INT_MIN;
        int level = -1;
        while(!q.empty())
        {
            cur_level++;
            int sz = q.size();
            int local_sum = 0;
            for(int i=0; i<sz; i++)
            {
                TreeNode *tmp = q.front();
                q.pop();
                local_sum += tmp->val;
                if(tmp->left){
                    q.push(tmp->left);
                }
                if(tmp->right)
                {
                    q.push(tmp->right);
                }
            }
            if(local_sum > mx_sum){
                mx_sum = local_sum;
                level = cur_level;
            }
        }
        return level;
    }
};

Find Words That Can Be Formed by Characters

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.
Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        if(words.size() == 0)
            return 0;
        
        map<char, int> ma;
        map<char, int> co;
        
        for(int i=0; i<chars.size(); i++)
            ma[chars[i]]++;
        
        int count = 0;
        for(int i=0; i<words.size(); i++)
        {
            co = ma;
            int flag = 0;
            for(int j=0; j<words[i].size(); j++)
            {
                if(co[words[i][j]]!=0)
                {
                    co[words[i][j]]--;
                }
                else
                {
                    flag = 1;
                    break;
                }
            }
            if(flag == 0)
                count += words[i].size();
        }
        return count;
    }
};

Last Substring in Lexicographical Order

Given a string s, return the last substring of s in lexicographical order.

1 2	Input: "leetcode" Output: "tcode"

class Solution {
public:
    string lastSubstring(string s) {
        int start = 0, N = s.size();
        for(int i=1; i<N; i++)
        {
            if(s[i] == s[start] && s[i-1] == s[start]) continue;
            for(int j=0; i+j < N; j++)
            {
                if(s[start+j] == s[i+j]) continue;
                start = s[start+j] > s[i+j] ? start : i;
                break;
            }
        }
        return s.substr(start);
    }
};

As Far from Land as Possible

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

BFS

 class Solution {
public:
    int maxDistance(vector<vector<int>>& g) {
        int steps = 0;
        queue<pair<int, int>> q, q1;
        for(auto i=0; i< g.size(); i++)
        {
            for(auto j=0; j < g[i].size(); j++)
            {
                if(g[i][j] == 1)
                {
                    q.push({i-1, j});
                    q.push({i+1, j});
                    q.push({i, j-1});
                    q.push({i, j+1});
                }
            }
        }
        while(!q.empty())
        {
            ++steps;
            while(!q.empty())
            {
                int i=q.front().first, j = q.front().second;
                q.pop();
                if(i >= 0 && j >= 0 && i < g.size() && j < g[i].size() && g[i][j] == 0){
                    g[i][j] = steps;
                    q1.push({i-1, j});
                    q1.push({i+1, j});
                    q1.push({i, j-1});
                    q1.push({i, j+1});
                }
            }
            swap(q1, q);
        }
        return steps == 1 ? -1 : steps-1;
    }
};

Weekly Contest 152

Posted on 2019-09-20 | In leetcode , Weekly-Contest |

Words count in article: 1.3k | Reading time ≈ 7

1. 求1~n中所有质数对应质数位置的排列的数量

class Solution {
public:
    int isPrime(int n)
    {
        if(n == 2)
            return 1;
        int t = n;
        for(int i=2; i*i <= t; i++)
        {
            if(t % i == 0)
                return 0;
        }
        return 1;
    }
    int numPrimeArrangements(int n) {
        int count1 = 0;
        int count2 = 0;
        for(int i=2; i<=n; i++)
        {
            if(isPrime(i))
                count1++;
        }
        count2 = n-count1;
        long long ret = 1;
        for(int i=1; i<=count1; i++)
        {
            ret = ret * i % 1000000007;
        }
        for(int i=1; i<=count2; i++)
        {
            ret = ret * i % 1000000007;
        }
        return ret % (1000000000 + 7);
    }
};

2. Can Make Palindrome from Substring

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], …, s[right], and then choose up to k of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return an array answer[], where answer[i] is the result of the i-th query queries[i].

Note that: Each letter is counted individually for replacement so if for example s[left..right] = “aaa”, and k = 2, we can only replace two of the letters. (Also, note that the initial string s is never modified by any query.)

Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0] : substring = "d", is palidrome.
queries[1] : substring = "bc", is not palidrome.
queries[2] : substring = "abcd", is not palidrome after replacing only 1 character.
queries[3] : substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4] : substring = "abcda", could be changed to "abcba" which is palidrome.

class Solution {
public:
    // int helper(string s, vector<int> h)   // timeout!!
    // {
    //     int l = h[0];
    //     int r = h[1];
    //     int k = h[2];
    //     int ch[26] = {0};
    //     for(int i=l; i<=r; i++)
    //         ch[s[i]-'a']++;
    //     int count = 0;
    //     for(int i=0; i<26; i++)
    //     {
    //         if(ch[i] % 2 != 0)
    //             count++;
    //     }
    //     int ret = (count / 2 <= k);
    //     return ret;
    // }
    // vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
    //     vector<bool> ret;
    //     for(int i=0; i<queries.size(); i++)
    //     {
    //         int cur = helper(s, queries[i]);
    //         if(cur)
    //         {
    //             bool rem = true;
    //             ret.push_back(rem);
    //         }
    //         else
    //         {
    //             bool rem = false;
    //             ret.push_back(rem);
    //         }
    //     }
    //     return ret;
    // }
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
        int n=s.length();
        
        int freq[n][26];
        
        memset(freq,0,sizeof(freq));
        
        int i,j;
        
        for(i=0;i<n;i++)
        {
            freq[i][s[i]-'a']++;
        }
        for(i=1;i<n;i++)
        {
            for(j=0;j<26;j++)
            {
                freq[i][j]+=freq[i-1][j];
            }
        }
        vector<bool> answer;
        int u;
        bool ok=true;
        for(i=0;i<queries.size();i++)
        {
            int l,r,k;
            l=queries[i][0];
            r=queries[i][1];
            k=queries[i][2];
            int cnt=0;
            for(j=0;j<26;j++)
            {
                if(l==0)
                    u=freq[r][j];
                else
                    u=freq[r][j]-freq[l-1][j];
                
                if(u%2==1)
                {
                    cnt++;
                }
            }
            
            if((cnt/2)<=k)
            {
                answer.push_back(ok);
            }
            else
            {
                answer.push_back(!ok);
            }
        }
        return answer;
	}
};

3. Number of Valid Words for Each Puzzle

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

word contains the first letter of puzzle.

For each letter in word, that letter is in puzzle.

For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”; while invalid words are “beefed”

(doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

Input: 
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

class Solution {
public:
    vector<int> bb;
    void bbit(vector<string>& w)
    {
        for(auto s : w)
        {
            int bit = 0;
            set<char> tmp;
            for(auto t: s)
            {
                tmp.insert(t);
                bit = bit | (1 << (t-'a'));
            }
            if(tmp.size() > 7) continue;
            bb.push_back(bit);
        }
    }
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        vector<int> ret;
        bbit(words);
        
        for(auto& s: puzzles)
        {
            int num = 0;
            int first = 1 << (s[0] - 'a');
            int bit = 0;
            for(auto aa : s)
            {
                bit = bit | (1 << (aa-'a'));
            }
            for(auto v: bb)
            {
                if((v & bit) == v && ((first & v) == first))
                    num++;
            }
            
            ret.push_back(num);
            
        }
        
        return ret;
    }
};

class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        // Lengths
        int P = puzzles.size();
        int W = words.size();
        
        // Letter masks
        vector<int> letterMask(26, 0);
        
        for (int i = 0, mask = 1; i < 26; ++i, mask <<= 1) {
            letterMask[i] = mask;
        }
        
        // Word masks with count info
        unordered_map<int, int> wordsMask;
        
        // For each word
        for (int i = 0; i < W; ++i) {
            // Compute word mask
            int mask = 0;
            
            for (char c: words[i]) {
                mask = mask | letterMask[c - 'a'];
            }
            
            ++wordsMask[mask];
        }
       
         // Result : result[i] => number of words covered by puzzles[i]
        vector<int> result(P, 0); 
        
        // For each puzzle
        for (int i = 0; i < P; ++i) {
            // Compute puzzle mask
            int mask = 0;
            
            for (char c: puzzles[i]) {
                mask = mask | letterMask[c - 'a'];
            }
            
            // Iterate through all valid subset of mask i.e. subset of puzzle chars = 2^7 = 64 in count
            // This makes the complexity O(P*64)
            int subMask = mask;
            
            while (subMask) {
                if ((subMask & letterMask[puzzles[i][0] - 'a']) && wordsMask.count(subMask)) {
                    result[i] += wordsMask[subMask];
                }
                
                // Only select valid bits i.e. bits corresponding to chars in puzzle
                subMask = (subMask - 1) & mask;
            }
        }
        
        return result;
    }
};

Exercise two

Posted on 2019-09-19 | In java , java面向对象程序设计 |

Words count in article: 1.4k | Reading time ≈ 8

MyInteger类

import java.util.Scanner;

class MyInteger{
	int value;
	MyInteger(int e){
		this.value = e;
	}
	public int getter() {
		return this.value;
	}
	public boolean isEven() {
		return (this.value % 2 == 0);
	}
	public boolean isOdd() {
		return (this.value % 2 == 1);
	}
	public boolean isPrime() {
		for(int i=2; i*i <= this.value; i++)
		{
			if(this.value % i == 0)
				return false;
		}
		return true;
	}
	public static boolean isEven(int e) {
		return (e % 2 == 0);
	}
	public static boolean isOdd(int e) {
		return (e % 2 == 1);
	}
	public static boolean isPrime(int e) {
		for(int i=2; i*i <= e; i++)
		{
			if(e % i == 0)
				return false;
		}
		return true;
	}
	public static boolean isEven(MyInteger e) {
		return (e.value % 2 == 0);
	}
	public static boolean isOdd(MyInteger e) {
		return (e.value % 2 == 1);
	}
	public static boolean isPrime(MyInteger e) {
		for(int i=2; i*i <= e.value; i++)
		{
			if(e.value % i == 0)
				return false;
		}
		return true;
	}
	public boolean equals(int e) {
		return this.value == e;
	}
	public boolean equals(MyInteger e) {
		return this.value == e.value;
	}
}

public class Main{
	 public static void main(String[] args) {
		 Scanner x = new Scanner(System.in);
		 int a = x.nextInt();
		 int b = x.nextInt();
		 int c = x.nextInt();
		 MyInteger mi = new MyInteger(a);
		 MyInteger ni = new MyInteger(b);
		 System.out.println(mi.isEven());
		 System.out.println(mi.isOdd());
		 System.out.println(mi.isPrime());
		 System.out.println(mi.isPrime(c));
		 System.out.println(mi.isPrime(ni));
		 System.out.println(mi.equals(c));
		 System.out.println(mi.equals(ni));
		 x.close();
	 }
}

Circle2D 类

import java.util.Scanner;

class Circle2D{
	double x;
	double y;
	double radius;
	
	Circle2D(){
		this.x = 0;
		this.y = 0;
		this.radius = 1;
	}
	
	Circle2D(double xx, double yy, double rr){
		this.x = xx;
		this.y = yy;
		this.radius = rr;
	}
	
	public double getterx() {
		return this.x;
	}
	public double gettery() {
		return this.y;
	}
	public double  getterradius() {
		return this.radius;
	}
	
	public double getArea() {
		return Math.PI * this.radius * this.radius;
	}
	
	public double getPerimeter() {
		return Math.PI * this.radius * 2;
	}
	
	public boolean contains(double xx, double yy) {
		double tmp = (xx - this.x)*(xx - this.x) + (yy - this.y)*(yy - this.y);
		return Math.sqrt(tmp) < this.radius;
	}
	
	public boolean contains(Circle2D e) {
		return Math.abs(this.radius-e.radius) > (Math.sqrt((e.x - this.x)*(e.x - this.x) + (e.y - this.y)*(e.y - this.y)));
	}
	
	public boolean overlaps(Circle2D e) {
		if(this.contains(e)) return false;
		if(e.contains(this)) return false;
		return Math.sqrt((e.x - this.x)*(e.x - this.x) + (e.y - this.y)*(e.y - this.y)) < (Math.abs(this.radius) + Math.abs(e.radius));
	}
}



public class Main1 {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		Circle2D op1 = new Circle2D(input.nextDouble(),input.nextDouble(),input.nextDouble());
		Circle2D op2 = new Circle2D(input.nextDouble(),input.nextDouble(),input.nextDouble());
		double x = input.nextDouble();
		double y = input.nextDouble();
		System.out.println("The circle's area is "+op1.getArea());
		System.out.println("The circle's perimeter is "+op1.getPerimeter());
		System.out.println("The circle overlaps with the specified circle: "+op1.overlaps(op2));
		System.out.println("The circle contains the specified point: "+op1.contains(x, y));
		System.out.println("The circle contains the specified circle: "+op1.contains(op2));
		input.close();
	}
}

Author与BOok类


class Author{
	private String name;
	private String email;
	private char gender;
	
	public Author(String name, String email, char gender)
	{
		this.name = name;
		this.email = email;
		this.gender = gender;
	}
	
	public String getName() {
		return this.name;
	}
	
	public String getEmail() {
		return this.email;
	}
	
	public char getgen() {
		return this.gender;
	}
	
	public String toString() {
		String gg;
		if(this.gender == 'm')
			gg = "m";
		else
			gg = "f";
		return "Author[name = " + this.name + ", email = " + this.email + ", gender = " + gg + "]";
	}
}

class Book{
	private String name;
	private Author author;
	private double price;
	private int qty;
	
	Book(String name, Author author, double price, int qty){
		this.name = name;
		this.author = author;
		this.price = price;
		this.qty = qty;
	}
	
	Book(String name, Author author, double price){
		this.name = name;
		this.author = author;
		this.price = price;
		this.qty = 0;
	}
	
	public String getName() {
		return this.name;
	}
	public Author getAuthor() {
		return this.author;
	}
	public double getPrice() {
		return this.price;
	}
	public void setPrice(double e) {
		this.price = e;
	}
	public int getQty() {
		return this.qty;
	}
	public void setQty(int e)
	{
		this.qty = e;
	}
	public String toString() {
		String au = this.author.toString();
		return "Book[name = "+this.getName()+", "+au+", price = "+this.getPrice()+", qty = "+this.getQty() + "]";
	}
}


public class Main2 {
    public static void main(String[] args){
	Author ahTeck = new Author("Tan Ah Teck", "ahteck@nowhere.com", 'm');
	System.out.println(ahTeck);  // Author's toString()

	Book dummyBook = new Book("Java for dummy", ahTeck, 19.95, 99);  // Test Book's Constructor
	System.out.println(dummyBook);  // Test Book's toString()

	// Test Getters and Setters
	dummyBook.setPrice(29.95);
	dummyBook.setQty(28);
	System.out.println("name is: " + dummyBook.getName());
	System.out.println("price is: " + dummyBook.getPrice());
	System.out.println("qty is: " + dummyBook.getQty());
	System.out.println("Author is: " + dummyBook.getAuthor());  // Author's toString()
	System.out.println("Author's name is: " + dummyBook.getAuthor().getName());
	System.out.println("Author's email is: " + dummyBook.getAuthor().getEmail());

	// Use an anonymous instance of Author to construct a Book instance
	Book anotherBook = new Book("more Java", new Author("Paul Tan", "paul@somewhere.com", 'm'), 29.95);
	System.out.println(anotherBook);  // toString()    
    }
}

股票

三种：

只能买卖一次
不限买卖次数
只能买两次

import java.util.Scanner;

class StockSeller{
	int[] price;
	StockSeller(int[] price){
		this.price = price;
	}
	public int MaxProfit1() {
		if(price.length <= 1) return 0;
		if(price.length == 2) return price[1] > price[0] ? price[1] - price[0] : 0;
		int ret = 0;
		int min = this.price[0];
		for(int i=1; i<price.length; i++)
		{
			if(price[i] > min)
			{
				int cur = price[i] - min;
				ret = ret > cur ? ret : cur;
			}
			else if(price[i] < min)
				min = price[i];
		}
		return ret;
	}
	public int MaxProfit2() {
//		int[] dpbuy = new int[this.price.length];
//		int[] dpsell = new int[this.price.length];
//		
//		dpbuy[0] = -price[0];
//		dpsell[0] = 0;
//		for(int i=1; i<this.price.length; i++)
//		{
//			dpbuy[i] = Math.max(dpbuy[i-1], dpsell[i-1]-price[i]);
//			dpsell[i] = Math.max(dpsell[i-1], dpbuy[i-1] + price[i]);
//		}
//		return dpsell[price.length-1];
		int sum = 0;
	    for(int i=1;i<price.length;i++){
	        if(price[i]-price[i-1] > 0)
	            sum+= price[i]-price[i-1];
	    }
	    return sum;
	}
	
	public int MaxProfit3() {
		if(price.length <= 1) return 0;
		if(price.length == 2) return price[1] > price[0] ? price[1] - price[0] : 0;
		int[] l = new int[price.length];
		int[] r = new int[price.length];
		
		int ret = 0;
		int cur = 0;
		int min = price[0];
		for(int i=0; i<price.length; i++)
		{
			if(price[i] >= min)
			{
				cur = price[i] - min;
				ret = ret > cur ? ret : cur;
			}
			else if(price[i] < min)
				min = price[i];
			l[i] = ret;
		}
		
		ret = 0;
		int max = price[price.length-1];
		for(int i=price.length-1; i>=0; i--)
		{
			if(price[i] <= max)
			{
				cur = max - price[i];
				ret = ret > cur ? ret : cur;
			}
			else if(price[i] > max)
				max = price[i];
			r[i] = ret;
		}
		max = 0;
		for(int i=0; i<price.length-1; i++)
		{
			cur = l[i] + r[i+1];
			if(cur > max) max = cur;
		}
		if(max < r[0])
			max = r[0];
		return max;
	}
}

public class Main3 {
	public static void main(String[] args) {
		Scanner x=new Scanner(System.in);
        while(x.hasNext()){
            int m=x.nextInt();
            int[] price = new int[m];
            for(int i=0;i<m;i++)
                price[i]=x.nextInt();
            StockSeller stock_seller = new StockSeller(price);
            System.out.println(stock_seller.MaxProfit1());
	        System.out.println(stock_seller.MaxProfit2());
	        System.out.println(stock_seller.MaxProfit3());
         }
	x.close();
	}
}

P1217 [USACO1.5]回文质数 Prime Palindromes

Posted on 2019-09-18 | In C++ , 算法题 |

Words count in article: 346 | Reading time ≈ 1

题目描述
因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。

写一个程序来找出范围 [a,b] (5 \le a < b \le 100,000,000)a,b( 一亿)间的所有回文质数。

输入格式
第 1 行: 二个整数 a 和 b .

输出格式
输出一个回文质数的列表，一行一个。

1.偶数位数回文数（除11）必定不是质数（自行百度），所以只要运行到10000000。2.偶数肯定不是质数。这样至少排除一半多的数据量。3，你回文数已经判断出来了，在此中判断即可。

优化

线性筛

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
using namespace std;

int prime[10000005];
bool pp[10000005];
int vis[10000005];

bool h(int x)
{
	int y=x, num=0;
	while(y!=0)
	{
		num = num * 10 + y % 10;
		y /= 10;	
	}	
	if(num == x) return 1;
	else  return 0;
}

int main()
{
	int a, b;
	cin >> a >> b;
	int cnt = 0;
	if(b > 10000000) b = 10000000;
	for(int i=2; i<=b; i++)
	{
		if(!vis[i]) prime[cnt++] = i, pp[i] = 1;
		for(int j=0; j<cnt&&i*prime[j]<=b; j++)
		{
			vis[i*prime[j]] = i;
			if(i%prime[j]==0) break;
		}
	}
	for(int i=a; i<=b; i++)
	{
		if(i > 10000000) break;
		if(h(i) && pp[i]) printf("%d\n", i);
	}
}

web2.0作业二：设计movie review

Posted on 2019-09-18 | In web2.0 and 移动网络安全技术 |

Words count in article: 1.6k | Reading time ≈ 9

<!DOCTYPE html>
<html lang="en">
	<head>
		<meta charset="utf-8" />
		<title>TMNT - Rancid Tomatoes</title>
		<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
		<link href="movie.css" type="text/css" rel="stylesheet" />
	</head>
	<body>
		<div class="banner">
			<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/banner.png" alt="Rancid Tomatoes" />
		</div>
		<h1>TMNT (2007)</h1>
		<div class="box1">
			<div class="content">
				<div class="rright">
					<div>
						<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/generaloverview.png" alt="general overview" />
					</div>
					<dl>
						<dt>STARRING</dt>
						<dd>Mako <br /> Sarah Michelle Gellar</dd>

						<dt>DIRECTOR</dt>
						<dd>Kevin Munroe</dd>

						<dt>RATING</dt>
						<dd>PG</dd>

						<dt>THEATRICAL RELEASE</dt>
						<dd>Mar 23, 2007</dd>

						<dt>MOVIE SYNOPSIS</dt>
						<dd>After the defeat of their old arch nemesis, The Shredder, the Turtles have grown apart as a family.</dd>

						<dt>MPAA RATING</dt>
						<dd>PG, for animated action violence, some scary cartoon images and mild language</dd>

						<dt>RELEASE COMPANY</dt>
						<dd>Warner Bros.</dd>

						<dt>GENRE</dt>
						<dd>Action/Adventure, Comedies, Childrens, Martial Arts, Superheroes, Ninjas, Animated Characters</dd>

						<dt>OFFICIAL MOVIE SITE</dt>
						<dd><a href="http://www.tmnt.com/">The Official TMNT Site</a></dd>
					</dl>
				</div>
				<div class="all">
					<div class="contenthead">
						<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/rottenbig.png" alt="Rotten" />
						<span class="num1">32%</span><span class="num2">(88 reviews total)</span>
					</div>
					<div class="leftt">	
						<div class="qbox">
								<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/rotten.gif" alt="Rotten" />
								<q>Ditching the cheeky, self-aware wink that helped to excuse the concept's inherent corniness, the movie attempts to look polished and 'cool,' but the been-there animation can't compete with the then-cutting-edge puppetry of the 1990 live-action movie.</q>
						</div>	
						<p class="reviewsinfo">
							<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/critic.gif" alt="Critic" />
							Peter Debruge <br />
							<span>Variety</span>
						</p>
						<div class="qbox">
								<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/fresh.gif" alt="Fresh" />
								<q>TMNT is a fun, action-filled adventure that will satisfy longtime fans and generate a legion of new ones.</q>
						</div>
						<p  class="reviewsinfo">
							<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/critic.gif" alt="Critic" />
							Todd Gilchrist <br />
							<span>IGN Movies</span>
						</p>
						<div class="qbox">
								<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/rotten.gif" alt="Rotten" />
								<q>It stinks!</q>
						</div>
						<p  class="reviewsinfo">
							<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/critic.gif" alt="Critic" />
							Jay Sherman (unemployed)
						</p>
						<div class="qbox">
								<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/rotten.gif" alt="Rotten" />
								<q>The rubber suits are gone and they've been redone with fancy computer technology, but that hasn't stopped them from becoming dull.</q>
						</div>
						<p  class="reviewsinfo">
							<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/critic.gif" alt="Critic" />
							Joshua Tyler <br />
							<span>CinemaBlend.com</span>
						</p>
					</div>
					<div class="rightt">
						<div class="qbox">
								<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/rotten.gif" alt="Rotten" />
								<q>The turtles themselves may look prettier, but are no smarter; torn irreparably from their countercultural roots, our superheroes on the half shell have been firmly co-opted by the industry their creators once sought to spoof.</q>
						</div>
						<p  class="reviewsinfo"> 
							<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/critic.gif" alt="Critic" />
							Jeannette Catsoulis <br />
							<span>New York Times</span>
						</p>
						<div class="qbox">
								<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/rotten.gif" alt="Rotten" />
								<q>Impersonally animated and arbitrarily plotted, the story appears to have been made up as the filmmakers went along.</q>
						</div>
						<p  class="reviewsinfo">
							<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/critic.gif" alt="Critic" />
							Ed Gonzalez <br />
							<span>Slant Magazine</span>
						</p>
						<div class="qbox">
								<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/fresh.gif" alt="Fresh" />
								<q>The striking use of image and motion allows each sequence to leave an impression. It's an accomplished restart to this franchise.</q>
						</div>
						<p  class="reviewsinfo">
							<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/critic.gif" alt="Critic" />
							Mark Palermo <br />
							<span>Coast (Halifax, Nova Scotia)</span>
						</p>
						<div class="qbox">
								<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/rotten.gif" alt="Rotten" />
								<q>The script feels like it was computer generated. This mechanical presentation lacks the cheesy charm of the three live action films.</q>
						</div>
						<p  class="reviewsinfo">
							<img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/critic.gif" alt="Critic" />
							Steve Rhodes <br />
							<span>Internet Reviews</span>
						</p>
					</div>
				</div>
				<p class="last">(1-8) of 88</p>
			</div>
			<div class="c3">
				<a href="http://validator.w3.org/check/referer"><img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/w3c-xhtml.png" alt="Valid XHTML 1.1" /></a> <br />
				<a href="http://jigsaw.w3.org/css-validator/check/referer"><img src="http://www.cs.washington.edu/education/courses/cse190m/09sp/homework/2/w3c-css.png" alt="Valid CSS!" /></a>
			</div>
		</div>
	</body>
</html>

body{
	background-image: url('http://hcp.sysu.edu.cn/wiki/download/attachments/32833570/background.png?version=1&modificationDate=1268939512000&api=v2');	 
	font-size: 8pt;
	font-family: "Verdana", "Tahoma", "sans-serif";
	margin: 0pt;
	padding: 0pt;
}


.banner{
	background-image: url('http://hcp.sysu.edu.cn/wiki/download/attachments/32833570/bannerbackground.png?version=1&modificationDate=1268939512000&api=v2');
	text-align: center;
	height: 50px;
}

h1{
	font-size: 24pt;
	font-weight: bold;
	text-align: center;
	font-family: "Tahoma", "Verdana", "sans-serif";
}

.content{
	margin: 0 auto;
	width: 800px;
	border: 4px gray solid;
	overflow: hidden;
}

.all{
	width: 550px;
}

.contenthead{
	width: 550px;
	float: left;
	background-image: url('http://hcp.sysu.edu.cn/wiki/download/attachments/32833570/rottenbackground.png?version=1&modificationDate=1268939585000&api=v2');
	height: 83px;
}

.contenthead img{
	float: left;
}

.contenthead .num1{
	font-size: 48pt;
	color: red;
	font-weight: bold;
	line-height: 140%;
	/*display: inline;*/
}

.contenthead .num2{
	font-size: 8pt;
	color: white;	
}

.leftt{
	width: 47%;
	padding-left: 2%;
	padding-right: 2%;
	padding-top: 2%;
	float: left;
}

.rightt{
	width: 47%;
	padding-right: 2%;
	padding-top: 2%;
	float: right;
}


.qbox{
	font-size: 8pt;
	font-weight: bold;
	background-color: #E1D697;
	border: 2px solid gray;
	padding: 8px;
	overflow: hidden;
}


.qbox img{
	float: left;
	padding-right: 5px;
}

.reviewsinfo{
	margin-bottom: 3em;
	overflow: hidden;
}

.reviewsinfo img{
	float: left;
	padding-right: 5px;
}

.reviewsinfo span{
	font-style: italic;
}

.rright{
	background-color: #A2B964;
	font-size: 8pt;
	font-family: "Arial", "sans-serif";
	float: right;
	width: 250px;
}

.rright dl{
	padding-left: 10px;
	padding-right: 10px;
}

.rright dt{
	font-weight: bold;
}

.rright dd{
	padding-bottom: 1em;
}

.last{
	background-color: #A2B964;
	padding: 5px;
	clear: right;
	margin: 0;
	text-align: center;
}

.c3{
	position: absolute;
	right: 0;
	bottom: 0;
}

.box1{
	position: relative;
}

Weekly Contest 153

Posted on 2019-09-17 | In leetcode , Weekly-Contest |

Words count in article: 941 | Reading time ≈ 5

1184. Distance Between Bus Stops

A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given start and destination stops.

1
2
3

Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

class Solution {
public:
    int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
        int sum1 = 0;
        int sum2 = 0;
        if(start > destination){
            int tmp = start;
            start = destination;
            destination = tmp;
        }
        for(int i=start; i<destination; i++)
        {
             sum1 += distance[i];
        }    
        for(int i=destination; i<start+distance.size(); i++)
            sum2 += distance[i%distance.size()];
        if(sum1 < sum2) return sum1;
        else return sum2;
    }
};

1185. Day of the Week

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the day, month and year respectively.

Return the answer as one of the following values {“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday”, “Saturday”}.

Example 1:

Input: day = 31, month = 8, year = 2019
Output: "Saturday"
Example 2:

Input: day = 18, month = 7, year = 1999
Output: "Sunday"
Example 3:

Input: day = 15, month = 8, year = 1993
Output: "Sunday"

class Solution {
public:
        string dayOfTheWeek(int day, int month, int year) {
            string daysInWeek[7] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
            int DaysByMonthMod7[12] = {0,3,2,5,0,3,5,1,4,6,2,4};
            if(month < 3) year -= 1;
            return daysInWeek[(year + (year/4 -year/100 + year/400) + DaysByMonthMod7[month-1] + day) % 7];
        }      
};

Constraints:

The given dates are valid dates between the years 1971 and 2100.

1186. Maximum Subarray Sum with One Deletion

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

Example 1:

Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.
Example 2:

Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.
Example 3:

Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

Constraints:

1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4

class Solution {
public:
    int maximumSum(vector<int>& v) {
        int res = 0, n = v.size();
        int cur_max = v[0], overall_max = v[0];
        vector<int> f(n);
        vector<int> b(n);
        f[0] = v[0];
        
        for(int i=1; i<n; i++)
        {
            cur_max = max(v[i], cur_max+v[i]);
            overall_max = max(overall_max, cur_max);
            
            f[i] = cur_max;
        }
        
        cur_max = overall_max = b[n-1] = v[n-1];
        for(int i=n-2; i>=0; i-- )
        {
            cur_max = max(v[i], cur_max + v[i]);
            overall_max = max(overall_max, cur_max);
            
            b[i] = cur_max;
        }
        
        res = overall_max;
        for(int i=1; i<n-1; i++)
        {
            res = max(res, f[i-1] + b[i+1]);
        }
        
        return res;
    }
};

1187. Make Array Strictly Increasing

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].
Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].
Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

Constraints:

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

class Solution {
public:
    int dp[2001][2001] = {};

    int dfs(vector<int>& a1, vector<int>&a2, int i1, int i2, int prev){
        if(i1 >= a1.size()) return 0;
        i2 = upper_bound(begin(a2) + i2, end(a2), prev) - begin(a2);
        if(dp[i1][i2]) return dp[i1][i2];
        int r1 = i2 < a2.size() ? 1 + dfs(a1, a2, i1+1, i2+1, a2[i2]) : a2.size()+1;
        int r2 = prev < a1[i1] ? dfs(a1, a2, i1+1, i2, a1[i1]) : a2.size()+1;
        dp[i1][i2] = min(r1, r2);
        return dp[i1][i2];
    }
    
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(), arr2.end());
        int res = dfs(arr1, arr2, 0, 0, INT_MIN);
        return res > arr2.size() ? -1 : res;
    }
};