leetcode刷題記錄(最新推薦)

更新時(shí)間：2024年12月07日 11:22:05 作者：阿偉*rui

本文給大家分享的leetcode刷題記錄包括矩陣置0、螺旋矩陣、旋轉(zhuǎn)圖像、搜索二維矩陣、反轉(zhuǎn)鏈表、回文鏈表,每道題目提供了解答方法和思路,感興趣的朋友跟隨小編一起看看吧

day4 73：矩陣置0

題目：

我的答案：

ArrayList<Integer> x = new ArrayList<>();
ArrayList<Integer> y = new ArrayList<>();
for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[i].length; j++) {
        if (matrix[i][j]==0){
            x.add(i);
            y.add(j);
        }
    }
}
for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[i].length; j++) {
        if (x.contains(i)||y.contains(j)){
            matrix[i][j]=0;
        }
    }
}

使用集合記錄哪一行哪一列含有0，記錄下只后，再次遍歷矩陣，只要這一行出現(xiàn)0，那么全部就是0，列也是；

題解：

int m=matrix.length;
int n =matrix[0].length;
boolean x=false;boolean y =false;
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (matrix[i][0]==0){
            y=true;
        }
    }
}
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (matrix[0][j]==0){
            x=true;
        }
    }
}
for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        if (matrix[i][j]==0){
            matrix[i][0]=matrix[0][j]=0;
        }
    }
}
for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        if (matrix[i][0]==0||matrix[0][j]==0){
            matrix[i][j]=0;
        }
    }
}
if (x){
    for (int i = 0; i < n; i++) {
        matrix[0][i]=0;
    }
}
if (y){
    for (int i = 0; i < m; i++) {
        matrix[i][0]=0;
    }
}

題解不再使用額外的數(shù)據(jù)結(jié)構(gòu)，而是使用變量來標(biāo)記，這里的主要思路是，利用第一行和第一列來記該行和該列有沒有0，因?yàn)榈谝恍泻偷谝涣斜挥米鳂?biāo)記，所以我們要先記錄下來，第一行和第一列有沒有0，通過兩個(gè)循環(huán)記錄下來，然后遍歷整個(gè)矩陣，如果一個(gè)位置是0，那么這個(gè)位置所在行的第一行，和第一列標(biāo)為0；然后再通過一個(gè)循環(huán)，如果遍歷的位置的第一行或第一列為0那么該位置也為0；然后對第一行和第一列進(jìn)行處理，如果標(biāo)記的為0那么第一行或者第一列全部為0；

54：螺旋矩陣

答案：

int left=0;
    int right= matrix[0].length-1;
    int top=0;
    int bottom= matrix.length-1;
    ArrayList<Integer> res = new ArrayList<>();
    while (left<=right&&top<=bottom){
        for (int i = left; i <= right; i++) {
            res.add(matrix[top][i]);
        }
        top++;
        for (int j = top; j <=bottom ; j++) {
            res.add(matrix[j][right]);
        }
        right--;
        if (top<=bottom){
        for (int i = right; i >=left ; i--) {
            res.add(matrix[bottom][i]);
        } bottom--;
        }
        if (left<=right){
        for (int j = bottom; j >=top ; j--) {
                res.add(matrix[j][left]);
        }
            left++;}
    }
    return res;
}

從左到右，頂部一層遍歷完往下移一位，top++；從上到下，遍歷完右側(cè)往左移一位，right–；從右到左，判斷top <= bottom，即是否上下都走完了。遍歷完底部上移，bottom–；從下到上，判斷left <= right，遍歷完左側(cè)右移，left++；

48-旋轉(zhuǎn)圖像

題目要求不能創(chuàng)建新的矩陣。我們先來使用一個(gè)矩陣來模擬一下過程：

 int[][]copy=new int[n][n];
 for (int i = 0; i < n; i++) {
     for (int j = 0; j < n; j++) {
         copy[j][n-i-1]=matrix[i][j];
     }
 }
 for (int i = 0; i < n; i++) {
     for (int j = 0; j < n; j++) {
         matrix[i][j]=copy[i][j];
     }
 }

具體的規(guī)律就是第一行的元素都跑到最后一列按順序從上到下排序，我們可以找到坐標(biāo)的規(guī)律；

摸索到坐標(biāo)之間的規(guī)律后，我們就要考慮實(shí)現(xiàn)題目中的使用原始的矩陣進(jìn)行旋轉(zhuǎn)；

