发表于

描述
问题1:给定要给整数n，求n!中末尾0的个数
问题2:给定整数n，求n!中最低位1的位置

问题1
分析一下，就是统计含有5的个数,于是有代码:
emmm,算法的时间复杂度为O(n*log2(k))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countFac0(int n){
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int k = i;
        while (k) {
            if (k % 5 == 0) {
                sum++;
                k /= 5;
            }
            break;
        }
    }
    return sum;
}

书中改进后的代码,显然更优，也理解起来更加费力
先整体除以5，求数目，再求25的倍数，以此类推

1
2
3
4
5
6
7
8
int countFac2(int n) {
    int sum = 0;
    while (n) {
        sum += n / 5;
        n /= 5;
    }
    return sum;
}

问题二
关键要转换成求这个阶乘数的质因数2的个数，加个1就好。
二进制数，末尾为0=>为偶数，那就看有多少个0，也就是能除以多少个2，题目要求1的位置，于是要加个1。

类似问题一的二解法,本问还可以计算1的个数，用N减得到的即为质因数的个数。

发表于

普通法

1
2
3
4
5
6
7
8
int countBinary1(int num) {
    int sum = 0;
    while (num) {
        sum += num % 2;
        num /= 2;
    }
    return sum;
}

移位法

1
2
3
4
5
6
7
8
int countBinary2(int num) {
    int sum = 0;
    while (num) {
        sum += num & 1;
        num >>= 1;
    }
    return sum;
}

快速法
这个效率是与1的个数有关，超级牛逼！

1
2
3
4
5
6
7
8
int countBinary3(int num) {
    int sum = 0;
    while (num) {
        num &= (num - 1);
        sum++;
    }
    return sum;
}

还有以空间换取时间的方法,列出一个很大是数组，直接返回， 时间复杂度是O(1).
参考文章

发表于

切换hexo+next代码高亮

主站点配置文件改成这个样子

1
2
3
4
5
highlight:
  enable: true
  line_number: true
  auto_detect: false  <<-----//这里改成false
  tab_replace:

next主题配置文件更改

1
2
3
4
5
6
# Code Highlight theme
# Available value:
#    normal | night | night eighties | night blue | night bright
# https://github.com/chriskempson/tomorrow-theme
# highlight_theme: normal
highlight_theme: night eighties

密码移位

1
ch = (ch+i-'a')%26+'a';

not is

1
2
3
4
5
6
7

if (ch+i>'z'){
   ch = (ch+i-'z')+'a';
}
else{
   ch = ch+i;
}

发表于

描述
给定一个int类数据集合，你需要判断这两个数据集合能否分成两个相等的部分，也就是说一部分等于总和的一般
我想了一个算法，枚举，O(2^N)，(*￣ω￣)

我的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sumval = accumulate(nums.begin(), nums.end(), 0);
        if (sumval % 2 == 1) { return false; }
        int midval = sumval / 2;
        int nNums = nums.size();

        for (auto num : nums) {
            if (num > midval) {
                return false;
            }
        }

        for (int i = 0; i < pow(2, nNums); i++) {
            int sumNums = 0;
            for (int j = 0; j < nNums; j++) {
                if (i >> nNums - 1 - j & 1) { sumNums += nums[j]; }
                if (sumNums == midval) { return true; }
                else if (sumNums > midval) { break; }
            }
        }
        return false;
    }
};

这个是我写的一个递归的版本，好像没有什么效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public:
    bool canPartition(vector<int>& nums) {
        int sumval = accumulate(nums.begin(), nums.end(), 0);
        if (sumval % 2 == 1) { return false; }
        int midval = sumval / 2;
        int nNums = nums.size();

        for (auto num : nums) {
            if (num > midval) {
                return false;
            }
        }

        if(findn(nNums-1,midval,nums)==ture){return true;}
        return false;
    }

    bool findn(int iNum, int midval, vector<int>& nums) {
    if (midval == 0) {
        return true;
    }
    if (midval < 0) {
        return false;
    }
    if (iNum == 0 && midval == nums[0]) {
        return true;
    }
    if (iNum == 0 && midval != nums[0]) {
        return false;
    }
    return findn(iNum - 1, midval - nums[iNum], nums) || findn(iNum - 1, midval, nums);
}
};

