• 【leetcode学习计划】算法入门（1 / 14）

    目录

    DAY1.二分查找 

    704.二分查找

    278.第一个错误版本

    ！35.搜索插入位置

    DAY2.双指针

    977.有序数组的平方

    189.轮转数组

    DAY3.双指针

    ！283.移动零

    ！167.两数之和 2 - 输入有序数组

    DAY4.双指针

    557.反转字符串中的单词3

    DAY5.双指针

    876.链表的中间结点

    19.删除链表的倒数第n个结点

    DAY6.滑动窗口

    3.无重复字符的最长子串

    unordered_set

    567.字符串的排列

    DAY7. DFS/BFS

    733.图像渲染

    方法一：dfs

    方法二：bfs 

    695.岛屿的最大面积

    方法一：dfs

     方法二：bfs

    DAY8.DFS/BFS

    617.合并二叉树

    ！116.填充每个节点的下一个右侧节点指针

    DAY9. DFS/BFS

    542.01矩阵

    994.腐烂的橘子

    DAY10.递归/回溯

    21.合并两个有序链表

    206.反转链表

    DAY11.递归/回溯

    77.组合

    46.全排列

    784.字母大小写全排列

    DAY12.动态规划

    70.爬楼梯

    198.打家劫舍

    120.三角形最小路径和

    DAY13.位运算

    231.2的幂

    191.位1的个数

     Integer.bitCount(n) 返回1的个数

    DAY14.位运算

    190.颠倒二进制位

     Integer.reverse(n); 反转

    136.只出现一次的数字

    DAY1.二分查找 

    704.二分查找

    力扣

    1. class Solution {
    2. public:
    3.     int search(vector<int>& nums, int target) {
    4.         int l=0,r=nums.size()-1;
    5.         while(l
    6.         {
    7.             int mid=l+r>>1;
    8.             if(nums[mid]>=target) r=mid;
    9.             else l=mid+1;
    10.         }
    11.         if(nums[l]!=target) return -1;
    12.         else return l;
    13.     }
    14. };

    278.第一个错误版本

    力扣

    直接mid = l+r >> 1会溢出，要改变一下，mid=l+(r-l) / 2

    1. class Solution {
    2. public:
    3.     int firstBadVersion(int n) {
    4.         int l=1,r=n;
    5.         while(l
    6.         {
    7.             int mid=l+(r-l)/2;
    8.             if(isBadVersion(mid)==true) r=mid;
    9.             else l=mid+1;
    10.         }
    11.         return l;
    12.     }
    13. };

    ！35.搜索插入位置

    力扣

    需要加个特判，如果这个数比最终查找位置大，返回位置应该+1

    如果比最终位置小，直接返回该数下标即可

    例如：1 3 5 6  插入0  输出：0

               1 3 5 6  插入7  输出：4

    1. class Solution {
    2. public:
    3.     int searchInsert(vector<int>& nums, int target) {
    4.         int l=0,r=nums.size()-1;
    5.         while(l
    6.         {
    7.             int mid=l+r+1>>1;
    8.             if(nums[mid]<=target) l=mid;
    9.             else r=mid-1;
    10.         }
    11.         if(nums[l]return l+1;
    12.         return l;
    13.     }
    14. };

    DAY2.双指针

    977.有序数组的平方

    力扣

    1. class Solution {
    2. public:
    3.     vector<int> sortedSquares(vector<int>& nums) {
    4.         int n=nums.size();
    5.         int l=0,r=n-1;
    6.         int cnt=n-1;
    7.         vector<int>res(n);
    8.         while(l<=r)
    9.         {
    10.             if(nums[l]*nums[l]>nums[r]*nums[r]) 
    11.                 res[cnt--]=nums[l]*nums[l],l++;
    12.             else res[cnt--]=nums[r]*nums[r],r--;
    13.         }
    14.         return res;
    15.     }
    16. };

    189.轮转数组

    力扣

    直接定位法

    1. class Solution {
    2. public:
    3.     void rotate(vector<int>& nums, int k) {
    4.         int n=nums.size();
    5.         vector<int>res(n);
    6.         for(int i=0;i
    7.             res[(i+k)%n]=nums[i]; 
    8.         nums=res;
    9.     }
    10. };

    翻转数组法：

    例如：1 2 3 4 5

    第一步先翻转整个数组 5 4 3 2 1

    第二步按k划分 5 4 3    2 1

    第三步各自翻转 3 4 5 1 2 

    1. class Solution {
    2. public:
    3.     void reverse(vector<int>& nums,int l,int r)
    4.     {
    5.         while(l
    6.         {
    7.             swap(nums[l],nums[r]);
    8.             l++;
    9.             r--;
    10.         }
    11.     }
    12.  
    13.     void rotate(vector<int>& nums, int k) {
    14.         int n=nums.size();
    15.         k%=n;
    16.         reverse(nums,0,n-1);
    17.         reverse(nums,0,k-1);
    18.         reverse(nums,k,n-1);
    19.     }
    20. };

    DAY3.双指针

    ！283.移动零

    力扣

    左指针指向为0的数

    右指针指向不为0的数

    1. class Solution {
    2. public:
    3.     void moveZeroes(vector<int>& nums) {
    4.         int n=nums.size();
    5.         int l=0,r=0;
    6.         while(r
    7.         {
    8.             if(nums[r]) swap(nums[l],nums[r]),l++;
    9.             r++;
    10.         }   
    11.     }
    12. };

    ！167.两数之和 2 - 输入有序数组

    力扣

    双指针法

    1. class Solution {
    2. public:
    3.     vector<int> twoSum(vector<int>& numbers, int target) {
    4.         int n=numbers.size();
    5.         int l=0,r=n-1;
    6.         while(l
    7.         {
    8.             if(numbers[l]+numbers[r]>target) r--;
    9.             else if(numbers[l]+numbers[r]
    10.             else return{l+1,r+1};
    11.         }
    12.         return {-1,-1};
    13.     }
    14. };

    二分法 

    可以先固定一个数i，再利用二分，在比i大的区间里找另一个数满足n[i]+n[l]==target

    1. class Solution {
    2. public:
    3.     vector<int> twoSum(vector<int>& numbers, int target) {
    4.         int n=numbers.size();
    5.         for(int i=0;i
    6.         {
    7.             int l=i+1,r=n-1;
    8.             while(l
    9.             {
    10.                 int mid=l+r>>1;
    11.                 if(numbers[i]+numbers[mid]>=target) r=mid;
    12.                 else l=mid+1;
    13.             }
    14.             if(numbers[i]+numbers[r]==target) return{i+1,r+1};
    15.         }
    16.         return {-1,-1};
    17.     }
    18. };

    DAY4.双指针

    557.反转字符串中的单词3

    力扣

    双指针法

    1. class Solution {
    2. public:
    3.     string reverseWords(string s) {
    4.         int n=s.size();
    5.         int l=0,r;
    6.         for(int i=0;i<=n;i++)
    7.             if(s[i]==' '||s[i]=='\0')
    8.             {
    9.                 for(r=i-1;r>l;r--,l++) swap(s[l],s[r]);
    10.                 l=i+1;
    11.             }
    12.         return s;
    13.     }
    14. };

    1. class Solution {
    2. public:
    3.     string reverseWords(string s) {
    4.         stringstream ss(s);
    5.         string str;
    6.         string res;
    7.         bool f=false;
    8.         while(ss>>str)
    9.         {
    10.             reverse(str.begin(),str.end());
    11.             if(f)res+=" ";
    12.             f=true;
    13.             res+=str;
    14.         }
    15.         return res;
    16.     }
    17. };

    DAY5.双指针

    876.链表的中间结点

    力扣

    暴力遍历

    先求链表长度 再找len/2的位置

    1. class Solution {
    2. public:
    3.     ListNode* middleNode(ListNode* head) {
    4.         int len=0;
    5.         ListNode *t=head;
    6.         while(t!=NULL)
    7.         {
    8.             len++;
    9.             t=t->next;
    10.         }
    11.         int i=0;
    12.         while(i2)
    13.         {
    14.             head=head->next;
    15.             i++;
    16.         }
    17.         return head;
    18.     }
    19. };

    快慢指针

    快指针一次走两步 慢指针一次走一步

    当快指针走到末尾时 慢指针恰好走到中间位置 

    • 奇数情况：如1 2 3 4 5 当慢指针在中点3时，快指针在5位置，即high->next=NULL
    • 偶数情况：如1 2 3 4 5 6 当慢指针在4时，快指针在6的后一位置，即high=NULL

    如果high指针满足以上两个条件的任意一个，则不需要移动指针，而返回慢指针

    1. class Solution {
    2. public:
    3.     ListNode* middleNode(ListNode* head) {
    4.         ListNode *slow=head,*high=head;
    5.         while(high!=NULL&&high->next!=NULL) 
    6.         {
    7.             high=high->next->next;
    8.             slow=slow->next;
    9.         }
    10.         return slow;
    11.     }
    12. };

    19.删除链表的倒数第n个结点

    力扣

    暴力遍历

    需要注意特判 链表长度为1 和 删除的是头结点的情况（即len==n）

    1. class Solution {
    2. public:
    3.     ListNode* removeNthFromEnd(ListNode* head, int n) {
    4.         int len=0;
    5.         ListNode *t=head;
    6.         while(t!=NULL)
    7.         {
    8.             t=t->next;
    9.             len++;
    10.         }
    11.         if(len==1||len==n) return head->next; //如果链表只有一个元素则返回NULL 如果要删除头结点 直接返回头结点之后的链表
    12.         ListNode *p=head,*q=NULL;
    13.         for(int i=1;inext;
    14.         q=p->next;
    15.         p->next=q->next;
    16.         return head;
    17.     }
    18. };

    快慢指针

    快指针先走n个结点 然后快慢指针同时走

    当快指针走到末尾时 慢指针恰好指向倒数第n个节点的前驱结点

    1. class Solution {
    2. public:
    3.     ListNode* removeNthFromEnd(ListNode* head, int n) {
    4.         if(head->next==NULL) return head->next; 
    5.         ListNode *high=head,*slow=head;
    6.         for(int i=0;inext;
    7.         if(!high) return head->next; //如果快指针指出范围 说明要删除的是头结点
    8.         while(high->next)
    9.         {
    10.             high=high->next;
    11.             slow=slow->next;
    12.         }
    13.         slow->next=slow->next->next;
    14.         return head;
    15.     }
    16. };

    DAY6.滑动窗口

    3.无重复字符的最长子串

    力扣

    unordered_set

    该容器中不包含重复元素

    mp.find() 查找对应元素，成功返回对应的迭代器，失败返回最后一个元素迭代器（即 mp.end() ）

    1. class Solution {
    2. public:
    3.     int lengthOfLongestSubstring(string s) {
    4.         if(s.size()==0) return 0;
    5.         int maxl=-1,l;
    6.         unordered_set<char>mp;
    7.         for(int i=0;isize();i++)
    8.         {
    9.             while(mp.find(s[i])!=mp.end())//如果在窗口中找到重复元素 则擦除左端 移动窗口
    10.             {
    11.                 mp.erase(s[l]);
    12.                 l++;
    13.             }
    14.             maxl=max(maxl,i-l+1);
    15.             mp.insert(s[i]);
    16.         }
    17.         return maxl;
    18.     }
    19. };

    567.字符串的排列

    力扣

    1. class Solution {
    2. public:
    3.     bool checkInclusion(string s1, string s2) {
    4.         if(s1.size()>s2.size()) return false;
    5.         vector<int>v1(26,0);
    6.         vector<int>v2(26,0);
    7.         for(int i=0;isize();i++) //因为不要求顺序 所以只要统计字母的出现次数就可以
    8.         {
    9.             v1[s1[i]-'a']++;
    10.             v2[s2[i]-'a']++;
    11.         }
    12.         if(v1==v2) return true;
    13.  
    14.         for(int i=s1.size();isize();i++)
    15.         {
    16.             v2[s2[i]-'a']++;
    17.             v2[s2[i-s1.size()]-'a']--; //保持窗口长度为s1的长度
    18.             if(v1==v2) return true;
    19.         }
    20.         return false;
    21.     }
    22. };

    DAY7. DFS/BFS

    733.图像渲染

    力扣

    方法一：dfs

    我们从给定的起点开始，进行深度优先搜索。

    每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格的颜色更新，以防止重复搜索；如果不相同，则进行回溯。

    1. class Solution {
    2. public:
    3.     int dx[4]={0,0,-1,1};
    4.     int dy[4]={1,-1,0,0};
    5.  
    6.     void dfs(vectorint>>&g,int x,int y,int cur,int color)
    7.     {
    8.         int m=g.size(),n=g[0].size();
    9.         if(g[x][y]==cur)
    10.         {
    11.             g[x][y]=color;
    12.             for(int i=0;i<4;i++)
    13.             {
    14.                 int a=x+dx[i],b=y+dy[i];
    15.                 if(a<0||a>m-1||b<0||b>n-1) continue;
    16.                 dfs(g,a,b,cur,color);
    17.             }
    18.         }
    19.     }
    20.     
    21.     vectorint>> floodFill(vectorint>>& g, int sr, int sc, int color) {
    22.         int cur=g[sr][sc];
    23.         if(cur!=color)
    24.             dfs(g,sr,sc,cur,color);
    25.         return g;
    26.     }
    27. };

    方法二：bfs 

    我们从给定的起点开始，进行广度优先搜索。

    每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格加入队列，并将该方格的颜色更新，以防止重复入队。

    注意：因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。

    1. typedef pair<int,int> PII;
    2. class Solution {
    3. public:
    4.     int dx[4]={0,0,-1,1};
    5.     int dy[4]={1,-1,0,0};
    6.  
    7.     void bfs(vectorint>>&g,int x,int y,int cur,int color)
    8.     {
    9.         int m=g.size(),n=g[0].size();
    10.         g[x][y]=color;
    11.         queueq;
    12.         q.push({x,y});
    13.         while(!q.empty())
    14.         {
    15.             auto t=q.front();
    16.             int a=t.first,b=t.second;
    17.             q.pop();
    18.             for(int i=0;i<4;i++)
    19.             {
    20.                 int aa=a+dx[i],bb=b+dy[i];
    21.                 if(aa<0||aa>m-1||bb<0||bb>n-1) continue;
    22.                 if(g[aa][bb]==cur) g[aa][bb]=color,q.push({aa,bb});
    23.             }
    24.         }
    25.     }
    26.     
    27.     vectorint>> floodFill(vectorint>>& g, int sr, int sc, int color) {
    28.         int cur=g[sr][sc];
    29.         if(cur!=color)
    30.             bfs(g,sr,sc,cur,color);
    31.         return g;
    32.     }
    33. };

    695.岛屿的最大面积

    力扣

    方法一：dfs

    1. class Solution {
    2. public:
    3.     int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
    4.  
    5.     int dfs(vectorint>>&g,int x,int y)
    6.     {
    7.         int m=g.size(),n=g[0].size();
    8.         if(x<0||x>m-1||y<0||y>n-1) return 0;
    9.         if(g[x][y]==0) return 0;
    10.         g[x][y]=0;
    11.         int res=1;
    12.         for(int i=0;i<4;i++)
    13.         {
    14.             int a=x+dx[i],b=y+dy[i];
    15.             res+=dfs(g,a,b);
    16.         }
    17.         return res;
    18.     }
    19.  
    20.     int maxAreaOfIsland(vectorint>>& g) {
    21.         int m=g.size(),n=g[0].size();
    22.         int res=0;
    23.         for(int i=0;i
    24.             for(int j=0;j
    25.                 res=max(res,dfs(g,i,j));
    26.         return res;
    27.     }
    28. };

     方法二：bfs

    1. typedef pair<int,int> PII;
    2. class Solution {
    3. public:
    4.     int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
    5.  
    6.     int bfs(vectorint>>&g,int x,int y)
    7.     {
    8.         int m=g.size(),n=g[0].size();
    9.         queueq;
    10.         q.push({x,y});
    11.         g[x][y]=0;
    12.         int res=1;
    13.         while(!q.empty())
    14.         {
    15.             auto t=q.front();
    16.             q.pop();
    17.             int a=t.first,b=t.second;
    18.             for(int i=0;i<4;i++)
    19.             {
    20.                 int aa=a+dx[i],bb=b+dy[i];
    21.                 if(aa<0||aa>m-1||bb<0||bb>n-1) continue;
    22.                 if(g[aa][bb]==1) q.push({aa,bb}),res++,g[aa][bb]=0;
    23.             }
    24.         }
    25.         return res;
    26.     }
    27.  
    28.     int maxAreaOfIsland(vectorint>>& g) {
    29.         int m=g.size(),n=g[0].size();
    30.         int res=0;
    31.         for(int i=0;i
    32.             for(int j=0;j
    33.                 if(g[i][j]==1)
    34.                     res=max(res,bfs(g,i,j));
    35.         return res;
    36.     }
    37. };

    DAY8.DFS/BFS

    617.合并二叉树

    力扣

    1. class Solution {
    2.     public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    3.         if(t1==null) return t2;
    4.         if(t2==null) return t1;
    5.  
    6.         //如果都存在结点 则创建一个新结点储存两个结点值之和
    7.         TreeNode newroot=new TreeNode(t1.val+t2.val);
    8.         //递归合并左子树
    9.         newroot.left=mergeTrees(t1.left,t2.left);
    10.         //递归合并右子树
    11.         newroot.right=mergeTrees(t1.right,t2.right);
    12.  
    13.         return newroot;
    14.     }
    15. }

    ！116.填充每个节点的下一个右侧节点指针

    力扣

    • 如果结点为NULL或者左右子树均为NULL：没有需要做的，直接返回结点本身。
    • 对于左右子树均存在的结点：
    • 首先左子树的next一定不会指向NULL，直接设置指向右子树即可；
    • 对于右子树，他的next是要指向父结点右兄弟的左子树的，可以通过root->next->left找到这个结点，但只有一种情况下例外，就是父结点没有右兄弟（root->next == NULL）
    1. class Solution {
    2.     public Node connect(Node root) {
    3.         if(root==null||root.left==null) return root;
    4.         root.left.next=root.right; //左子树的next肯定不为空 直接指向右子树
    5.         if(root.next!=null) //如果父结点有右兄弟
    6.             root.right.next=root.next.left;//指向父节点右兄弟的左子树
    7.         connect(root.left);
    8.         connect(root.right);
    9.         return root;
    10.     }
    11. }

    DAY9. DFS/BFS

    542.01矩阵

    542. 01 矩阵

    bfs：

    首先把每个源点 0入队，然后从各个 0 同时开始一圈一圈的向 1 扩散（每个 1 都是被离它最近的 0 扩散到的 ）

    1. class Solution {
    2.     public int[][] updateMatrix(int[][] g) {
    3.         int m=g.length,n=g[0].length;
    4.         Queue<int[]> q=new LinkedList<>();
    5.         //将所有0入队，并将1的位置设成-1 标记为未访问
    6.         for(int i=0;i
    7.             for(int j=0;j
    8.                 if(g[i][j]==0) q.offer(new int[] {i,j});
    9.                 else g[i][j]=-1;
    10.  
    11.         int[] dx=new int[]{0,0,-1,1},dy=new int[]{1,-1,0,0};
    12.         while(!q.isEmpty())
    13.         {
    14.             int[] t=q.poll();
    15.             int x=t[0],y=t[1];
    16.             for(int i=0;i<4;i++)
    17.             {
    18.                 int a=dx[i]+x,b=dy[i]+y;
    19.                 if(a>=0&&a=0&&b1)
    20.                 {
    21.                     g[a][b]=g[x][y]+1;
    22.                     q.offer(new int[] {a,b});
    23.                 }
    24.             }
    25.         }
    26.         return g;
    27.     }
    28. }

    994.腐烂的橘子

    994. 腐烂的橘子

    bfs：

    让腐烂的橘子入队 遍历第一次腐烂的橘子 逐一感染

    1. class Solution {
    2.     public int orangesRotting(int[][] g) {
    3.         int m=g.length,n=g[0].length;
    4.         int res=0;
    5.         Queue<int[]> q=new LinkedList<>();
    6.         for(int i=0;i
    7.             for(int j=0;j
    8.                 if(g[i][j]==2) q.offer(new int[] {i,j});
    9.  
    10.         int[] dx=new int[]{0,0,1,-1},dy=new int[]{1,-1,0,0};
    11.         while(!q.isEmpty())
    12.         {
    13.             int num=q.size();//统计本轮腐烂橘子的个数
    14.             for(int i=0;i
    15.             {
    16.                 int[] t=q.poll();
    17.                 int x=t[0],y=t[1];
    18.                 for(int j=0;j<4;j++)
    19.                 {
    20.                     int a=dx[j]+x,b=dy[j]+y;
    21.                     if(a<0||a>=m||b<0||b>=n) continue;
    22.                     if(g[a][b]==1)
    23.                     {
    24.                         g[a][b]=2;
    25.                         q.offer(new int[] {a,b});
    26.                     } 
    27.                 }
    28.             }
    29.             if(!q.isEmpty()) res++;//如果一开始就感染完了 res=0
    30.         }
    31.         //检查还有没有新鲜橘子
    32.         for(int i=0;i
    33.             for(int j=0;j
    34.                 if(g[i][j]==1) return -1;
    35.         return res;
    36.     }
    37. }

    DAY10.递归/回溯

    21.合并两个有序链表

    力扣

    1. class Solution {
    2.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    3.         ListNode head=new ListNode(-1);
    4.         ListNode p=head;
    5.         while(l1!=null&&l2!=null)
    6.         {
    7.             if(l1.val>l2.val)
    8.             {
    9.                 p.next=l2;
    10.                 l2=l2.next;
    11.             }else{
    12.                 p.next=l1;
    13.                 l1=l1.next;
    14.             }
    15.             p=p.next;
    16.         }
    17.         p.next= l1==null?l2:l1;
    18.         return head.next;
    19.     }
    20. }

    206.反转链表

    力扣

    1. class Solution {
    2.     public ListNode reverseList(ListNode head) {
    3.         ListNode p=null;
    4.         ListNode cur=head;
    5.         while(cur!=null)
    6.         {
    7.             ListNode t=cur.next;
    8.             cur.next=p;
    9.             p=cur;
    10.             cur=t;
    11.         }
    12.         return p;
    13.     }
    14. }
    1. class Solution {
    2.     public ListNode reverseList(ListNode head) {
    3.         if(head==null||head.next==null) return head;
    4.         ListNode cur=reverseList(head.next);
    5.         head.next.next=head;
    6.         head.next=null;
    7.         return cur;
    8.     }
    9. }

    DAY11.递归/回溯

    77.组合

    77. 组合

    思路：

    关于剪枝：

    • 要组成大小为k的v，此时还需要k - v.size()个数，如果[i, n]这个区间内(有n - i + 1个数)不足这么多，则肯定没有结果，直接剪枝。
    • 因此剪枝条件为：n - i + 1 < k - v.size()，推出来上界为i = n - k + v.size() + 1
    1. class Solution {
    2.     List> res=new ArrayList<>();
    3.     List v=new ArrayList<>();
    4.     public List> combine(int n, int k) {
    5.         dfs(1,n,k);
    6.         return res;
    7.     }
    8.  
    9.     public void dfs(int start,int n,int k)
    10.     {
    11.         if(v.size()==k) //如果一组已经存满了 则把结果存入res
    12.         {
    13.             res.add(new ArrayList<>(v));//深拷贝 对象中开辟一个新地址，存放的内容为list链表，所以后续不会被影响
    14.             return;
    15.         }
    16.  
    17.         for(int i=start;i<=n-k+v.size()+1;i++)
    18.         {
    19.             v.add(i);
    20.             dfs(i+1,n,k);
    21.             v.remove(v.size()-1);//回溯操作(回退处理结点[1, 2] 撤销2 ,[1, 3] 撤销3)，然后继续遍历
    22.         }
    23.     }
    24. }

    46.全排列

    46. 全排列

    思路：

    1. class Solution {
    2.     List> res = new ArrayList<>();
    3.     List v=new ArrayList<>();
    4.  
    5.     public List> permute(int[] nums) {
    6.  
    7.         int[] visited = new int[nums.length];
    8.         backtrack(nums,visited);
    9.         return res;
    10.     }
    11.  
    12.     private void backtrack(int[] nums, int[] visited) {
    13.         if(v.size()==nums.length) {
    14.             res.add(new ArrayList<>(v));
    15.             return;
    16.         }
    17.         for(int i=0;i
    18.         {
    19.             if(visited[i]==1) continue;
    20.             v.add(nums[i]);
    21.             visited[i]=1;
    22.             backtrack(nums,visited);
    23.             visited[i]=0;
    24.             v.remove(v.size()-1);
    25.         }
    26.     }
    27. }

    784.字母大小写全排列

    784. 字母大小写全排列

    1. class Solution {
    2.     List res=new ArrayList<>();
    3.  
    4.     public List letterCasePermutation(String s) {
    5.         
    6.         char[] ch=s.toCharArray();
    7.         int n=s.length();
    8.         dfs(ch,n,0);
    9.         return res;
    10.     }
    11.  
    12.     private void dfs(char[] ch,int n,int idx)
    13.     {
    14.         res.add(new String(ch));
    15.         for(int i=idx;i
    16.             if(!Character.isDigit(ch[i]))
    17.             {
    18.                 char t=ch[i];
    19.                 ch[i]=(char)((ch[i]-'a'>=0)? ch[i]-32:ch[i]+32);
    20.                 dfs(ch,n,i+1);
    21.                 ch[i]=t; //恢复现场
    22.             }
    23.     }
    24. }

    DAY12.动态规划

    70.爬楼梯

    70. 爬楼梯

    本问题其实常规解法可以分成多个子问题，爬第n阶楼梯的方法数量，等于 2 部分之和

    • 爬上 n-1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
    • 爬上 n-2 阶楼梯的方法数量。因为再爬2阶就能到第n阶

    所以我们得到公式 dp[n] = dp[n-1] + dp[n-2]
    同时需要初始化 dp[0]=1和dp[1]=1

    第0阶台阶1种方法 第1阶台阶1种方法 

    1. class Solution {
    2.     public int climbStairs(int n) {
    3.         int[] dp=new int[n+1];
    4.         dp[0]=1;
    5.         dp[1]=1;
    6.         for(int i=2;i<=n;i++) dp[i]=dp[i-1]+dp[i-2];
    7.         return dp[n];
    8.     }
    9. }

    斐波那契数列

    其实就是斐波那契数列

    1 2 3 5 8…… 

    1. class Solution {
    2.     public int climbStairs(int n) {
    3.         if(n<=2) return n;
    4.         int a=1,b=2,t;
    5.         for(int i=3;i<=n;i++)
    6.         {
    7.             t=a+b;
    8.             a=b;
    9.             b=t;
    10.         }
    11.         return b;
    12.     }
    13. }

    198.打家劫舍

    198. 打家劫舍

    dp[i] 第i间房可盗窃的最大值

    因为不可以闯入相邻的房间 所以在第n间房可以盗窃的最大值=

    • 不盗取第n间房，所以盗取第n-1间房  dp[n]=dp[n-1]
    • 盗取第n间房，所以不能盗窃第n-1间房  dp[n]=dp[n-2]+当前房的值num

    所以动态规划方程：dp[n] = max( dp[n-1],dp[n-2]+num )

    eg:

    1号房可盗窃最大值为3        dp[1]=3

    2号房可盗窃最大值为4        dp[2]=4

    3号房值为2 num=2              dp[3]=max(dp[2],dp[1]+num)=max(4,3+2)=5

    1. class Solution {
    2.     public int rob(int[] nums) {
    3.         int n=nums.length;
    4.         int[] dp=new int[n+1]; //开辟的是0~n的空间
    5.         dp[0]=0;
    6.         dp[1]=nums[0];
    7.         for(int i=2;i<=n;i++)
    8.             dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
    9.         return dp[n];
    10.     }
    11. }

    120.三角形最小路径和

    120. 三角形最小路径和

    dp[i][j] 表示从点 (i, j) 到底边的最小路径和

    自下而上算

    dp[i][j]=min(下一行的左右数值）+自己的值

    最后返回顶上的值就是最小路径和

    1. class Solution {
    2.     public int minimumTotal(List> t) {
    3.         int n=t.size();
    4.         int[][] dp=new int[n+1][n+1];
    5.         for(int i=n-1;i>=0;i--) // 最后一行跳过 从倒数第二行开始算
    6.             for(int j=0;j<=i;j++)
    7.              dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+t.get(i).get(j);
    8.         return dp[0][0];
    9.     }
    10. }

     

    DAY13.位运算

    231.2的幂

    231. 2 的幂

    1. class Solution {
    2.     public boolean isPowerOfTwo(int n) {
    3.         return n>0 && (n&(n-1))==0;
    4.     }
    5. }

    191.位1的个数

    191. 位1的个数

    1. public class Solution {
    2.     public int hammingWeight(int n) {
    3.         int res=0;
    4.         while(n!=0)
    5.         {
    6.             n&=n-1;
    7.             res++;
    8.         }
    9.         return res;
    10.     }
    11. }

     Integer.bitCount(n) 返回1的个数

    1. public class Solution {
    2.     public int hammingWeight(int n) {
    3.         return Integer.bitCount(n);
    4.     }
    5. }

    DAY14.位运算

    190.颠倒二进制位

    190. 颠倒二进制位

    1. public class Solution {
    2.     public int reverseBits(int n) {
    3.         int res=0;
    4.         for(int i=0;i<32;i++)
    5.         {
    6.             int t=n&1; //获取最后的数字
    7.             n>>=1;
    8.             res<<=1; //结果数字左移，为新到来的数字腾出空间
    9.             res|=t; //或运算，将新到来的数字加到原来的数字上
    10.         }
    11.         return res;
    12.     }
    13. }

     Integer.reverse(n); 反转

    1. public class Solution {
    2.     public int reverseBits(int n) {
    3.         return Integer.reverse(n);
    4.     }
    5. }

    136.只出现一次的数字

     136. 只出现一次的数字

    1. class Solution {
    2.     public int singleNumber(int[] a) {
    3.         int res=0;
    4.         for(int x:a) res^=x;
    5.         return res;
    6.     }
    7. }

  • 相关阅读:
    JavaScript中的设计原则
    使用 FasterTransformer 和 Triton 推理服务器部署 GPT-J 和 T5
    基于核心素养劳动教育与学科教学融合研究结题报告
    关于HTTP模块访问之后响应网页
    Java 性能优化实战案例分析：多线程锁的优化
    景联文科技提供全方位图像标注服务
    TouchGFX之缓存位图
    NOWAIT及SKIP LOCKED的使用
    GRU 浅析
    Oracle中的Rollup 使用方法
  • 原文地址：https://blog.csdn.net/weixin_61639349/article/details/126858112