Android开发之广告开屏界面

发表于 2018-11-29

这个Demo是暑期实习时对安卓唯一的接触了（大概八月份），顺便也在这个博客里更一下吧。

项目地址：https://github.com/RebornC/AdLaunch

效果图如下所示。屏幕约3/4的上方用来放置广告图，1/4的下方放置该APP相关的图片，界面右上角有个显示3秒倒计时的按钮。点击广告图即打开广告链接进入相应界面（我使用了webView来装载），点击下方图片或者倒计时按钮则进入APP主界面，也可以什么都不做，等待界面3秒后自动跳转。

关于广告信息的获取，不会搭建后台的我偷懒使用EasyMock创建了一个简单的restful API，然后用Retrofit进行网络请求即可获得返回的数据，结构大致如下：

简单谈谈我的设计思路：每一次启动APP时都是先显示本地已存储的广告信息，然后再检测有没有广告版本有没有更新，有则重新下载并存储到本地，等下一次启动时即可显示最新广告，这样能够避免网络请求与图片加载的缓慢，从而提高用户体验。

具体实现看代码吧挺简单的。
最后再放一张点击广告图进入相应链接的效果动图，有点糊嘿嘿 > <

Android自定义侧滑抽屉菜单

发表于 2018-11-28

项目地址：https://github.com/RebornC/SlidingMenu

预览图

界面布局

传统的抽屉菜单一般采取DrawerLayout+Toolbar+NavigationView的布局组合。而为了使菜单栏界面设计更加自由，这儿使用自定义布局来代替NavigationView。在设计布局之前，先在styles.xml中将“DarkActionBar”改为“NoActionBar”，删去标题栏，然后待会我们用Toolbar替代。

1	<style name="AppTheme" parent="Theme.AppCompat.Light.NoActionBar">

接着开始写我们的主界面，采取Material Design的DrawerLayout布局。
activity_main.xml

<?xml version="1.0" encoding="utf-8"?>
<android.support.v4.widget.DrawerLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    android:id="@+id/drawer_layout"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:background="@color/white">

    <android.support.v7.widget.CardView
        android:id="@+id/card_view"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        app:cardCornerRadius="0dp"
        app:cardElevation="20dp">

        <android.support.constraint.ConstraintLayout
            android:layout_width="match_parent"
            android:layout_height="match_parent">

            <android.support.v7.widget.Toolbar
                android:id="@+id/toolbar"
                android:fitsSystemWindows="true"
                android:layout_width="match_parent"
                android:layout_height="wrap_content" />

            <FrameLayout
                android:id="@+id/content_view"
                android:layout_width="match_parent"
                android:layout_height="match_parent"
                app:layout_constraintTop_toBottomOf="@+id/toolbar"/>

        </android.support.constraint.ConstraintLayout>

    </android.support.v7.widget.CardView>

    <fragment
        android:id="@+id/nav_view"
        android:name="com.example.yc.androidsrc.MenuFragment"
        android:layout_gravity="start"
        android:layout_width="match_parent"
        android:layout_height="match_parent" />

</android.support.v4.widget.DrawerLayout>

DrawerLayout布局下的第一个子视图表示主内容视图，我将其嵌套在一个CardView里面，主要是为了当拉开菜单时，主内容视图的边缘能呈现出卡片式的圆角和阴影。主内容视图主要包括Toolbar和FrameLayout，其中FrameLayout用以动态加载各个菜单选项所对应的fragment。

DrawerLayout布局下的第二个子视图表示菜单栏视图，我们使用静态加载fragment的方式来呈现界面内容，其中android:layout_gravity="start"表示抽屉菜单是从左边拉开，而end则表示右边。

菜单布局不详说了。不过菜单选项的ListView Item布局左边有个设置为透明的View，当该项被选中时才显示为黑色，充当“视觉标签”的作用。

菜单侧滑时的监听事件

我们主要实现的效果是：当滑动菜单时，主视图逐渐缩小，移至界面右边并呈现出卡片式的圆角与阴影，菜单栏视图逐渐放大并完整呈现在界面左边。

