leetcode刷题记录(1)

第一题

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();
            }
        }
    }
};

第七题

1. 递归写法

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);
    }
};

2. 非递归写法

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;
    }
};

第八题（（。－_－。），写指针写烦了，换java）

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;
    }
}