20. Valid Parentheses

解題思路

這題是 stack 很經典的題目──括號匹配問題。

記得想好 edgecase。

程式碼

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;

        for(int i=0; i<s.size(); i++)
        {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{')
                st.push(s[i]);
            else if(!st.empty() && s[i] == ')' && st.top() == '(')
                st.pop();
            else if(!st.empty() && s[i] == ']' && st.top() == '[')
                st.pop();
            else if(!st.empty() && s[i] == '}' && st.top() == '{')
                st.pop();
            else
                return false;
        }
        return st.empty();
    }
};

1. Two Sum

解題思路

第一時間想到的暴力解，是直接兩層迴圈去找相加和等不等於 target，時間複雜度 O(n^2)。

看提示中的 tag 有 hashTable，於是想到可以只用一次迴圈，也就是時間複雜度 O(n) 的解法。由於我們要找兩個 index，分別表示 array 中相加為 target 的兩個數，所以當我們有某個數值 n ，則需要找另一個數值 target - n 是否存在於 array。

既然這樣，那就在這一次的迴圈中，看當下這個新的數字 n，它的配對數字 target - n 是不是已經看過了(存在 map 中)。如果有，就結束這回合；如果沒有，記得把當下的數字 n 存進 map 中。

程式碼

方法一：暴力解

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        for(int i=0; i<nums.size(); i++)
        {
            for(int j=i+1; j<nums.size(); j++)
            {
                if(nums[i] + nums[j] == target)
                {
                    ans.push_back(i);
                    ans.push_back(j);
                    return ans;
                }
            }
        }
        return ans;
    }
};

方法二：hashTable

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mp;
        vector<int> ans;
        for(int i=0; i<nums.size(); i++)
        {
            if(mp.count(target - nums[i]))
            {
                ans.push_back(i);
                ans.push_back(mp[target - nums[i]]);
                return ans;
            }
            mp[nums[i]] = i;
        }
        return ans;
    }
};

git: push a folder to an empty repo

git init

git add .

git remote add origin https://gitlab.com/username/repo.git

git commit -m "your message"

git push -u origin master

Done!

i524: 11988: Broken Keyboard (a.k.a. Beiju Text)

程式碼

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

int main()
{
	string s;
	while (cin >> s)
	{
		string ans = "";
		int index = 0;
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == '[')
			{
				index = 0;
			}
			else if (s[i] == ']')
			{
				index = ans.size() ;
				if (index < 0) index = 0;
			}
			else
			{
				ans.insert(index, string(1, s[i]));
				index++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

h033: 雜訊移除 (Noise)

程式碼

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

int main()
{
	string s;
	int n;
	cin >> s >> n;
	int i = 0;
	while (i != s.size())
	{
		if (s[i] - '0' == n)
		{
			s.erase(i, 1);
		}
		else
			i++;
	}
	bool flag = true;
	for (int i = 0; i < s.size() / 2; i++)
	{
		if (s[i] != s[s.size() - i - 1])
		{
			flag = false;
			break;
		}
	}
	if (flag) cout << "Yes";
	else cout << "No";
	return 0;
}

h081: 1. 程式交易

解題心得

題目中的利潤跟我認知的不一樣，整題花在理解題意上面的時間最久。

程式碼

#include<iostream>
using namespace std;

int main()
{
	int n, d, a[101] = { 0 }, sum = 0, current = -1;
	bool flag = false;
	cin >> n >> d;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		if (i == 0)
		{
			current = a[i];
			flag = true;
		}
		else if (flag && a[i] >= current + d)
		{
			sum += a[i] - current;
			current = a[i];
			flag = false;
		}
		else if (!flag && a[i] <= current - d) // 當下沒有持有股票
		{
			current = a[i];
			flag = true;
		}
	}
	cout << sum;
	return 0;
}

g796: 檔案分類 (Files)

程式碼

#include<iostream>
using namespace std;

int main()
{
	int n, file[100] = { 0 }, index = 0;
	string s;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		index = (s[3] - '0') * 10 + (s[4] - '0');
		file[index] ++ ;
	}
	for (int i = 0; i < 100; i++)
	{
		if (file[i])
		{
			cout << i << " " << file[i] << endl;
		}
	}
	return 0;
}

i399: 1. 數字遊戲

程式碼

#include<iostream>
using namespace std;

int main()
{
	int index[10] = { 0 }, maxTime = 0, n;
	for (int i = 0; i < 3; i++)
	{
		cin >> n;
		index[n]++;
	}
	for (int i = 0; i < 10; i++)
	{
		if (index[i] > maxTime)
			maxTime = index[i];
	}
	cout << maxTime << " ";
	for (int i = 9; i >= 0; i--)
	{
		if (index[i])
		{
			cout << i;
			maxTime--;
			if (3 - maxTime != 0) cout << " ";
		}
	}
	return 0;
}

i071: 風景 (Landscape)

解題心得

往左看一次，往右也看一次。

程式碼

#include<iostream>
using namespace std;

int main()
{
	int n, m, arr[1001], sum = 0, height;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	m -= 1;
	height = arr[m];
	for (int i = m - 1; i >= 0; i--)
	{
		if (arr[i] > height)
		{
			height = arr[i];
			sum++;
		}
	}
	height = arr[m];
	for (int i = m + 1; i < n; i++)
	{
		if (arr[i] > height)
		{
			height = arr[i];
			sum++;
		}
	}
	cout << sum;
	return 0;
}

h659: 計程車 (Taxi)

解題心得

想了一下才想到如何判斷區間QQ

程式碼

#include<iostream>
using namespace std;

int main()
{
	int k, w, s, e, sum = 0;
	cin >> k >> w >> s >> e;

	if (k < 2)
		sum += 20;
	else
		sum += 20 + (k - 2) * 5;
	sum += (w / 2) * 5;
	bool time[24] = { false };
	for (int i = s; i <= e; i++)
		time[i] = true;

	if (time[18] && time[19]) sum += 185;
	if (time[19] && time[20]) sum += 195;
	if (time[20] && time[21]) sum += 205;
	if (time[21] && time[22]) sum += 215;
	if (time[22] && time[23]) sum += 225;
	cout << sum;
	return 0;
}

h658: 捕魚 (Fishing)

程式碼

#include<iostream>
using namespace std;

int main()
{
	int x, y, n, fishX[501] = { 0 }, fishY[501] = { 0 }, ansX = 0, ansY = 0;
	cin >> x >> y >> n;
	
	for (int i = 0; i < n; i++)
	{
		cin >> fishX[i] >> fishY[i];
		int now = abs(x - fishX[i]) * abs(x - fishX[i]) + abs(y - fishY[i]) * abs(y - fishY[i]);
		int best = abs(x - fishX[ansX]) * abs(x - fishX[ansX]) + abs(y - fishY[ansY]) * abs(y - fishY[ansY]);
		if (now < best)
		{
			ansX = i;
			ansY = i;
		}
	}
	cout << fishX[ansX] << " " << fishY[ansY];
	return 0;
}