因此我们需要监听DrawerLayout的滑动事件，代码如下：

mDrawerLayout.addDrawerListener(new DrawerLayout.DrawerListener() {
    @Override
    public void onDrawerSlide(View drawerView, float slideOffset) {
        View mContent = mDrawerLayout.getChildAt(0);
        View mMenu = drawerView;
        float scale = 1 - slideOffset;
        float rightScale = 0.8f + scale * 0.2f;
        float leftScale = 0.5f + slideOffset * 0.5f;
        mMenu.setAlpha(leftScale);
        mMenu.setScaleX(leftScale);
        mMenu.setScaleY(leftScale);
        mContent.setPivotX(0);
        mContent.setPivotY(mContent.getHeight() * 1/2);
        mContent.setScaleX(rightScale);
        mContent.setScaleY(rightScale);
        mContent.setTranslationX(mMenu.getWidth() * slideOffset);
    }

    @Override
    public void onDrawerOpened(View drawerView) {
        cardView.setRadius(20);
    }

    @Override
    public void onDrawerClosed(View drawerView) {
        cardView.setRadius(0);
    }

    @Override
    public void onDrawerStateChanged(int newState) {

    }
});

我们来分析一下：其中参数slideOffset代表此时菜单栏的滑动比例，数值为0~1。而在这个过程中，我希望主内容视图的尺寸从原本的1缩放至最后的0.8，因此我们可以得到一个很简单的线性函数，即主内容视图的尺寸Scale=0.8+(1-slideOffset)x0.2。同样的，我设置在这个过程中，菜单栏的尺寸由0.5扩大到1，因此它的尺寸线性函数为0.5+slideOffset*0.5。而此时主内容视图的右移尺寸刚好对应为菜单栏滑出来的宽度，因此设置为mContent.setTranslationX(mMenu.getWidth()xslideOffset)。另外关于主内容视图要从以哪个坐标点为中心进行缩放，可通过setPivot进行设置，我觉得从左边界的中间点进行缩放，效果会比较好看些。当然，以上这些数据你都可以自由设计，不同的数据得到的界面动态效果各有千秋。

主要的代码如下：

MainActivity.java

public class MainActivity extends AppCompatActivity {

    private DrawerLayout mDrawerLayout;
    private FrameLayout contentFrameLayout;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        mDrawerLayout = (DrawerLayout) findViewById(R.id.drawer_layout);
        mDrawerLayout.setScrimColor(Color.TRANSPARENT); // 菜单滑动时content不被阴影覆盖

        Toolbar toolbar = (Toolbar) findViewById(R.id.toolbar);
        setSupportActionBar(toolbar);
        getSupportActionBar().setTitle(""); // 不显示程序应用名
        toolbar.setNavigationIcon(R.drawable.ic_menu_black_24dp); // 在toolbar最左边添加icon
        toolbar.setNavigationOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                mDrawerLayout.openDrawer(GravityCompat.START);
            }
        });

        final CardView cardView = (CardView) findViewById(R.id.card_view);

        contentFrameLayout = (FrameLayout) findViewById(R.id.content_view);
        replaceFragment(new TabFragment1());

        // 监听抽屉的滑动事件
        mDrawerLayout.addDrawerListener(new DrawerLayout.DrawerListener() {
            @Override
            public void onDrawerSlide(View drawerView, float slideOffset) {
                View mContent = mDrawerLayout.getChildAt(0);
                View mMenu = drawerView;
                float scale = 1 - slideOffset;
                float rightScale = 0.8f + scale * 0.2f;
                float leftScale = 0.5f + slideOffset * 0.5f;
                mMenu.setAlpha(leftScale);
                mMenu.setScaleX(leftScale);
                mMenu.setScaleY(leftScale);
                mContent.setPivotX(0);
                mContent.setPivotY(mContent.getHeight() * 1/2);
                mContent.setScaleX(rightScale);
                mContent.setScaleY(rightScale);
                mContent.setTranslationX(mMenu.getWidth() * slideOffset);
            }

            @Override
            public void onDrawerOpened(View drawerView) {
                cardView.setRadius(20); // 拉开菜单时，主内容视图的边缘能呈现出卡片式的圆角和阴影
            }

            @Override
            public void onDrawerClosed(View drawerView) {
                cardView.setRadius(0); // 菜单关闭，圆角消失
            }

            @Override
            public void onDrawerStateChanged(int newState) {

            }
        });

    }

    public void replaceFragment(Fragment fragment) { // 动态加载fragment
        FragmentManager fragmentManager = getSupportFragmentManager();
        FragmentTransaction transaction = fragmentManager.beginTransaction();
        transaction.replace(R.id.content_view, fragment);
        transaction.addToBackStack(null);
        transaction.commit();
    }

}

