5.Move Zeroes
Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note: You must do this in-place without making a copy of the array. Minimize the total number of operations.
Analysis
空间压缩，并且要求是0的元素到最后去，而非0的元素的顺序不变。
并且不能开辟新空间，只用交换顺序来完成。
思路，先找0值，如果是0那么就找下一个非0值来交换，并且让空位变成0。
要操作数最少，那么需要保存每次找到了非0值的位置，下次依然接着寻找，这样交换的次数是最少的
Solution-C/C++
void moveZeroes(int* nums, int numsSize)
{
int i = 0, j = 0;
for (i = 0; i<numsSize; i++)
if (nums[i] == 0)
//寻找下一个非0值，进行交换，0的个数增加
for (j = i + 1; j<numsSize; j++)
if (nums[j] != 0)
{
nums[i] = nums[j];
nums[j] = 0;
break;
}
}
Solution-Python
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i = 0
j = 0
for i in range(i, len(nums)) :
if (nums[i] == 0) :
j = i + 1
for j in range(j, len(nums)) :
if (nums[j] != 0) :
nums[i] = nums[j]
nums[j] = 0
break
6.Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
Analysis
检测两个二叉树是不是相同的子树.
这里认为镜面对称的二叉树是不同子树.
- 如果相同位置节点都存在且值相等,该位置对称
- 如果相同位置节点都不存在,对称
- 非以上两种情况,不对称
Solution-C/C++
递归
class Solution
{
public:
bool isSameTree(TreeNode* p, TreeNode* q)
{
if(p&&q&&p->val==q->val)
{
return isSameTree(p->left,q->left)&isSameTree(p->right,q->right);
}
else if(p==NULL&&q==NULL)
{
return true;
}
else
return false;
}
};
如果要判断是否镜像对称,可以在返回的地方加上判断镜像的部分
//如果加上下面的判断，就是对称相等也算相同
return isSameTree(p->left,q->left)&isSameTree(p->right,q->right)
||isSameTree(p->left,q->right)&isSameTree(p->right,q->left);
迭代
用迭代的方法，那么就是简单的左右子树相比较，但是需要一个容器用来存储上一次比较的地方，队列就可以了
class Solution
{
public:
bool isSameTree(TreeNode* p, TreeNode* q)
{
queue<TreeNode*> ptemp;
queue<TreeNode*> qtemp;
while(1)
{
if(p==NULL && q==NULL)
{
//从队列中获得上一个分支，再进行比较
//如果分支为空，那么直接返回true
if(ptemp.empty() && qtemp.empty() )
return true;
else
{
p=ptemp.front();
ptemp.pop();
q=qtemp.front();
qtemp.pop();
}
}
if((p==NULL && q!=NULL)||(p!=NULL && q==NULL)||(p->val!=q->val))
return false;
if(p->left!=NULL&&q->left!=NULL)
{
if(p->right!=NULL&&q->right!=NULL)
{
ptemp.push(p->right);
qtemp.push(q->right);
//把分支加入队列
}
else if((p->right==NULL&&q->right!=NULL)||(p->right!=NULL&&q->right==NULL))
return false;
p=p->left;
q=q->left;
}
else if((p->left==NULL&&q->left!=NULL)||(p->left!=NULL&&q->left==NULL))
return false;
else
{
if((p->right==NULL&&q->right!=NULL)||(p->right!=NULL&&q->right==NULL))
return false;
else if(p->right!=NULL&&q->right!=NULL)
{
p=p->right;
q=q->right;
continue;
}
if(p->right==NULL&&q->right==NULL)
{
if(ptemp.empty() && qtemp.empty() )
return true;
else
{
p=ptemp.front();
ptemp.pop();
q=qtemp.front();
qtemp.pop();
}
}
}
}
}
};
2017年2月20日 17:20:00
上面这是第一次写的,判断逻辑太罗嗦了.
其实逻辑应该很简单:
- 从队列中取出节点,判断是否为空,全为空,继续循环
- 判断节点是否都存在,都存在情况下是否值相等,都相等,则取出其左右节点放入队列中
- 不相等的话说明,两树不等,返回false
class Solution
{
public:
bool isSameTree(TreeNode* p, TreeNode* q)
{
//if(!q&&!p)
// return true;
queue<TreeNode*> qq;
queue<TreeNode*> pq;
qq.push(q);
pq.push(p);
while(!qq.empty() && !pq.empty())
{
TreeNode* curq=qq.front();
TreeNode* curp=pq.front();
qq.pop();
pq.pop();
if(curq==NULL&&curp==NULL)
continue;
if((curq&&curp)&&(curq->val==curp->val))
{
qq.push(curq->left);
qq.push(curq->right);
pq.push(curp->left);
pq.push(curp->right);
continue;
}
else
{
return false;
}
}
return true;
}
};
Solution-Python
递归
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if not((p and q and p.val==q.val)or(p==None and q==None)):
return False
if (p==None and q==None) :
return True
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
//如果加上下面的判断，就是对称相等也算相同
//or (self.isSameTree(p->left,q->right) and self.isSameTree(p->right,q->left))
才发现，python的class中递归自身需要前置self，不然就会提示没找到
2017年2月20日 17:30:34 第二遍写
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if (p and q and p.val==q.val):
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
elif(p==None and q==None):
return True;
else:
return False;
迭代
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
ptemp=[];
qtemp=[];
while 1 :
if(p==None and q==None):
if(ptemp==[] and qtemp==[]):
return True;
else:
p=ptemp[0]
ptemp.remove(ptemp[0])
q=qtemp[0]
qtemp.remove(qtemp[0])
if(p==None and q!=None)or(p!=None and q==None)or(p.val!=q.val):
return False
if(p.left!=None and q.left!=None):
if(p.right!=None and q.right!=None):
ptemp.append(p.right)
qtemp.append(q.right)
elif(p.right==None and q.right!=None)or(p.right!=None and q.right==None):
return False
p=p.left
q=q.left
elif (p.left==None and q.left!=None)or(p.left!=None and q.left==None):
return False
else:
if(p.right!=None and q.right!=None):
p=p.right
q=q.right
continue
elif(p.right==None and q.right!=None)or(p.right!=None and q.right==None):
return False
else:
if(ptemp==[] and qtemp==[]):
return True;
else:
p=ptemp[0]
ptemp.remove(ptemp[0])
q=qtemp[0]
qtemp.remove(qtemp[0])
2017年2月20日 17:44:33 第二次写
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
qq=[]
pq=[]
qq.append(q)
pq.append(p)
while not(qq==[]) and not(pq==[]):
curq=qq[0]
curp=pq[0]
qq.remove(qq[0])
pq.remove(pq[0])
if(curq==None and curp==None):
continue;
if(curq!=None and curp!=None)and(curq.val==curp.val):
qq.append(curq.left)
qq.append(curq.right)
pq.append(curp.left)
pq.append(curp.right)
else:
return False
return True
7.Invert Binary Tree
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia: This problem was inspired by this original tweet by Max Howell: Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
7.Analysis
就是要翻转二叉树，用递归就是遍历到最后一个节点然后开始依次往上翻转，并且是做节点的交换，而不是值的交换（值交换，需要判读空的情况，并且新建节点，而且值交换的情况下，需要左右大子树交换的时候就很麻烦了，必须得用节点交换才比较方便）
7.Solution-C/C++
递归
递归思路：首先找到左右子树最下面的叶子节点，然后由叶子节点开始交换位置，并且依次往上进行
class Solution
{
public:
TreeNode* invertTree(TreeNode* root)
{
TreeNode* temp;
if(root==NULL)
return NULL;
invertTree(root->left);
invertTree(root->right);
temp=root->left;
root->left=root->right;
root->right=temp;
return root;
}
};
迭代
非递归就需要挨个遍历一遍，依次交换.
我是用自上而下的遍历方法：
1.先把第一个根进行左右交换
2.判断根的左是否为空，右是否为空，都不为空，就把右存起来，如果左空，右不空，就用右作为根继续遍历
3.左右都为空的情况下，检查存储区是否有内容，有就拿来做为根，没有就是整个遍历结束了
class Solution
{
public:
TreeNode* invertTree(TreeNode* root)
{
TreeNode* temp;
TreeNode* tmproot=root;
if(root==NULL)
return NULL;
stack<TreeNode*>store;
while(1)
{
temp=tmproot->left;
tmproot->left=tmproot->right;
tmproot->right=temp;
if(tmproot->left!=NULL)
{
if(tmproot->right!=NULL)
store.push(tmproot->right);
tmproot=tmproot->left;
}
else
{
if(tmproot->right!=NULL)
{
tmproot=tmproot->right;
continue;
}
if(store.empty())
return root;
tmproot=store.top();
store.pop();
}
}
}
};
2017年2月20日 18:17:15
第二次重写,思路更加清晰明确
- 加入队列
- 取队列头,不为空,交换左右
- 不为空,把左右节点加入队列,循环
class Solution
{
public:
TreeNode* invertTree(TreeNode* root)
{
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
TreeNode* cur=q.front();
q.pop();
if(cur!=NULL)
{
TreeNode* temp;
q.push(cur->left);
q.push(cur->right);
temp=cur->left;
cur->left=cur->right;
cur->right=temp;
}
}
return root;
}
};
Solution-Python
递归
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root==None:
return None;
self.invertTree(root.left)
self.invertTree(root.right)
temp=root.left
root.left=root.right
root.right=temp
return root
迭代
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
store=[]
store.append(root)
while len(store)!=0:
cur=store[0];
store.remove(store[0]);
if(cur!=None):
store.append(cur.left)
store.append(cur.right)
temp=cur.left
cur.left=cur.right
cur.right=temp
return root;
8.Valid Anagram
Given two strings s and t, write a function to determine if t is an anagram of s.
For example, s = “anagram”, t = “nagaram”, return true. s = “rat”, t = “car”, return false.
Note: You may assume the string contains only lowercase alphabets.
Analysis
关键在于anagram这个词，意思是相同字母但是改变了顺序，而不是逆序。
想到两个方法
- 从s中依次取一个字母，然后去t中查找，找到后删除，如果最后没剩余，则是ok的
- 提前预备好26个字母，然后遍历s和t将其所含字母对应数组内容依此加一/减一，最后检测一次求数组总和，总和为0，则是ok的否则就是错的
想想看那个用的时间更少，第一种方法则是s/t越大，需要消耗时间更多。第二种方法则耗时更少一些
百度了一下还看到一种思路，直接字母排序判等，这种貌似也可以，但是考虑时间的消耗当然是计数的方法最好只需要一遍就ok。（字母排序并不够稳定，耗时也很多）
Solution-C/C++
c用计数的方法来完成
bool isAnagram(char* s, char* t)
{
int num[26],i;
for(i=0;i<26;i++)
num[i]=0;
if(s==t&&s==NULL)
return true;
while(*s)
{
num[(int)(*s-'a')]++;
s++;
}
while(*t)
{
num[(int)(*t-'a')]--;
t++;
}
for(i=0;i<26;i++)
if(num[i]!=0)
return false;
return true;
}
Solution-Python
python就用第三种排序的方法来解决这个问题 python的list有自带的排序功能比较好用，而c没有，c++就要用STL库的容器来弄。虽然python也需要转换一下容器。
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
lists = list(s)
listt = list(t)
lists.sort()
listt.sort()
if(lists==listt):
return True
else:
return False
当然这里也学习了一次如何把list和string相互转换
>>> import string
>>> str = 'abcde'
>>> list = list(str)
>>> list
['a', 'b', 'c', 'd', 'e']
>>> str
'abcde'
>>> str_convert = ''.join(list)
>>> str_convert
'abcde'
>>>
Quote
http://segmentfault.com/a/1190000003768716
http://www.linuxidc.com/Linux/2015-01/111637.htm
http://blog.devtang.com/blog/2015/06/16/talk-about-tech-interview/
http://piziyin.blog.51cto.com/2391349/568426
http://www.cnblogs.com/ganganloveu/p/4694703.html