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;
}
