秋招算法刷题8

20240422

2.两数相加

时间复杂度O（max(m,n))，空间复杂度O（1）

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head=null,tail=null;int carry=0;while(l1!=null||l2!=null){int n1=l1!=null?l1.val:0;int n2=l2!=null?l2.val:0;int sum=n1+n2+carry;if(head==null){head=tail=new ListNode(sum%10);}else{tail.next=new ListNode(sum%10);tail=tail.next;}carry=sum/10;if(l1!=null){l1=l1.next;}if(l2!=null){l2=l2.next;}}if(carry>0){tail.next=new ListNode(carry);}return head;}

19.删除链表的倒数第N个节点

1.计算链表长度
时间复杂度O（n）空间复杂度O（1）

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy=new ListNode(0,head);int length=getLength(head);ListNode cur=dummy;for(int i=1;i<length-n+1;++i){cur=cur.next;}cur.next=cur.next.next;ListNode ans=dummy.next;return ans;}public int getLength(ListNode head){int length=0;while(head!=null){++length;head=head.next;}return length;}
}

2.双指针法
时间复杂度O（n）空间复杂度O（1）

public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy=new ListNode(0,head);ListNode first=head;ListNode second=dummy;for(int i=0;i<n;++i){first=first.next;}while(first!=null){first=first.next;second=second.next;}second.next=second.next.next;ListNode ans=dummy.next;return ans;}

24.俩两交换链表中的节点

1.递归
时间空间复杂度O（n）

class Solution {public ListNode swapPairs(ListNode head) {if(head==null||head.next==null){return head;}ListNode newHead=head.next;head.next=swapPairs(newHead.next);newHead.next=head;return newHead;}
}

2.迭代
时间复杂度O（n）,空间复杂度O（1）

public ListNode swapPairs(ListNode head) {ListNode dummyHead=new ListNode(0);dummyHead.next=head;ListNode temp=dummyHead;while(temp.next!=null&&temp.next.next!=null){ListNode node1=temp.next;ListNode node2=temp.next.next;temp.next=node2;node1.next=node2.next;node2.next=node1;temp=node1;}return dummyHead.next;}

20240423

138.随机链表的复制

1.回溯+哈希表
时间复杂度和空间复杂度O（n）

class Solution {Map<Node,Node> cacheNode=new HashMap<Node,Node>();public Node copyRandomList(Node head) {if(head==null){return null;}if(!cacheNode.containsKey(head)){Node headNew=new Node(head.val);cacheNode.put(head,headNew);headNew.next=copyRandomList(head.next);headNew.random=copyRandomList(head.random);}return cacheNode.get(head);}
}

2.迭代+节点拆分
时间O（n），空间O（1）

public Node copyRandomList(Node head) {if(head==null){return null;}for(Node node=head;node!=null;node=node.next.next){Node nodeNew=new Node(node.val);nodeNew.next=node.next;node.next=nodeNew;}for(Node node=head;node!=null;node=node.next.next){Node nodeNew=node.next;nodeNew.random=(node.random!=null)?node.random.next:null;}Node headNew=head.next;for(Node node=head;node!=null;node=node.next){Node nodeNew=node.next;node.next=node.next.next;nodeNew.next=(nodeNew.next!=null)?nodeNew.next.next:null;}return headNew;}

14.最长公共前缀

1.横向扫描

public String longestCommonPrefix(String[] strs) {if(strs==null||strs.length==0){return "";}String prefix=strs[0];int count=strs.length;for(int i=1;i<count;i++){prefix=longestCommonPrefix(prefix,strs[i]);if(prefix.length()==0){break;}}return prefix;}public String longestCommonPrefix(String str1,String str2){int length=Math.min(str1.length(),str2.length());int index=0;while(index<length&&str1.charAt(index)==str2.charAt(index)){index++;}return str1.substring(0,index);}
}

2.纵向扫描

public String longestCommonPrefix(String[] strs) {if(strs==null||strs.length==0){return "";}int length=strs[0].length();int count=strs.length;for(int i=0;i<length;i++){char c=strs[0].charAt(i);for(int j=1;j<count;j++){if(i==strs[j].length()||strs[j].charAt(i)!=c){return strs[0].substring(0,i);}}}return strs[0];}

给定一个 n，算出 1 到 n 的最小公倍数