至于菜单栏视图，主要是设置好每个选项的点击事件。这里我通过getActivity()强行获得MainActivity对象，然后再直接通过上面写好的replaceFragment()函数去动态加载对应的fragment，将所要的不同功能视图呈现在主视图中。

MenuFragment

public class MenuFragment extends Fragment {

    private ListView mListView;
    private List<MenuItem> menuItemList = new ArrayList<>();
    private MenuItemAdapter adapter;

    @Override
    public View onCreateView(LayoutInflater inflater, ViewGroup container,
                             Bundle savedInstanceState)
    {
        View navView = inflater.inflate(R.layout.activity_menu, container, false);
        mListView = (ListView) navView.findViewById(R.id.menu_list_view);
        mListView.setDivider(null); // 去掉分割线
        initListView();
        clickEvents();
        return navView;
    }

    public void initListView() {
        String[] data_zh = getResources().getStringArray(R.array.menu_zh);
        String[] data_en = getResources().getStringArray(R.array.menu_en);
        for (int i = 0; i < data_zh.length; i++) {
            MenuItem menuItem = new MenuItem(data_zh[i], data_en[i]);
            menuItemList.add(menuItem);
        }
        adapter = new MenuItemAdapter(getActivity(), R.layout.menu_list_item, menuItemList);
        mListView.setAdapter(adapter);
    }

    public void clickEvents() {
        mListView.setOnItemClickListener(new AdapterView.OnItemClickListener() {
            @Override
            public void onItemClick(AdapterView<?> parent, View view, int position, long id) {
                adapter.changeSelected(position); // 先定义好样式如何改变
                MainActivity activity = (MainActivity) getActivity();
                DrawerLayout mDrawerLayout = (DrawerLayout) activity.findViewById(R.id.drawer_layout);
                mDrawerLayout.closeDrawer(Gravity.START);
                switch (position) {
                    case 0:
                        activity.replaceFragment(new TabFragment1());
                        break;
                    case 1:
                        activity.replaceFragment(new TabFragment2());
                        break;
                    case 2:
                        activity.replaceFragment(new TabFragment3());
                        break;
                    case 3:
                        activity.replaceFragment(new TabFragment4());
                        break;
                    case 4:
                        activity.replaceFragment(new TabFragment5());
                        break;
                    default:
                        break;
                }
            }
        });

    }
}

沉浸式状态栏

可以看到效果图上的顶部状态栏为沉浸式，背景色与Toolbar一致并且字体为黑色（一般为白色）。

首先，应该明白各个版本的区别：要修改状态栏，Android版本至少要在4.4以上，并且在4.4是不能让状态栏透明的，只能达到一种半透明的阴影背景，而在5.x的版本中，是可以修改背景颜色但无法修改字体颜色的，只有在6.0以上是可以随意修改的。但是在魅族和小米第三方ROM在4.4版本以上的手机都提供了修改的接口。

这里就不详细展开了，具体怎么做，我觉得这两篇博客总结得比较好，放上地址：

https://blog.csdn.net/zephyr_g/article/details/53489320

https://www.jianshu.com/p/0acc12c29c1b

改进：避免fragment重复加载

2018/11/30 Debug

因为之前只是做了个小Demo，今天将其加入项目时，发现在每次切换菜单选项时，主视图内容所在的fragment都需要重新实例化，也就是运行OnCreatVIew()方法。这样就造成了很不好的用户体验。