進(jìn)行旋轉(zhuǎn)其實(shí)是四個(gè)元素進(jìn)行交換位置，就比如四個(gè)邊角，就是順時(shí)針的交換位置，我們可以總結(jié)一下，四個(gè)邊角坐標(biāo)之間的關(guān)系，然后進(jìn)行交換位置，需要注意的是需要交換位置的元素有哪些，因?yàn)橐幌戮褪?個(gè)元素，我們需要進(jìn)行篩選，根據(jù)每一行來看，不論奇數(shù)還是偶數(shù)，只要旋轉(zhuǎn)n/2的行數(shù)。根據(jù)每一列來看，如果是偶數(shù)比如說4列，那么我們只需要旋轉(zhuǎn)前面兩列就行，如果是奇數(shù)，比如說是5，那么除了1，2列還有第三列要單獨(dú)處理，所以說要3列也就是n+1/2；

所以：

int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
    for (int j = 0; j < (n + 1) / 2; j++) {
        int temp=matrix[i][j];
        matrix[i][j]=matrix[n-j-1][i];
        matrix[n-j-1][i]=matrix[n-i-1][n-j-j];
        matrix[n-i-1][n-j-j]=matrix[j][n-i-1];
        matrix[j][n-i-1]=temp;
    }
}

然后就是第三種方法，第三種方法使用交換，旋轉(zhuǎn)90度我們可以找到規(guī)律就是先是上下翻轉(zhuǎn)，然后是按照對角線進(jìn)行反轉(zhuǎn)：

int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
    for (int j = 0; j < n; j++) {
        int temp=matrix[i][j];
        matrix[i][j]=matrix[n-i-1][j];
        matrix[n-i-1][j]=temp;
    }
}
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        int temp=matrix[i][j];
        matrix[i][j]=matrix[j][i];
        matrix[j][i]=temp;
    }
}

24-搜索二維矩陣||

題目：

答案：

這題直接遍歷搜索也能過；

然后可以優(yōu)化，比如適用二分查找對每一行數(shù)據(jù)進(jìn)行查找；

for (int[] ints : matrix) {
    int index = search(ints,target);
    if (index>=0){
        return true;
    }
}
return false;

public static int search(int[]matrix,int target){
    int left=0;
    int right=matrix.length;
    while (left<=right){
        int mid=(right-left)/2+left;
        if (matrix[mid]==target){
            return mid;
        }
        if (matrix[mid]>target){
            right=mid-1;
        }else {
            left=mid+1;
        }
    }
    return -1;
}

然后還可以從右上角開始檢索：

int m =0;
int n =matrix[0].length-1;
while (n>=0&&m<matrix.length){
    if (matrix[m][n]==target){
        return true;
    }
    if (matrix[m][n]>target){
        n--;
    }else {
        m++;
    }
}
return false;

從右上角開始，如果當(dāng)前值小于目標(biāo)值就向下遍歷，因?yàn)橄旅娴拇?，如果大于目?biāo)值就像左移。有點(diǎn)類似于二叉搜索樹，左邊是左子樹，下面是右子樹；

206-反轉(zhuǎn)鏈表

第一種：迭代：

ListNode pre=null;
  ListNode cur=head;
  while (cur!=null){
      ListNode temp=cur.next;
      cur.next=pre;
      pre=cur;
      cur=temp;
  }
  return pre;

這里需要使用虛擬頭節(jié)點(diǎn)：

這里先用中間變量記錄cur。next，然后反轉(zhuǎn)指針，將指針指向前面的節(jié)點(diǎn)。

然后再使pre=cur；

cur=temp

第二種：遞歸：

if (head==null||head.next==null){
    return head;
}
ListNode node = reverseList(head.next);
node.next.next=node;
node.next=null;
return node;

234：回文鏈表

題目：

第一種：雙指針：

List<Integer>res=new ArrayList<>();
 while (head!=null){
     res.add(head.val);
     head=head.next;
 }
 int l =0;
 int r=res.size()-1;
 while (l<r){
     if (res.get(l)!=res.get(r)){
         return false;
     }
     l++;
     r--;
 }
 return true;

先將整個(gè)鏈表的數(shù)據(jù)加入到集合中，然后再利用雙指針進(jìn)行判斷是否是回文子串；

第二種：

cur=head;
return reserve(head);

public boolean reserve(ListNode node){
    if (node!=null){
        if (!reserve(node.next)){
            return false;
        }
        if (cur.val!=node.val){
            return false;
        }
        cur=cur.next;
    }
    return true;
}

將鏈表放到外部，然后在函數(shù)內(nèi)部遞歸，使指針遍歷到鏈表的末尾，然后再拿外部的鏈表和內(nèi)部的鏈表末尾進(jìn)行比較；

141-環(huán)形鏈表

解法1：使用集合判斷是否相同：

 HashSet<ListNode> nodes = new HashSet<>();
 ListNode cur=head;
 while (cur!=null){
     if (!nodes.contains(cur)){
         nodes.add(cur);
     }else {
         return true;
     }
     cur=cur.next;
 }
 return false;

