寫CODE，會想到騎車也在想.....: leet code

顯示具有 leet code 標籤的文章。顯示所有文章

2016年2月26日星期五

LEET code -- Rotate Image

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

下面這寫法要額外空間

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int size=matrix.size();
        vector<vector<int>> co(size,vector<int>(size,0));
        co=matrix;
        for(int i=0;i<size;i++){
            for(int j=0;j<size ;j++){
                matrix[j][size-i-1]=co[i][j];
            }
        }
    }
};

------------
每次轉四個角落
一起轉不用額外空間

要注意邊界
左上是 col會跑
左下是row會跑
右上是row會跑
右下是col會跑

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int size=matrix.size();
        for(int row=0;row<size/2;row++){
            for(int col=row;col<size-1-row;col++){
                int temp=matrix[row][col];//left up
                matrix[row][col]=matrix[size-1-col][row];//left button
                matrix[size-1-col][row]=matrix[size-1-row][size-1-col];//right button
                matrix[size-1-row][size-1-col]=matrix[col][size-1-row];//right up
                matrix[col][size-1-row]=temp;
            }
        }

    }
};

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.

Note:
You are not suppose to use the library's sort function for this problem.

如果current 當下不等於 i (顏色)
就往後找看有沒有如果找不到就換下一個顏色

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int current=0;
        int size=nums.size();
        for(int i=0;i<3;i++){
            int color=current;
            while(color<size && current<size){
                if(nums[current]!=i){
                    color=current+1;
                    while(color<size && nums[color]!=i)color++;
                    if(color<size){
                        int temp=nums[color];
                        nums[color]=nums[current];
                        nums[current]=temp;
                    }else break;
                }
                current++;
                
            }
        }
    }
};

-----------

The solution requires the use of tracking 3 positions, the Low, Mid and High.
We assume that the mid is the "Unknown" area that we must evaluate.
If we encounter a 0, we know that it will be on the low end of the array, and if we encounter a 2, we know it will be on the high end of the array.
To achieve this in one pass without preprocessing (counting), we simply traverse the unknown will generating the low and high ends.
Take this example:
Assume our input is: 1 0 2 2 1 0 (short for simplicity).

Running the algorithm by hand would look something like:

    1 0 2 2 1 0
    ^         ^
    L         H
    M

    Mid != 0 || 2
    Mid++

    1 0 2 2 1 0
    ^ ^       ^
    L M       H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 1 2 2 1 0
      ^ ^     ^
      L M     H

    Mid == 2
    Swap High and Mid
    High--

    0 1 0 2 1 2
      ^ ^   ^
      L M   H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 0 1 2 1 2
        ^ ^ ^
        L M H

    Mid == 2
    Swap High and Mid
    High--

    0 0 1 1 2 2
        ^ ^
        L M
          H

    Mid <= High is our exit case

class Solution {
    public:
    void sortColors(vector<int>& nums) 
    {
        int tmp = 0, low = 0, mid = 0, high = nums.size() - 1;

        while(mid <= high)
        {
            if(nums[mid] == 0)
            {
                tmp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = tmp;
                low++;
                mid++;
            }
            else if(nums[mid] == 1)
            {
                mid++;
            }
            else if(nums[mid] == 2)
            {
                tmp = nums[high];
                nums[high] = nums[mid];
                nums[mid] = tmp;
                high--;
            }
        }
    }
};

LEET code -- Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
Hint:

Try to utilize the property of a BST.
What if you could modify the BST node's structure?
The optimal runtime complexity is O(height of BST).

就是找出DFS他parse的順序找出來

為了可以提早結束我用-1代表找到
rank代表現在找到第幾個數字了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if(root==NULL)return 0;
        rank=0;
        DFS(root,k);
        return reuslt;
        
    }
    int DFS(TreeNode* root,int level){
        if(root==NULL)return rank;
        int left=DFS(root->left,level);
        if(left<0)return -1;
        rank=rank+1;
        if(level==rank){
            reuslt=root->val;
            return -1;
        }
        int right=DFS(root->right,level);
        if(right <0)return -1;
        return 1;
    }
private:
    int rank;
    int reuslt;
};

--------------------------

class Solution {
public:
    TreeNode* current = NULL;
    stack<TreeNode*> s;
    int kthSmallest(TreeNode* root, int k) {
        current = root;
        int count = 1;
        while(1)
        {
        while(current)
        {
            s.push(current);
            current = current->left;
        }
        if(count == k)
        {
            TreeNode* node = s.top();
            return node->val;
        }
        if(count != k)
        {
            TreeNode* node = s.top();
            s.pop();
            current = node->right;
            count++;
        }
        }
    }
};

LEET code -- Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

印出所有的排列組合，使樣回朔法來跑

用一個boo;陣列來記錄那些數字用過了
接著丟給下一個去紀錄

class Solution {
public:
    void find(vector<vector<int>> &ans, vector<int> &current, vector<int> &nums, bool *use){
        if(current.size() == nums.size()){
            ans.push_back(current);
            return ;
        }
        for(int i=0;i<nums.size();i++){
            if(use[i]==false){
                current.push_back(nums[i]);
                use[i]=true;
                find(ans,current,nums,use);
                current.pop_back();
                use[i]=false;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        int size=nums.size();
        bool use[size]={0};
        vector<vector<int>> ans;
        vector<int> current;
        find(ans,current,nums,use);//not &use
        //for(int i=0;i<size;i++)use[i]=false;
        return ans;
    }
};

--------------------
旋轉的方式

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        create(nums,res,0);
        return res;
    }

    void create(vector<int>& nums,vector<vector<int>> &res,int n)
    {
        if(n==nums.size()-1)
            res.push_back(nums);
        else
        {
            for(int i=n;i<nums.size();i++)
            {
                swap(nums[i],nums[n]);
                create(nums,res,n+1);
                swap(nums[i],nums[n]);
            }
        }
    }

    void swap(int &a,int &b)
    {
        int tmp=a;
        a=b;
        b=tmp;
    }
};

LEET code -- 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:

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

下面利用Backtracking的方式我現在選擇( 後面的選擇丟給下一個recursive來決定
leftsize代表有多少( 這個數目不能超過n
rightsize代表有多少) 這個數目不能超過(

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string s="(";
        findparent(ans,s,1,0,n);
        return ans;
    }
    
    void findparent(vector<string> &ans, string s,int leftsize,int rightsize,int n){//left is (   right is )
        if(n*2==leftsize+rightsize){
            ans.push_back(s);
            return;
        }
        if(leftsize<n)findparent(ans,s+"(",leftsize+1,rightsize,n);
        if(rightsize<leftsize)findparent(ans,s+")",leftsize,rightsize+1,n);
        
    }
};


-----------------------

-------------------------

神人iterater

logic here is simple:
First, store a result vector, then for every entry:

add '(', when cannot add ')'
add ')', when cannot add '('
copy this entry and add '(' and ')' separately to original and new copy, when both are valid

here count and countleft are vectors that store check values.

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result(1);
        vector<int> count(1,0),countleft(1,0);
        for(int i=0;i<2*n;++i){
            int m=count.size();
            for(int j=0;j<m;++j){
                if(count[j]==0){
                    result[j]+='(';
                    count[j]++;
                    countleft[j]++;
                }
                else if(countleft[j]==n) result[j]+=')';
                else{
                    result.push_back(result[j]+')');
                    count.push_back(count[j]-1);
                    countleft.push_back(countleft[j]);
                    result[j]+='(';
                    count[j]++;
                    countleft[j]++;
                }
            }
        }
        return result;
    }
};

LEET code -- Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

可以發現每一排的最後右邊一定最大
所以可以先搜尋最右邊去找要搜尋哪一排

但是我找到那排是用for loop找會太慢可以改成binary search

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        
        for(int i=0;i<matrix.size();i++){
            if(target <=matrix[i][ matrix[i].size()-1 ] ){
                for(int j=0;j<matrix[i].size();j++){
                    if(target == matrix[i][j])return true;
                }
                return false;
            }
        }
        return false;
    }
};

-------------
用binary search

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        
        for(int i=0;i<matrix.size();i++){
            if(target <=matrix[i][ matrix[i].size()-1 ] ){
                int start=0,end=matrix[i].size()-1;
                while(start<=end){
                    int mid = start +(end-start)/2;//prevent overflow
                    if(matrix[i][mid]==target)return true;
                    if(matrix[i][mid] > target)end=mid-1;
                    else start=mid+1;
                }
                return false;
            }
        }
        return false;
    }
};

LEET code -- Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

queue 的STL 注意是push 跟front 還有pop

reverse也是STL

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;//initial ,empty
        queue<TreeNode*> parse;
        if(root==NULL)return ans;
        parse.push(root);
        while(parse.size()>0){
            vector<int> level;//local level
            for(int i=parse.size();i>0;i--){
                TreeNode * front = parse.front();
                level.push_back(front->val);
                if(front->left!=NULL)parse.push(front->left);
                if(front->right!=NULL)parse.push(front->right);
                parse.pop();
            }
            ans.push_back(level);
            
        }
        reverse(ans.begin(),ans.end());
        
    }
};

---------------------------
recursive

class Solution {
public:

    vector< vector<int> > result;

    void dfs(TreeNode *root, int level)
    {
        if(!root) return;

        if(level == result.size()) 
            result.push_back( vector<int>() );

        vector<int> &vec = result[level];
        vec.push_back(root->val);

        dfs(root->left, level+1);
        dfs(root->right, level+1);
    }

    vector<vector<int>> levelOrderBottom(TreeNode* root)
    {
        if(!root) return vector< vector<int> >();

        dfs(root, 0);

        return vector< vector<int> >(result.rbegin(), result.rend());
    }
};

2016年2月25日星期四

LEET code -- Burst Balloons 難爆炸

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:
Given [3, 1, 5, 8]
Return 167

    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
   coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

這題超難的

這題是事實上可以當成DP來寫

不要想每次 怎麼消除氣球

而是去想 最後一個被消除的

因為一開始去想要怎麼消第一個  他左右兩邊會合併  所以不能divide concour

但是如果反過來 使用最後被消除的    因為他是被最後消除  所以左右邊兩邊是分開的!!!

状态转移方程：

dp[l][r] = max(dp[l][r], nums[l] * nums[m] * nums[r] + dp[l][m] + dp[m][r])

dp[l][r]表示扎破(l, r)范围内所有气球获得的最大硬币数，不含边界；

l与r的跨度k从2开始逐渐增大；

三重循环依次枚举范围跨度k，左边界l，中点m；右边界r = l + k；

Be Naive First



When I first get this problem, it is far from dynamic programming to me. I started with the most naive idea the backtracking.



We have n balloons to burst, which mean we have n steps in the game. 
In the i th step we have n-i balloons to burst, i = 0~n-1. Therefore we 
are looking at an algorithm of O(n!). Well, it is slow, probably works 
for n < 12 only.



Of course this is not the point to implement it. We need to identify the redundant works we did in it and try to optimize.



Well, we can find that for any balloons left the maxCoins does not 
depends on the balloons already bursted. This indicate that we can use 
memorization (top down) or dynamic programming (bottom up) for all the 
cases from small numbers of balloon until n balloons. How many cases are
 there?  For k balloons there are C(n, k) cases and for each case it 
need to scan the k balloons to compare. The sum is quite big still. It 
is better than O(n!) but worse than O(2^n).



Better idea



We then think can we apply the divide and conquer technique? After 
all there seems to be many self similar sub problems from the previous 
analysis.



Well,  the nature way to divide the problem is burst one balloon and 
separate the balloons into 2 sub sections one on the left and one one 
the right. However, in this problem the left and right become adjacent 
and have effects on the maxCoins in the future.



Then another interesting idea come up. Which is quite often seen in 
dp problem analysis. That is reverse thinking. Like I said the coins you
 get for a balloon does not depend on the balloons already burst. 
Therefore
instead of divide the problem by the first balloon to burst, we divide 
the problem by the last balloon to burst. 



Why is that? Because only the first and last balloons we are sure of their adjacent balloons before hand!



For the first we have nums[i-1]*nums[i]*nums[i+1] for the last we have nums[-1]*nums[i]*nums[n].



OK. Think about n balloons if i is the last one to burst, what now?



We can see that the balloons is again separated into 2 sections. But 
this time since the balloon i is the last balloon of all to burst, the 
left and right section now has well defined boundary and do not affect 
each other! Therefore we can do either recursive method with memoization
 or dp.



Final



Here comes the final solutions. Note that we put 2 balloons with 1 as
 boundaries and also burst all the zero balloons in the first round 
since they won't give any coins.
The algorithm runs in O(n^3) which can be easily seen from the 3 loops 
in dp solution.









下面的K 是長度, i是最後才被搓破的  left跟right是最後戳破時的左右那兩個

int maxCoinsDP(vector<int> &iNums) {
    int nums[iNums.size() + 2];
    int n = 1;
    for (int x : iNums) if (x > 0) nums[n++] = x;
    nums[0] = nums[n++] = 1;


    int dp[n][n] = {};
    for (int k = 2; k < n; ++k) {
        for (int left = 0; left < n - k; ++left)
            int right = left + k;
            for (int i = left + 1; i < right; ++i)
                dp[left][right] = max(dp[left][right],
                     nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
        }

    return dp[0][n - 1];
}

LEET code -- Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

是一個DP問題

事實上只要碰到1 就不要再算了因為路只有一條

但是下面版本跑太慢了

class Solution {
public:
    int uniquePaths(int m, int n) {
        int down=0,right=0;
        if(m==1 || n==1)return 1;
        //else if(m==1)right=uniquePaths(m,n-1);
        //else if(n==1)down=uniquePaths(m-1,n);
        else {
            right=uniquePaths(m,n-1);
            down=uniquePaths(m-1,n);
        }
        return right+down;
    }
};

---------------
會慢是因為這題可以用陣列寫完
所以recursive太慢

做 M*N的大小double vector
vector> a(m,vector(n,0));

邊全部都是1 因為這些都是1步可以到的

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> ans(m,vector<int> (n,0) );//double vector
        for(int i=0;i<m;i++)ans[i][0]=1;
        for(int j=0;j<n;j++)ans[0][j]=1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                ans[i][j]=ans[i-1][j]+ans[i][j-1];
            }
        }
        return ans[m-1][n-1];
    }
};

LEET code -- Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.
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.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

把幾個case寫出來會發現

先是0--> 0->00
1 01
11
10

會發現在第三個bit之前是倒過來看的

像是下面的紅色跟藍色剛好是倒過來
所以每次算好一個bit 下一個bit就是把之前的倒過來+上2的倍數就好
000 0
001 1
011 3
010 2

110 2+2
111 2+3
101 2+1
100 2+0

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        ans.push_back(0);
        for(int i=1;i<=n;i++){
            int factor=1<<(i-1);
            for(int j=ans.size()-1;j>=0;j--){
                ans.push_back( ans[j]+factor );
            }
        }
        return ans;
    }
};

LEET code -- Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.

You may assume no duplicate exists in the array.

class Solution {
public:
    int findMin(vector<int>& nums) {
        int size=nums.size();
        int min=nums[0];
        for(int i=1;i<size;i++){
            if(nums[i]<nums[i-1])return nums[i];
        }
        return min;
    }
};

-----------------------
或是BTS
比較快

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<r){
            int mid = l + (r-l)/2;
            nums[mid]>nums[r] ? l=mid+1:r=mid;
        }
        return nums[l];
    }
};

2016年2月24日星期三

LEET code -- 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.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* swapPairs(struct ListNode* head) {
    if(head==NULL)return NULL;
    struct ListNode *Current=head, *Next=head->next;
    
    while(Next!=NULL&&Current!=NULL){
        int temp=Next->val;
        Next->val=Current->val;
        Current->val=temp;
        Current=Next->next;
        if(Current!=NULL)Next=Current->next;
    }
    return head;
    
}

2016年2月21日星期日

LEET code -- Count Primes

Description:
Count the number of prime numbers less than a non-negative number, n.
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Hint:

Let's start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrime function would be O(n) and hence counting the total prime numbers up to n would be O(n²). Could we do better?
As we know the number must not be divisible by any number > n / 2, we can immediately cut the total iterations half by dividing only up to n / 2. Could we still do better?

Let's write down all of 12's factors:

As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.
Our total runtime has now improved to O(n^1.5), which is slightly better. Is there a faster approach?

public int countPrimes(int n) {
   int count = 0;
   for (int i = 1; i < n; i++) {
      if (isPrime(i)) count++;
   }
   return count;
}

private boolean isPrime(int num) {
   if (num <= 1) return false;
   // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i <= num; i++) {
      if (num % i == 0) return false;
   }
   return true;
}