public static BigInteger f(int n){int[] x = new int[n+1];for(int i=1; i<=n; i++) x[i] = i;for(int i=2; i<n; i++){for(int j=i+1; j<=n; j++){if(x[j] % x[i]==0)x[j]=x[j]/x[i];}}//解决大数相乘BigInteger m = BigInteger.ONE;for(int i=2; i<=n; i++){m = m.multiply(BigInteger.valueOf((long)x[i]));}return m;}

二叉树的前、中、后遍历

1.非递归
栈

https://www.bilibili.com/video/BV1GY4y1u7b2/?spm_id_from=pageDriver&vd_source=4bff775c9c6da7af76663b10f157a21f

2.递归

https://blog.csdn.net/loss_rose777/article/details/131399871

5.最长回文子串

1.动态规划
时间复杂度、空间O（n^2)

public String longestPalindrome(String s) {int len=s.length();if(len<2){return s;}int maxLen=1;int begin=0;boolean[][] dp=new boolean[len][len];for(int i=0;i<len;i++){dp[i][i]=true;}char[] charArray=s.toCharArray();for(int L=2;L<=len;L++){for(int i=0;i<len;i++){int j=L+i-1;if(j>=len){break;}if(charArray[i]!=charArray[j]){dp[i][j]=false;}else{if(j-i<3){dp[i][j]=true;}else{dp[i][j]=dp[i+1][j-1];}}if(dp[i][j]&&j-i+1>maxLen){maxLen=j-i+1;begin=i;}}}return s.substring(begin,begin+maxLen);}

2.中心扩展算法

class Solution {public String longestPalindrome(String s) {if(s==null||s.length()<1){return "";}int start=0,end=0;for(int i=0;i<s.length();i++){int len1=expandAroundCenter(s,i,i);int len2=expandAroundCenter(s,i,i+1);int len=Math.max(len1,len2);if(len>end-start){start=i-(len-1)/2;end=i+len/2;}}return s.substring(start,end+1);}public int expandAroundCenter(String s,int left,int right){while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){--left;++right;}return right-left-1;}
}

20.回文子串

class Solution {public int countSubstrings(String s) {if(s==null||s.length()==0){return 0;}int count=0;for(int i=0;i<s.length();++i){count+=countPalindrome(s,i,i);count+=countPalindrome(s,i,i+1);}return count;}private int countPalindrome(String s,int start,int end){int count=0;while(start>=0&&end<s.length()&&s.charAt(start)==s.charAt(end)){count++;start--;end++;}return count;}
}

605.种花问题

public boolean canPlaceFlowers(int[] flowerbed, int n) {int count=0;int m=flowerbed.length;int prev=-1;for(int i=0;i<m;i++){if(flowerbed[i]==1){if(prev<0){count+=i/2;}else{count+=(i-prev-2)/2;}if(count>=n){return true;}prev=i;}}if(prev<0){count+=(m+1)/2;}else{count+=(m-prev-1)/2;}return count>=n;}

20240426

136.只出现一次的数字

华为od面试题：我23年5月7日竟然写过这个题，但是我一年后面试时候还是不会。都不知道我是太笨了呢，还是没努力呢
(其余出现2次)

public int singleNumber(int[] nums) {int single=0;for(int num:nums){single^=num;}return single;}

137.只出现一次的数字（其余出现三次)

1.哈希表
时间空间都是O（n)

public int singleNumber(int[] nums) {Map<Integer,Integer> freq=new HashMap<Integer,Integer>();for(int num:nums){freq.put(num,freq.getOrDefault(num,0)+1);}int ans=0;for(Map.Entry<Integer,Integer> entry:freq.entrySet()){int num=entry.getKey(),occ=entry.getValue();if(occ==1){ans=num;break;}}return ans;}

2.遍历统计

public int singleNumber(int[] nums) {int[] counts=new int[32];for(int num:nums){for(int j=0;j<32;j++){counts[j]+=num&1;num>>>=1;}}int res=0,m=3;for(int i=0;i<32;i++){res<<=1;res|=counts[31-i]%m;}return res;}

260.只出现一次的数字III

1.哈希表

public static int singleNumber(int[] nums) {Map<Integer,Integer> freq=new HashMap<Integer,Integer>();for(int num:nums){//freq.put(num, freq.getOrDefault(num,0)+1);freq.put(num,freq.containsKey(num)?freq.get(num)+1:1);}int ans=0;for(Map.Entry<Integer,Integer> entry:freq.entrySet()){int num=entry.getKey(),occ=entry.getValue();if(occ==1){ans=num;break;}}return ans;}

2.位运算

public int[] singleNumber(int[] nums) {int xorsum=0;for(int num:nums){xorsum^=num;}int lowbit=xorsum&-xorsum;int[] ans=new int[2];for(int x:nums){ans[(x&lowbit)==0?0:1]^=x;}return ans;}