就是一直遍歷，一邊遍歷，一邊將鏈表的元素加入到集合中，如果發(fā)現(xiàn)加入的元素在集合中已經(jīng)存在了那么就可以說明這是一個(gè)環(huán)形鏈表，于是就返回true。如果一直都沒有重復(fù)的，遍歷結(jié)束就會(huì)返回false

解法2：使用快慢指針，快的走2格，慢的走一格，總會(huì)相遇的：

ListNode fast=head;
ListNode slow=head;
while (fast!=null&&fast.next!=null){
    fast=fast.next.next;
    slow=slow.next;
    if (fast==slow){
        return true;
    }
}
return false;

就是快慢指針，如果快指針和慢指針是一個(gè)元素說明是環(huán)形鏈表；為什么一定相遇呢：這是因?yàn)閒ast是走兩步，slow是走一步，其實(shí)相對于slow來說，fast是一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的靠近slow的，所以fast一定可以和slow重合。

142-環(huán)形鏈表||：

題目：

答案1：

通過集合：

HashSet<ListNode> nodes = new HashSet<>();
ListNode cur = head;
while (cur != null) {
    if (!nodes.contains(cur)) {
        nodes.add(cur);
    }else {
        return cur;
    }
    cur=cur.next;
}
return null;

當(dāng)出現(xiàn)重復(fù)的元素時(shí)就直接返回就行，返回的就是環(huán)形的入口元素；

答案2：快慢指針：

ListNode fast=head;
ListNode slow=head;
while (fast!=null&&fast.next!=null){
    fast=fast.next.next;
    slow=slow.next;
    if (fast==slow){
        break;
    }
}
if (fast==slow){
    fast=head;
    while (fast!=slow){
        fast=fast.next;
        slow=slow.next;
    }
    return fast;
}
return null;

在快慢指針重合之后：

我們來討論一下：f是快指針走的路程。s是慢指針走的路程；

f=s+nb。f=2s。----》s=nb。然后到洞口走的路程的可能是：a+nb；a是環(huán)口與鏈表首部的距離；

相遇的時(shí)候s=nb，如果s走a步就是s+nb，正好到環(huán)口；

此時(shí)我們將快指針放在鏈表的首部，也走a步也會(huì)走到環(huán)口，所以當(dāng)將快指針放到環(huán)口時(shí)只要快慢指針相遇就是環(huán)口的位置；

02-兩數(shù)相加

題目：

答案：

ListNode sentry = new ListNode(0);
ListNode cur = sentry;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
    int num1 = l1 != null ? l1.val : 0;
    int num2 = l2 != null ? l2.val : 0;
    int sum=num1+num2+carry;
    carry=sum/10;
    ListNode newNode=new ListNode(sum%10);
    cur.next=newNode;
    cur=newNode;
    if (l1!=null)l1=l1.next;
    if (l2!=null)l2=l2.next;
}
return sentry.next;

由于輸入的兩個(gè)鏈表都是逆序存儲(chǔ)數(shù)字的位數(shù)的，因此兩個(gè)鏈表中同一位置的數(shù)字可以直接相加。

我們同時(shí)遍歷兩個(gè)鏈表，逐位計(jì)算它們的和，并與當(dāng)前位置的進(jìn)位值相加。具體而言，如果當(dāng)前兩個(gè)鏈表處相應(yīng)位置的數(shù)字為 n1,n2，進(jìn)位值為 carry，則它們的和為 n1+n2+carry；其中，答案鏈表處相應(yīng)位置的數(shù)字為 (n1+n2+carry)mod10，而新的進(jìn)位值為 ⌊
10
n1+n2+carry

⌋。

如果兩個(gè)鏈表的長度不同，則可以認(rèn)為長度短的鏈表的后面有若干個(gè) 0 。

此外，如果鏈表遍歷結(jié)束后，有 carry>0，還需要在答案鏈表的后面附加一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的值為 carry。

19-刪除鏈表中第n個(gè)元素：

題目：

ListNode fast=head;
for (int i = 0; i < n; i++) {
    fast=fast.next;
}
ListNode head1=new ListNode(0);
head1.next=head;
ListNode slow=head1;
while (fast!=null){
    fast=fast.next;
    slow=slow.next;
}
slow.next=slow.next.next;
return head1.next;

24-兩兩交換鏈表的元素

題目：

if (head==null||head.next==null){
    return head;
}
ListNode head0=new ListNode(0);
ListNode pre=head0;
pre.next=head;
ListNode cur=head;
while (cur.next!=null){
    pre.next=cur.next;
    pre=cur;
  cur=cur.next;
   pre.next=cur.next;
   cur.next=pre;
   pre=cur;
   cur=cur.next;
}
return head0.next;