263. Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

 

解题思路：

水题、、、、、

class Solution { public:     bool isUgly(int num) {         if(num<1)return false;         // 4ms         while((num&1)==0)num>>=1;         // 8ms         //while((num%2)==0)num/=2;         while(num%3==0)num/=3;         while(num%5==0)num/=5;         return num==1;     } };

 

 

70. 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?

 

解题思路：

斐波那契。。。

class Solution { public:     int climbStairs(int n) {         if(n<=2)return n;         int a=1,b=2;         for(int i=3;i<=n;i++){             int tmp=a+b;             a=b;             b=tmp;         }         return b;     } };

 

 

53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray [4,−1,2,1] has the largest sum = 6.

 

结题报告：

最大连续和，动态规划思想

class Solution { public:     int maxSubArray(vector<int>& nums) {         int n=nums.size();         if(n==0)return 0;         int max=0x80000000;         int s=0;         for(int i=0;i<n;i++){             if(s+nums[i]<nums[i])s=nums[i];             else             s+=nums[i];             if(s>max)max=s;         }         return max;     } };

 

 

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

 

解题思路：

DFS

class Solution { public:     vector<string> generateParenthesis(int n) {         vector<string>res;         if(n==0)return res;         dfs(res,n,0,0,"");         return res;     }     void dfs(vector<string>&res,int n,int l,int r,string s){         if(l==n&&r==n){             res.push_back(s);             return ;         }         if(l==n){             dfs(res,n,l,r+1,s+")");             return ;         }         if(l==r){             dfs(res,n,l+1,r,s+"(");             return ;         }         dfs(res,n,l+1,r,s+"(");         dfs(res,n,l,r+1,s+")");               } };