2018-10-29

leetcode-编辑距离(72)

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1:

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

思路：

背包问题，动态规划

设dp(i , j) 表示word1的前i个字符组成word2的前j个字符需要的最小步数。

那么结论如下：

if( word1[i] ==word2[j] ){

那么dp(i,j)=dp(i-1,j-1);

}else{

dp(i,j) = min{ dp(i-1,j-1) dp(i-1,j) dp(i,j-1) } + 1;

}

我们分析horse转ros

	“”	h	ho	hor	hors	horse
“”	0	1	2	3	4	5
r	1	1	2	2	3	4
ro	2	2	1	2	3	4
ros	3	3	2	2	2	3

我们很容易可以写出第一行跟第一列，之后一行一行的填充

word1[i] ==word2[j] 这种 case 很容易理解，

我们分析不等的case，比如 hor——》ros，

我们可以知道

ho -> ro 最少需要1步就可以，那么hor->ros 我们只需要替换最后一位即可，
hor -> ro最少需要2步，那么hor->ros，我们需要再插入最后一位
ho -> ros最少需要2步，那么hor->ros,我们需要删除最后一位

我们选择其中最小的步数+1即可。

代码

class Solution {
    public int minDistance(String word1, String word2) {
        //初始化
        if(word1==null||word2==null){
            return -1;
        }
        int len1 = word1.length();
        int len2 = word2.length();
        //算法开始
        int [][] re = new int[len1+1][len2+1];
        for(int i=0;i<=len1;i++){
            re[i][0]=i;
        }
        for(int i=0;i<=len2;i++){
            re[0][i]=i;
        }
        
        for(int i=1;i<=len1;i++){
            char temp1=word1.charAt(i-1);
            for(int j =1 ;j <=len2;j++){
                char temp2=word2.charAt(j-1);
                if(temp1==temp2){
                    re[i][j]=re[i-1][j-1];
                }else{
                    int s1=re[i-1][j-1]>re[i-1][j]?re[i-1][j]:re[i-1][j-1];
                    re[i][j]=(s1>re[i][j-1]?re[i][j-1]:s1)+1;
                }
            }
        }
        return re[len1][len2];
    }
}

2018-10-22

leetcode-分割等和子集(416)

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

思路

0-1 背包问题：

首先计算出dp[0][w]  w:0 ~ target-1;
之后计算出dp[i][0]  i:0 ~ 数组len-1；

case 1 :vi == j+1   dp[i][j]=true;
case 2 :vi >j+1 	dp[i][j]=dp[i-1][j];
case 3 :vi <j+1		dp[i][j]=dp[i-1][j] || dp[i-1][j-vi];

代码

class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int total=0;
        for(int i =0;i<len;i++){
            total+=nums[i];
        }
        if(total%2==1){
            return false;
        }
        int y=total/2;
        boolean[][] dp = new boolean[len][y];
        int temp =nums[0];
        for(int i =0;i<y;i++){
            dp[0][i]=(temp==(i+1));
        }
        boolean containOne=false;
        for(int i =0;i<len;i++){
            if(containOne){
            }else{
               if(nums[i]==1){
                   containOne=true;
               } 
            }
            dp[i][0]=containOne;
        }
        for(int i=1;i<len;i++){
            int vi = nums[i];
            for(int j=1;j<y;j++){
                if(vi==(j+1)){
                    dp[i][j]=true;  
                }else if(vi > (j+1)){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-vi];
                }
            }
        }
        return dp[len-1][y-1];
    }
}

2018-10-19

leetcode-最长上升子序列(300)

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

1
2
3

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

思路

dp[n]表示以nums[n]结尾的最长上升子序列；

dp[n]=dp[往前走小于nums[n]的数] 中最大的值 + 1；

代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        //dp[n]=dp[往前走小于nums[n]的数]中最大的值+1；
        int len=nums.length;
        if(len==0){
            return 0;
        }
        int re =1;
        int []dp =new int[len];
        for(int i = 0;i<len;i++){
            dp[i]=1;
            int temp = nums[i];
            int index=i;
            index--;
            while(index>=0){
                if(nums[index]<temp){
                    dp[i]=Math.max(dp[index]+1,dp[i]);
                }
                index--;
            }
            re = (re < dp[i] ? dp[i] : re);
        }
        return re;
    }
}

