線性資料結構 --- array (3)

只有不斷學習,練習,,複習才會越來越厲害

因此開始記錄依照不同資料結構搭配Leetcode來練習

方便未來可以隨時拿來複習




Leetcode出處 : https://leetcode.com/problems/longest-consecutive-sequence/


                                 Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.



分析

因為題目說是unsorted integer，但是又說complexity必須是O(n)
因此，需要想到用hash table
我打算用unsorted_set來解此問題，並且以set裡面的元素為中心向外尋找下一個職是否在set裡，直到不連續為止
乍看之下時間複雜度是O(n^2)，但是因為在numsSet.erase(j)後，之前出現過的就不會再進入內層兩個迴圈裡，因此類積下來的次數就是nums元素個數。
另外，如果沒有說到要O(n)，我們可以先排序再做，因此時間複雜度就是O(n log n)



Sample Code (C++)

	class Solution {
	public:
	int longestConsecutive(vector<int>& nums) {
	int longestLen = 0;
	int currentLen = 0;
	unordered_set<int> numsSet;
	for (auto& i : nums)
	numsSet.insert(i);
	for (auto& i : nums) {
	currentLen = 1;
	/* Search smaller than i */
	for (int j = i-1; numsSet.find(j) != numsSet.end(); j--) {
	currentLen++;
	numsSet.erase(j);
	}
	/* Search bigger than i */
	for (int j = i+1; numsSet.find(j) != numsSet.end(); j++) {
	currentLen++;
	numsSet.erase(j);
	}
	longestLen = max(currentLen, longestLen);
	}
	return longestLen;
	}
	};

view raw .cpp hosted with ❤ by GitHub

線性資料結構 --- array (2)

只有不斷學習,練習,,複習才會越來越厲害

因此，開始記錄依照不同資料結構搭配Leetcode來練習

方便未來可以隨時拿來複習


Leetcode出處 : /https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/


                                 Remove Duplicates from Sorted Array II

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.



分析

和Remove Duplicates from Sorted Array解法差不多



Sample Code (C++)

	class Solution {
	public:
	int removeDuplicates(vector<int>& nums) {
	int index = 2;
	int length = nums.size();
	if (length<=2)
	return length;
	for(int i = 2; i<length; i++) {
	if (nums[i] != nums[index-2])
	nums[index++] = nums[i];
	}
	return index;
	}

view raw .cpp hosted with ❤ by GitHub

線性資料結構 --- array (1)

只有不斷學習,練習,,複習才會越來越厲害
因此，開始記錄依照不同資料結構搭配Leetcode來練習
方便未來可以隨時拿來複習


Leetcode出處 : https://leetcode.com/problems/remove-duplicates-from-sorted-array/

             Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. 


Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.


Sample Code (C++)

	class Solution {
	public:
	int removeDuplicates(vector<int>& nums) {
	int length = nums.size();
	int index = 1;
	if (length == 0)
	return 0;
	for(int i=1; i<length; i++) {
	if (nums[i] != nums[i-1])
	nums[index++] = nums[i];
	}
	return index;
	}
	};

view raw .cpp hosted with ❤ by GitHub

[AI 探討] AI︑Machine Learning︑Deep Learning簡單介紹

前言

由於接下來工作內容要開始玩電腦視覺(Computer Vision, CV)

在開始摸CV之前來好好研究一下幾個常見名詞: AI︑ Machine Learning ︑Deep Learning

以前完全沒碰過這個技術... ...等於是從0開始

前兩年因為AlphaGo在圍棋上不斷擊敗職業棋士，因此AI才開始變成熱門話題

因為早期電腦硬體的效能和限制只能用來解決一些簡單的問題，無法實際用在解決現實生活

的問題，所以變成只有在發展理論，但是卻一直不是熱門話題。

台大李琳山教授便是語音辨識先驅，很多華語語音辨識都參考到他的研究。

另外，有興趣學machine learning卻不知從何開始，可以考慮台大林軒田教授的開放課程，只

能說強者一個~

coursera 連結如下:

https://zh-tw.coursera.org/instructor/htlin

ptt鄉民也整理出來學習路線:
https://www.ptt.cc/bbs/DataScience/M.1518514290.A.816.html

正文

人工智慧(AI)

指由人類製造出來能夠表現出智慧的技術。通常是指電腦模擬或模擬人類思維過程的行為能力。

在電影裡看到機器人像人類一樣有自我意識，可以做很多非特定任務的工作，這就是人工智慧。

基本上擁有一個rule-based的系統也是屬於AI範疇下。

所謂的rule-based就是指根據經驗設定判斷依據，例如: ⌈狗只會汪汪叫︑貓只會喵喵叫⌋︑⌈貓不太理人︑狗很黏人⌋

不過現在可以實現的人工智慧還侷限於⌈弱人工智慧(Narrow AI)⌋，這些技術只能完成特定任務。

機器學習(Machine Learning)

一種實現人工智慧的方法，使用演算法來分析資料並學習，然後對已發生或未發生的事件做出決定或預測。

通常透過大量的資料和演算法來⌈訓練⌋，給予它學習如何執行任務的能力。

機器學習流程大概如下: 資料輸入  → 特徵擷取 → 建立模型  → 答案輸出







透過大量資訊輸入來訓練並且不斷更正提高正確率，並且建立出一個誤差低︑準確度高的模型。

常見演算法包括: 決策數學習︑歸納邏輯程式設計︑聚類︑強化學習等等。

而現在熱門應用領域則是電腦視覺(CV)，可以很快速找辨識出物體

︑

深度學習(Deep Learning)

一種實現機器學習的技術，使用神經網路(Neural Network, NN)做分析的機器學習方法。

深度學習流程大概如下: 資料輸入→ 建立模型 → 答案輸出




神經網路的靈感來自於我們對人類大腦生物學的理解，所有的神經元之間相互聯繫。

神經網路就是一堆函數的集合，我們丟進去一堆數值，整個網路就輸出一堆數值，並且從裡

面找出一個最好的結果。

大概長成這個樣子:

結語

未來會用GPU跑caffe演算法，到時再來發心得文






︑

[ JPEG 系列 ] JPEG圖片格式探討 (一)

前言

由於工作上常常碰到Jpeg, Exif等名詞，雖然大學有修過多媒體概論，有基本介紹一般常見的

儲存格式，但是總體來說還是只是為了考試，實際上對這些內容完全沒有概念。

在不斷解issue過程也開始對JPEG有比較深刻的體會，也不得不整理一些資料。

*想到就加入內容，有查到更多資料可以分享再來更新

正文

平常聽到JPEG檔案其實是一種針對相片影像而廣泛使用的失真壓縮標準方法
並且透過JFIF（JPEG File Interchange Format，JPEG檔案交換格式) 詳細說明如何從一個JPEG串流，產出一個適合於電腦儲存和傳輸（像是在網際網路上）的檔案。
請參考維基百科介紹。


