今天总结了下刷 leetCode 的学习方法
首先不要在 idea 设备上编译通过再写上去，应该自己先拿纸和笔写完再打上去。
其中在刷题的时候，一个一个专题的刷，切忌盲目乱刷。在写代码的时候应该先思考清楚：
- 容错处理有没有做
- 代码的简洁性
- 代码的更优化算法
这些都要在你打代码上去之前先想好，应该在纸和笔上面先写出来。
然后在解题的时候，首先应该考虑好：
该题的解题规律
该题的特殊情况
该题用什么数据结构
写完之后总分析，参考别人的思路。做笔记。
leetCode Array 专题
- 第一个问题
对于数组问题，一般比较多的是数组中的数字重复次数，比较问题。
那么对于这个数组中元素重复次数的比较，HashMap 这个数据结构有个很好的存储作用。
原因在于，它的键值对都有存储信息，况且寻找信息的中间环节被省略。
重点：
所以一般使用 HashMap.getOrDefault() 方法来判断该元素是否已经重复。
HashMap.getOrDefault() 主要是用来判断 HashMap 中是否已有该元素。
HashMap.put("a",HashMap.getOrDefault("a",0)+1); // 判断 hashMap 中是否已有以 “a” 为键的值，有便取出，没有便取为 0 。
但在今天看到了另外一个思路：
具体问题已经忘记了，但是要求还是找一个数组中是否有重复元素，而且该数组都为正数，要求最好是线性时间并且不用额外的存储空间。
节省了使用 HashMap 的存储空间。
Hashmap 的最重要方法就是 hash ，散列表。
对于不同索引上的相同元素，我们要实现这个散列表的思想。
也就是说，我们应该用一个相同的算法，让相同元素通过这个算法得到的结果是一样的，但是由于数组上的元素是有意义的，我们不能随意改变。但是我们可以改变
数字的正负值，这样的话，当判断某一个数为负数时,那么就可以判断已经是重复过的了。这个问题的核心就是，实现散列方法。让不同值得到不一样的结果，相同值得到相同的结果。
对于 n 个元素的数组：
for(int i = 0;i<n;i++){
int index = Math.abs(nums[i])-1;
if（nums[index]<0）{
list.add(index+1);
}
nums[index] = -nums[index];
}
- 第二个问题
Product of Array Except Self
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
该题目主要是在一个数组里面返回除了该位置上的数的其他数的乘积。
首先遇到这个问题时，我的最初想法是：
首先声明一个变量来存储这个数组上的所有数乘积；
然后再在每一个位置上除去该数。
但是我没有很好地考虑到，假如数组中有 0 元素 ，如果恰好在 除数是 0 元素，这便会出错。而且此时的乘数总积一定是 0，那么结果一定是不对的。
但是在 discuss 的一些讨论。一个很好的办法是：
由于每一个索引的数是由于该索引左右两边的所有数乘积。那么，可以将索引左边部分存储起来，索引右边存储起来，之后两部分相乘。
沿着这个思路，我们可以再想一下，对于最后一个索引来说，索引上的数字应该就是前边所有数的乘积，对于倒数第二个索引来说，索引上的数字应该就是前边所有数和最后一个数的乘积。
以此类推，我们基本可以得到，我们需要另外开辟一个数组来存储该数组上的对应索引前面的所有数乘积。
res[0] = 1;
for(int i=1;i<n;i++){
res[i]=res[i-1]*nums[i-1];
}
然后就是要计算右边乘积，为了方便计算，我们应该从右边开始计算右边的乘积。
for(int j=n-1;j>=0;j++){
res[j] = res[j]*right;
right = right*nums[i];
}
综合起来结果就是：
int[] Result(int[] nums){
int n = nums.length;
int[ ] res = new int[n];
res[0] = 1;
for(int i=1;i<n;i++){
res[i]=res[i-1]*nums[i-1];
}
int right =1;
for(int j=n-1;j>=0;j++){
res[j] = res[j]*right;
right = right*nums[i];
}
return res;
}
- 第三个问题
在一个数组中，找出数组中能组成三角形的数目有多少。
例如：{2,3,4,5,9}中，有 3 组数能组成三角形。
对于这一道题目，我原先的想法是使用通过递归算法。
但是 leetcode 上好像说是超出了限制时间，但是我觉得这个办法在其他问题上可能是好办法。
对于递归算法，我的想法就是怎样在这个数组里面任意取出 k 个数。
我是用了一个 List 来存储当前存储的数据的数量，当存储到 k 个数的时候就判断是否符合要求。然后每一次递归完成就表明这个结果已经完成，我们需要将这个数组中的最后一个数去掉并让他重新填充数据。
list.add(A[i]);
checkTriangle(A[],k,index+1);
list.remove(list.size()-1);
按着基本数据的填充方式是：
1,2,3 1,2,4 1,3,4 2,3,4
所以我们开启一个循环从指标处开始往下走:
for(int i=index;i<A.length,i++){
list.add(A[i]);
checkTriangle(A[],k,index+1);
list.remove(list.size()-1);
}
综合结果：
int count=0;
List<Integer> list = new ArrayList<>();
public int triangleNumber(int[] A){
checkTriangleNumber(A,3,0); //对于数组中能形成三角形的数组整理
return count;
}
public void checkTriangle(int[] A,int k,int index){
if(A.length<k)
return;
if(list.length==k){
if(list.get(0)+list.get(1)>list.get(2)&&Math.abs(list.get(0)-list.get(1))<list.get(2))
count++;
return;
}
for(int i=index;i<A.length,i++){
list.add(A[i]);
checkTriangle(A[],k,index+1);
list.remove(list.size()-1);
}
}
然后只要改变 k 值，基本也就可以生成数组的所有子数组。
对于生成子数组，还有一种是二进制格雷码法：
原理：对于一个数组生成子对象，我们可以将该数组全部看成是内容看成是二进制码，假如要取出数组中的某一个数，那么就是 1，否则就是 0 。这个的好处就是电脑是采用二进制存储数据的。
例如：对于 1101 我们让 0001跟 1101 进行与运算，由于最后一位都是 1，那么就是最后一个为取出。然后0001左移一位，变成 0010，然后再与 1101 进行与运算，那便没有取出。以此类推。
public void Solution(int[] A){
for(int i =0;i<2^A.length;i++){ //二进制数 0000,0001,0010 .....
resultPrint(A,i);
}
}
public void resultPrint(int[] A,int current){
int j =A.length;
for(int i=0;i<j;i++){
if(current&(1<<i)){
print(A[j]);
}
}
}
既然说到了生成子对象算法，那么想必也要了解一下的是生成全排列算法。
下面这篇文章我觉得解释得很清楚。
https://blog.csdn.net/u013309870/article/details/68941284
discuss 讨论：
该问题主要是为了算出该数组中符合三角形的组数。由于三角形的定义，两边之和大于第三边，两边之差小于第三边。那么首先，假如两个较小的数之和大于较大的数，那么肯定的就是两个较小的数之差小于较大的数。所以，第一步，我们要对这个数组进行排序。这也是预排序的思想。一次排序，多次使用。
而且，排序完了之后，还有更巧妙的点，设数组里面一个较大数为 k, 在比 k 小的所有数中，最小数设为 l ,最大数设为 r 。我们知道假如有一个数比 l 大，比 r 小。那么仍然是成立的。那么由于数组已经排好顺序，所以假如 l 跟 r 之和大于 k ，那么 l 与 r 之间的所有数加上 r 都成立。
public int triangleNumber(int[] A) {
Arrays.sort(A);
int count = 0, n = A.length;
for (int i=n-1;i>=2;i--) {
int l = 0, r = i-1;
while (l < r) {
if (A[l] + A[r] > A[i]) { // 比较大数中小 的最小数和最大数之后大于较大数
count += r-l; //最小数之上的所有数和最大数之和都符合
r--; //最大数往前减一
}
else l++; //最小数与最大数小于最大数，提高最小数
}
}
return count;
}
最后，最近看了关于 RecyclerView 万能适配器。觉得挺好用的，但是又不难，觉得没必要重新写一个博客。我就写在这里啦，会详细解释注释的，里面也包括也加载更多的一些代码。
GIF.gif
/** 设置多种类型的接口
* Created by ${Learning_Yeachlz} on 2018-04-01.
*/
public interface DiversitySupport { //这个接口主要是用来扩展多种类型的 viewType
int getViewType(int position); // 根据数据的位置返回不同的 type
int getLayoutId(int type); // 根据不同的 type 返回不同的 layout
}
/** 通用 viewHolder
* Created by ${Learning_Yeachlz} on 2018-04-01.
*/
public class ViewHolder extends RecyclerView.ViewHolder{
private View mItemView;
private SparseArray<View> mViewTree ; // SparseArray 与 HashMap 相似，也是键值对的形式，但是 key 固定为 Integer，访问效率比 HashMap 高。这样就不用每次都用 findViewById() 。
private ViewHolder(View itemView) {
super(itemView);
mViewTree = new SparseArray<>();
mItemView = itemView;
}
/** 根据 layoutId 返回不同 viewHolder
* @return
*/
public static ViewHolder getViewHolder(Context context, int layoutId, ViewGroup parent){
View view = LayoutInflater.from(context).inflate(layoutId,parent,false);
ViewHolder viewHolder = new ViewHolder(view);
return viewHolder;
}
/** 根据id 返回相应的 view
* @param viewId
* @return
*/
public View getView(int viewId){
View view = mViewTree.get(viewId); // 在 SparseArray 中找到是否有该 view 。
if (view==null){ 如果找不到该 view
View view1 = mItemView.findViewById(viewId);
mViewTree.put(viewId,view1); 存储该 view 的相关信息
return view1;
}else {
return view ;
}
}
/** 设置文本信息
* @param viewId
* @param s
*/
public void setText(int viewId,String s){
TextView textView = (TextView)getView(viewId);
textView.setText(s);
}
/**设置图片信息
* @param viewId
* @param resource
*/
public void setImagResource(int viewId ,int resource){
ImageView imageView = (ImageView)getView(viewId);
imageView.setImageResource(resource);
}
/** holder 内容的点击监听
* @param viewId
* @param onclickListener
*/
public void setOnClickListener(int viewId,View.OnClickListener onclickListener){
View view = getView(viewId);
onclickListener.onClick(view);
}
/** holder 内容的长按监听
* @param viewId
* @param onclickListener
*/public void setLongClickListener(int viewId,View.OnLongClickListener onLongClickListener){
View view = getView(viewId);
onLongClickListener.onLongClick(view);
}
}
/** 万能适配器 支持多种类型 viewHolder
* Created by ${Learning_Yeachlz} on 2018-04-01.
*/
public abstract class BaseAdapter<T> extends RecyclerView.Adapter<ViewHolder> {
protected DiversitySupport diversitySupport ;
protected Context mContext;
protected List<T> mDataList;
public BaseAdapter(Context context,List<T> mDataList,DiversitySupport diversitySupport){
mContext = context;
this.diversitySupport = diversitySupport;
this.mDataList = mDataList;
}
@Override
public ViewHolder onCreateViewHolder(ViewGroup parent, int viewType) {
int layoutId = diversitySupport.getLayoutId(viewType); //接口回调获得 layoutId
ViewHolder viewHolder = ViewHolder.getViewHolder(mContext, layoutId,parent);
return viewHolder;
}
@Override
public void onBindViewHolder(ViewHolder holder, int position) {
if (position!=mDataList.size()-1) {
convert(holder, position); // 抽象函数，设置内容
}
}
/** 抽象方法
* @param holder
* @param position
*/
public abstract void convert(ViewHolder holder,int position);
@Override
public int getItemViewType(int position) {
return diversitySupport.getViewType(position);
}
@Override
public int getItemCount() {
return mDataList==null?0:mDataList.size();
}
}
final List<String> list = new ArrayList<>();
for(int i=0;i<10;i++){
list.add("hhh");
}
final BaseAdapter baseAdapter = new BaseAdapter<String>(this, list, new DiversitySupport() {
@Override
public int getViewType(int position) {
if (position==list.size()-1) { //尾部加载更多的 type
return 0;
}else if (position%2==0) { // 根据不同位置设置不同 type
return 1;
}else {
return 2;
}
}
@Override
public int getLayoutId(int type) { //根据不同 type 设置不同 layout
if (type==1) {
return R.layout.item_rv_show_one;
}else if (type==2){
return R.layout.item_rv_show_two;
}else {
return R.layout.item_load_more;
}
}
})
{
@Override
public void convert(ViewHolder holder, int position) { //设置 viewHolder 里面的内容
holder.setText(R.id.text,list.get(position));
}
};
final LinearLayoutManager linearLayoutManager = new LinearLayoutManager(this);
recyclerView.addOnScrollListener(new RecyclerView.OnScrollListener() { //滑动监听函数
int lastVisibleItem =0;
@Override
public void onScrollStateChanged(RecyclerView recyclerView, int newState) {
super.onScrollStateChanged(recyclerView, newState);
if (newState == RecyclerView.SCROLL_STATE_IDLE && lastVisibleItem + 1 == baseAdapter.getItemCount()) { //RecyclerView 滑动到尾部的条件：当前状态处于滑动且已经滑动到最后一个。
recyclerView.postDelayed(new Runnable() {
@Override
public void run() {
for(int i=0;i<10;i++){
list.add("aaa");
}
baseAdapter.notifyItemRemoved(baseAdapter.getItemCount());// 将尾部加载 view 去掉
baseAdapter.notifyDataSetChanged();
}
},1000);
}
}
@Override
public void onScrolled(RecyclerView recyclerView, int dx, int dy) {
super.onScrolled(recyclerView, dx, dy);
lastVisibleItem = linearLayoutManager.findLastVisibleItemPosition();
}
});
recyclerView.setAdapter(baseAdapter);
recyclerView.setLayoutManager(linearLayoutManager);
}
对于数据集的更新，用 notifyDataSetChanged() 不是一个好的选择，因为他是每一次都是要从头开始进行 createViewHolder(),onBindViewHolder() 。但是对于数据集的更新，我们不需要那么做，在此我推荐一下 DiffUtil 的用法。适合解决这类问题。
网友评论