The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. But don't let that name scare you, I promise that the concept is surprisingly simple.

Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve of Eratosthenes Animation" by SKopp is licensed under CC BY 2.0.
We start off with a table of n numbers. Let's look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well?
4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be marked off. There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?
In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p², then in increments of p: p² + p, p² + 2p, ... Now what should be the terminating loop condition?
It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient. Do you still remember Hint #3?

Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off. When the loop terminates, all the numbers in the table that are non-marked are prime.
The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia.

public int countPrimes(int n) {
   boolean[] isPrime = new boolean[n];
   for (int i = 2; i < n; i++) {
      isPrime[i] = true;
   }
   // Loop's ending condition is i * i < n instead of i < sqrt(n)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i < n; i++) {
      if (!isPrime[i]) continue;
      for (int j = i * i; j < n; j += i) {
         isPrime[j] = false;
      }
   }
   int count = 0;
   for (int i = 2; i < n; i++) {
      if (isPrime[i]) count++;
   }
   return count;
}

----------------------------

要找一個數字的值因數或是小於她的值數

最白癡作法就是 1~n全部對他除一遍

但是好一點就是只找 1~根號n

再好一點的就是上面講的方法

建一個Table 把非值數的全部mark起來

非常厲害的算法

要注意在 3行一定要malloc
因為靜態的Stack不一定有這麼多的記憶體可以拿

int countPrimes(int n) {
   // int half=sqrt(n);
    int *table=malloc(sizeof(int)*n);
    memset(table,0,sizeof(int)*n);
    for(int i=2;i*i<n;i++){
        if(table[i]==0){
            for(int j=i;j*i<n;j++){
                table[j*i]=1;
            }
        }
    }
    int ans=0;
    for(int i=2;i<n;i++){
        if(table[i]==0){ans++;}
    }
    return ans;
}

LEET code -- Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

-----------------------------
要注意因為我在 27跟28 還有30
是直接傳s[head]進去函數所以她是傳一個char進去
如果想要bool isalqh(char *s) 用指標去接
那在外面必須要把記憶體位置傳進去 &s[head]

還有數字也算字母
別忘了要轉乘一樣的字母大小

bool isalqh(char s){//we only get a char inside , not char *s
    
    int alqh=(int)s; //not *s
    //printf("%d ",alqh);
    if(  alqh >= 'A' && alqh <='Z'  )return true;
    else if( alqh >='a' && alqh<='z'  )return true;
    else if ( alqh >='0' && alqh<='9' )return true;
    else return false;
}

bool isans(char s1,char s2){//not *s1
    int s1lower=(int)s1;
    int s2lower=(int)s2;
    if(  s1lower >= 'A' && s1lower <='Z'  )s1lower+=('a'-'A');//change to lowwer cast
    if(  s2lower >= 'A' && s2lower <='Z'  )s2lower+=('a'-'A');//change to lowwer cast
    //printf("%c %c\n",s[head],s[end]);
    if(s1lower==s2lower)return true;
    else return false;
}

bool isPalindrome(char* s) {
    int size=strlen(s);
    if(!*s)return true; //empyt is true
    int head=0,end=size-1;
    while(head<end){
        
        while(head<size && !isalqh(s[head]))head++;
        while(end>=0 && !isalqh(s[end]))end--;
        //printf("%c %c\n",s[head],s[end]);
        if(!isans(s[head],s[end]))return false;
        head++;
        end--;
    }
    return true;
}

------------------
C++

class Solution {
public:
    bool isPalindrome(string s) {
        int size=s.length();
        int left=0,right=size-1;
        if(size==0)return true;
        while(left<right){
            while(left<size && !Isalph(s[left]))left++;
            while(right>0 && !Isalph(s[right]))right--;
            if(left<right && s[left]!=s[right])return false;
            left++;
            right--;
        }
        return true;
        
    }
private:
    bool Isalph(char &s){
        if( (s>='a' && s<='z') || ( s>='0' && s<='9' ) )return true;
        else if( s>='A' && s<='Z' ){
            s= s+'a'-'A';
            return true;
        }else return false;
    }

};

訂閱：文章 (Atom)

2016年2月26日 星期五

2016年2月25日 星期四

2016年2月24日 星期三

2016年2月21日 星期日

2016年2月26日星期五

2016年2月25日星期四

2016年2月24日星期三

2016年2月21日星期日