因此，可以知道JPEG是一種壓縮標準，而JFIF是一種檔案格式。

JPEG是第一個國際圖像壓縮標準，其特性如下:

• 圖像壓縮演算法提供良好的壓縮率，並且可以在解壓縮後獲得較高的還原率
• 廣泛使用於圖像︑影像領域
• PEG的壓縮方式通常是失真壓縮（lossy compression），即在壓縮過程中圖像的品質會遭受到可見的破壞

JIFF是一個圖檔格式標準，其特性如下:

• 使用JPEG圖像壓縮技術儲存圖片的方式
• 方便用戶在不同的裝置之間傳輸JPEG圖像
• 定義圖片長寬︑解析度︑色彩空間等基本訊息，這些訊息在JPEG壓縮標準沒有定義
• 由系列標記（marker）或標記段（marker segments）組成

[UVa][ Volume V ] 579 - Clock Hands

UVa Volume V  579 - Clock Hands

題目來源 : Clock Hands

解題 :

此題在判斷某時的分針和時針角度差。

首先，資料輸入方面這次直接用scanf()來抓取資料省去麻煩。

接著，在處理角度差時，我處理方式如下 :

將hour乘以30︑minute乘以6來換算成角度。
需要注意的是，當分針不是指向00時候，還需要將時針加上些微的移動。
因為每個小時的角度為30度，所以將30除以60(每個小時60分)，
便可以得到 :
每過一分鐘時針移動角度為0.5度

最後整理出公式為 : h * 30 + m * 0.5 - m * 6

參考解答(C++)

	#include <iostream>
	#include <iomanip>
	using namespace std;
	int main(void)
	{
	// 設定顯示至小數點第三位
	cout << setiosflags(ios::fixed) << setprecision(3);
	while (1)
	{
	int h, m;
	scanf("%d:%d", &h, &m);
	if (!h && !m)
	{
	break;
	}
	// 分針每前進 1 度, 時針就前進 0.5 度
	double angle = (double)h * 30 - (double)m * 5.5;
	if (angle < 0)
	{
	angle *= -1;
	}
	if (angle > 180)
	{
	angle = 360 - angle;
	}
	cout << angle << endl;
	}
	system("pause");
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

[UVa][ Volume IV ] 406 - Prime Cuts

UVa Volume IV  406 - Prime Cuts


題目來源 : Prime Cuts

解題 :

常見的質數題目，一般來說都會用到埃氏篩法(Sieve of Eratosthenes)來找出質數。

首先，我建立一個prime -- 大小為n的一維boolean陣列，代表某數字是否為質數。

埃氏篩法(Sieve of Eratosthenes)作法如下 :

若一個正整數為另一個正整數的倍數，則這個整數必定不是質數。
所以，從最小質數2開始，將所有2的倍數(不包含2)標記為⌈非質數⌋。
接著，往下下一個沒有被標記成質數的數字3，再將3的倍數(不包含3)標記為⌈非質數⌋。
以此類推下去，直到找出所有小於等於n的質數。

找出所有質數後，只要根據質數的數量，並且依找題目要求輸出中間2*C (或是 2*C - 1)個質數

參考解答(C++)

	#include <iostream>
	using namespace std;
	int main(void)
	{
	int n, c;
	while (cin >> n >> c)
	{
	// 變數初始化
	bool *prime = new bool[n];
	for (int i = 0; i < n; i++)
	{
	prime[i] = true;
	}
	// 紀錄哪些數是質數
	int num = 1;
	for (int i = 2; i <= n; i++)
	{
	if (prime[i - 1])
	{
	num++;
	for (int j = 2; j * i <= n; j++)
	{
	prime[j * i - 1] = false;
	}
	}
	}
	cout << n << " " << c << ":";
	int i, x, p = 2 * c - (num % 2 ? 1 : 0);
	// 跳過不需輸出的質數
	x = 0;
	for (i = 0; x < (num - p) / 2; i++)
	{
	if (prime[i])
	{
	x++;
	}
	}
	// 開始輸出的質數
	x = 0;
	for (; x < p && i < n; i++)
	{
	if (prime[i])
	{
	cout << " " << i + 1;
	x++;
	}
	}
	cout << endl
	<< endl;
	}
	system("pause");
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub