第一题
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if( head == NULL) return false;
ListNode *slow = head;
ListNode *fast = head;
while(fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) return true;
}
return false;
}
};
第二题
二分查找
int searchInsert(int A[], int n, int target) {
int low = 0, high = n - 1;
int mid=0;
while (low <= high) {
mid = low + (high - low) / 2;
if (A[mid] == target) return mid;
else if (A[mid] < target) low = mid + 1;
else high = mid - 1;
}
return low;
}
class Solution {
public:
int uniquePaths(int m, int n) {
int a[m][n];
a[0][0] = 1;
a[0][1] = 1, a[1][0] = 1;
a[1][1] = 2;
for(int j= 0;j<n;j++) a[0][j] =1;
for(int i=0;i<m;i++) a[i][0] = 1;
for(int i = 1;i < m; i++) {
for(int j = 1; j < n; j++) {
a[i][j] = a[i-1][j] + a[i][j-1];
}
}
return a[m-1][n-1];
}
};
class Solution {
public:
void sortColors(int A[], int n) {
int zero = 0,two=n-1;
for(int i=0;i<n;i++)
{
while(i<two && A[i]==2) swap(A[i],A[two--]);
while(i>zero && A[i]==0) swap(A[i],A[zero++]);
}
}
};
第五题
二叉树的中序遍历的非递归形式
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> v;
if(root == NULL) return v;
TreeNode *p = root;
stack<TreeNode*> stk;
while(p ||!stk.empty()) {
if(p) {
stk.push(p);
p = p->left;
}else {
p = stk.top();
stk.pop();
v.push_back(p->val);
p = p->right;
}
}
return v;
}
};
(层序遍历的应用)
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root == nullptr) return;
queue<TreeLinkNode*> q;
TreeLinkNode* temp,*tail = root;
q.push(root);
while(!q.empty()) {
temp = q.front();
q.pop();
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
if(temp == tail) {
temp->next = nullptr;
tail = q.back();
}
else {
temp->next = q.front();
}
}
}
};
- 递归写法
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
if(!root) return false;
if(root->left == NULL && root->right == NULL && sum - root->val == 0)
return true;
return hasPathSum(root->left,sum - root->val) || hasPathSum(root->right,sum - root->val);
}
};
- 非递归写法
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
if(!root) return false;
queue<TreeNode*> q;
queue<int> sum_q;
q.push(root);
sum_q.push(root->val);
while(!q.empty()) {
TreeNode* cur = q.front();
q.pop();
int temp = sum_q.front();
sum_q.pop();
if(cur->left==nullptr && cur->right ==nullptr && temp==sum) {
return true;
}
if(cur->left) {
q.push(cur->left);
sum_q.push(temp+cur->left->val);
}
if(cur->right) {
q.push(cur->right);
sum_q.push(temp+cur->right->val);
}
}
return false;
}
};
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null) return true;
if(p==null||q==null) return false;
if(p.val!=q.val) return false;
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
第九题 二叉树的先序遍历（非递归实现）
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.*;
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> al = new ArrayList<Integer>();
if(root == null) return al;
Stack<TreeNode> s = new Stack<TreeNode>();
s.push(root);
while(!s.empty()) {
TreeNode temp = s.pop();
al.add(temp.val);
if(temp.right!=null) s.push(temp.right);
if(temp.left!=null) s.push(temp.left);
}
return al;
}
}