更好的解法

参考链接
基于贪心的dp算法，强大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) { return false; }
        int half = sum / 2;

        //sort it from big to small then you can use dp
        //it is quickly,because it's greedy
        sort(nums.begin(), nums.end(), greater<int>());
        return canPartitionRecrusion(nums, half, 0);
    }

    bool canPartitionRecrusion(vector<int>& nums,int half,int index) {
        for (int i = index; i < nums.size(); i++) {
            int h = half - nums[i];
            if (h == 0) { return true; }
            if (h <0) { return false; }
            if (canPartitionRecrusion(nums, h, i + 1) == true) { return true; };
        }

        return false;
    }

};

另一种解法

代码很精炼，有点难理解，下标即总和，厉害。
实际上利用了一个数组模拟了所有的加法总和情况，太精巧了。Ψ(￣∀￣)Ψ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = std::accumulate(nums.begin(), nums.end(), 0);
        if (sum%2!=0) return false;
        vector<int> dp(sum+1, 0);
        dp[0] = 1;
        for (const int num: nums){
            for (int i= sum; i>=0; --i){
                if (dp[i]) dp[i+num]= true;
            }
            if (dp[sum/2]) return true;
        }return false;
    }
};

参考资料
原题链接

发表于

添加了七牛+极简图床

登录极简图床，这个网站有较详细的教程

algolia搜索出现Record is too big 错误

将command.js中的var storedPost =替换

1
2
// var storedPost = _.pick(data, ['title', 'date', 'slug', 'path', 'content', 'excerpt', 'objectID']);
 var storedPost = _.pick(data, ['title', 'date', 'slug', 'path', 'objectID']);

注释的为未修改时的代码,参考文章
这样的缺点是只能搜索标题和标签。

发表于

描述
1、海明距离:两个数化成二进制，计算各位的不同的数目。
2、问题要求n个数两两之间的海明距离

思路

  • 初步想法：写一个函数计算两个数之间的海明距离，再求n个数，时间复杂度为O(N^2*M)，慢的要死
  • 进一步想法：统计每个数尾数为0和1的个数，迭代至最长长度。sum=sum+number0*number1;

我的解法
简单粗暴 (*￣ω￣)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int maxlen = 0;
        int nNums = nums.size();
        for (auto num : nums) {
            if (maxlen < getLen(num)) { maxlen = getLen(num); }
        }
        int haiming_sum = 0;
        for (int i = 0; i < maxlen; i++) {
            int count01[2] = { 0 };
            for (int j = 0; j < nNums; j++) {
                int lastnum = nums[j] % 2;
                nums[j] /= 2;
                if (lastnum == 0) { count01[0]++; }
                if (lastnum == 1) { count01[1]++; }
            }
            haiming_sum += count01[0] * count01[1];
        }
        return haiming_sum;
    }

    int getLen(int num) {
        int lenNum = 0;
        while (num != 0) {
            lenNum++;
            num /= 2;
        }
        return lenNum;
    }
};


更好的解法
采用了位运算，很快，很短 ～(￣▽￣～)(～￣▽￣)～
还省去了计算最大长度，不计算0的个数，直接减，厉害啊！老哥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int total_cnt = 0;
        for(int i=0;i<32;i++){
            int loc_cnt = 0;
            for(int j=0;j<nums.size();j++){
                loc_cnt += (nums[j]>>i & 1);
            }
            total_cnt += loc_cnt*(nums.size()-loc_cnt);
        }
        return total_cnt;
    }
};