如果fragment加载内容耗时，在弹出主视图时可能会有菜单滑动卡顿的现象。

每次重新加载，之前的内容进度消失，体验极其差劲。

之前我们是使用replace()方法来替换fragment，即把容器清空后再进行添加，因此需要重新走一遍新的fragment的生命周期，数据也需重新拉取。而改进的方式是使用add()－hide()－show()。add()即往容器添加fragment，新添加进来的fragment都是可见的（visible），后添加的fragment会展示在先添加的fragment上面，在绘制界面的时候会绘制所有可见的view，因此我们需要利用hide()等方法来避免重叠。切换时，判断该fragment是否已经存在容器中，如果是的话，则hide()当前fragment，则show()该传进来的fragment；如果不存在的话，则先add()后再重复刚刚的步骤。

/**
* 切换主视图的fragment，避免重复实例化加载
* @param position
*/
public void switchFragment(int position) {
    Fragment fragment = tabFragments.get(position);
    if (currentFragment != fragment) {
        FragmentManager fragmentManager = getSupportFragmentManager();
        FragmentTransaction transaction = fragmentManager.beginTransaction();
        if (fragment.isAdded()) {
            transaction.hide(currentFragment)
                    .show(fragment)
                    .commit();
        } else {
            transaction.hide(currentFragment)
                    .add(R.id.content_view, fragment)
                    .commit();
        }
        currentFragment = fragment;
    }
}

如果想要从源码角度了解replace()、add()两者之间的区别，可以参考下面这篇博客。

https://www.jb51.net/article/103489.htm

Android自定义控件之GifView

发表于 2018-11-19

最近的项目需要在主界面显示Gif动图，于是查了一下资料，一般是使用开源框架 Glide 或 android-gif-drawable ，前者加载速度较慢，并且没有单独的Gif播放与暂停接口，后者使用JNI加载，不会出现OOM问题，速度更快，性能更优。

由于我对自定义控件这方面了解不深，所以想趁这个机会刚好学习一下，自己写一个可以流畅显示Gif动图并能控制播放的GifView控件。

自定义控件一般有以下三种方式：

组合原生控件

使用几个基本控件组合在一起，形成一个新的控件。这种方式通常都需要继承一个合适的 ViewGroup，再给它添加指定功能的控件，形成新的空间。通过这种方式创建的控件我们还可以给它指定一些可配置的属性，增强它的可操控性。比如很多应用中普遍使用的标题栏控件。
继承原生控件

继承已有的控件，创建新控件，保留继承的父控件的特性，并且还可以引入新特性。
重写：自绘控件

如果继承原生控件或者是组合原生控件都不能满足我们的特殊需求，这种时候就只能够自己重头写一个全新的控件了。创建一个全新的 View 重点在于绘制和交互的部分，通常需要继承 View 类，并重写 onDraw() 、onMeasure() 等方法，还可以像刚才的组合控件一样，引入自定义属性来丰富控件的可控性。

实践内容参考此链接，这里不再赘述。

而这一次的GifView自定义控件则采取第三种方式：自绘。

首先我们先了解Android自带的类：android.graphics.Movie。它管理着Gif动画中的多个帧，可以将其加载并播放，我们只要换算好时间关系，通过setTime()让它在draw()的时候绘制出对应的帧图像，即可实现Gif播放的效果。

在动手之前，先通过官网文档了解 android.graphics.Movie 这个类，要养成一种阅读官方资料或源码的习惯，在足够了解的基础上才能够更好地进行二次创造。

本来是想自己动手写的，但是发现Github上已经有人很好地实现了…所以我打算直接跟着他的代码进行讲解…（没错其实是我想偷懒orz）

这是源码地址：https://github.com/Cutta/GifView

首先，在res/values目录下添加自定义属性，进行属性配置：

attrs.xml

<?xml version="1.0" encoding="utf-8"?>
<resources>
    <declare-styleable name="GifView">
        <attr name="gif" format="reference" />
        <attr name="paused" format="boolean" />
    </declare-styleable>

    <declare-styleable name="CustomTheme">
        <attr name="gifViewStyle" format="reference" />
    </declare-styleable>
