31. 下一个排列实现获取下一个排列的函数算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列则将数字重新排列成最小的排列即升序排列。必须原地修改只允许使用额外常数空间。以下是一些例子输入位于左侧列其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1来源力扣LeetCode链接https://leetcode-cn.com/problems/next-permutation本质上这种题有两种情况:(1):如果是降序数组,则下一个排列数字为最小数字,即将数组全部反转即可;(2):一般情况,首先定义两个index1和index2指针用于保存左右要交换的数字,首先从后往前遍历,得到第一次的nums[i - 1] nums[i],将下标保存分别赋值index1i-1,index2i,(如果遍历完后index还是等于-1,即数组为降序数组,直接反转数组即可),而index2不一定是当前下标,需要从iindex2到数组末尾继续遍历,如果nums[i] nums[index1]就继续遍历赋值,最后反转index1 1到数组末尾的数字即可得到下一个排列;class Solution { public void nextPermutation(int[] nums) { int index1 -1, index2 -1; for (int i nums.length - 1; i 0; i--) { if (nums[i] nums[i - 1]) { index1 i - 1; index2 i; break; } } if (index1 -1) { int start 0, end nums.length - 1; while (start end) { int temp nums[start]; nums[start] nums[end]; nums[end--] temp; } return; } for (int i index2; i nums.length; i) { if (nums[i] nums[index1]) index2 i; } int temp nums[index1]; nums[index1] nums[index2]; nums[index2] temp; int start index1 1, end nums.length - 1; while (start end) { int tem nums[start]; nums[start] nums[end]; nums[end--] tem; } } }145. 二叉树的后序遍历给定一个二叉树返回它的 后序 遍历。示例:输入: [1,null,2,3]1\2/3输出: [3,2,1]来源力扣LeetCode链接https://leetcode-cn.com/problems/binary-tree-postorder-traversal递归方式/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { ListInteger list new ArrayList(); public ListInteger postorderTraversal(TreeNode root) { post(root); return list; } public void post(TreeNode root){ if(root null){ return ; } postorderTraversal(root.left); postorderTraversal(root.right); list.add(root.val); } }迭代方式求二叉树后序遍历可以如下操作用stack存储当前节点的左右子树output保存输出当前节点 结束后对output在进行翻转/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { public ListInteger postorderTraversal(TreeNode root) { LinkedListTreeNode stack new LinkedList(); LinkedListInteger output new LinkedList(); if (root null) { return output; } stack.add(root); while (!stack.isEmpty()) { TreeNode node stack.pollLast(); output.addFirst(node.val); if (node.left ! null) { stack.add(node.left); } if (node.right ! null) { stack.add(node.right); } } return output; } }412. Fizz Buzz写一个程序输出从 1 到 n 数字的字符串表示。1. 如果 n 是3的倍数输出“Fizz”2. 如果 n 是5的倍数输出“Buzz”3.如果 n 同时是3和5的倍数输出 “FizzBuzz”。示例n 15,返回:[1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz]来源力扣LeetCode链接https://leetcode-cn.com/problems/fizz-buzzclass Solution { public ListString fizzBuzz(int n) { ListString list new ArrayList(); for (int i 1; i n; i) { StringBuilder sb new StringBuilder(); if(i % 3 0 ){ sb.append(Fizz); } if(i %5 0){ sb.append(Buzz); } if(sb.toString().equals()){ sb.append(i); } list.add(sb.toString()); } return list; } }1171. 从链表中删去总和值为零的连续节点给你一个链表的头节点 head请你编写代码反复删去链表中由 总和 值为 0 的连续节点组成的序列直到不存在这样的序列为止。删除完毕后请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。注意下面示例中的所有序列都是对 ListNode 对象序列化的表示。示例 1输入head [1,2,-3,3,1]输出[3,1]提示答案 [1,2,1] 也是正确的。示例 2输入head [1,2,3,-3,4]输出[1,2,4]示例 3输入head [1,2,3,-3,-2]输出[1]提示给你的链表中可能有 1 到 1000 个节点。对于链表中的每个节点节点的值-1000 node.val 1000.来源力扣LeetCode链接https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val x; } * } */ class Solution { /* 我们可以考虑如果给的入参不是链表是数组的话只需要求出前缀和对于前缀和相同的项 那他们中间的部分即是可以消除掉的比如以 [1, 2, 3, -3, 4] 为例 其前缀和数组为 [1, 3, 6, 3, 7] 我们发现有两项均为 3则 6 和 第二个 3 所对应的原数组中的数字是可以消掉的。换成链表其实 也是一 样的思路把第一个 3 的 next 指向第二个 3 的 next 即可 */ public ListNode removeZeroSumSublists(ListNode head) { ListNode dummy new ListNode(0); dummy.next head; MapInteger, ListNode prefixSumMap new HashMap(); ListNode p dummy; int prefixSum 0; while (p ! null) { prefixSum p.val; if (prefixSumMap.containsKey(prefixSum)) { p prefixSumMap.get(prefixSum).next; int val prefixSum p.val; while (val ! prefixSum) { //以下代码是删去 两个前缀和相同的结点之间的结点 //不然会导致之后可能某些结点的前缀和错误匹配了本应该被删去的节点 prefixSumMap.remove(val); p p.next; val p.val; } prefixSumMap.get(prefixSum).next p.next; } else { prefixSumMap.put(prefixSum, p); } p p.next; } return dummy.next; } }344. 反转字符串编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。示例 1输入[h,e,l,l,o]输出[o,l,l,e,h]示例 2输入[H,a,n,n,a,h]输出[h,a,n,n,a,H]来源力扣LeetCode链接https://leetcode-cn.com/problems/reverse-stringclass Solution { public void reverseString(char[] s) { for (int i 0,j s.length-1; i j; i,j--) { char temp s[i]; s[i] s[j]; s[j] temp; } } }19. 删除链表的倒数第N个节点给定一个链表删除链表的倒数第 n 个节点并且返回链表的头结点。示例给定一个链表: 1-2-3-4-5, 和 n 2.当删除了倒数第二个节点后链表变为 1-2-3-5.说明给定的 n 保证是有效的。来源力扣LeetCode链接https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list一次遍历算法首先我们将添加一个哑结点作为辅助该结点位于列表头部。哑结点用来简化某些极端情况例如列表中只含有一个结点或需要删除列表的头部。上述算法可以优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n1 步而第二个指针将从列表的开头出发。现在这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。删除链表的倒数第 N 个元素/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val x; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode first dummy; ListNode second dummy; for (int i 1; i n 1; i) { first first.next; } while (first ! null) { first first.next; second second.next; } second.next second.next.next; return dummy.next; } }
31. 下一个排列实现获取下一个排列的函数算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列则将数字重新排列成最小的排列即升序排列。必须原地修改只允许使用额外常数空间。以下是一些例子输入位于左侧列其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1来源力扣LeetCode链接https://leetcode-cn.com/problems/next-permutation本质上这种题有两种情况:(1):如果是降序数组,则下一个排列数字为最小数字,即将数组全部反转即可;(2):一般情况,首先定义两个index1和index2指针用于保存左右要交换的数字,首先从后往前遍历,得到第一次的nums[i - 1] nums[i],将下标保存分别赋值index1i-1,index2i,(如果遍历完后index还是等于-1,即数组为降序数组,直接反转数组即可),而index2不一定是当前下标,需要从iindex2到数组末尾继续遍历,如果nums[i] nums[index1]就继续遍历赋值,最后反转index1 1到数组末尾的数字即可得到下一个排列;class Solution { public void nextPermutation(int[] nums) { int index1 -1, index2 -1; for (int i nums.length - 1; i 0; i--) { if (nums[i] nums[i - 1]) { index1 i - 1; index2 i; break; } } if (index1 -1) { int start 0, end nums.length - 1; while (start end) { int temp nums[start]; nums[start] nums[end]; nums[end--] temp; } return; } for (int i index2; i nums.length; i) { if (nums[i] nums[index1]) index2 i; } int temp nums[index1]; nums[index1] nums[index2]; nums[index2] temp; int start index1 1, end nums.length - 1; while (start end) { int tem nums[start]; nums[start] nums[end]; nums[end--] tem; } } }145. 二叉树的后序遍历给定一个二叉树返回它的 后序 遍历。示例:输入: [1,null,2,3]1\2/3输出: [3,2,1]来源力扣LeetCode链接https://leetcode-cn.com/problems/binary-tree-postorder-traversal递归方式/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { ListInteger list new ArrayList(); public ListInteger postorderTraversal(TreeNode root) { post(root); return list; } public void post(TreeNode root){ if(root null){ return ; } postorderTraversal(root.left); postorderTraversal(root.right); list.add(root.val); } }迭代方式求二叉树后序遍历可以如下操作用stack存储当前节点的左右子树output保存输出当前节点 结束后对output在进行翻转/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { public ListInteger postorderTraversal(TreeNode root) { LinkedListTreeNode stack new LinkedList(); LinkedListInteger output new LinkedList(); if (root null) { return output; } stack.add(root); while (!stack.isEmpty()) { TreeNode node stack.pollLast(); output.addFirst(node.val); if (node.left ! null) { stack.add(node.left); } if (node.right ! null) { stack.add(node.right); } } return output; } }412. Fizz Buzz写一个程序输出从 1 到 n 数字的字符串表示。1. 如果 n 是3的倍数输出“Fizz”2. 如果 n 是5的倍数输出“Buzz”3.如果 n 同时是3和5的倍数输出 “FizzBuzz”。示例n 15,返回:[1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz]来源力扣LeetCode链接https://leetcode-cn.com/problems/fizz-buzzclass Solution { public ListString fizzBuzz(int n) { ListString list new ArrayList(); for (int i 1; i n; i) { StringBuilder sb new StringBuilder(); if(i % 3 0 ){ sb.append(Fizz); } if(i %5 0){ sb.append(Buzz); } if(sb.toString().equals()){ sb.append(i); } list.add(sb.toString()); } return list; } }1171. 从链表中删去总和值为零的连续节点给你一个链表的头节点 head请你编写代码反复删去链表中由 总和 值为 0 的连续节点组成的序列直到不存在这样的序列为止。删除完毕后请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。注意下面示例中的所有序列都是对 ListNode 对象序列化的表示。示例 1输入head [1,2,-3,3,1]输出[3,1]提示答案 [1,2,1] 也是正确的。示例 2输入head [1,2,3,-3,4]输出[1,2,4]示例 3输入head [1,2,3,-3,-2]输出[1]提示给你的链表中可能有 1 到 1000 个节点。对于链表中的每个节点节点的值-1000 node.val 1000.来源力扣LeetCode链接https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val x; } * } */ class Solution { /* 我们可以考虑如果给的入参不是链表是数组的话只需要求出前缀和对于前缀和相同的项 那他们中间的部分即是可以消除掉的比如以 [1, 2, 3, -3, 4] 为例 其前缀和数组为 [1, 3, 6, 3, 7] 我们发现有两项均为 3则 6 和 第二个 3 所对应的原数组中的数字是可以消掉的。换成链表其实 也是一 样的思路把第一个 3 的 next 指向第二个 3 的 next 即可 */ public ListNode removeZeroSumSublists(ListNode head) { ListNode dummy new ListNode(0); dummy.next head; MapInteger, ListNode prefixSumMap new HashMap(); ListNode p dummy; int prefixSum 0; while (p ! null) { prefixSum p.val; if (prefixSumMap.containsKey(prefixSum)) { p prefixSumMap.get(prefixSum).next; int val prefixSum p.val; while (val ! prefixSum) { //以下代码是删去 两个前缀和相同的结点之间的结点 //不然会导致之后可能某些结点的前缀和错误匹配了本应该被删去的节点 prefixSumMap.remove(val); p p.next; val p.val; } prefixSumMap.get(prefixSum).next p.next; } else { prefixSumMap.put(prefixSum, p); } p p.next; } return dummy.next; } }344. 反转字符串编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。示例 1输入[h,e,l,l,o]输出[o,l,l,e,h]示例 2输入[H,a,n,n,a,h]输出[h,a,n,n,a,H]来源力扣LeetCode链接https://leetcode-cn.com/problems/reverse-stringclass Solution { public void reverseString(char[] s) { for (int i 0,j s.length-1; i j; i,j--) { char temp s[i]; s[i] s[j]; s[j] temp; } } }19. 删除链表的倒数第N个节点给定一个链表删除链表的倒数第 n 个节点并且返回链表的头结点。示例给定一个链表: 1-2-3-4-5, 和 n 2.当删除了倒数第二个节点后链表变为 1-2-3-5.说明给定的 n 保证是有效的。来源力扣LeetCode链接https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list一次遍历算法首先我们将添加一个哑结点作为辅助该结点位于列表头部。哑结点用来简化某些极端情况例如列表中只含有一个结点或需要删除列表的头部。上述算法可以优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n1 步而第二个指针将从列表的开头出发。现在这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。删除链表的倒数第 N 个元素/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val x; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode first dummy; ListNode second dummy; for (int i 1; i n 1; i) { first first.next; } while (first ! null) { first first.next; second second.next; } second.next second.next.next; return dummy.next; } }