**参考资料**
[原题链接](https://leetcode.com/submissions/detail/175053103/)

发表于

细胞生命游戏

简介：
“人口过少”：任何活细胞如果活邻居少于2个，则死掉。
“正常”：任何活细胞如果活邻居为2个或3个，则继续活。
“人口过多”：任何活细胞如果活邻居大于3个，则死掉。
“繁殖”：任何死细胞如果活邻居正好是3个，则活过来。
这里假设领域为3*3的大小

利用java实现,三个类

Main.java

1
2
3
4
5
6
7
8
package life_game3;
import javax.swing.*;

public class Main {
	public static void main(String []args) {
	    Paint ptPaint = new Paint();
	}
}

Logic.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

public class Logic {
	public static final int ROWS = 10;
	public static final int COLS = 10;
	public static final int WIDTH = 40;
	public static final int HIGHT = 40;

	private int map[][] = new int[][] {
		{1,1,1,1,1,1,1,1,1,1},
		{0,0,0,0,0,0,0,0,0,0},
		{1,1,1,1,1,1,1,1,1,1},
		{0,1,0,0,1,1,0,1,0,1},
		{0,0,1,1,0,0,0,1,0,0},
		{0,0,1,1,0,0,1,0,1,0},
		{0,1,0,0,1,1,0,0,0,1},
		{1,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0},
		{1,1,1,1,1,1,1,1,1,1},
	};

	public Logic() {
		 ;
	}

	public  int[][] newmap(int [][] map){
		// copy new 2d array
		int [][] map0 = new int [ROWS][COLS];
		for(int i=0;i<ROWS;i++) {
			map0[i] =map[i].clone();
		}

		//go through the map
		for(int i=0;i<ROWS;i++) {
			for(int j=0;j<COLS;j++) {
				int count =0;
				if(i-1>=0 && j-1>=0 && map[i-1][j-1]==1) {count++;}
				if(i-1>=0 && j>=0 && map[i-1][j]==1) {count++;}
				if(i-1>=0 && j+1<COLS && map[i-1][j+1]==1) {count++;}

				if(i>=0 && j-1>=0 && map[i][j-1]==1) {count++;}
				if(i>=0 && j+1<COLS && map[i][j+1]==1) {count++;}

				if(i+1<ROWS && j-1>=0 && map[i+1][j-1]==1) {count++;}
				if(i+1<ROWS && j>=0 && map[i+1][j]==1) {count++;}
				if(i+1<ROWS && j+1<COLS && map[i+1][j+1]==1) {count++;}

				if(! (count==2 || count==3)) {
					map0[i][j]=0;
				}
				if( count==3 ) {
					map0[i][j]=1;
				}


			}
		}
		return map0;

	}

	public int[][] getMap(){
		return map;
	}

	public void  updateMap(){
		this.map = newmap(map);
	}
}

Paint.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package life_game3;
import javax.swing.*;
import java.awt.*;

public class Paint  extends JPanel{
	Logic gamelogic = new Logic();
	int blank =0;

	public Paint() {
		JFrame frame = new JFrame("生命游戏");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

		frame.setBounds(800, 400, 420,445);

		 new Thread(new Runnable() {
			   public void run() {
			    while (true) {
			     try {
			      Thread.sleep(1000);
			     } catch (InterruptedException e) {
			    	 e.printStackTrace();
			     }
			     repaint();
			    }
			   }
			  }).start();
		frame.setResizable(false);
		frame.add(this);
		frame.setVisible(true);
	}
	 public void paint(Graphics g) {
		super.paint(g);
		int map[][] = gamelogic.getMap();
		gamelogic.updateMap();
	    g.setColor(Color.black);
	    for(int i=0;i<gamelogic.ROWS;i++) {
	    	for(int j=0;j<gamelogic.COLS;j++) {
	    		if(map[i][j]==1) {
	    			g.fillRect( j*gamelogic.WIDTH+blank,i*gamelogic.HIGHT, gamelogic.WIDTH, gamelogic.HIGHT);
	    		}
	    		else if(map[i][j]==0){
	    			g.drawRect(j*gamelogic.WIDTH+blank,i*gamelogic.HIGHT,  gamelogic.WIDTH, gamelogic.HIGHT);
	    		}
	    	}
	    }
	  }
}

遇到的一个小问题

JFrame挡住了界面
解决方法：不要直接在JFrame中画，在JPannel中画，然后将其添加到JFrame里面去。

参考文章:paint定时刷新

发表于


链表节点要这么画成图2这样的不要简单的画图1表示了。
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    ListNode * swapPairs(ListNode* head) {
        auto p = head;
        //no node
        if (p == NULL) { return p; }

        //swap first two nodes
        if (p&&p->next) {
            auto next = p->next;
            p->next = p->next->next;
            next->next = p;
            head = next;//change head node
        }
        //only one node
        else {
            return p;
        }

        //swap rest nodes;
        auto prev = head->next;
        p = head->next->next;
        while (p&&p->next){
            auto next = p->next;
            p->next = p->next->next;
            next->next = p;
            prev->next = next;
            prev = p;
            p = p->next;
        }
        return head;
    }
};

