i********s
发帖数: 22 | 1 value是0-(n-1)之间的么?
那直接dfs就可以了，O(N)复杂度
vector used(n, false);
for (int i = 0; i < n; ++i) {
if (!used[i]) {
dfs(i, , i, arr, used, len);
if (len > max_len) {
max = len;
}
}
}
void dfs(int start, int idx, int[] arr, vector& used, int &len) {
used[idx] = true;
len ++;
if (!used[arr[idx]]) {
dfs(start, arr[idx], arr, used, len);
} else {
assert(start == idx)
}
} |
|
z***e
发帖数: 58 | 2 小弟的代码， 复杂度O(n)
void taxiCub(int n)
{
int limit = n;
n =(int)pow(n,(double)1/(double)3)+1;
vector remark = vector(n+1,0);
vector used = vector(2*n*n*n+1,false);
for(int i = 0 ;i < n+1; i++)
{
remark[i] = i*i*i;
}
for(int i = 1 ; i <= n-1;i++)
{
for(int j = i+1;j <= n;j++)
{
int start = i+1;
int end = j-1;
if(start < end)
{
int sum = remark[i] + remark[... 阅读全帖 |
|
z***e
发帖数: 58 | 3 小弟的代码， 复杂度O(n)
void taxiCub(int n)
{
int limit = n;
n =(int)pow(n,(double)1/(double)3)+1;
vector remark = vector(n+1,0);
vector used = vector(2*n*n*n+1,false);
for(int i = 0 ;i < n+1; i++)
{
remark[i] = i*i*i;
}
for(int i = 1 ; i <= n-1;i++)
{
for(int j = i+1;j <= n;j++)
{
int start = i+1;
int end = j-1;
if(start < end)
{
int sum = remark[i] + remark[... 阅读全帖 |
|
s********u
发帖数: 1109 | 4 就是用condition_variable的时候，wait函数有一个参数是predicate，一般就是传一
个bool函数进去。
但我用gcc 4.8.1试了下这几种都不行(设计blocking queue）：
_cond.wait(locker, [](){ return !_queue.empty() } );
_cond.wait(locker, []{ return !_queue.empty() } );
bool notEmpty(){return !_queue.empty() ;}
_cond.wait(locker, notEmpty);
错误是： 'this' was not captured for this lambda function
编译器问题？
顺便问下就是这种写法等效么：
while(_queue.empty())
_cond.wait(locker);
要是等效就不费事了。 |
|
J**9
发帖数: 835 | 5 Problem at
http://discuss.leetcode.com/questions/765/word-break
This does not seem to be a DP problem, just do it in a straightforward way.
Here's my implementation in C. Any issue?
Thanks.
//===========================================================
#include
#include
#include
#include
#include
/**
* Given a string s and a dictionary of words dict, determine if s can be
segmented into a space-separated sequence of one or more
* dictionary w... 阅读全帖 |
|
s********u
发帖数: 1109 | 6 我觉得，在实际使用中，可以就写个node，就是自带一个bool值，一个char值，和一个
vector。其他的函数，可以写成global或者solution类里面。否则你既要写
node，还要写trie类。
比如boggle game那个题，明显就是不用trie自己的search比较好，因为每次只需要
search一个char就行了。用trie自己的，就要search一个string。
struct TrieNode {
char mContent;
bool mMarker;
vector mChildren;
Node(char *c) { mContent = c; mMarker = false; }
}; |
|
s********u
发帖数: 1109 | 7 我觉得，在实际使用中，可以就写个node，就是自带一个bool值，一个char值，和一个
vector。其他的函数，可以写成global或者solution类里面。否则你既要写
node，还要写trie类。
比如boggle game那个题，明显就是不用trie自己的search比较好，因为每次只需要
search一个char就行了。用trie自己的，就要search一个string。
struct TrieNode {
char mContent;
bool mMarker;
vector mChildren;
Node(char *c) { mContent = c; mMarker = false; }
}; |
|
kx
发帖数: 16384 | 8 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: （麻烦转到jobhunting版）Splunk面经
发信站: BBS 未名空间站 (Fri Nov 1 12:33:13 2013, 美东)
--------------------------------------------
对方发来email，要求找以下三段code有什么问题：
1.
bool f(int x)
{
return !(x & 7);
}
2.
uint v[10];
uint i = 0;
while (i < 10)
v[i] = i++;
3.
bool f( uint n )
{
return (n & (n-1)) == 0;
}
这道题我只找到一个问题，就是调用f(n)时如果n是INT_MIN，那么返回true。
-------------------------------------------- |
|
kx
发帖数: 16384 | 9 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: （麻烦转到jobhunting版）Splunk面经
发信站: BBS 未名空间站 (Fri Nov 1 12:33:13 2013, 美东)
--------------------------------------------
对方发来email，要求找以下三段code有什么问题：
1.
bool f(int x)
{
return !(x & 7);
}
2.
uint v[10];
uint i = 0;
while (i < 10)
v[i] = i++;
3.
bool f( uint n )
{
return (n & (n-1)) == 0;
}
这道题我只找到一个问题，就是调用f(n)时如果n是INT_MIN，那么返回true。
-------------------------------------------- |
|
k******4
发帖数: 94 | 10 这个也是你那本书上推荐的解法之一，但是总有个担心，万一BST中最小的元素等于
lowBound的初始值怎么办？
试着贴个刚在leetcode通过的代码
bool isBST(TreeNode*root, TreeNode*&pre)
{
if(root == NULL)
return true;
if(!isBST(root->left, pre) || (pre != NULL && pre->val >= root->val)
)
return false;
pre = root;
return isBST(root->right, pre);
}
bool isValidBST(TreeNode *root) {
TreeNode *pre = NULL;
return isBST(root,pre);
} |
|
D**********d
发帖数: 849 | 11 一行代码搞掂
initial call: bool IsBST(root, INT_MIN - 1ll, INT_MAX + 1ll);
bool IsBST(Tree* root, long long MIN, long long MAX){
return root == 0? true: root->val < MAX && root->val > MIN && IsBST(root->
left, MIN, root->val) && IsBST(root->right, root->val, MAX);
} |
|
k******4
发帖数: 94 | 12 这个也是你那本书上推荐的解法之一，但是总有个担心，万一BST中最小的元素等于
lowBound的初始值怎么办？
试着贴个刚在leetcode通过的代码
bool isBST(TreeNode*root, TreeNode*&pre)
{
if(root == NULL)
return true;
if(!isBST(root->left, pre) || (pre != NULL && pre->val >= root->val)
)
return false;
pre = root;
return isBST(root->right, pre);
}
bool isValidBST(TreeNode *root) {
TreeNode *pre = NULL;
return isBST(root,pre);
} |
|
D**********d
发帖数: 849 | 13 一行代码搞掂
initial call: bool IsBST(root, INT_MIN - 1ll, INT_MAX + 1ll);
bool IsBST(Tree* root, long long MIN, long long MAX){
return root == 0? true: root->val < MAX && root->val > MIN && IsBST(root->
left, MIN, root->val) && IsBST(root->right, root->val, MAX);
} |
|
n****e
发帖数: 678 | 14 照着你的架构写写：
bool play_game(bool contestant_will_switch_doors) {
srand( time(NULL) );
int contestant_index = rand() % 3;
int host_count = rand() % 2;
int host_index;
for (host_index = 0; host_index < 3; host_index++) {
if (host_index != contestant_index) {
host_count--;
}
if (host_count < 0) {
break;
}
}
if (contestant_will_switch_doors) {
return vec[3- contestant_index - host_index] == prize... 阅读全帖 |
|
n****e
发帖数: 678 | 15 照着你的架构写写：
bool play_game(bool contestant_will_switch_doors) {
srand( time(NULL) );
int contestant_index = rand() % 3;
int host_count = rand() % 2;
int host_index;
for (host_index = 0; host_index < 3; host_index++) {
if (host_index != contestant_index) {
host_count--;
}
if (host_count < 0) {
break;
}
}
if (contestant_will_switch_doors) {
return vec[3- contestant_index - host_index] == prize... 阅读全帖 |
|
|
b*******e
发帖数: 123 | 17 来自主题: JobHunting版 - 上一道小题 10 不是palinedrome. 第一个可以用try and error once...
Full code 太烦了。。
vector getall(int m, int n){
string nstr = to_string(n);
vector res;
function func = [](string s,bool addone){
int isodd = s.size() % 2;
int half = stoi(s.substr(0,(s.size()+1)/2));
string res = to_string(half+(addone?1:0));
string ires = res.substr(0,res.size()-isodd);
reverse(ires.begin(),ires.end());
res += ires;
if(res.size() > s.size()+1){
res = string(s... 阅读全帖 |
|
l***h
发帖数: 96 | 18 上上周五去MTV onsite的，这周一HR说HC已经过了，等这周EC省材料，下周给我消息。
希望不要在最后一步出啥问题吧。
电面题目：
一位国人大哥，先在这里谢过啦，时间刚好45分钟，吐槽下Google docs上写程序好蛋
疼，什么时候可以搞个可以支持Vim的编辑器吧。。。。
Assume some binary (each pixel is either black or white ) images, have same
width and height, and the length is power of 2. Present it by quadtree:
divide the image into quarters, each quarter can be all back, all white or
mixed, subdivide the mixed ones… recurse.
+-------+---+---+
| | F | F |
| T +---+---+
| | T | T |
+---+---+---+---+
| F ... 阅读全帖 |
|
s********u
发帖数: 1109 | 19 struct Line{
double slope;
double intercept;
Line(Point p, Point q){
if(p.x == q.x){
slope = numeric_limits::max();
intercept = p.x;
}else{
slope = (double)(p.y - q.y)/(double)(p.x - q.x);
intercept = p.y - slope * p.x;
}
}
};
struct Comp{
static double eps;
bool operator()( const Line &l1, const Line &l2){
if( l1.slope - l2.slope < -eps )
... 阅读全帖 |
|
b*****a
发帖数: 70 | 20 These two are very good book for improving your skills in C++. Strongly
recommend it if you want to enhance your C++ ability.
The authors of EPI also applied lots of concepts from "Effective C++" and "
Effective STL" in EPI. For example, they use deque instead of vector<
bool>, which is item 18 from Effective STL, and the extensively usage of
smart pointers, which came from Effective C++. Those features are good
things to learn. Therefore, I think EPI is a good C++ interview book to
study. |
|
C****y
发帖数: 77 | 21 Last executed input: "eegiicgaeadbcfacfhifdbiehbgejcaeggcgbahfcajfhjjdgj"
但是offline测试是通过了，研究了半天没找出来为何。
求大神指点。
Code:
class Solution {
public:
int minCut(string s) {
int len = s.length();
vector dp(len, len);
for (int i = 0; i < len; i++) {
dp[i] = i;
}
vector > pM(len, vector(len, false));
for (int l = 1; l < len + 1; l++) {
for (int i = 0; i < len; i++) {
int j = i + l -1;
... 阅读全帖 |
|
y***1
发帖数: 18 | 22 这是我当时写的
bool BST_Helper(TreeNode* root, int low, int high)
{
if(!root) return true;
if(root->val >= low && root->val <= high)
return BST_Helper(root->left, low, root->val)
&& BST_Helper(root->right, root->val+1, high);
else return false;
}
bool isValidBST2(TreeNode* root)
{
if(!root) return true;
return BST_Helper(root, INT_MIN, INT_MAX);
}
你走一下root->val = INT_MAX, root->right 非空就会有overflow |
|
D****t
发帖数: 17 | 23 没有那么简单，所以是你弱 :-)
bool IsLastOneByteChar(unsigned char * bytes, int len)
{
int leadCount = 0;
len--;
bool lastByteIsLead = bytes[len] & 0x80;
while(len > 0)
{
if (bytes[len] & 0x80) leadCount++;
if (!(bytes[len] & 0x80)) break;
}
if (leadCount/2 == 0)
{
if (lastByteIsLead)
return true; //second byte of a 2-byte char
else
return false; //single byte char;
}
else
{
if (lastByteIsLead)
... 阅读全帖 |
|
f**********t
发帖数: 1001 | 24 // 一个deque，但是只支持pushBack，pushFront，popBack， 没有popFront
// 给一个1-N的排列，问能否把1-N按照从小到大的顺序push到deque，pop的时机可以
任选
// ，使得pop出的顺序刚好是给定的排列
// 比如： 给定 23145， 那么对12345对应的操作序列是pushBack，pushBack，
popBack，
// pushBack，popBack，popBack，pushBack，popBack，pushBack，popBack
// 要求如果可能，输出任意一个可能的操作序列，如果没有可能的操作序列，输出
// impossible
bool OpSequense(vector vi) {
deque dq;
size_t cur = 0;
vector indexes(vi.size() + 1);
for (size_t i = 0; i < vi.size(); ++i) {
indexes[vi[i]] = i;
}
for (int i =... 阅读全帖 |
|
a***e
发帖数: 413 | 25 请教leetcode上的那道Word Break II
Given a string s and a dictionary of words dict, add spaces in s to
construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
http://oj.leetcode.com/problems/word-break-ii/
Can anyone tell me why the following code generated Memory Limit Exceeded? I
tested it in VS for that catsanddog string, whic... 阅读全帖 |
|
f******n
发帖数: 53 | 26 来自主题: JobHunting版 - M的面试题 如果是考虑多种组合，显然是DP算法。
构建dp[s.length][s.length]
根据dict设置dp[i][j] = 1 其中s[i...j]可以在dict中找到
dp每行会有多个1
根据ilovethisgame的静态算法如下
显示的a[i] 为每个word的第一个字母位置
void printpath (int a[13])
{
for (int i = 0; i < 13; i++)
printf("%d ", a[i]);
printf("n");
}
bool findAllPath(int dp[13][13], int a[13], int s, int e)
{
if (dp[s][e] == 1)
{
a[s]=1;
printpath(a);
return true;
}
int i = s;
bool found = false;
while (i <= e)
{
if (dp[s][i] == 1)
... 阅读全帖 |
|
H*********a
发帖数: 34 | 27 我也发一个想法，从string的第2位开始扫（为了保证那个子string的长度为2），当前
位的char和string首char一样的时候，就以首位到当前位的子string为模型，匹配后面
的相隔同等位置，同等长度的子string。这个方法不能处理"aaaaaaaaaa"，因为认为这
是"aaaaa"乘以2。
bool check(int l, int n, string s) {
if (n % l != 0)
return false;
for (int j = 1; j < n/l; j++) {
if (s.substr(0, l) != s.substr(j*l, l))
return false;
}
return true;
}
bool isMultiple(string s) {
int n = s.size();
if (n <= 3)
return false;
for (int i = 2; i <= n/2; i++) {
... 阅读全帖 |
|
H*********a
发帖数: 34 | 28 我也发一个想法，从string的第2位开始扫（为了保证那个子string的长度为2），当前
位的char和string首char一样的时候，就以首位到当前位的子string为模型，匹配后面
的相隔同等位置，同等长度的子string。这个方法不能处理"aaaaaaaaaa"，因为认为这
是"aaaaa"乘以2。
bool check(int l, int n, string s) {
if (n % l != 0)
return false;
for (int j = 1; j < n/l; j++) {
if (s.substr(0, l) != s.substr(j*l, l))
return false;
}
return true;
}
bool isMultiple(string s) {
int n = s.size();
if (n <= 3)
return false;
for (int i = 2; i <= n/2; i++) {
... 阅读全帖 |
|
l********e
发帖数: 3 | 29 这是我的思路，
1）假设输入字符串是s1, 长度为 N, 我们要找的重复的短字符串为result
2）一开始把result 设成s1的前两个字符。
3）引入两个索引变量i,j，i指向s1的字符，j指向result的字符。i=2, j=0
4）检查 s1[i] == result[j]，如果成立，则j++；否则的话说明出现了mismatch,说明
result可能太短，需要扩展。扩展的字符应该是 s1[i-j,i],把这个扩展追加到result,
并且把j设置成0。
5)循环结束后检查result的长度和j是否相等，如果相等的话说明满足要求。当然还要
进一步确定result.size() == s1.size()，如果相等说名没有重复，返回false。
以下是不太严谨的的代码，
#include
#include
#include
#include
using namespace std;
bool isRepeated(string s1) {
size_t N = s1.size();
strin... 阅读全帖 |
|
l********e
发帖数: 3 | 30 这是我的思路，
1）假设输入字符串是s1, 长度为 N, 我们要找的重复的短字符串为result
2）一开始把result 设成s1的前两个字符。
3）引入两个索引变量i,j，i指向s1的字符，j指向result的字符。i=2, j=0
4）检查 s1[i] == result[j]，如果成立，则j++；否则的话说明出现了mismatch,说明
result可能太短，需要扩展。扩展的字符应该是 s1[i-j,i],把这个扩展追加到result,
并且把j设置成0。
5)循环结束后检查result的长度和j是否相等，如果相等的话说明满足要求。当然还要
进一步确定result.size() == s1.size()，如果相等说名没有重复，返回false。
以下是不太严谨的的代码，
#include
#include
#include
#include
using namespace std;
bool isRepeated(string s1) {
size_t N = s1.size();
strin... 阅读全帖 |
|
l********e
发帖数: 3 | 31 这是我的思路，
1）假设输入字符串是s1, 长度为 N, 我们要找的重复的短字符串为result
2）一开始把result 设成s1的前两个字符。
3）引入两个索引变量i,j，i指向s1的字符，j指向result的字符。i=2, j=0
4）检查 s1[i] == result[j]，如果成立，则j++；否则的话说明出现了mismatch,说明
result可能太短，需要扩展。扩展的字符应该是 s1[i-j,i],把这个扩展追加到result,
并且把j设置成0。
5)循环结束后检查result的长度和j是否相等，如果相等的话说明满足要求。当然还要
进一步确定result.size() == s1.size()，如果相等说名没有重复，返回false。
以下是不太严谨的的代码，
#include
#include
#include
#include
using namespace std;
bool isRepeated(string s1) {
size_t N = s1.size();
strin... 阅读全帖 |
|
w********s
发帖数: 1570 | 32 bool next_permutate(std::vector& numbers)
{
int length = numbers.size();
if (length < 2) return false;
bool found = false;
int i = length - 1;
int j = length - 2;
while(!found && j >= 0)
{
int n1 = numbers[i];
int n2 = numbers[j];
if (n1 > n2)
{
found = true;
int k = i + 1;
while (k <= length - 1 && n2 < numbers[k])
{
++k;
}
//swap k+ 1, j
... 阅读全帖 |
|
h****n
发帖数: 1093 | 33 bool wordBreak(string s, unordered_set &dict) {
int N = s.size();
vector dp(N+1, false);
dp[0] = true;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= i; j++) {
if (dp[i-j] && (dict.find(s.substr(i-j, j)) != dict.end())) {
dp[i] = true;
break;
}
}
return dp[N];
} |
|
s******d
发帖数: 424 | 34 bool wordBreak(string s, unordered_set &dict) {
vector f(s.size() + 1, false);
f[0] = true;
for (int i = 1; i <= s.size(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
f[i] = true;
break;
}
}
}
return f[s.size()];
} |
|
f******h
发帖数: 45 | 35 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
j****z
发帖数: 13 | 36 是不是可以这么写
void sort(int ind, vector>& graph, vector& result, vector
& visited){
if(visited[ind])return;
visited[ind]=true;
for(auto i:graph[ind])
sort(i,graph,result,visited);
result.push_back(ind+'a');
}
void topocharacter(vector& in,vector& result){
vector> graph(26,vector());
for(int i=0;i
for(int j=0;in[i][j]&&in[i+1][j];j++)
if(in[i][j]!=in[i+1][j])
g... 阅读全帖 |
|
t**r
发帖数: 3428 | 37 这个解法好么？
1: bool isScramble(string s1, string s2) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: if(s1.size() != s2.size()) return false;
5: int A[26];
6: memset(A,0,26*sizeof(A[0]));
7: for(int i =0;i
8: {
9: A[s1[i]-'a']++;
10: }
11: for(int i =0;i
12: {
13: ... 阅读全帖 |
|
l*********8
发帖数: 4642 | 38 int maxConsecutive(const vector & ary) {
int changed[2] = {0, 0};
int noChange[2] = {0, 0};
int maxL = 0;
for (bool x : ary) {
maxL = max(maxL, ++changed[x]);
maxL = max(maxL, ++noChange[x]);
changed[1-x] = noChange[1-x];
noChange[1-x] = 0;
}
return maxL;
}
0 |
|
l*********8
发帖数: 4642 | 39 写错了， 谢谢指出。
loop 里面第三行少了个 加1
int maxConsecutive(const vector & ary) {
int changed[2] = {0, 0};
int noChange[2] = {0, 0};
int maxL = 0;
for (bool x : ary) {
maxL = max(maxL, ++changed[x]);
maxL = max(maxL, ++noChange[x]);
changed[1-x] = 1 + noChange[1-x];
noChange[1-x] = 0;
}
return maxL;
} |
|
l*********8
发帖数: 4642 | 40 赞！
还是出bug啊，
改正了：
int maxConsecutive(const vector & ary) {
int changed[2] = {0, 0};
int noChange[2] = {0, 0};
int maxL = 0;
for (bool x : ary) {
++changed[x];
++noChange[x];
changed[1-x] = 1 + noChange[1-x];
noChange[1-x] = 0;
maxL = max(maxL, changed[x]);
maxL = max(maxL, changed[1-x]);
}
return maxL;
} |
|
R******9
发帖数: 267 | 41 first print the left boundary, then all the leaves, and the right boundary.
1
2 3
4 5 6
7 8 9
should be 1 2 4 7 8 9 6 3.
void traverse(Node* root, bool left_most, bool right_most)
{
if (!root) return; // bottom condition
if (left_most) cout << root->val << ' '; //先序打印左边界
traverse(root->left, left_most, false);
if (!root->left && !root->right && !left_most && !right_most) cout <<
root->val << ' '; //中叙打印叶子
tr... 阅读全帖 |
|
l*********8
发帖数: 4642 | 42 left_most, right_most这个思路不错，学习了。
还可以简化一下：
void traverse(TreeNode * root, bool leftMost = true, bool rightMost = true) {
if (!root) return;
if (leftMost || (!rightMost && !root->left && !root->right))
print(root);
traverse(root->left, leftMost, false);
tarverse(root->right, false, rightMost);
if (rightMost && !leftMost)
print(root);
} |
|
c*******y
发帖数: 98 | 43 DP好难，我来贴个无脑的，不知道题目理解对了没有。。
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int findMaxAllOneTopLeftSquare(vector>& matrix)
{
int i, j;
int m = matrix.size(); if (!m) return 0;
int n = matrix[0].size(); if (!n) return 0;
int max = min(m, n);
for (i=0; i
for (j=0; j<=i; j++){
if (matri... 阅读全帖 |
|
f**********t
发帖数: 1001 | 44 来自主题: JobHunting版 - 一道在线题 int numVisible(TreeNode *root) {
vector sk;
vector visited;
int res = 0;
while (!sk.empty() || root) {
while (root) {
bool biggest = true;
for (auto p : sk) {
if (p->val > root->val) {
biggest = false;
}
}
if (biggest) {
++res;
}
sk.push_back(root);
visited.push_back(false);
root = root->left;
} //while
if (visited.back() == true) {
visited.pop_back();
sk.pop_back();... 阅读全帖 |
|
Z**********4
发帖数: 528 | 45 session 1一个class {int a, bool c, int b} 里面每个variable所占的空间都不同
，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
或者16bytes。都是2的次方就是。
问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
费。
比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
时候就会浪费一些空间。
所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
object。
其实这个就是用排序，然后从大的变量依次放进block。
有个followup的问题就是：因为我不想过多移动这些变量，所以怎么才能设计一个算法
所需要移动的object最少。
比如如果变量的size一次是4, 4, 1, 1, 8, 8, 1, 1最好的排法是4, 4, 8, 8, 1, 1,
1, 1.而不是8 8 4 4 1 1 1 1因为前一种所需要移动的cost最小。这个没想出来了。。
应该用divide... 阅读全帖 |
|
|
a***e
发帖数: 413 | 47 还有类似的题
https://oj.leetcode.com/problems/wildcard-matching/
我写的这种TLE，请问怎么计算这种recursion的复杂度啊？
bool isMatch(const char *s, const char *p) {
if (*p=='\0')
return (*s=='\0');
if (*p!='*')
{
if (*s==*p&&*s!='\0'||*p=='?')
{
s++;
p++;
return isMatch(s,p);
}
else
return false;
}
else
{
while(*p=='*')
p++;
... 阅读全帖 |
|
a*****p
发帖数: 1285 | 48 如果不用额外的space，比如不转成string／char［］，下面这个能再java上实现么？
这个是leetcode上的检查一个整数是不是palindromic的。下面是c++的版本，java上变
量好像用户不直接控制stack space？
bool isPalindrome(int x, int &y) {
if (x < 0) return false;
if (x == 0) return true;
if (isPalindrome(x/10, y) && (x%10 == y%10)) {
y /= 10;
return true;
} else {
return false;
}
}
bool isPalindrome(int x) {
return isPalindrome(x, x);
} |
|
s*i
发帖数: 5025 | 49 recursive的话，下面这个解法更简洁些。
bool isSymmetric(Node n)
{
return isMirror(n, n);
}
bool isMirrow(Node left, Node right)
{
if(left == null && right == null) return true;
if(left == null || right == null) return false;
if(left.val != right.val) return false;
if(!isMirrow(left.left, right.right)) return false;
if(!isMirrow(left.right, right.left)) return false;
return true;
} |
|
l****s
发帖数: 75 | 50 We only need to consider lower case
"bob" // is a palindrome
"a man, a plan, a canal, panama!" // is a palindrome
".374" // is a palindrome
" ;" // is a palindrome
bool isAlpha(char c); //provided
bool isPalindrome(const string & s)
{
if (s.empty()) return true;
int i = 0;
int j = s.size() - 1;
while (i < j)
{
while (!isAlpha(s[i]) && i < j)
{
++i;
}
// i == s.size() - 1;
while (!isAlpha(s[j]) && j > i)
{
... 阅读全帖 |
|