</resources>

如果你对自定义控件的属性配置不够了解，可以阅读博客1或者博客2。

然后，在继承View的基础上开始编写我们的GifView了。

GifView.class

package com.example.yc.androidsrc;

import android.annotation.SuppressLint;
import android.content.Context;
import android.content.res.TypedArray;
import android.graphics.Canvas;
import android.graphics.Movie;
import android.os.Build;
import android.support.annotation.Nullable;
import android.util.AttributeSet;
import android.view.View;

/**
 * 自定义控件，用于显示Gif动图
 * Created by yc on 2018/11/18.
 */

public class GifView extends View {

    private static final int DEFAULT_MOVIE_VIEW_DURATION = 1000; // 默认1秒

    private int mMovieResourceId;
    private Movie movie;

    private long mMovieStart;
    private int mCurrentAnimationTime;

    private float mLeft;
    private float mTop;

    private float mScale;
    
    private int mMeasuredMovieWidth;
    private int mMeasuredMovieHeight;

    private volatile boolean mPaused;
    private boolean mVisible = true;

    /**
     * 构造函数
     */
    public GifView(Context context) {
        this(context, null);
    }

    public GifView(Context context, AttributeSet attrs) {
        this(context, attrs, R.styleable.CustomTheme_gifViewStyle);
    }

    public GifView(Context context, AttributeSet attrs, int defStyle) {
        super(context, attrs, defStyle);

        setViewAttributes(context, attrs, defStyle);
    }

    @SuppressLint("NewApi")
    private void setViewAttributes(Context context, AttributeSet attrs, int defStyle) {
        
        // 从 HONEYCOMB(Api Level:11) 开始，必须关闭HW加速度才能在Canvas上绘制Movie
        if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.HONEYCOMB) {
            setLayerType(View.LAYER_TYPE_SOFTWARE, null);
        }
        // 从描述文件中读出Gif的值，绘制出Movie实例
        final TypedArray array = context.obtainStyledAttributes(attrs,
                R.styleable.GifView, defStyle, R.style.Widget_GifView);

        mMovieResourceId = array.getResourceId(R.styleable.GifView_gif, -1); // -1为默认值
        mPaused = array.getBoolean(R.styleable.GifView_paused, false);

        array.recycle();

