实习之外----算法学习
我觉得衡量一个程序员的能力不能光从他能不能实现这个功能评判，而是看他的学习能力，自学能力，理解能力。重要的还是基础，实习这几个月以来很少碰算法相关的知识了，在学校里学到的数据结构和算法都慢慢的不熟练了。所以最近一个月自己每天在上下班的公交上或者地铁上 都会汲取新的知识，复习旧的知识。我一般是在简书上和掘金app上来看一些别人分享的知识来学习。还有慕课网上我会下载一些比较对我有用的视频来学习。还会在lintcode上面做题，目前做了几十道了，我是按照难易程度来排列的，目前入门的算法题已经全部做完，目前在做简单的算法题，但是我感觉简单的算法题也有点难度，自己就一边一边积累，把不会的、想法新奇的一些思路记下来，以巩固自己的底子。
下面给大家分享一点我积累的一些知识：
1、小写字母和大写字母 ascll码 相差32，可以把字母转换成int计算后再转换成char 返回。 ---------lintcode 145题。
2、斐波那契数列 大家应该很熟悉了，我这里了解到的有两种解法:
（1）递归、//未优化 斐波那契数列
public class Solution {
/**
* @param n: an integer
* @return: an ineger f(n)
*/
public int fibonacci(int n) {
// write your code here
if(n==1 ){
return 0;
}
if(n==2){
return 1;
}
return fibonacci(n-1)+fibonacci(n-2);
}
}
（2）非递归:
//优化 斐波那契数列
public class Solution {
/**
* @param n: an integer
* @return: an ineger f(n)
*/
public int fibonacci(int n) {
// write your code here
if(n==1 ){
return 0;
}
if(n==2){
return 1;
}
int a = 0;// n-2
int b = 1;//n-1
int c = 0;//n
for (int i = 3; i < n + 1; i++) {
c = a + b;//n = (n-1)+(n-2)
a = b; // n-2 = n-1
b = c;//n-1 = n
}
return c;
}
}
3、最近学习了一道 谷歌的面试算法题
漂亮数,意思就是每个数字都会转换成 由N个1组成的数字，只不过是进制不同，所以给你一系列数字让你求出这些数字对应的最小的进制.
比如：输入3 它可以转换成 11 所以他的最小进制就是2进制， 13 可以转换成111 它的进制就是3进制。
思路：判断传入的数据最大多少，例：10^18, 最多64个1
所以N=r^(k-1)+r^(k-2)+...+r+1
所以循环判断N对应的1的位数 有没有对应的进制
算法时间复杂度 logN*logN*logN ~= 64*64*64 << 10^8 ~=秒级运算
查找对应的进制，用二分查找法，min=2，max=N;
然后把对应的进制，位数，转换成数 与N作比较。
转换时用 等比函数求和，还要防止溢出。
具体的代码就不贴了。
数学归纳法：
数学归纳法证明断言对所有自然数成立:
证明对于N=1成立
证明N>1时：如果对于N-1成立，那么对于N成立。
可以把假设的N-1 成立的结果带入，然后计算是否成立。
递归书写方法：
1、严格定义递归函数作用，包括参数，返回值，Side-effect
2、先一般，后特殊
3、每次调用必须缩小问题规模
4、每次问题规模缩小程度必须为1
比较两个字符串：
public class Solution {
/**
* @param A: A string
* @param B: A string
* @return: if string A contains all of the characters in B return true else return false
*/
// write your code here
public boolean compareStrings(String A, String B) {
int[] counts = new int[26];
for (int i = 0; i < 26; i++) {
counts[i] = 0;
}
for (int i = 0; i < A.length(); i++) {
counts[A.charAt(i) - 'A'] ++;
}
for (int i = 0; i < B.length(); i++) {
counts[B.charAt(i) - 'A'] --;
if (counts[B.charAt(i) - 'A'] < 0) {
return false;
}
}
return true;
}
}
思路：把A中所有字母减去'A' 得到的就是A中字符ascll码 ，然后判断B中字母是否都存在A中
这个算法的思路真是太独特了，真心的佩服 算法工程师的想法。学习了~
还有这一道：
样例
给出 numbers = [2, 7, 11, 15], target = 9, 返回 [0, 1].
给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。
你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
if (map.get(numbers[i]) != null) {
int[] result = {map.get(numbers[i]), i};
return result;
}
map.put(target - numbers[i], i);
}
int[] result = {};
return result;
}
这个思路也是很不错的，我发自内心的佩服这些牛人，可以想到一些想法特别新颖的解题思路。