2018-10-19

leetcode-完全平方数(279)

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

1
2
3

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

1
2
3

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

思路

假设dp[i]表示i对应的完全平方数，考虑dp[12];

那么

Case1 : dp[12] = dp[12-1]+1;

Case2 : dp[12]= dp[12-4]+1;

Case3 : dp[12]= dp[12-9]+1;

最终dp[12]= 3种case的最小值。

代码

class Solution {
    public int numSquares(int n) {
        ArrayList<Integer> al= new ArrayList();
        for(int i =1;i*i<=n;i++){
            al.add(i*i);
        }
        int [] dp = new int[n+1];
        dp[0]=0;
        for(int i =1;i<=n;i++){
            dp[i]=Integer.MAX_VALUE;
            for(int j =0;j<al.size();j++){
                int temp =al.get(j);
                if(temp>i){
                    break;
                }
                if(dp[i-temp]+1<dp[i]){
                    dp[i]=dp[i-temp]+1;
                }
            }
        }
        
        return dp[n];
    }
}

2018-10-19

leetcode-判断子序列（392）

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1:
s = "abc", t = "ahbgdc"

返回 true.

示例 2:
s = "axc", t = "ahbgdc"

返回 false.

代码

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s==null || t==null){
            return false;
        }
        int i =0, j =0;
        int sLen=s.length();
        int tLen=t.length();
        while (i<sLen && j < tLen){
            char temps=s.charAt(i);
            char tempt=t.charAt(j);
            if(temps==tempt){
                i++;
            }
            j++;
        }
        return i==sLen;
    }
}

2018-10-15

Android - https

https 是什么？

https是更安全的http协议（http+ssl）

ssl是加密相关的协议

https做什么？

假设在通信过程中需要传递一些敏感信息（用户名，密码等），如果使用http那么这些信息被截获之后，因为http是明文传递，所以就会出现信息泄露的问题。

为了解决这类问题，就出现了https。

https怎么做？

准备工作：

服务器需要有ca证书；这个证书需要向特定的组织申请，比如：GlobalSign，GeoTrust等，这个证书实质上是一个public key + 一个private key；我们可以把public key比作一把锁，那么private key就是这把锁的钥匙。

另外这些组织生成的证书会被加到chrome，火狐等浏览器的信任证书列表中。

ps：这个锁跟钥匙还是比较贵的，一年大概6000块。。

https://common-buy.aliyun.com/?spm=5176.7968328.231195..4366815bhOY8tI&commodityCode=cas#/buy

具体流程

准备工作完成之后，我们的服务端就有了一把锁跟一个钥匙

chrome中输入www.baidu.com
服务器返回百度的证书（public key（包含百度公司相关的信息等等）也就是“锁”）
chrome查看信任列表中是否有该证书（public key ）
如果没有，提示https warning；结束
如果有，那么chrome生成一个随机串，用服务器给的“锁”把该随机串锁上，之后给到服务器
服务器拿到数据使用“钥匙”打开”锁”，获取到随机串
到这里chrome跟服务器就有了一段相同的字符串
服务器拿到response之后用该字符串加密之后返回给chrome
chrome根据该字符串解密之后拿到数据
done。。

细节：

http 80 https 443
http 免费 https：要买锁，付费

参考：

https://juejin.im/entry/58d7635e5c497d0057fae036

https://blog.csdn.net/lmj623565791/article/details/48129405

https://www.jianshu.com/p/ca7df01a9041

2018-10-12

leetcode-回文子串(647)

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

1
2
3

输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

示例 2:

1
2
3

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

思路：

动态规划：考虑已知前i长度的字符串的回文子串的个数，加一个数之后如何判断，具体看代码。

代码：

class Solution {
    public int countSubstrings(String s) {
        if(s==null||s.length()<=0){
            return 0;
        }
        int len = s.length();
        int [] re = new int[len];
        re[0]=1;
        for(int i =1;i<len;i++){
            int count =1;
            char c=s.charAt(i);
            for(int j=0;j<i;j++){
                if(s.charAt(j)==c && isTrue(s.substring(j,i+1))){
                    count++;
                }
            }
            re[i]=re[i-1]+count;
        }
        return re[len-1];
    }
    
    public boolean isTrue(String s){
        int length = s.length();
        int start=0;
        int end=length -1;
        while(start<=end){
            if(s.charAt(start)==s.charAt(end)){
                start++;
                end--;
            }else{
                return false;
            }
        }
        return true;
    }
}

2018-10-11

leetcode-等差数列划分(413)

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，以下数列为等差数列:

1
2
3

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

以下数列不是等差数列。

1	1, 1, 2, 5, 7

数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。

如果满足以下条件，则称子数组(P, Q)为等差数组：

元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

示例:

1
2
3

A = [1, 2, 3, 4]

返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

思路：

动态规划：假设已经知道了（a[0]~a[i+1]）的等差数组个数为re[i]，并且知道了以第i个数结尾的等差数组长度（beforeNumber）,计算(a[0]~a[i+2]))数组的等差数组个数，一共4种情况，具体看代码。

代码:

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int length =A.length;
        if(length<3){
            return 0;
        }
        int[] re=new int[length+1];
        re[0]=0;
        re[1]=0;
        re[2]=0;
        
        int beforeNumber=0;
        for(int i =3;i<length+1;i++){
            boolean isCurrentTrue=isTrue(A[i-1],A[i-2],A[i-3]);
            if(beforeNumber==0){
                if(isCurrentTrue){
                    re[i]=re[i-1]+1;
                    beforeNumber=3;
                }else{
                    re[i]=re[i-1];
                }
            }else{
                if(isCurrentTrue){
                    re[i]=re[i-1]+(beforeNumber-1);
                    beforeNumber++;
                }else{
                    re[i]=re[i-1];
                    beforeNumber=0;
                }
            }
        }
        return re[length];
    }
    
    public boolean isTrue(int a,int b ,int c){
        return (b-a)==(c-b);
    }
}

2018-10-11

Android-Arouter（调整人民日报结构）

背景

项目要求解耦各个模块，每个大模块可以作为一个单独的module。那么就需要解决如下问题：

跨模块跳转（A模块的act要跳转到B模块的act）
跨模块调用（A模块要使用B模块的数据）

最终选择了利用Arouter来解决如上问题。

ps（另外为了编译速度，是否每个module都可以单独运行？？？？？）

Arouter

官方文档：https://github.com/alibaba/ARouter/blob/master/README_CN.md

2018-09-28

Android- viewPager +fragment 实现懒加载

public abstract class LazyLoadFragment extends BaseLazyFragment {
    protected boolean isViewInitiated;
    protected boolean isVisibleToUser;
    protected boolean isDataInitiated;

    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        Bundle bundle = getArguments();
        if (bundle != null && bundle.size() > 0) {
            initVariables(bundle);
        }
    }

    protected abstract void initVariables(Bundle bundle);

    @Override
    public void onActivityCreated(Bundle savedInstanceState) {
        super.onActivityCreated(savedInstanceState);
        isViewInitiated = true;
        prepareFetchData();
    }

    @Override
    public void setUserVisibleHint(boolean isVisibleToUser) {
        super.setUserVisibleHint(isVisibleToUser);
        this.isVisibleToUser = isVisibleToUser;
        prepareFetchData();
        if (getUserVisibleHint()) {
            onVisible();
        } else {
            onInvisible();
        }
    }

    protected abstract void onVisible();
    protected abstract void onInvisible();
    protected abstract void onFirstVisible();

    @Override
    public void onHiddenChanged(boolean hidden) {
        super.onHiddenChanged(hidden);
        this.isVisibleToUser = !hidden;
        prepareFetchData();
        if (!hidden) {
            onVisible();
        } else {
            onInvisible();
        }
    }

    public abstract void fetchData();

    public boolean prepareFetchData() {
        return prepareFetchData(false);
    }

    public boolean prepareFetchData(boolean forceUpdate) {
        if (isVisibleToUser && isViewInitiated && (!isDataInitiated || forceUpdate)) {
            fetchData();
            isDataInitiated = true;
            onFirstVisible();
            return true;
        }
        return false;
    }
}