leetcode 地址: https://leetcode.com/contest/detail/1
(1)-- Lexicographical Numbers
Given an integer n, return 1 - n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.
好久没有上leetcode了, 突然发现leetcode开始搞竞赛了, 做了 热身赛的第一题,
简单的leetcode风格的题目,使用dfs,深度优先遍历,字典序的经典做法。
class Solution { public: void dfs(int cur, int n, vector<int> &ret){ if(cur > n){ return; } ret.push_back(cur); for(int i=0; i<=9; i++){ dfs(cur*10+i, n, ret); } } vector<int> lexicalOrder(int n) { vector<int> t; for(int i=1; i<=9; i++){ dfs(i, n, t); } return t; } };
(2) First Unique Character in a String
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
Examples:
s = "leetcode" return 0. s = "loveleetcode", return 2.
Note: You may assume the string contain only lowercase letters.
查找字符串中的第一个单一字符,
典型的hash 方法, 字符串只含有lowercase的字符, 构造一个26维度的数组,作为hash table。
算法复杂度为O(n), n为字符串的长度,就是扫一次字符串就可以得到。
class Solution { public: int firstUniqChar(string s) { int vis[26] = {0}; for(int i=0; i<s.length(); i++){ if(vis[s[i]-'a'] == 0){ vis[s[i]-'a'] = i+1; }else{ vis[s[i]-'a'] = -1; } } int ans = 1000000; bool flag = false; for(int i=0; i<26; i++){ if(vis[i] != 0 && vis[i] != -1 && vis[i] < ans){ ans = vis[i]; flag = true; } } if(flag){ ans = ans - 1; }else{ ans = -1; } return ans; } };
(3), Longest Absolute File Path
求出最长的文件路径(记得要加上dir与dir之间的 ‘/’ , 也算是一个字符), 明显字符串的组成就是dfs的方式,不妨利用dfs数组进行一个遍历。
时间复杂度: O(n), 扫描字符串数组的长度n。
class Solution { public: void dfs(int cur, int depth, int *a, int& ans, string& s){ int isFile, i = cur; while(i < s.length()){ if(s[i] == ' '){ isFile = 0; break; }else if(s[i] == '.'){ isFile = 1; break; } i++; } if(isFile == 1){ int tmp = 0; for(int j=0; j<depth; ++j){ tmp += a[j] + 1; } while(i<s.length() && s[i] != ' '){ i++; } tmp += i - cur; if( tmp > ans){ ans = tmp; } if(i < s.length() && s[i] == ' '){ int j = i+1, cnt = 0; while(j<s.length() && s[j] ==' '){ j = j + 1; cnt = cnt + 1; } if(j < s.length() ){ dfs(j, cnt, a, ans, s); } } }else{ a[depth] = i - cur; if(s[i]==' '){ int j = i+1, cnt = 0; while(j<s.length() && s[j]==' '){ j = j + 1; cnt = cnt + 1; } if(j < s.length() ){ dfs(j, cnt, a, ans, s); } } } } int lengthLongestPath(string input) { int *a = new int[100]; for(int i=0; i<100; i++){ a[i] = 0; } int ans = 0; dfs(0, 0, a, ans, input); delete[] a; return ans; } };