kanrourou’s gists

kanrourou / Linked List Cycle II.cpp

Created December 25, 2018 05:30

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:

kanrourou / Linked List Cycle.cpp

Created December 25, 2018 05:27

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:

kanrourou / Rotate List.cpp

Created December 25, 2018 04:38

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:

kanrourou / Maximum Sum of 3 Non-Overlapping Subarrays.cpp

Created December 24, 2018 05:58

	class Solution {
	public:
	vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
	int len = nums.size();
	if(len < 3 * k)return {};
	//store index, use presum to get the value
	vector<int> left(len, -1), right(len, -1), presums(len + 1, 0);
	int sum = 0;
	//init presum
	for(int i = 0; i < len; ++i)

kanrourou / Maximum Subarray II.cpp

Created December 23, 2018 18:45

	class Solution {
	public:
	/*
	* @param nums: A list of integers
	* @return: An integer denotes the sum of max two non-overlapping subarrays
	*/
	int maxTwoSubArrays(vector<int> &nums) {
	int len = nums.size(), localMax = INT_MIN;
	vector<int> dp(len, 0);
	//left to right

kanrourou / Maximum Subarray III.cpp

Created December 23, 2018 18:13

	class Solution {
	public:
	/**
	* @param nums: A list of integers
	* @param k: An integer denote to find k non-overlapping subarrays
	* @return: An integer denote the sum of max k non-overlapping subarrays
	*/
	int maxSubArray(vector<int> &nums, int k) {
	int len = nums.size();
	if(len < k)return 0;

kanrourou / Best Time to Buy and Sell Stock with Cooldown.cpp

Created December 22, 2018 19:42

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	int len = prices.size();
	if(len < 2)return 0;
	vector<int> dp(2, 0);
	dp[1] = max(0, prices[1] - prices[0]);
	int maxDiff = dp[0] - prices[2], e = 0;
	for(int i = 2; i < len; ++i, e ^= 1)
	{

kanrourou / Best Time to Buy and Sell Stock.cpp

Created December 22, 2018 05:41

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	if(prices.empty())return 0;
	int len = prices.size(), globalMax = 0, minPrice = prices[0];
	for(int i = 1; i < len; ++i)
	{
	int localMax = prices[i] - minPrice;
	globalMax = max(globalMax, localMax);
	minPrice = min(minPrice, prices[i]);

kanrourou / 3Sum Smaller.cpp

Created December 21, 2018 06:14

	class Solution {
	public:
	int threeSumSmaller(vector<int>& nums, int target) {
	int len = nums.size(), res = 0;
	if (len < 3)return 0;
	sort(nums.begin(), nums.end());
	for (int i = 0; i + 2 < len; ++i)
	{
	int lo = i + 1, hi = len - 1;
	while (lo < hi)

kanrourou / 4Sum II.cpp

Created December 21, 2018 06:11

	class Solution {
	public:
	int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
	unordered_map<int, int> map;
	int res = 0;
	for (int i = 0; i < A.size(); ++i)
	{
	for (int j = 0; j < B.size(); ++j)
	{
	int sum = A[i] + B[j];

Ke Xu kanrourou