leetcode刷題記錄(最新推薦)
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)，而是使用變量來標記，這里的主要思路是，利用第一行和第一列來記該行和該列有沒有0，因為第一行和第一列被用作標記，所以我們要先記錄下來，第一行和第一列有沒有0，通過兩個循環(huán)記錄下來，然后遍歷整個矩陣，如果一個位置是0，那么這個位置所在行的第一行，和第一列標為0；然后再通過一個循環(huán)，如果遍歷的位置的第一行或第一列為0那么該位置也為0；然后對第一行和第一列進行處理，如果標記的為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)建新的矩陣。我們先來使用一個矩陣來模擬一下過程：
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ī)律就是第一行的元素都跑到最后一列按順序從上到下排序，我們可以找到坐標的規(guī)律；
摸索到坐標之間的規(guī)律后，我們就要考慮實現(xiàn)題目中的使用原始的矩陣進行旋轉(zhuǎn)；
進行旋轉(zhuǎn)其實是四個元素進行交換位置，就比如四個邊角，就是順時針的交換位置，我們可以總結(jié)一下，四個邊角坐標之間的關(guān)系，然后進行交換位置，需要注意的是需要交換位置的元素有哪些，因為一下就是4個元素，我們需要進行篩選，根據(jù)每一行來看，不論奇數(shù)還是偶數(shù)，只要旋轉(zhuǎn)n/2的行數(shù)。根據(jù)每一列來看，如果是偶數(shù)比如說4列，那么我們只需要旋轉(zhuǎn)前面兩列就行，如果是奇數(shù)，比如說是5，那么除了1，2列還有第三列要單獨處理，所以說要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)，然后是按照對角線進行反轉(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ù)進行查找；
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;從右上角開始，如果當前值小于目標值就向下遍歷，因為下面的大，如果大于目標值就像左移。有點類似于二叉搜索樹，左邊是左子樹，下面是右子樹；
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é)點：
這里先用中間變量記錄cur。next，然后反轉(zhuǎn)指針，將指針指向前面的節(jié)點。
然后再使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;先將整個鏈表的數(shù)據(jù)加入到集合中，然后再利用雙指針進行判斷是否是回文子串；
第二種：
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)部的鏈表末尾進行比較；
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)存在了那么就可以說明這是一個環(huán)形鏈表，于是就返回true。如果一直都沒有重復(fù)的，遍歷結(jié)束就會返回false
解法2：使用快慢指針，快的走2格，慢的走一格，總會相遇的：
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;就是快慢指針，如果快指針和慢指針是一個元素說明是環(huán)形鏈表；為什么一定相遇呢：這是因為fast是走兩步，slow是走一步，其實相對于slow來說，fast是一個節(jié)點一個節(jié)點的靠近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;當出現(xiàn)重復(fù)的元素時就直接返回就行，返回的就是環(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)口與鏈表首部的距離；
相遇的時候s=nb，如果s走a步就是s+nb，正好到環(huán)口；
此時我們將快指針放在鏈表的首部，也走a步也會走到環(huán)口，所以當將快指針放到環(huán)口時只要快慢指針相遇就是環(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;由于輸入的兩個鏈表都是逆序存儲數(shù)字的位數(shù)的，因此兩個鏈表中同一位置的數(shù)字可以直接相加。
我們同時遍歷兩個鏈表，逐位計算它們的和，并與當前位置的進位值相加。具體而言，如果當前兩個鏈表處相應(yīng)位置的數(shù)字為 n1,n2，進位值為 carry，則它們的和為 n1+n2+carry；其中，答案鏈表處相應(yīng)位置的數(shù)字為 (n1+n2+carry)mod10，而新的進位值為 ⌊
10
n1+n2+carry⌋。
如果兩個鏈表的長度不同，則可以認為長度短的鏈表的后面有若干個 0 。
此外，如果鏈表遍歷結(jié)束后，有 carry>0，還需要在答案鏈表的后面附加一個節(jié)點，節(jié)點的值為 carry。
19-刪除鏈表中第n個元素：
題目：
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;
到此這篇關(guān)于leetcode刷題記錄(最新推薦)的文章就介紹到這了,更多相關(guān)leetcode刷題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
ChatGPT最近霸屏了,咱們也來玩玩,下面這篇文章主要給大家介紹使用ChatGPT輔助寫代碼的體驗,需要的朋友可以參考下2023-02-02
域名（Domain Name）是由字母、數(shù)字和連字符組成的字符串,用于標識互聯(lián)網(wǎng)上的計算機、服務(wù)或資源,通過映射到IP地址（如192.0.2.1）,讓人類能夠更方便地訪問網(wǎng)絡(luò)資源,在互聯(lián)網(wǎng)世界中,域名如同現(xiàn)實世界的門牌號碼,是連接用戶與數(shù)字資源的橋梁2025-04-04
一文助你搞懂參數(shù)傳遞原理解析(java、go、python、c++)
這篇文章主要介紹了多種語言參數(shù)傳遞原理解析(java、go、python、c++),本文通過實例圖文相結(jié)合給大家介紹的非常詳細，對大家的學(xué)習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-01-01
99%的程序員都會收藏的書單 你讀過幾本？用書籍來武裝你的大腦，拯救你的人生，還在等什么，速速收藏2017-11-11
這篇文章主要介紹了5個Linux平臺程序員最愛的開發(fā)工具匯總,程序最重要的工具就是源碼編輯器了,或者是一個全能的IDE,本文就羅列了5個Linux平臺最常用的編輯給大家,需要的朋友可以參考下2014-09-09
這篇文章主要介紹了一個30多年編程經(jīng)驗的程序員總結(jié),在我30多年的程序員生涯里,我學(xué)到了不少有用的東西,下面是我這些年積累的經(jīng)驗精華,需要的朋友可以參考下2014-09-09
今天用Typora因為升級了一下，所以需要激活雖然勉強能用，但是老是彈出激活頁面，很是苦惱，只能通過百度找方法進行解決一下了，下面跟隨小編看下Typora使用方法,需要的朋友可以參考下2022-04-04
基于Python和Java實現(xiàn)單詞計數(shù)(Word Count)
Spark框架也是MapReduce-like模型，采用“分治-聚合”策略來對數(shù)據(jù)分布進行分布并行處理，本文就來利用Spark實現(xiàn)單詞統(tǒng)計的功能，需要的可以參考一下2023-05-05
Kettle是一個實現(xiàn)ETL開發(fā)的一款開發(fā)工具，Spoon是Kettle工具提供的圖形化界面，它由Java開發(fā)，支持跨平臺運行，本文給大家分享Kettle下載與安裝配置教程，感興趣的朋友一起看看吧2022-11-11
Git是一個很強大的分布式版本控制系統(tǒng)。它不但適用于管理大型開源軟件的源代碼,管理私人的文檔和源代碼也有很多優(yōu)勢。 本文主要介紹了全網(wǎng)最全Git命令手冊，感興趣的可以了解一下2021-12-12