发表于

这道题很有趣，很灵活。
我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        string s1 = delS(S);
        string t1 = delS(T);
        int len = s1.size() < t1.size() ? s1.size() : t1.size();
        for (int i = 0; i < len; i++) {
            if (s1[i] != t1[i]) { return false; }
        }
        return true;
    }

    string delS(string S) {
        string S2 = S;

        int len = S.size();
        for (int i = 0; i < len; i++) { S2[i] = '0'; }

        for (int i = len - 1; i >= 0; i--) {
            if (S[i] == '#') {
                S[i] = '0';
                int k = i - 1;
                int delCnt = 1;
                while (k >= 0 && S[k] == '#')
                {
                    S[k] = '0';
                    delCnt++;
                    k--;
                }
                while (delCnt > 0 && k >= 0) {
                    if (S[k] != '#' && S[k] != '0') {
                        S[k] = '0';
                        k--; delCnt--;
                    }
                    else { k--; };
                }


            }
        }
        int ind = 0;
        for (int i = 0; i <= len - 1; i++) {
            if (S[i] != '0') { S2[ind++] = S[i]; }
        }
        return S2;
    }
};

大佬代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        if (delS(S) == delS(T)) { return true; }
        else { return false; }
    }

    string delS(string S) {
        stack<char> stk;
        for (char c : S) {
            if (c != '#') {
                stk.push(c);
            }
            else {
                if (!stk.empty()) {
                    stk.pop();
                }
            }
        }
        string str="";
        while (!stk.empty()) {
            str += stk.top();
            stk.pop();
        }

        return str;
    }
};

大佬代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;
        while (i >= 0 || j >= 0){
            while (i >= 0) {
                if (S[i] == '#') { skipS++; i--; }
                else if (skipS > 0) { skipS--; i--; }
                else { break; }
            }
            while (j >= 0) {
                if (T[j] == '#') { skipT++;j--; }
                else if (skipT > 0) { skipT--; j--; }
                else { break; }
            }
            if (i>=0 && j>=0 && S[i] != T[j]) { return false; }
            i--, j--;
        }
        return false;
    }

};

参考资料
原题链接

发表于

描述
求一个有峰值的序列的峰值

思路
很简单的一道题，但是考验一点点思维和仔细。我直接找最大值了，算法效率是O(N)。

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int max_val = A[0];
        int ind = 0;
        for (int i = 1; i < A.size(); i++) {
            if(max_val<A[i]){
                max_val = A[i];
                ind = i;
            }
        }
        return ind;
    }
};

大佬代码
大佬采用了二分查找，时间复杂度为O(log2(N))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int len = A.size();
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] < A[mid + 1]) { left = mid + 1; }
            else { right = mid; }
        }
        return left;
    }
};

另外，这道题其实不是找最大值，而是找峰值，于是这样也可以解决，时间负责度为O(N)

1
2
3
4
5
6
7
class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int i = 0;
        while (A[i] < A[i+1]) i++;
        return i;
    }
}

参考链接
原题链接