        if (mMovieResourceId != -1) {
            movie = Movie.decodeStream(getResources().openRawResource(mMovieResourceId));
        }
    }

    /**
     * 设置Gif资源
     */
    public void setGifResource(int movieResourceId) {
        this.mMovieResourceId = movieResourceId;
        movie = Movie.decodeStream(getResources().openRawResource(mMovieResourceId));
        requestLayout();
    }

    /**
     * 获取Gif资源
     */
    public int getGifResource() {
        return this.mMovieResourceId;
    }

    /**
     * 播放
     */
    public void play() {
        if (this.mPaused) {
            this.mPaused = false;

            /**
             * 计算新的movie开始时间，使它从刚刚停止的帧重新播放
             */
            mMovieStart = android.os.SystemClock.uptimeMillis() - mCurrentAnimationTime;

            invalidate();
        }
    }

    /**
     * 暂停
     */
    public void pause() {
        if (!this.mPaused) {
            this.mPaused = true;

            invalidate();
        }

    }

    /**
     * 判断Gif动图当前处于播放还是暂停状态
     */
    
    public boolean isPaused() {
        return this.mPaused;
    }

    public boolean isPlaying() {
        return !this.mPaused;
    }

    @Override
    protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {

        if (movie != null) {
            int movieWidth = movie.width();
            int movieHeight = movie.height();

			/**
             * 计算水平方向上的扩展
			 */
            float scaleH = 1f;
            int measureModeWidth = MeasureSpec.getMode(widthMeasureSpec);

            if (measureModeWidth != MeasureSpec.UNSPECIFIED) {
                int maximumWidth = MeasureSpec.getSize(widthMeasureSpec);
                if (movieWidth > maximumWidth) {
                    scaleH = (float) movieWidth / (float) maximumWidth;
                }
            }

			/**
             * 计算竖直方向上的扩展
			 */
            float scaleW = 1f;
            int measureModeHeight = MeasureSpec.getMode(heightMeasureSpec);

            if (measureModeHeight != MeasureSpec.UNSPECIFIED) {
                int maximumHeight = MeasureSpec.getSize(heightMeasureSpec);
                if (movieHeight > maximumHeight) {
                    scaleW = (float) movieHeight / (float) maximumHeight;
                }
            }

			/**
             * 计算扩展规模
			 */
            mScale = 1f / Math.max(scaleH, scaleW);

            mMeasuredMovieWidth = (int) (movieWidth * mScale);
            mMeasuredMovieHeight = (int) (movieHeight * mScale);

            setMeasuredDimension(mMeasuredMovieWidth, mMeasuredMovieHeight);

        } else {
			/**
			 * Movie为空，设置最小可用大小
			 */
            setMeasuredDimension(getSuggestedMinimumWidth(), getSuggestedMinimumHeight());
        }
    }

    @Override
    protected void onLayout(boolean changed, int l, int t, int r, int b) {
        super.onLayout(changed, l, t, r, b);
		/**
		 * 计算距离，以便绘制动画帧
		 */
        mLeft = (getWidth() - mMeasuredMovieWidth) / 2f;
        mTop = (getHeight() - mMeasuredMovieHeight) / 2f;

        mVisible = getVisibility() == View.VISIBLE;
    }

    @Override
    protected void onDraw(Canvas canvas) {
        if (movie != null) {
            if (!mPaused) {
                updateAnimationTime();
                drawMovieFrame(canvas);
                invalidateView();
            } else {
                drawMovieFrame(canvas);
            }
        }
    }


    @SuppressLint("NewApi")
    private void invalidateView() {
        if (mVisible) {
            if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.JELLY_BEAN) {
                postInvalidateOnAnimation();
            } else {
                invalidate();
            }
        }
    }

    /**
     * 计算当前动画时间
     */
    private void updateAnimationTime() {
        long now = android.os.SystemClock.uptimeMillis();
        // 如果是第一帧，记录起始时间
        if (mMovieStart == 0) {
            mMovieStart = now;
        }
        // 取出动画的时长
        int dur = movie.duration();
        if (dur == 0) {
            dur = DEFAULT_MOVIE_VIEW_DURATION;
        }
        // 算出需要显示第几帧
        mCurrentAnimationTime = (int) ((now - mMovieStart) % dur);
    }

    /**
     * 绘制当前要显示的Gif帧
     */
    private void drawMovieFrame(Canvas canvas) {

        movie.setTime(mCurrentAnimationTime);

        canvas.save(Canvas.MATRIX_SAVE_FLAG);
        canvas.scale(mScale, mScale);
        movie.draw(canvas, mLeft / mScale, mTop / mScale);
        canvas.restore();
    }

    @SuppressLint("NewApi")
    @Override
    public void onScreenStateChanged(int screenState) {
        super.onScreenStateChanged(screenState);
        mVisible = screenState == SCREEN_STATE_ON;
        invalidateView();
    }

    @SuppressLint("NewApi")
    @Override
    protected void onVisibilityChanged(View changedView, int visibility) {
        super.onVisibilityChanged(changedView, visibility);
        mVisible = visibility == View.VISIBLE;
        invalidateView();
    }

    @Override
    protected void onWindowVisibilityChanged(int visibility) {
        super.onWindowVisibilityChanged(visibility);
        mVisible = visibility == View.VISIBLE;
        invalidateView();
    }

}

使用方式：

直接在xml布局文件中设置该控件的gif属性指向哪个资源

1
2
3

<com.example.yc.androidsrc.GifView
        app:gif="@drawable/rain"
        ... />

在activity中通过setGifResource(int movieResourceId)进行设置

1 2	final GifView gifV = (GifView) findViewById(R.id.gifV); gifV.setGifResource(R.drawable.rain);

