1、Single Number:Given an array of integers, every element appears twice except for one. Find that single one.
异或,不仅能处理两次的情况,只要出现偶数次,都可以清零。

int singleNumber(int A[], int n) 
{
    // 数字范围不清楚,bitmap失败
    int x=0;
    for(size_t i=0;i<n;++i)
        x^=A[i];
    return x;
}

2、Maximum Depth of Binary Tree:Given a binary tree, find its maximum depth.The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
递归求解左右子树。

int maxDepth(TreeNode *root) 
{
    if(root==NULL)
        return 0;
    else
        return max(maxDepth(root->left),maxDepth(root->right))+1;
}

3、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.
递归版:

bool isSameTree(TreeNode *p, TreeNode *q) 
{
    if(!p && !q)        
        return true;
    if(!p || !q)
        return false;
    return p->val==q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

迭代版:

stack<TreeNode*> s;
s.push(p);
s.push(q);
while(!s.empty())
    {
        p=s.top();s.pop();
        q=s.top();s.pop();
        if(!p && !q) continue;
        if(!p || !q) return false;
        if(p->val !=q->val) return false;
        s.push(p->left);
        s.push(q->left);
        s.push(p->right);
        s.push(q->right);
    }
return true;

4、Reverse Integer:Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321

// 1、char存储字符ASCII码,0->48(...)
// 2、10,100(...)
// 3、overflow(?) atoi处理范围(X)
// 4、__int64->int(X)
int reverse(int x) 
{
    __int64 r = 0;
    for (; x; x /= 10)
        r = r * 10 + x % 10;
    return r;
}

最终没有AC(Ex.1534236469),实际结果r是正确的,在__int64->int过程中溢出了,对于返回值为int的无解(int:-2^31~2^31-1),但是看到网上有Java AC的


5、Best Time to Buy and Sell Stock II:Say you have an array for which the ith element is the price of a given stock on day i.Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
(1)、贪心算法:高价卖出,低价买入
(2)、把原始价格序列变成差分序列,本题也可以做是最大m 子段和,m = 数组长度(不要求连续!)。

int maxProfit(vector<int> &prices) 
{
    int sum=0;
    for(int i=1;i<prices.size();++i)
    {
        int tmp=prices[i]-prices[i-1];
        if(tmp>0)
            sum+=tmp;
    }
    return sum;
}

6、Unique Binary Search Trees:Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
思路1:卡特兰数,n个结点的二叉树有Cn=(2n)!/((n+1)!*n!)种形式;(难点:阶乘溢出!
思路2:一维动态规划问题,

f(i) =Σf(k-1)*f(i-k)(1=<k<=i)
f(0)=1
f(1)=1
---------------------------------------------------
int numTrees(int n) 
{
    vector<int> f(n + 1, 0);
    f[0] = 1;
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int k = 1; k <= i; ++k)
            f[i] += f[k-1] * f[i - k];
    }
    return f[n];
}

f(i)表示含有i个结点时数的个数,Σf(k-1)*f(i-k)(1=<k<=i)将原问题规模i,分解成左右子树形式,减少规模!

7、Linked List Cycle:Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
判断链表是否有环:第一想法-快慢指针;

bool hasCycle(ListNode *head) 
{
    ListNode *p1=head;
    ListNode *p2=head;
    while(p1 && p2->next)
    {
        p1=p1->next;
        p2=p2->next->next;
        if(p1==p2)
            return true;
    }
    if(p2->next==NULL)
        return false;
}

8、Binary Tree Preorder Traversal:Given a binary tree, return the preorder traversal of its nodes' values.
递归方式

vector<int> order;
vector<int> preorderTraversal(TreeNode *root) 
{
    if(root)
    {
        order.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        
    }
    return order;
}

栈方式

vector<int> preorderTraversal(TreeNode *root) 
{
    vector<int> result;        
    const TreeNode *p;
    stack<const TreeNode*> s;
    p=root;
    if(p)
        s.push(p);

    while(!s.empty())
    {
        p=s.top();
        result.push_back(p->val);
        if(p->right)
            s.push(p->right);
        if(p->left)
            s.push(p->left);
    }
    return result;
}

Morris
Morris遍历方法过去都没听说过,这次长知识了!和线索二叉树有什么区别?利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点

