今天總結(jié)了下刷 leetCode 的學習方法
首先不要在 idea 設備上編譯通過再寫上去，應該自己先拿紙和筆寫完再打上去。
其中在刷題的時候南缓，一個一個專題的刷蛀骇，切忌盲目亂刷厌秒。在寫代碼的時候應該先思考清楚：
- 容錯處理有沒有做
- 代碼的簡潔性
- 代碼的更優(yōu)化算法
這些都要在你打代碼上去之前先想好，應該在紙和筆上面先寫出來擅憔。
然后在解題的時候鸵闪，首先應該考慮好：
該題的解題規(guī)律
該題的特殊情況
該題用什么數(shù)據(jù)結(jié)構(gòu)
寫完之后總分析，參考別人的思路暑诸。做筆記蚌讼。
leetCode Array 專題
- 第一個問題
對于數(shù)組問題，一般比較多的是數(shù)組中的數(shù)字重復次數(shù)个榕，比較問題篡石。
那么對于這個數(shù)組中元素重復次數(shù)的比較，HashMap 這個數(shù)據(jù)結(jié)構(gòu)有個很好的存儲作用西采。
原因在于凰萨，它的鍵值對都有存儲信息，況且尋找信息的中間環(huán)節(jié)被省略械馆。
重點：
所以一般使用 HashMap.getOrDefault() 方法來判斷該元素是否已經(jīng)重復胖眷。
HashMap.getOrDefault() 主要是用來判斷 HashMap 中是否已有該元素。
HashMap.put("a",HashMap.getOrDefault("a",0)+1); // 判斷 hashMap 中是否已有以 “a” 為鍵的值霹崎，有便取出珊搀，沒有便取為 0 。
但在今天看到了另外一個思路：
具體問題已經(jīng)忘記了尾菇，但是要求還是找一個數(shù)組中是否有重復元素境析，而且該數(shù)組都為正數(shù)，要求最好是線性時間并且不用額外的存儲空間错沽。
節(jié)省了使用 HashMap 的存儲空間簿晓。
Hashmap 的最重要方法就是 hash ，散列表千埃。
對于不同索引上的相同元素憔儿，我們要實現(xiàn)這個散列表的思想。
也就是說放可，我們應該用一個相同的算法谒臼，讓相同元素通過這個算法得到的結(jié)果是一樣的朝刊，但是由于數(shù)組上的元素是有意義的，我們不能隨意改變蜈缤。但是我們可以改變
數(shù)字的正負值拾氓，這樣的話，當判斷某一個數(shù)為負數(shù)時,那么就可以判斷已經(jīng)是重復過的了底哥。這個問題的核心就是咙鞍，實現(xiàn)散列方法。讓不同值得到不一樣的結(jié)果趾徽，相同值得到相同的結(jié)果续滋。
對于 n 個元素的數(shù)組：
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].
該題目主要是在一個數(shù)組里面返回除了該位置上的數(shù)的其他數(shù)的乘積。
首先遇到這個問題時孵奶，我的最初想法是：
首先聲明一個變量來存儲這個數(shù)組上的所有數(shù)乘積疲酌；
然后再在每一個位置上除去該數(shù)。
但是我沒有很好地考慮到了袁，假如數(shù)組中有 0 元素 朗恳，如果恰好在 除數(shù)是 0 元素，這便會出錯载绿。而且此時的乘數(shù)總積一定是 0粥诫，那么結(jié)果一定是不對的。
但是在 discuss 的一些討論卢鹦。一個很好的辦法是：
由于每一個索引的數(shù)是由于該索引左右兩邊的所有數(shù)乘積臀脏。那么，可以將索引左邊部分存儲起來冀自，索引右邊存儲起來揉稚，之后兩部分相乘。
沿著這個思路熬粗，我們可以再想一下搀玖，對于最后一個索引來說，索引上的數(shù)字應該就是前邊所有數(shù)的乘積驻呐，對于倒數(shù)第二個索引來說灌诅，索引上的數(shù)字應該就是前邊所有數(shù)和最后一個數(shù)的乘積。
以此類推含末，我們基本可以得到猜拾，我們需要另外開辟一個數(shù)組來存儲該數(shù)組上的對應索引前面的所有數(shù)乘積。
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];
}
綜合起來結(jié)果就是：
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;
}
- 第三個問題
在一個數(shù)組中，找出數(shù)組中能組成三角形的數(shù)目有多少盯仪。
例如：{2,3,4,5,9}中紊搪，有 3 組數(shù)能組成三角形。
對于這一道題目全景，我原先的想法是使用通過遞歸算法耀石。
但是 leetcode 上好像說是超出了限制時間，但是我覺得這個辦法在其他問題上可能是好辦法爸黄。
對于遞歸算法滞伟，我的想法就是怎樣在這個數(shù)組里面任意取出 k 個數(shù)。
我是用了一個 List 來存儲當前存儲的數(shù)據(jù)的數(shù)量馆纳，當存儲到 k 個數(shù)的時候就判斷是否符合要求诗良。然后每一次遞歸完成就表明這個結(jié)果已經(jīng)完成，我們需要將這個數(shù)組中的最后一個數(shù)去掉并讓他重新填充數(shù)據(jù)鲁驶。
list.add(A[i]);
checkTriangle(A[],k,index+1);
list.remove(list.size()-1);
按著基本數(shù)據(jù)的填充方式是：
1,2,3 1,2,4 1,3,4 2,3,4
所以我們開啟一個循環(huán)從指標處開始往下走:
for(int i=index;i<A.length,i++){
list.add(A[i]);
checkTriangle(A[],k,index+1);
list.remove(list.size()-1);
}
綜合結(jié)果：
int count=0;
List<Integer> list = new ArrayList<>();
public int triangleNumber(int[] A){
checkTriangleNumber(A,3,0); //對于數(shù)組中能形成三角形的數(shù)組整理
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 值，基本也就可以生成數(shù)組的所有子數(shù)組舞骆。
對于生成子數(shù)組钥弯，還有一種是二進制格雷碼法：
原理：對于一個數(shù)組生成子對象，我們可以將該數(shù)組全部看成是內(nèi)容看成是二進制碼督禽，假如要取出數(shù)組中的某一個數(shù)脆霎，那么就是 1，否則就是 0 狈惫。這個的好處就是電腦是采用二進制存儲數(shù)據(jù)的睛蛛。
例如：對于 1101 我們讓 0001跟 1101 進行與運算，由于最后一位都是 1胧谈，那么就是最后一個為取出忆肾。然后0001左移一位，變成 0010菱肖，然后再與 1101 進行與運算客冈，那便沒有取出。以此類推稳强。
public void Solution(int[] A){
for(int i =0;i<2^A.length;i++){ //二進制數(shù) 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 討論：
該問題主要是為了算出該數(shù)組中符合三角形的組數(shù)渠缕。由于三角形的定義，兩邊之和大于第三邊褒繁，兩邊之差小于第三邊亦鳞。那么首先，假如兩個較小的數(shù)之和大于較大的數(shù)，那么肯定的就是兩個較小的數(shù)之差小于較大的數(shù)蚜迅。所以舵匾，第一步，我們要對這個數(shù)組進行排序谁不。這也是預排序的思想坐梯。一次排序，多次使用刹帕。
而且吵血，排序完了之后，還有更巧妙的點偷溺，設數(shù)組里面一個較大數(shù)為 k, 在比 k 小的所有數(shù)中蹋辅，最小數(shù)設為 l ,最大數(shù)設為 r 。我們知道假如有一個數(shù)比 l 大挫掏，比 r 小侦另。那么仍然是成立的。那么由于數(shù)組已經(jīng)排好順序尉共，所以假如 l 跟 r 之和大于 k 褒傅，那么 l 與 r 之間的所有數(shù)加上 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]) { // 比較大數(shù)中小 的最小數(shù)和最大數(shù)之后大于較大數(shù)
count += r-l; //最小數(shù)之上的所有數(shù)和最大數(shù)之和都符合
r--; //最大數(shù)往前減一
}
else l++; //最小數(shù)與最大數(shù)小于最大數(shù)袄友，提高最小數(shù)
}
}
return count;
}
最后殿托，最近看了關于 RecyclerView 萬能適配器。覺得挺好用的剧蚣，但是又不難支竹，覺得沒必要重新寫一個博客。我就寫在這里啦鸠按，會詳細解釋注釋的礼搁，里面也包括也加載更多的一些代碼。
/** 設置多種類型的接口
* Created by ${Learning_Yeachlz} on 2018-04-01.
*/
public interface DiversitySupport { //這個接口主要是用來擴展多種類型的 viewType
int getViewType(int position); // 根據(jù)數(shù)據(jù)的位置返回不同的 type
int getLayoutId(int type); // 根據(jù)不同的 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;
}
/** 根據(jù) 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;
}
/** 根據(jù)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 內(nèi)容的點擊監(jiān)聽
* @param viewId
* @param onclickListener
*/
public void setOnClickListener(int viewId,View.OnClickListener onclickListener){
View view = getView(viewId);
onclickListener.onClick(view);
}
/** holder 內(nèi)容的長按監(jiān)聽
* @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); //接口回調(diào)獲得 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); // 抽象函數(shù)测蹲，設置內(nèi)容
}
}
/** 抽象方法
* @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) { // 根據(jù)不同位置設置不同 type
return 1;
}else {
return 2;
}
}
@Override
public int getLayoutId(int type) { //根據(jù)不同 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 里面的內(nèi)容
holder.setText(R.id.text,list.get(position));
}
};
final LinearLayoutManager linearLayoutManager = new LinearLayoutManager(this);
recyclerView.addOnScrollListener(new RecyclerView.OnScrollListener() { //滑動監(jiān)聽函數(shù)
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 滑動到尾部的條件：當前狀態(tài)處于滑動且已經(jīng)滑動到最后一個莹捡。
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);
}
對于數(shù)據(jù)集的更新，用 notifyDataSetChanged() 不是一個好的選擇扣甲，因為他是每一次都是要從頭開始進行 createViewHolder(),onBindViewHolder() 篮赢。但是對于數(shù)據(jù)集的更新齿椅，我們不需要那么做，在此我推薦一下 DiffUtil 的用法启泣。適合解決這類問題涣脚。
