互联网网站项目方案书,幼教资源网网站开发策划书,句容住房和城乡建设局网站,wordpress ajax取头像算法题【面试准备】 前言推荐算法题NC72二叉树的镜像NC8:二叉树根节点到叶子节点和为指定值的路径NC9二叉树中是否存在节点和为指定值的路径NC14二叉树的之字形层序遍历[NC15 求二叉树的层序遍历](https://www.nowcoder.com/study/live/689/2/69)NC37:合并区间[NC111 最大数](h… 算法题【面试准备】 前言推荐算法题NC72二叉树的镜像NC8:二叉树根节点到叶子节点和为指定值的路径NC9二叉树中是否存在节点和为指定值的路径NC14二叉树的之字形层序遍历[NC15 求二叉树的层序遍历](https://www.nowcoder.com/study/live/689/2/69)NC37:合并区间[NC111 最大数](https://www.nowcoder.com/study/live/689/2/71)[NC16 判断二叉树是否对称](https://www.nowcoder.com/study/live/689/2/72)[NC13 二叉树的最大深度](https://www.nowcoder.com/study/live/689/2/73)[NC62 平衡二叉树](https://www.nowcoder.com/study/live/689/2/74)NC7股票一次交易[NC22 合并两个有序的数组](https://www.nowcoder.com/study/live/689/2/76)NC52括号序列[NC102 最近公共祖先](https://www.nowcoder.com/study/live/689/2/78)[NC78 反转链表](https://www.nowcoder.com/study/live/689/2/79)[NC103 反转字符串](https://www.nowcoder.com/study/live/689/2/80)[NC33 合并有序链表](https://www.nowcoder.com/study/live/689/2/81)NC75数组中只出现一次的数字哈希法NC75数组中只出现一次的数字位运算法NC61两数之和暴力NC61两数之和哈希法NC59矩阵的最小路径和NC19子数组的最大累加和问题NC4判断链表中是否有环NC4判断链表中是否有环(空间复杂度o(1))NC34求路径NC68跳台阶NC112进制转换NC65斐波那契数列NC76用两个栈实现队列[NC41 最长无重复子串](https://www.nowcoder.com/study/live/689/2/94)NC133链表的奇偶重排NC116把数字翻译成字符串NC135股票两次交易NC126换钱的最少货币数NC45实现二叉树先序中序和后序遍历递归[NC90 设计getMin功能的栈](https://www.nowcoder.com/study/live/689/2/100)NC67连续子数组的最大和NC115栈和排序NC73数组中出现次数超过一半的数字NC134股票无限次交易NC114旋转字符串 最后 前言
2023-2-9 16:34:07
补充 2023-7-16 17:55:56
公开发布于 2024-5-20 12:50:15
以下内容源自算法题 仅供学习交流使用
推荐
牛客
LeetCode
算法题
NC72二叉树的镜像
2023-2-9 16:40:26
NC72二叉树的镜像
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pRoot TreeNode类 * return TreeNode类*/public TreeNode Mirror (TreeNode pRoot) {// write code hereif(pRootnull){return null;}TreeNode temppRoot.left;pRoot.leftpRoot.right;pRoot.righttemp;Mirror(pRoot.left);Mirror(pRoot.right);return pRoot;}
}剑指 Offer 27. 二叉树的镜像
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public TreeNode mirrorTree(TreeNode root) {if(rootnull){return null;}TreeNode tmproot.left;root.leftroot.right;root.righttmp;mirrorTree(root.left);mirrorTree(root.right);return root;}
}2023-2-9 16:45:40
NC8:二叉树根节点到叶子节点和为指定值的路径
2023-2-9 16:48:54
二叉树根节点到叶子节点和为指定值的路径
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* }*/public class Solution {/*** * param root TreeNode类 * param sum int整型 * return int整型ArrayListArrayList*/ArrayListArrayListInteger resnew ArrayList();ArrayListInteger tmpnew ArrayList();public ArrayListArrayListInteger pathSum (TreeNode root, int sum) {// write code heredfs(root,sum,0);return res;}void dfs(TreeNode root, int sum,int s){if(rootnull){return;}tmp.add(root.val);sroot.val; if(root.leftnullroot.rightnull){if(ssum){res.add(new ArrayList(tmp));}}else{dfs(root.left,sum,s);dfs(root.right,sum,s);}tmp.remove(tmp.size()-1);}
}剑指 Offer 34. 二叉树中和为某一值的路径
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {ListListInteger resnew ArrayList();ListInteger tmpnew ArrayListInteger();public ListListInteger pathSum(TreeNode root, int target) {dfs(root,target,0);return res;}void dfs(TreeNode root, int target,int sum){if(rootnull){return;}tmp.add(root.val);sumroot.val;if(root.leftnullroot.rightnull){if(sumtarget){res.add(new ArrayList(tmp));}}else{dfs(root.left,target,sum);dfs(root.right,target,sum);}tmp.remove(tmp.size()-1);}}有注释版 注意两处细节
class Solution {// 用来存储结果private ListListInteger res new ArrayList();// 用来存贮路径// (先不向上转型要使用LinkedList的API)// 你也可以使用 双端队列Deque// 但是Deque不能直接被list加入需要调用 list.add(new ArrayList(deque));// 通过构造方法添加private LinkedListInteger path new LinkedList();// 方案一 这道题想都不用想肯定DFS深度搜索优先// 从根节点出发到叶子节点返回public ListListInteger pathSum(TreeNode root, int target) {dfs(root, target);return res;}private void dfs(TreeNode root, int target) {// 递归截至条件if (root null) {return;}// 减去当前node的值并加入路径target - root.val;path.add(root.val);// 题目必须要求必须是叶子节点才行// 查看当前target消耗后是否为0如果为0加入到结果中if (root.left null root.right null target 0) {// 细节为什么我要通过构造方法传入path不能直接res.add(path)// 因为直接加入加入的是引用(指向的堆中数据会变化)需要克隆一份加入res.add(new LinkedList(path));// 细节找到后不能直接return需要在path中移除最后一个元素// 因为即使你到根节点找到或找不到该节点不能影响其他搜索}dfs(root.left, target);dfs(root.right, target);path.removeLast(); // 将本次搜索结果移除方便其他搜索使用path变量}
}NC9二叉树中是否存在节点和为指定值的路径
和前一题一样
NC14二叉树的之字形层序遍历
NC14 按之字形顺序打印二叉树
- 设计思想:
定义一个队列
往队列中加入当前节点
当队列不为空的时候进行以下两个操作
1求出当前队列的长度大小len。
2取出队列前len个节点每取出一个节点就把对应节点的左右孩子入队前提左右孩子不为空)
因为我们是之字形遍历在遍历每一层节点的时候我们需要判断树的高度是不是奇偶如果是偶数就倒着存储如果是奇数就正着储存。import java.util.*;/*
public class TreeNode {int val 0;TreeNode left null;TreeNode right null;public TreeNode(int val) {this.val val;}}
*/
public class Solution {public ArrayListArrayListInteger Print(TreeNode pRoot) {ArrayListArrayListInteger resnew ArrayListArrayListInteger();if(pRootnull){return res;}// 定义一个队列QueueTreeNode qnew LinkedList();// 往队列中加入当前节点q.add(pRoot);int height1;// 当队列不为空的时候进行以下两个操作 while(!q.isEmpty()){ArrayListInteger tempnew ArrayList();//存储每一层结点// 1求出当前队列的长度大小len。int lenq.size();// 2取出队列前len个节点每取出一个节点就把对应节点的左右孩子入队前提左右孩子不为空)for(int i0;ilen;i){TreeNode nodeq.poll();// 因为我们是之字形遍历在遍历每一层节点的时候我们需要判断树的高度是不是奇偶如果是偶数就倒着存储如果是奇数就正着储存。if(height%20){temp.add(0,node.val);//插入到数组的最末尾}else{temp.add(node.val);}if(node.left!null){q.add(node.left);}if(node.right!null){q.add(node.right);}}height;//高度res.add(new ArrayList(temp)); //把这一层的节点插入到res中}return res;}}
2023-7-16 17:56:19
103. 二叉树的锯齿形层序遍历
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger ansnew LinkedListListInteger();if(rootnull){return ans;}QueueTreeNode nodeQueue new ArrayDequeTreeNode();nodeQueue.offer(root);boolean isOrderLefttrue;while(!nodeQueue.isEmpty()){DequeInteger levelListnew LinkedListInteger();int sizenodeQueue.size();for(int i0;isize;i){TreeNode curNodenodeQueue.poll();if(isOrderLeft){levelList.offerLast(curNode.val);}else{levelList.offerFirst(curNode.val);}if(curNode.left!null){nodeQueue.offer(curNode.left);}if(curNode.right!null){nodeQueue.offer(curNode.right);}}ans.add(new LinkedListInteger(levelList));isOrderLeft!isOrderLeft;}return ans;}
}2023-7-16 18:32:33
NC15 求二叉树的层序遍历
2023-3-9 21:10:48
NC15 求二叉树的层序遍历
思路比上一题简单
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* }*/public class Solution {/*** * param root TreeNode类 * return int整型ArrayListArrayList*/public ArrayListArrayListInteger levelOrder (TreeNode root) {// write code hereArrayListArrayListInteger resnew ArrayList();if(rootnull){return res;}QueueTreeNode qnew LinkedList();q.add(root);while(!q.isEmpty()){ArrayListInteger tempnew ArrayList();int lenq.size();for(int i0;ilen;i){TreeNode nodeq.poll();temp.add(node.val);if(node.left!null){q.add(node.left);}if(node.right!null){q.add(node.right);}}res.add(new ArrayList(temp));}return res;}
}2023-3-9 21:18:15
102. 二叉树的层序遍历
2023-7-16 18:41:55
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger resnew ArrayListListInteger();if(rootnull){return res;}QueueTreeNode qnew LinkedListTreeNode();q.add(root);while(!q.isEmpty()){ArrayListInteger tempnew ArrayList();int lenq.size();for(int i0;ilen;i){TreeNode curq.poll();temp.add(cur.val);if(cur.left!null){q.add(cur.left);}if(cur.right!null){q.add(cur.right);}}res.add(new ArrayList(temp));}return res;}
}2023-7-16 18:41:55
NC37:合并区间
2023-3-9 21:18:19
NC37 合并区间
设计思想
这道题的基本思路就是先排序在合并
首先说排序:按照区间的左端点从小到大来排序区间
排序好后我们就按照排序好后的区间进行操作
首先定义两个变量l和rl用来保存合并区间的左即startr用来保存合并区间的右即end
然后使用指针r开始往后寻找如果后续的区间的左端点即start比r小就说明是重复区间可以进行合并然后更新合并区间的最大值即r直到区间断开然后将当前的lr插入到答案里
重复上述过程直到全部区间遍历一次
import java.util.*;
/*** Definition for an interval.* public class Interval {* int start;* int end;* Interval() { start 0; end 0; }* Interval(int s, int e) { start s; end e; }* }*/
public class Solution {public ArrayListInterval merge(ArrayListInterval intervals) {ArrayListInterval resnew ArrayList();// 这道题的基本思路就是先排序在合并// 首先说排序: 按照区间的左端点从小到大来排序区间intervals.sort((a, b) - (a.start - b.start));// 排序好后我们就按照排序好后的区间进行操作// 首先定义两个变量l和rl用来保存合并区间的左即startr用来保存合并区间的右即endint l,r;// 然后使用指针r开始往后寻找如果后续的区间的左端点即start比r小就说明是重复区间可以进行合并然后更新合并区间的最大值即rint i0;while(iintervals.size()){lintervals.get(i).start;rintervals.get(i).end;//合并区间while(iintervals.size()-1rintervals.get(i1).start){i;rMath.max(r,intervals.get(i).end);}// 直到区间断开然后将当前的1r插入到答案里res.add(new Interval(l,r));i;// 重复上述过程直到全部区间遍历一次}return res;}
}56. 合并区间
2023-7-16 19:23:29
class Solution {public int[][] merge(int[][] intervals) {// 注这里是通过Listint[]来保存二维数组的// 通过List#add很方便但在最后返回时要toArray(new int[0][])表示放到一个二维数组Listint[] res new ArrayList();if(intervals.length 0 || intervals null) return res.toArray(new int[0][]); // 1.排序// 这里通过lamada用函数式接口实现了Comptor接口表示比较两个一维数组i1i2通过i[0]比较Arrays.sort(intervals, (i1, i2) - i1[0] - i2[0]);// 2.初始区间int start intervals[0][0], end intervals[0][1];// 3.创建区间for(int[] arr:intervals){if(arr[0]end){endMath.max(end,arr[1]);}else{res.add(new int[]{start,end});startarr[0];endarr[1];}}// 4.剩余处理res.add(new int[]{start, end});return res.toArray(new int[0][]); }
}class Solution {public int[][] merge(int[][] intervals) {if(intervals.length0){return new int[0][2];}//首先我们将列表中的区间按照左端点升序排序。Arrays.sort(intervals,new Comparatorint[](){public int compare(int[] interval1,int[] interval2){return interval1[0]-interval2[0];}});Listint[] mergednew ArrayList();for(int i0;iintervals.length;i){int Lintervals[i][0],Rintervals[i][1];//然后我们将第一个区间加入 merged 数组中并按顺序依次考虑之后的每个区间//如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后那么它们不会重合if(merged.size()0||merged.get(merged.size()-1)[1]L){//我们可以直接将这个区间加入数组 merged 的末尾merged.add(new int[]{L,R});}else{//否则它们重合//我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点//将其置为二者的较大值。merged.get(merged.size()-1)[1]Math.max(merged.get(merged.size()-1)[1],R);}}return merged.toArray(new int[merged.size()][]);}
}2023-7-16 19:42:57
NC111 最大数
2023-3-9 21:43:27
NC111 最大数
-3、设计思想:
这道题题目已经提示输出用字符串的形式了所以我们第一步就是把整数数组变为字符串数组。
第二步呢就是将字符串数组排序那么排序规则是什么呢?
排序规则就是:每次将相邻的两个字符串正反拼接然后比大小从而确定相邻的两个字符串是否交换位置。
还有一个细节就是如果排序好的数组第一个元素就是”O”那么结果直接返回字符串”O”就好了。
如果排序好后的数组第一个元素不是”O”,那么直接从头到尾拼接返回就好了。import java.util.*;public class Solution {/*** 最大数* param nums int整型一维数组* return string字符串*/public String solve (int[] nums) {// write code here// 这道题题目已经提示输出用字符串的形式了所以我们第一步就是把整数数组变为字符串数组。ArrayListString list new ArrayList();for (int i 0; i nums.length; i) {list.add(String.valueOf(nums[i]));}// 第二步呢就是将字符串数组排序那么排序规则是什么呢 ?// 排序规则就是 :// 每次将相邻的两个字符串正反拼接然后比大小从而确定相邻的两个字符串是否交换位置。Collections.sort(list, new ComparatorString() {public int compare(String a, String b) {return (b a).compareTo(a b);}});// 还有一个细节就是如果排序好的数组第一个元素就是”O”那么结果直接返回字符串”O”就好了。if (list.get(0).equals(0)) return 0;// 如果排序好后的数组第一个元素不是”O”,// 那么直接从头到尾拼接返回就好了。StringBuilder res new StringBuilder(); for (int i 0; i list.size();i ) { res.append(list.get(i));}return res.toString();}
}NC16 判断二叉树是否对称
NC16 对称的二叉树
/*
public class TreeNode {int val 0;TreeNode left null;TreeNode right null;public TreeNode(int val) {this.val val;}}
*/
public class Solution {boolean isSymmetrical(TreeNode pRoot) {if (pRoot null) {return true;}return like(pRoot.left, pRoot.right);}boolean like(TreeNode pLeft, TreeNode pRight) {if (pLeftnullpRightnull){return true;}if (pLeft null || pRight null) {return false;}return pLeft.val pRight.val like(pLeft.left,pRight.right) like(pLeft.right,pRight.left);}
}
NC13 二叉树的最大深度
NC13 二叉树的最大深度
思路
树的高度max(左子树的高度右子树的高度)1import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* }*/public class Solution {int height1;/*** * param root TreeNode类 * return int整型*/public int maxDepth (TreeNode root) {// write code hereif(rootnull){return 0;}int lhmaxDepth(root.left);int rhmaxDepth(root.right);return Math.max(lh,rh)1;}}2023-3-9 22:17:32
NC62 平衡二叉树
NC62 判断是不是平衡二叉树
public class Solution {public boolean IsBalanced_Solution(TreeNode root) {if (root null) {return true;}return Math.abs(getHeight(root.left)-getHeight(root.right))1IsBalanced_Solution(root.left)IsBalanced_Solution(root.right);}public int getHeight(TreeNode root){if(root null) return 0;int lh getHeight(root.left);int rh getHeight(root.right);return Math.max(lh,rh) 1;}
}2023-3-9 22:23:51
NC7股票一次交易
2023-3-9 22:24:35
NC7 买卖股票的最好时机(一)
-3、 设计思想
我们先解读题意题目中给了两个限定条件:1)只能有一次买入和卖出2只有买入了股票以后才能卖出
因此我们就定义一个状态即dp[i][j](其中j 0或1)dp[i][0]代表下标为i天的时候手上没有股票最大正收益为多少
dp[i][1]代表下表为i天的时候手上有股票最小负收益为多少。
此时我们定义初始状态dp[0][0] 0, dp[i][1] prices[0]
我们定义好dp方程式后我们开始来推转移方程。
dp[i][o] max(dp[i-1][o], prices[i] - dp[i-1][1])
dp[i][1] min(dp[i-1][1], prices[i]);
最后返回dp[prices-1][0]即为所求当我们到读懂了上面的方程后我们可以把二维空间优化为一维空间因为你会发现这道题只有2种依态就是0:代表卖股票1:代表持有股票。也就是说我们只需要求得dp[0]的最大值,所以将方程变为
dp[0] max(dp [0] , prices[i] - dp[1]);
dp[1] min(dp[1], prices[i]);当我们看完上一张ppt时优化后的方程我们知道因为只有两种状态那么我们连数组都不需要开所以直接定义两个变量就好了min_input:代表你买入的股票价钱即上一张ppt的dp[1]max_output:代表你卖出股票价钱即上一张ppt的dp[0]所以方程如下
min_input min(min_input, prices[i]);
max_output max (max_output.prices[i]-min_input) ;
import java.util.*;public class Solution {/**** param prices int整型一维数组* return int整型*/public int maxProfit (int[] prices) {// write code here//我们先解读题意题目中给了两个限定条件:1)只能有一次买入和卖出2只有买入了股票以后才能卖出// 因此我们就定义一个状态即dp[i][j](其中j 0或1)dp[i][0]代表下标为i天的时候手上没有股票最大正收益为多少 // dp[i][1]代表下表为i天的时候手上有股票最小负收益为多少。int [][] dpnew int[prices.length][2];// 此时我们定义初始状态dp[0][0] 0, dp[i][1] prices[0]dp[0][0] 0;for(int i0;idp.length;i){dp[i][1] prices[0];}// 我们定义好dp方程式后我们开始来推转移方程。// dp[i][0] max(dp[i-1][0], prices[i] - dp[i-1][1])// dp[i][1] min(dp[i-1][1], prices[i]);for(int i1;idp.length;i){dp[i][0] Math.max(dp[i-1][0], prices[i] - dp[i-1][1]);dp[i][1] Math.min(dp[i-1][1], prices[i]);}// 最后返回dp[prices-1][0]即为所求return dp[dp.length-1][0];}
}2023-3-9 22:42:32
NC22 合并两个有序的数组
NC22 合并两个有序的数组
import java.util.*;
public class Solution {public void merge(int A[], int m, int B[], int n) {int i0;//用来遍历Bint j0;//用来遍历Awhile(in){while(B[i]A[j]jm){//找到比B大的A元素的位置jj;}if(jm){//如果找到最后都没有就在最后插入put(A,m,j,B[i]);//因为添加了一个A的长度m1} put(A,m,j,B[i]);//因为添加了一个A的长度m1i; }}public void put(int A[], int m,int j,int n){//在j的位置插入元素nfor(int im;ij;i--){A[i]A[i-1];}A[j]n;System.out.println(Arrays.toString(A));}
}2023-3-9 23:22:56
NC52括号序列
2023-3-10 10:40:10
NC52 有效括号序列
import java.util.*;public class Solution {/*** * param s string字符串 * return bool布尔型*/public boolean isValid (String s) {// write code hereStackCharacter stnew Stack();char[] charss.toCharArray();for(int i0;ichars.length;i){//遍历字符数组if(left(chars[i])){//左括号入栈st.push(chars[i]);}if(right(chars[i])){//右括号if(st.isEmpty()){//如果栈为空没有匹配的左括号return false;}boolean pmatch(st.pop(),chars[i]);//匹配栈顶左括号if(pfalse){//匹配失败return false;}}}return st.isEmpty();//判断有没有多余的左括号}public boolean left(char c){return c(||c[||c{;}public boolean right(char c){return c)||c]||c};}public boolean match(char c1,char c2){if(c1(c2)) return true;if(c1[c2]) return true;if(c1{c2}) return true;return false;}
}2023-3-10 11:12:23
NC102 最近公共祖先
2023-3-10 11:13:19
NC102 在二叉树中找到两个节点的最近公共祖先
设计思想
对于树的题我们第一想法就是递归那么对于这道题我们同样是递归查询两个给定的两个节点o1, o2
如果这棵树中的某个节点等于节点o1或者o2那么就向上返回这个节点给父节点
如果当前节点的左右子树返回值分别是o1、o2那么当前这个节点就是最近公共祖先
如果当前节点只有一个子树的返回值为o1或o2节点则返回该值
如果当前节点的两个子树返回值都为空则返回空指针。import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* }*/public class Solution {/**** param root TreeNode类* param o1 int整型* param o2 int整型* return int整型*/public int lowestCommonAncestor (TreeNode root, int o1, int o2) {// write code herereturn dfs(root,o1,o2).val;}// 对于树的题我们第一想法就是递归那么对于这道题我们同样是递归查询两个给定的两个节点o1,o2public TreeNode dfs(TreeNode root,int o1,int o2){// 如果这棵树中的某个节点等于节点o1或者o2那么就向上返回这个节点给父节点// 如果当前节点的两个子树返回值都为空则返回空指针。if(rootnull||root.valo1||root.valo2){return root;}TreeNode leftdfs(root.left,o1,o2);TreeNode rightdfs(root.right,o1,o2);// 如果当前节点的左右子树返回值分别是o1、o2那么当前这个节点就是最近公共祖先if(left!nullright!null){return root;}// 如果当前节点只有一个子树的返回值为o1或o2节点则返回该值return leftnull?right:left;}
}2023-3-10 11:24:24
NC78 反转链表
2023-3-10 11:25:28
NC78 反转链表
/*
public class ListNode {int val;ListNode next null;ListNode(int val) {this.val val;}
}*/
public class Solution {public ListNode ReverseList(ListNode head) {ListNode resnull;ListNode chead;while(c!null){ListNode nc.next;//记录下一个结点c.nextres;resc;cn;//遍历}return res;}
}
2023-3-10 11:33:04
NC103 反转字符串
2023-3-10 11:34:07
NC103 反转字符串
import java.util.*;public class Solution {/*** 反转字符串* param str string字符串 * return string字符串*/public String solve (String str) {// write code herechar [] charsstr.toCharArray();for(int i0;ichars.length/2;i){char tempchars[i];chars[i]chars[chars.length-1-i];chars[chars.length-1-i]temp;}return new String(chars);}
}2023-3-10 11:38:13
NC33 合并有序链表
/*
public class ListNode {int val;ListNode next null;ListNode(int val) {this.val val;}
}*/
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {if(list1null) return list2;if(list2null) return list1;ListNode resnew ListNode(-1);//虚拟结点ListNode cur1list1;//遍历1ListNode cur2list2;//遍历2ListNode curres;//遍历reswhile(cur1!nullcur2!null){if(cur1.valcur2.val){cur.nextcur1;curcur1;cur1cur1.next;}else{cur.nextcur2;curcur2;cur2cur2.next;}}if(cur1!null) cur.nextcur1;if(cur2!null) cur.nextcur2;return res.next;}
}
2023-3-10 11:46:22
NC75数组中只出现一次的数字哈希法
NC75 数组中只出现一次的两个数字
2023-3-10 11:47:31
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param array int整型一维数组 * return int整型一维数组*/public int[] FindNumsAppearOnce (int[] array) {// write code hereint[] resnew int[2];HashMapInteger,Integer mapnew HashMap();for(int i:array){if(!map.containsKey(i)){map.put(i,1);}else{map.put(i,map.get(i)1);}}int cnt0;for(int i0;iarray.length;i){if(map.get(array[i])1){res[cnt]array[i];}if(cnt2){break;}}if(res[0]res[1]){return new int[]{res[1],res[0]};}return res;}
}2023-3-10 11:55:19
NC75数组中只出现一次的数字位运算法
2023-3-10 16:31:36
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param array int整型一维数组 * return int整型一维数组*/public int[] FindNumsAppearOnce (int[] array) {// write code hereint s0;for(int n:array){s^n;} int rightOnes(~s1);// 提取出最右的1int one0;for(int n:array){if((nrightOne)!0){one^n;}}int otherone^s;if(oneother){return new int[]{other,one};}else{return new int[]{one,other};}}
}2023-3-10 16:40:42
NC61两数之和暴力
2023-3-10 16:41:28 NC61 两数之和
会运行超时
import java.util.*;public class Solution {/*** * param numbers int整型一维数组 * param target int整型 * return int整型一维数组*/public int[] twoSum (int[] numbers, int target) {// write code herefor(int i0;inumbers.length;i){for(int ji1;jnumbers.length;j){if(numbers[i]numbers[j]target){return new int[]{i1,j1};}}}return new int[2];}
}2023-3-10 16:47:47
NC61两数之和哈希法
import java.util.*;public class Solution {/*** * param numbers int整型一维数组 * param target int整型 * return int整型一维数组*/public int[] twoSum (int[] numbers, int target) {// write code hereHashMapInteger,Integer mapnew HashMap();for(int i0;inumbers.length;i){if(!map.containsKey(target-numbers[i])){map.put(numbers[i],i);}else{return new int[]{map.get(target-numbers[i])1,i1};}}return new int[2];}
}2023-3-10 16:52:30
NC59矩阵的最小路径和
2023-3-10 16:53:37
NC59 矩阵的最小路径和
-3、设计思想:
定义一个dp大小为n×m 矩阵其中 dp[i][j]的值代表走到(i,j)的最小路径和
当i 0 j 0时dp[i][j] matrix [i][j]
当i 0 j ! 0时, dp[i][j] dp[0][j-1] matrix[0][j]//第0列就是从00到n-1,0
当i ! 0j 0时, dp[i][j] dp[i-1][0] matrix[i][0] //第0行就是从0,0到0,m-1
当i ! 0 j ! 0时,dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) matrix[i][j] //比较 向下走和向右走哪个更短
最后返回值为dp[n-1][m-1]。import java.util.*;public class Solution {/**** param matrix int整型二维数组 the matrix* return int整型*/public int minPathSum (int[][] matrix) {// write code here// 定义一个dp大小为n×m 矩阵其中 dp[i][j]的值代表走到(i,j)的最小路径和int nmatrix.length;int mmatrix[0].length;int [][] dpnew int [n][m];for(int i0;in;i){for(int j0;jm;j){// 当i 0 j 0时dp[i][j] matrix [i][j]if(i0j0){dp[i][j]matrix[i][j];}// 当i 0 j ! 0时, dp[i][j] dp[0][j-1] matrix[0][j]if(i0j!0){dp[i][j] dp[0][j-1] matrix[0][j];}// 当i ! 0j 0时, dp[i][j] dp[i-1][0] matrix[i][0]if(i!0j0){dp[i][j] dp[i-1][0] matrix[i][0];}// 当i ! 0 j ! 0时,dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) matrix[i][j]if(i!0j!0){dp[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]) matrix[i][j];}}}// 最后返回值为dp[n-1][m-1]。return dp[n-1][m-1];}}2023-3-10 17:07:51
NC19子数组的最大累加和问题
2023-3-10 17:08:51
NC19 连续子数组的最大和
3、设计思想:
定义一个dp大小为n的数组其中 dp[i]的值代表到第i位的时侯以arr[i]结尾的连续子数组最大累加和。
当i 0 时dp[i] arr[0]
当i ! 0时dp[i] max(0,dp[i-1]) arr[i](若dp[i-1]0 时dl[i-1] ari还不arr[i]的本身大
所以当dp[i-1]0时 dp[i]array[i] 当p[i-1]0时dp[i]dp[i-1]array[i]
最后返回值为dp数组中最大的值
public class Solution {public int FindGreatestSumOfSubArray(int[] array) {// 定义一个dp大小为n的数组其中 dp[i]的值代表到第i位的时侯以arr[i]结尾的连续子数组最大累加和。int len array.length;int[] dp new int[len];// 当i 0 时dp[i] arr[0]dp[0]array[0];// 当i ! 0时dp[i] max(0,dp[i-1]) arr[i](若dp[i-1]0 时dl[i-1] ari还不arr[i]的本身大// 所以当dp[i-1]0时 dp[i]array[i] 当p[i-1]0时dp[i]dp[i-1]array[i] for (int i 1; i len; i) {dp[i] Math.max(0,dp[i - 1]) array[i];}// 最后返回值为dp数组中最大的值int resdp[0];for (int i 1; i len; i) {res Math.max(res,dp[i]);}return res;}
}
2023-3-10 17:25:25
NC4判断链表中是否有环
NC4 判断链表中是否有环
import java.util.*;/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {//hashHashSetListNode setnew HashSet();ListNode phead;while(p!null){if(set.contains(p)){return true;}else{set.add(p);}pp.next;}return false;}
}2023-3-10 17:37:47
NC4判断链表中是否有环(空间复杂度o(1))
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(headnull){return false;}//双指针ListNode phead;ListNode qhead.next;while(p!qp!nullq!null){pp.next;if(q.next!null){qq.next.next;}else{return false;}}return (p!nullq!null)?true:false;}
}2023-3-10 17:33:28
NC34求路径
NC34 不同路径的数目(一)
-3、设计思想:
定义一个dp大小为m×n矩阵其中 dp[i][j的值代表走到(i,j)的路径种类。
当i 0j 0时, dp[i][j] 1因为机器人只能从左边过来所以只有一种方案
当i 0 j 0时, dp[i][j] 1因为机器人只能从上边过来所以只有一种方案
当i !0, j !0 时, dp[i][j]dp[i - 1][j] dp[i][j -1]因为到达(i,j)只有两种策略1机器人从点(i-1, j)往下移动 2)机器人从点(i,j-1)往右移动所以dpl[i][j]二者的总和
最后返回值为dp[m-1][n-1]。import java.util.*;public class Solution {/*** * param m int整型 * param n int整型 * return int整型*/public int uniquePaths (int m, int n) {// write code here//定义一个dp大小为m×n矩阵其中 dp[i][j的值代表走到(i,j)的路径种类。int dp[][]new int[m][n];// 当i 0j 0时, dp[i][j] 1因为机器人只能从左边过来所以只有一种方案for(int j0;jn;j){dp[0][j]1;}// 当i 0 j 0时, dp[i][j] 1因为机器人只能从上边过来所以只有一种方案for(int i0;im;i){dp[i][0]1;}// 当i !0, j !0 时, dp[i][j]dp[i - 1][j] dp[i][j -1]因为到达(i,j)只有两种策略// 1机器人从点(i-1, j)往下移动 2)机器人从点(i,j-1)往右移动// 所以dpl[i][j]二者的总和for(int i1;im;i){for(int j1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1]; }}// 最后返回值为dp[n-1][m-1]。return dp[m-1][n-1];}
}2023-3-12 13:45:22
NC68跳台阶
NC68 跳台阶
-3、 设计思想
按照题解直接写这道题就好了
当只有1个台阶的时候只有一种方法
当有2个台阶的时候有2种跳法1一次跳1个2一次跳2个
当有n个台阶的时候它可以从n-1个台阶跳过来也可以从n-2个台阶跳过来
所以n台阶种类 n-1台阶种类 n-2台阶种类
public class Solution {public int jumpFloor(int target) {int [] dpnew int[target1];for(int i0;itarget1;i){// 当只有1个台阶的时候只有一种方法if(i0||i1){dp[i]1;}else{// 当有2个台阶的时候有2种跳法1一次跳1个2一次跳2个// 当有n个台阶的时候它可以从n-1个台阶跳过来也可以从n-2个台阶跳过来// 所以n台阶种类 n-1台阶种类 n-2台阶种类dp[i]dp[i-1]dp[i-2];}}return dp[target];}
}
2023-3-12 13:52:15
NC112进制转换
2023-3-12 13:53:41
NC112 进制转换
import java.util.*;public class Solution {/*** 进制转换* param M int整型 给定整数* param N int整型 转换到的进制* return string字符串*/public String solve (int M, int N) {// write code hereif(M0){return 0;}boolean flagfalse;if(M0){flagtrue;M-M;}StringBuilder sbnew StringBuilder();while(M!0){int mM%N;char c;if(m10){c(char)(A(m-10));}else{c(char)(0(m-0));}sb.append(c);M/N;}if(flagtrue){sb.append(-);}sb.reverse();return sb.toString();}}2023-3-12 14:05:12
NC65斐波那契数列
2023-3-12 14:06:02
NC65 斐波那契数列
public class Solution {public int Fibonacci(int n) {if(n1||n2){return 1;}else{return Fibonacci(n-1)Fibonacci(n-2);}}
}
2023-3-12 14:07:01
NC76用两个栈实现队列
2023-3-12 14:08:23
NC76 用两个栈实现队列
import java.util.Stack;public class Solution {StackInteger stack1 new StackInteger();StackInteger stack2 new StackInteger();public void push(int node) {//栈1不为空直接入栈 否则把栈2的内容倒回来if(!stack1.isEmpty()){stack1.push(node);}else{while(!stack2.isEmpty()){stack1.push(stack2.pop());}stack1.push(node);}}public int pop() {//栈2不为空直接出栈 否则把栈1的内容倒出来if(!stack2.isEmpty()){return stack2.pop();}while(!stack1.isEmpty()){stack2.push(stack1.pop());}return stack2.pop();}
}
2023-3-12 14:18:11
NC41 最长无重复子串
NC41 最长无重复子数组
import java.util.*;public class Solution {/*** * param arr int整型一维数组 the array* return int整型*/public int maxLength (int[] arr) {// write code hereHashSetInteger setnew HashSet();int l0;int r0;int cnt1;//长度while(larr.lengthrarr.length){if(!set.contains(arr[r])){set.add(arr[r]);r;cntMath.max(cnt,r-l);}else{set.remove(arr[l]);l;}}return cnt;}
}2023-3-12 14:30:27
NC133链表的奇偶重排
NC133 链表的奇偶重排
import java.util.*;/** public class ListNode {* int val;* ListNode next null;* public ListNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可* * param head ListNode类 * return ListNode类*/public ListNode oddEvenList (ListNode head) {// write code hereListNode res1new ListNode(-1);ListNode res2new ListNode(-1);int cnt1;ListNode curhead;ListNode cur1res1;ListNode cur2res2;while(cur!null){if(cnt%21){cur1.nextcur;cur1cur;}else{cur2.nextcur;cur2cur;}curcur.next;cnt;}cur2.nextnull;cur1.nextres2.next;return res1.next;}
}2023-3-12 14:46:09
NC116把数字翻译成字符串
2023-3-12 14:47:58
NC116 把数字翻译成字符串
import java.util.*;public class Solution {/*** 解码* param nums string字符串 数字串* return int整型*/public int solve (String nums) {// write code hereif(nums.charAt(0)0) return 0;int [] dpnew int[nums.length()];//dp[i]的含义代表长度在i位置时有几种翻译办法dp[0]1;//在第0个字符的时候只有一个字母所以只有一种翻译办法for(int i1;idp.length;i){if(nums.charAt(i)0){if(nums.charAt(i-1)1||nums.charAt(i-1)2){if(i1) dp[i]1;//特判字符串长度为2else dp[i]dp[i-2];//因为 10 20 这样的只有一种对应方案所以此时dp[i]取决于dp[i-2]}}else if(nums.charAt(i-1)1||(nums.charAt(i-1)2nums.charAt(i)1nums.charAt(i)6)){/*11-26 抛去 20这样的组合但是当i1的时候如 12 21 这样有两种方案当i1时候dp[i] 取决于 dp[i-1] 和 dp[i-2]的和*/if(i1) dp[i]2;else dp[i]dp[i-1]dp[i-2];}else{dp[i]dp[i-1];}}return dp[dp.length-1];}
}2023-3-12 15:03:03
NC135股票两次交易
2023-3-12 15:04:09
NC135 买卖股票的最好时机(三)
-3、设计思想:
我们先解读题意题目中给了一个限定条件:最多买卖两次也就是说他与股票(一次交易不同)点就是多了一次交易。但是多了一次交易就会产生巨大的变化。
股票(一次交易)只有两个状态但是本题就5个状态: 1)不操作2)第一次购买3)第一次卖出4)第二次购买5)第二次卖出
即db[i][j]代表第i天状态为j时产生的最大收益
dp[i][0]代表下标为i天的时候手上没有股票最大收益
dp[i][1]代表下表为i天的时候第一次购买手上有股票最大收益
dp[i][2]代表下表为i天的时候第一次卖出手上无股票最大收益
dp[i][3]代表下表为i天的时候第二次购买手上有股票最大收益
dp[i][4]代表下表为i天的时候第二次卖出手上五股票最大收益
来看初始化第0天没有操作所以dp[0][0] o
第0天做第一次买入, dp[0][1] -prices[0]
第0天做第一次卖出, dp[0][2] 0
第0天做第二次买入, dp[0][3] -prices[0]
第0天做第二次卖出, dp[0][4]0
来看状态方程:
dp[i][0] dp[i-1][0]
dp[i][1] max(dp[i-1][1],dp[i-1][0]-prices[i])其中dp[i][1]有两个操作1)第i天没有操作2)第i天买入股票所以此时最大收益应为这两个操作比大小
dp[i][2] max(dp[i-1][2],dp[i-1][1] prices[i])其中dp[i][2]有两个操作1)第i天没有操作2)第i天卖出股票所以此时最大收益应该为这两个操作比大小
dp[i][3] max(dp[i-1][3],dp[i-1][2]-prices[i])其中dp[i][3]有两个操作1)第i天没有操作2)第i天买入股票所以此时最大收益应该为这两个操作比大小
dp[i][4] max(dp[i-1][4],dp[i-1][3] prices[i])其中dp[i][4]有两个操作1)第i天没有操作2第i天卖出股票所以此时最大收益应该为这两个操作比大小import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可* 两次交易所能获得的最大收益* param prices int整型一维数组 股票每一天的价格* return int整型*/public int maxProfit (int[] prices) {// write code here// 我们先解读题意题目中给了一个限定条件:最多买卖两次也就是说他与股票(一次交易不同)点就是多了一次交易。但是多了一次交易就会产生巨大的变化。// 股票(一次交易)只有两个状态但是本题就5个状态: 1)不操作2)第一次购买3)第一次卖出4)第二次购买5)第二次卖出// 即db[i][j]代表第i天状态为j时产生的最大收益// dp[i][0]代表下标为i天的时候手上没有股票最大收益// dp[i][1]代表下表为i天的时候第一次购买手上有股票最大收益// dp[i][2]代表下表为i天的时候第一次卖出手上无股票最大收益// dp[i][3]代表下表为i天的时候第二次购买手上有股票最大收益// dp[i][4]代表下表为i天的时候第二次卖出手上五股票最大收益int nprices.length;int [][]dp new int[n][5];// 来看初始化第0天没有操作所以dp[0][0] 0// 第0天做第一次买入, dp[0][1] -prices[0]// 第0天做第一次卖出, dp[0][2] 0// 第0天做第二次买入, dp[0][3] -prices[0]// 第0天做第二次卖出, dp[0][4]0 dp[0][0]0;dp[0][1]-prices[0];dp[0][2]0;dp[0][3] -prices[0];dp[0][4]0;// 来看状态方程:for(int i1;in;i){// dp[i][0] dp[i-1][0]dp[i][0] dp[i-1][0];// dp[i][1] max(dp[i-1][1],dp[i-1][0]-prices[i])其中dp[i][1]有两个操作1)第i天没有操作2)第i天买入股票所以此时最大收益应为这两个操作比大小dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);// dp[i][2] max(dp[i-i][2],dp[i-1][1] prices[i])其中dp[i][2]有两个操作1)第i天没有操作2)第i天卖出股票所以此时最大收益应该为这两个操作比大小dp[i][2] Math.max(dp[i-1][2],dp[i-1][1] prices[i]);// dp[i][3] max(dp[i-1][3],dp[i-1][2]-prices[i])其中dp[i][3]有两个操作1)第i天没有操作2)第i天买入股票所以此时最大收益应该为这两个操作比大小dp[i][3] Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);// dp[i][4] max(dp[i][4],dp[i-1][3] prices[i])其中dp[i][4]有两个操作1)第i天没有操作2第i天卖出股票所以此时最大收益应该为这两个操作比大小dp[i][4] Math.max(dp[i-1][4],dp[i-1][3] prices[i]);}return dp[n - 1][4];}
}2023-3-12 15:29:28
NC126换钱的最少货币数
2023-3-12 15:30:08
NC126 兑换零钱(一)
-3、 设计思想
这道题你读完就会发现是完全背包问题如果你看过背包9讲这个题非常简单了。
首先我们定义一个dp[i]代表给定钱数为i的时候最少货币数是多少
然后我们确定状态转移方程假如给定钱币数为i那么它的换钱方案将由两个方案1)没办法兑换钱币arr[i]所以dp[i]dp[i] 2arr[i]可以兑换那么dp[i]dp[i-arr[i]1]。所以dp[i]min(dp[i],dp[i-arr[i]])
初始化dp数组首先当给定钱数为0的时候不需要兑换钱币所以dp[O]0但是我们要找一个最小值所以需要将下标非0的元素初始化为一个很大的import java.util.*;public class Solution {/*** 最少货币数* param arr int整型一维数组 the array* param aim int整型 the target* return int整型*/public int minMoney (int[] arr, int aim) {// write code here// 这道题你读完就会发现是完全背包问题如果你看过背包9讲这个题非常简单了。int Maxaim1;//定义一个全局最大数// 首先我们定义一个dp[i]代表给定钱数为i的时候最少货币数是多少int [] dpnew int[aim1];Arrays.fill(dp,Max);//把dp数组全部定为最大值// 然后我们确定状态转移方程假如给定钱币数为i那么它的换钱方案将由两个方案1)没办法兑换钱币arr[i]所以dp[i]dp[i] 2arr[i]可以兑换那么dp[i]dp[i-arr[i]1]。所以dp[i]min(dp[i],dp[i-arr[i]])// 初始化dp数组首先当给定钱数为0的时候不需要兑换钱币所以dp[O]0但是我们要找一个最小值所以需要将下标非0的元素初始化为一个很大的dp[0]0;for(int i 1;i aim;i ){// 遍历目标值for(int j 0;j arr.length;j ){// 遍历钱币if(arr[j] i){//如果当前的钱币比目标值小就可以兑换dp[i] Math.min(dp[i],dp[i-arr[j]] 1);}}}return dp[aim] aim ? -1 : dp[aim];}
}2023-3-12 15:42:35
NC45实现二叉树先序中序和后序遍历递归
NC45 实现二叉树先序中序和后序遍历
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* }*/public class Solution {ArrayListInteger prenew ArrayList();ArrayListInteger innew ArrayList();ArrayListInteger postnew ArrayList();/*** * param root TreeNode类 the root of binary tree* return int整型二维数组*/public int[][] threeOrders (TreeNode root) {// write code hereif(root null) return new int[][]{{},{},{}};//根节点为空直接返回ArrayListArrayListInteger res new ArrayList();//临时存储最终结果preOrders(root);inOrders(root);postOrders(root);res.add(new ArrayList(pre));//将先序遍历放进resres.add(new ArrayList(in));//将中序遍历放进resres.add(new ArrayList(post));//将后序遍历放进resint [][]ans new int[res.size()][res.get(0).size()];//用于返回最终的结果///需要将res的结果复制到ans里面for(int i 0;i res.size();i ){for(int j 0;j res.get(0).size();j ){ans[i][j] res.get(i).get(j);}}return ans;}public void preOrders(TreeNode root){if(rootnull){return ;}pre.add(root.val);preOrders(root.left);preOrders(root.right);}public void inOrders(TreeNode root){if(rootnull){return ;}inOrders(root.left);in.add(root.val);inOrders(root.right);} public void postOrders(TreeNode root){if(rootnull){return ;}postOrders(root.left);postOrders(root.right);post.add(root.val);}}2023-3-12 15:51:19
NC90 设计getMin功能的栈
2023-3-12 15:52:22
NC90 包含min函数的栈
-3、设计思想:
首先我们定义两个栈s1、s2s1就用来存储给定的数据s2用来维护栈的最小元素。
然后你需要定义3个函数1)Push 入栈2Pop出栈 3)getMin()获取最小值
Push:每次往s1加入一个元素后需要判断s2的栈顶元素是否比它大如果大就插入到s2
Pop:每次弹出一个的时候需要判断它和s2中的栈顶元素是否相等如果相等s2还得出栈
getMin:直接返回s2的栈顶元素就好了
import java.util.Stack;public class Solution {// 首先我们定义两个栈s1、s2s1就用来存储给定的数据s2用来维护栈的最小元素。StackInteger s1new Stack();StackInteger s2new Stack();// 然后你需要定义3个函数1)Push 入栈2Pop出栈 3)getMin()获取最小值// Push:每次往s1加入一个元素后需要判断s2的栈顶元素是否比它大如果大就插入到s2public void push(int node) {s1.push(node);if(s2.isEmpty()||s2.peek()node){s2.push(node);}}// Pop:每次弹出一个的时候需要判断它和s2中的栈顶元素是否相等如果相等s2还得出栈public void pop() {if(!s1.isEmpty()){if(s1.peek().equals(s2.peek())){s2.pop();}s1.pop();}}public int top() {return s1.peek();}// getMin:直接返回s2的栈顶元素就好了public int min() {return s2.peek();}
}
2023-3-12 16:08:18
NC67连续子数组的最大和
已做
NC115栈和排序
-3、 设计思想
因为要满足字典序最大所以第一个出栈的元素一定是n所以我们需要定义一个n来控制元素的出栈顺序为了满足字典序最大我们还得知道哪些元素己经入了栈因为n-1有可能在n之前就入栈了所以我们需要使用标记数组来指定哪些那些较大的数据入栈因为这些数据可以提取出栈
那么我们就遍历一遍数据通过n和标记数组来控制出栈的顺序如果数据遍历完栈还没有空我们只能将栈中元素全部弹出import java.util.*;public class Solution {/*** 栈排序* param a int整型一维数组 描述入栈顺序* return int整型一维数组*/public int[] solve (int[] a) {// write code hereStackInteger s new Stack();//定义一个栈用来存储数据int n a.length;int []res new int[n];//用来返回结果int cnt 0;boolean []vis new boolean[n10];//用来标记哪个数字出现过for(int i 0;i a.length;i ){//遍历数组s.push(a[i]);//压入栈vis[a[i]] true;//压入一个数就把对应的数字标记为truewhile(n0 vis[n]) n--;//检测现有栈中有多少个数出现了就是较大的哪些数出现了从大到小while(!s.empty() n s.peek()){//然后将栈中n的元素出栈res[cnt ] s.pop();}}//如果栈没为空就按照栈中原样直接出栈while(!s.empty()){res[cnt] s.pop();}return res;}
}2023-3-12 16:23:28
NC73数组中出现次数超过一半的数字
2023-3-12 16:24:14
NC73 数组中出现次数超过一半的数字
import java.util.*;
public class Solution {public int MoreThanHalfNum_Solution(int [] array) {HashMapInteger,Integer mapnew HashMap();for(int i0;iarray.length;i){if(!map.containsKey(array[i])){map.put(array[i],1);}else{map.put(array[i],1map.get(array[i]));}}for(int i0;iarray.length;i){if(map.get(array[i])array.length/2){return(array[i]);}}return 0;}
}2023-3-12 16:28:09
NC134股票无限次交易
2023-3-12 16:29:51
NC134 买卖股票的最好时机(二)
-3、 设计思想
因为是不限交易次数所以我们可以将问题简化到只要有正收益就可以即prices[i] - prices[i-1]〉0时就可以加入到我们最终的收益总和
所以只需要遍历一遍数组求一下prices[i] - prices[i-1]就解决了import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可* 计算最大收益* param prices int整型一维数组 股票每一天的价格* return int整型*/public int maxProfit (int[] prices) {// write code hereint res0;for(int i1;iprices.length;i){if(prices[i]-prices[i-1]0){resprices[i]-prices[i-1];}}return res;}
}NC114旋转字符串
2023-3-12 16:33:22
NC114 旋转字符串
import java.util.*;public class Solution {/*** 旋转字符串* param A string字符串 * param B string字符串 * return bool布尔型*/public boolean solve (String A, String B) {// write code here/*如果字符串的长度都不相同就直接返回false如果长度相同就让A字符串拼接自己然后在判断有没有B这个字符串*/return A.length() B.length() ? (AA).contains(B) : false;}
}最后
2023-3-12 16:35:42
这篇博客能写好的原因是站在巨人的肩膀上
这篇博客要写好的目的是做别人的肩膀
开源为爱发电
学习为我而行