效果图（录制屏幕后再转成Gif导致有点失真了orz 勉强看看）：

堆排序与海量TopK问题

发表于 2018-11-15

排序算法是个老生常谈的问题，笔试要考，面试也问，不过翻来覆去也就那几个花样吧。大概理解一下各个算法的原理，记下表格里的数据，然后再试试手撕代码，基本上就没问题了。

从表格里可以看出，堆排序是一个时间和空间复杂度都比较优秀的算法，至于它的原理，看懂是肯定能轻易看懂的，但是我总觉得如果你不自己亲手写一遍，就很容易忘记。并且，用递归的话，代码也是很简短的，还没写过的同学，不妨自己试着敲一下吧hhh。

因为太久没写博客了觉得不能这么颓废下去，所以今天打算好好整理堆排序的相关知识点，同时讲一下面试时经常会被问到的TopK问题。

堆排序

1. 什么是堆

堆（heap）是一种数据结构，也被称为优先队列（priority queue）。队列中允许的操作是先进先出（FIFO），在队尾插入元素，在队头取出元素。而堆也是一样，在堆底插入元素，在堆顶取出元素，但是堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的。这个优先顺序可以是元素的大小或者其他规则。
而二叉堆是一种特殊的堆，它是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。如下图。

2. 堆排序的原理

堆排序（HeapSort）是指利用堆这种数据结构所设计的一种排序算法。它的关键在于建堆和调整堆。步骤主要如下：

创建一个堆；

把堆首（最大值）和堆尾互换；

把堆的尺寸缩小1，并调整堆，把新的数组顶端数据调整到相应位置；

重复步骤 2，直到堆的尺寸为1，此时排序结束。

当然，光看文字肯定不能很直观地理解，我们跟着图示来学习吧。
现在，我们有一个待排序的数组 {2, 4, 3, 7, 5, 8}，我们通过构建最大堆的方法来排序。

步骤说明如下：
1. 将待排序的数组视作完全二叉树，按层次遍历。
2. 找到二叉树的最后一个非叶子节点，也就是最后一个节点的父节点。即是 (len-1)/2 索引在的位置。如果其子节点的值大于其本身的值，则把它和较大子节点进行交换，即将数字3和8交换。如果并没有子节点大于它，则无需交换。
3. 循环遍历，继续处理前一个节点，由于此时 4<7 ，因此再次交换。
4. 循环遍历，继续处理前一个节点，由于此时 2<8 ，因此再次交换。注意：如果某个节点和它的某个子节点交换后，该子节点又有子节点，系统还需要再次对该子节点进行判断，做相同处理。
5. 遍历完成后得到一个最大堆。将每次堆排序得到的最大元素与当前规模的数组最后一个元素（假设下标为i）交换，然后再继续调整前 i - 1 的数组。遍历终止之后，得到一个自小到大的排序数组。

C++代码实现如下

void adjust(vector<int> &arr, int index, int len) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int max_index = index;
    if (left < len && arr[left] > arr[max_index]) max_index = left;
    if (right < len && arr[right] > arr[max_index]) max_index = right;
    if (max_index != index) {
        swap(arr[max_index], arr[index]);
        adjust(arr, max_index, len); // 继续调整子节点
    }
}
void heapSort(vector<int> &arr, int len) {
    // 将数组进行堆排序
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjust(arr, i, len);
    }
    // 将每次堆排序得到的最大元素与当前规模的数组最后一个元素交换
    for (int i = len - 1; i >= 1; i--) {
        swap(arr[0], arr[i]);
        adjust(arr, 0, i);
    }
}

海量TopK问题

剑指Offer有这样一道题，求最小的K个数，题目描述：输入n个整数，找出其中最小的K个数。例如输入 4，5，1，6，2，7，3，8 这8个数字，则最小的4个数字是 1，2，3，4。
而在面试的时候，我们也可能遇到这样的问题：有一亿个浮点数，如何找出其中最大的10000个？

这类问题我们把称为TopK问题：指从大量数据（源数据）中获取最大（或最小）的K个数据。