vector<int> preorderTraversal(TreeNode *root) 
{
    vector<int> result;
    TreeNode *cur,*prev;
    cur=root;
    while(cur)
    {
        if(cur->left==NULL)
        {
            result.push_back(cur->val);
            prev=cur;
            cur=cur->right;
        }
        else
        {
            /* 查找前驱 */
            TreeNode *node=cur->left;
            while(node->right && node->right!=cur)
                node=node->right;

            if(node->right==NULL)
            {
                result.push_back(cur->val);
                node->right=cur;
                prev=cur;
                cur=cur->left;
            }
            else
            {
                node->right=NULL;
                cur=cur->right;
            }
        }
    }
    return result;
}


9、Binary Tree Inorder Traversal:Given a binary tree, return the inorder traversal of its nodes' values.
类似上题的先序遍历。
递归方式

vector<int> order;
vector<int> inorderTraversal(TreeNode *root) {
    if(root)
    {
        inorderTraversal(root->left);
        order.push_back(root->val);
        inorderTraversal(root->right);
    }
return order;
}

栈方式:

vector<int> inorderTraversal(TreeNode *root) 
{
    vector<int> result;
    stack<const TreeNode*> s;
    const TreeNode *p=root;

    while(!s.empty()||p)
    {
        if(p)
        {
            s.push(p);
            p=p->left;
        }
        else
        {
            p = s.top();        // 取栈顶、并不出栈
            s.pop();
            result.push_back(p->val);
            p = p->right;
        }
    }
    return result;
}

10、Populating Next Right Pointers in Each Node

struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
递归:

void connect(TreeLinkNode *root) 
{
    if(root==NULL)
        return;
    TreeLinkNode t(-1);
    for(TreeLinkNode* curr=root,*prev=&t;curr;curr=curr->next)
    {
        if(curr->left)
        {
            prev->next=curr->left;
            prev=prev->next;
        }
        if(curr->right)
        {
            prev->next=curr->right;
            prev=prev->next;
        }
    }
    connect(t.next);
}

迭代:

void connect(TreeLinkNode *root) 
{
    while(root)
    {
        TreeLinkNode *next=NULL;
        TreeLinkNode *prev=NULL;
        for(;root;root=root->next)
        {
            if(!next)
                next=root->left?root->left:root->right;
            if(root->left)
            {
                if(prev)
                    prev->next=root->left;
                prev=root->left;
            }
            if(root->right)
            {
                if(prev)
                    prev->next=root->right;
                prev=root->right;
            }
        }
        root=next;
    }
}

11、Search Insert Position:Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
重点考虑时间复杂度:本质是查找
O(n):线性扫描

int searchInsert(int A[], int n, int target) 
{
    int i=0;
    while(i<n && A[i]<target)
        i++;
    return i;
}

O(logn):二分

int searchInsert(int A[], int n, int target) 
{
    return lower_bound(A,A+n,target)-A;
}

lower_bound:二分查找,[A,A+n)内查找目标,返回指针,减去A得下标位置!

12、Remove Duplicates from Sorted List:Given a sorted linked list, delete all duplicates such that each element appear only once.
非常常规的一道题,我在循环条件里纠结了好久:

while(p && p->next) -> while(p->next && p)
while(q && p->val==q->val) -> while(p->val==q->val && q)
// 注意:&&的短路条件,当p为null时,先判断p->next有错,因为p根本不存在!
ListNode *deleteDuplicates(ListNode *head)
{
    if(!head)
        return NULL;
    else
    {
        ListNode* p=head,*q=NULL,*s=NULL;
        while(p && p->next)
        {
            q=p->next;
            while(q && p->val==q->val)
            {
                s=q->next;
                free(q);
                q=s;
            }

            p->next=q;
            p=q;
        }
        return head;
    }
}


13、Maximum Subarray:Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
寻找最大子串,注意当最大子串为负数时依然能寻找出!
动态规划:
对数而言,要么属于之前序列,加入其中,要么舍弃,从它开始为新序列;
当之前序列和为正,对当前序列有益,为负则新建序列。


f[i]=max{f[i-1]+A[i],A[i]}   1<i<=n
target f[j]  1<=j<=n

f[i]表示以A[i]结尾时最大子串和,f[i]并不是全局最大,每次需要筛选max。

int maxSubArray(int A[], int n) 
{
    int result = INT_MIN, f = 0;
    for (int i = 0; i < n; ++i) 
    {
        f = max(f + A[i], A[i]);
        result = max(result, f);
    }
    return result;
}

原序列预处理:
(1)预处理:用数组sum[]存储前i项的总和;
(2)查找:curmin存储前i项最小和,每次迭代max(sum[i]-sum)的最大字段。

int maxSubArray(int A[], int n) 
{
    int i, result, cur_min;
    int *sum = new int[n + 1]; // 前n 项和
    sum[0] = 0;
    result = INT_MIN;
    cur_min = sum[0];
    for (i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + A[i - 1];
    }
    for (i = 1; i <= n; i++) {
        result = max(result, sum[i] - cur_min);
        cur_min = min(cur_min, sum[i]);
    }
    delete[] sum;
    return result;
}

14、Climbing Stairs:You are climbing a stair case. It takes n steps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

f(n)表示爬n个台阶的方法,为了爬到第n阶,可以从n-1阶爬一步,或者从n-2阶爬两步.
f(n)=f(n-1)+f(fn-2)
即,斐波那契数列

递归方法:超时
....
迭代:

int climbStairs(int n) 
{
    int a=1;
    int b=1;
    int tmp;
    if(n==0)
        return 0;
    else
    {
        for(int i=1;i<=n;++i)
        {
            tmp=a+b;
            a=b;
            b=tmp;
        }
        return a;
    }
}

通项公式:
QQ截图20141123155923.jpg

int climbStairs(int n) 
{
    const double s=sqrt(double(5));
    return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1))/s + 0.5);
}

15、Single Number II:Given an array of integers, every element appears three times except for one. Find that single one.
方法一:与操作,用数组int[sizeof(int)*8]存储遍历数组之后该位‘1’的个数,‘%3’操作之后将该数组组成新数。

int singleNumber(int A[], int n) 
{
    const int w=sizeof(int)*8;
    int count[w];                        // count[i]表示第i位出现1的次数    
    fill_n(&count[0],w,0);                // [count[0],w]赋值0

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<w;j++)
        {        
            count[j]+=(A[i]>>j)&1;        // 判断j位0或1
            count[j]%=3;
        }
    }
    int result=0;
    for(int i=0;i<w;i++)
        result+=(count[i]<<i);
    return result;
}

方法二:模拟三进制运算,‘one’该位出现1一次,‘two’该位出现1两次,当one 和two 中的某一位同时为1 时表示该二进制位上1 出现了3 次,此时需要清零。

int singleNumber(int A[], int n) 
{
    int one=0,two=0,three=0;
    for(int i=0;i<n;++i)
    {
        two|=(one&A[i]);
        one^=A[i];
        three=~(one&two);
        one&=three;
        two&=three;
    }
    return one;
}

16、Roman to Integer:Given a roman numeral, convert it to an integer.Input is guaranteed to be within the range from 1 to 3999.
罗马数字转为阿拉伯数字:掌握规则,右边比左边大,将该数加入总和,减去两倍的前一个数,否则直接加入。

int romanToInt(string s) {
       map<char,int> num;
    num['I']=1;
    num['V']=5;
    num['X']=10;
    num['L']=50;
    num['C']=100;
    num['D']=500;
    num['M']=1000;
    int sum=0;

    for(int i=0;i<s.length();++i)
        if(i>0 && num[s[i]]>num[s[i-1]])
            sum+=(num[s[i]]-2*num[s[i-1]]);
        else
            sum+=num[s[i]];
    return sum;
    }


17、Integer to Roman:Given an integer, convert it to a roman numeral.Input is guaranteed to be within the range from 1 to 3999.
不是太明白!

string intToRoman(int num) 
{
    const int radix[]={1000,900,500,400,100,90,50,40,10,9,5,4,1};
    const string symbol[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
    string str;
    for(int i=0;num>0;++i)
    {
        int count=num/radix[i];
        num%=radix[i];
        for(;count>0;--count)
            str+=symbol[i];
    }
    return str;
}

18、Merge Two Sorted Lists:Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
    ListNode *head=new ListNode(-1);
    ListNode *p=head,*p1=l1,*p2=l2;
    while(p1 && p2)
    {
        if(p1->val<p2->val)
        {
            p->next=p1;
            p=p->next;
            p1=p1->next;
        }
        else
        {
            p->next=p2;
            p=p->next;
            p2=p2->next;
        }
    }
    while(p1)
    {
        p->next=p1;
        p=p->next;
        p1=p1->next;
    }
    while(p2)
    {
        p->next=p2;
        p=p->next;
        p2=p2->next;
    }
    return head->next;
}

19、Convert Sorted Array to Binary Search Tree:Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
分治、二分

template<typename RandomAccessIterator>
TreeNode* sortedArrayToBST(RandomAccessIterator first,RandomAccessIterator last)
{
    const auto length=distance(first,last);
    if(length<=0)
        return NULL;
    auto mid=first+length/2;
    TreeNode *root=new TreeNode(*mid);
    root->left=sortedArrayToBST(first,mid);
    root->right=sortedArrayToBST(mid+1,last);
    return root;
}

TreeNode *sortedArrayToBST(vector<int> &num) 
{    
    return sortedArrayToBST(num.begin(),num.end());
}

20、Remove Element:Given an array and a value, remove all instances of that value in place and return the new length.The order of elements can be changed. It doesn't matter what you leave beyond the new length.
O(n*n):

int removeElement(int A[], int n, int elem)
{
    int i=n-1;
    while(i>=0)
    {
        if(A[i]==elem)
        {
            for(int j=i;j<n-1;j++)
                A[j]=A[j+1];
            n--;
        }
        i--;
    }
    return n;
}

O(n):

int removeElement(int A[], int n, int elem) 
{
    int index = 0;
    for (int i = 0; i < n; ++i) {
        if (A[i] != elem) {
            A[index++] = A[i];
        }
    }
    return index;
}

STL:

int removeElement(int A[], int n, int elem) 
{
    return distance(A, remove(A, A+n, elem));
}

21、Swap Nodes in Pairs:Given a linked list, swap every two adjacent nodes and return its head.For example,Given 1->2->3->4, you should return the list as 2->1->4->3.

ListNode *swapPairs(ListNode *head) 
{
    ListNode *p=head;
    int tmp;
    while(p&&p->next)
    {
        tmp=p->val;
        p->val=p->next->val;
        p->next->val=tmp;
        p=p->next->next;
    }
    return head;
}

22、Balanced Binary Tree:Given a binary tree, determine if it is height-balanced.For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
深度->判别是否平衡

// 求子树的深度
int balancedHeight(TreeNode *root)
{
    if(root==NULL)
        return 0;
    int left=balancedHeight(root->left);
    int right=balancedHeight(root->right);
    if(left<0 || right<0 || abs(left-right)>1)
        return -1;
    else
        return max(left,right)+1;
}

// 判断是否为平衡树
bool isBalanced(TreeNode *root) 
{
    return balancedHeight(root)>=0;
}

23、Gray Code:Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
(1)整数n转为格雷码n^(n/2)

unsigned int binary2gray(unsigned int n)
{
    return n^(n>>1);
}
vector<int> grayCode(int n) 
{
    vector<int> result;
    unsigned int size=1<<n;
    for(unsigned int i=0;i<size;++i)
        result.push_back(binary2gray(i));
    return result;
}

(2)递归方式

vector<int> grayCode(int n)
{
    vector<int> result;
    result.reserve(1<<n);
    result.push_back(0);
    for(int i=0;i<n;i++)
    {
        const int highest_bit=1<<i;
        for(int j=result.size()-1;j>=0;j--)
            result.push_back(highest_bit|result[j]);
    }
    return result;
}

24、Sort Colors:Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
(1)分析:本质是排序,0-1-2,或者采用计数排序等

void sortColors(int A[], int n) 
{
    int tmp;
    for(int i=0;i<n-1;++i)
    {
        for(int j=0;j<n-i-1;++j)
        {
            if(A[j]>A[j+1])
            {
                tmp=A[j];
                A[j]=A[j+1];
                A[j+1]=tmp;
            }
        }
    }
}

(2)上文算法复杂度很高,改成O(n).

void sortColors(int A[],int n)
{
    int red=0;
    int blue=n-1;
    for(int i=0;i<blue+1;)
    {
        if(A[i]==0)
            swap(A[red++],A[i++]);
        else
            if (A[i]==2)
                swap(A[blue--],A[i++]);
            else
                i++;
    }
}

25、Remove Duplicates from Sorted Array:Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not allocate extra space for another array, you must do this in place with constant memory.
(1)STL

int removeDuplicates(int A[], int n) 
{
    return distance(A,unique(A,A+n));
}

(2)顺序替换-标志位,n==0需单独判断

int removeDuplicates(int A[], int n) 
{
    if(n==0)
        return 0;
    int i,len=0;
    for(i=1;i<n;i++)
    {
        if(A[len]!=A[i])
            A[++len]=A[i];
    }
    return len+1;
}

标签: LeetCode

评论已关闭