最容易想到的方法当然是全部排序再进行查找，然而时间复杂度怎么也要O(nlog₂n)，当n极其大时，该算法占用的内存也emmm。而我们题目所要求返回的只是前K个数据，所以没必要全部排序，做那么多无用功。我们可以先取下标 0~k-1 的局部数组，用它来维护一个大小为K的数组，然后遍历后续的数字，进行比较后决定是否替换。这时候堆排序就派上用场了。我们可以将前K个数字建立为一个最小（大）堆，如果是要取最大的K个数，则在后续遍历中，将数字与最小堆的堆顶数字进行比较，若比它大，则进行替换，然后再重新调整为最大堆。整个过程直至所有数字遍历完为止。时间复杂度为O(n*log₂K)，空间复杂度为K。

C++代码实现如下

class Solution {
public:
    void adjust(vector<int> &arr, int index, int len) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int max_index = index;
        if (left < len && arr[left] > arr[max_index]) max_index = left;
        if (right < len && arr[right] > arr[max_index]) max_index = right;
        if (max_index != index) {
            swap(arr[max_index], arr[index]);
            adjust(arr, max_index, len);
        }
    } 

    void heapSort(vector<int> &arr, int len) {
        for (int i = len / 2 - 1; i >= 0; i--) {
            adjust(arr, i, len);
        }
    //    for (int i = len - 1; i >= 1; i--) {
    //        swap(arr[0], arr[i]);
    //        adjust(arr, 0, i);
    //    }
    }

    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if (k <= 0 || k > input.size()) {
            vector<int> nullVec;
            return nullVec;
        }
        // 因为要取最小的k个数，所以取前k个数字构建一个最大堆
        // 相反，如果是取最大的k个数，则构建一个最小堆
        vector<int> sortedArray(input.begin(), input.begin() + k);
        heapSort(sortedArray, k);
        // 将后面的数字与这个构建好的二叉堆进行比较 
        for (int i = k; i < input.size(); i++) {
            if (input[i] < sortedArray[0]) {
                sortedArray[0] = input[i];
                adjust(sortedArray, 0, k);
            }
        }
        for (int i = k - 1; i >= 1; i--) {
            swap(sortedArray[0], sortedArray[i]);
            adjust(sortedArray, 0, i);
        }
        return sortedArray;
    }
};

相似的TopK问题还有：

有10000000个记录，这些查询串的重复度比较高，如果除去重复后，不超过3000000个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请统计最热门的10个查询串，要求使用的内存不能超过1GB。

有10个文件，每个文件1GB，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。按照query的频度排序。

有一个1GB大小的文件，里面的每一行是一个词，词的大小不超过16个字节，内存限制大小是1MB。返回频数最高的100个词。

提取某日访问网站次数最多的那个IP。

10亿个整数找出重复次数最多的100个整数。

搜索的输入信息是一个字符串，统计300万条输入信息中最热门的前10条，每次输入的一个字符串为不超过255B，内存使用只有1GB。

有1000万个身份证号以及他们对应的数据，身份证号可能重复，找出出现次数最多的身份证号。

等等…

对于这类问题，比如上面第1个，可以先利用hash表将查询串存储并计数，然后再构建最小堆，将查询串的个数进行比较从而得到结果。核心思想都是一样的。

今天就先写到这里吧，困了睡觉去 Orz

IntelliJ IDEA 许可证过期重新激活的方法

发表于 2018-11-05

如果在启动或运行IntelliJ IDEA时弹出“Your license has expired”，即说明你的许可证已过期，需要重新进行激活。

1 首先你要修改下系统配置，打开计算机的hosts文件。

Windows路径：C:\Windows\System32\drivers\etc\hosts

Linux路径：/etc/hosts

然后将“0.0.0.0 account.jetbrains.com”添加到hosts文件中并保存。

2 进入这个网址：http://idea.lanyus.com/
获取注册码后将其复制到Activation Code中即可。

注意：如果不进行第1步，即没有修改hosts文件，那么输入注册码后仍会弹框提示“This license XXX has been cancelled”。

Hello World

发表于 2018-11-02

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment