左闭右开
区间【left,right),对应代码：while(left < right) 右指针没意义，即right = nums.length
左闭右闭
区间【left,right】,对应代码：while(left <= right) 右指针有意义，即right = nums.length - 1;
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。 nums 的每个元素都将在 [-9999, 9999]之间。
class Solution{
public int search(int[] nums, int target){
int n = nums.length;
for(int i = 0; i < n; i++){
if(nums[i] == target){
return i;
}
}
return -1;
}
}
// nums = [-1,0,3,5,9,12], target = 8
class Solution {
public int search(int[] nums, int target) {
int left = 0 ; //指针
int right = nums.length - 1;
while(left <= right){ //终止条件
int mid = left + (right - left)/2; //中间值的索引
if(nums[mid] < target){ //目标值大于中间值,则中间值左边的值去掉，即左指针右移
left = mid + 1;
}else if(nums[mid] > target){ //目标值小于中间值，则去除右边的值，即右指针左移
right = mid - 1;
}else{
return mid; //相等，返回索引值
}
}
return -1; //目标值不在数组中
}
}
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1 示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
提示:
1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums 为 无重复元素 的 升序 排列数组 -104 <= target <= 104
题目中排序数组，适合用二分法 分析情况：
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0 ;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right-left)/2;
if(nums[mid] < target){
left = mid + 1;
}else if(nums[mid] > target){
right = mid - 1;
}else{
return mid; //情况1
}
}
return right + 1; //其他情况
}
}
给定一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1] 示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
提示：
0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 nums 是一个非递减数组 -10^9 <= target <= 10^9
分析:
// nums = [5,7,7,8,8,10], target = 8
// nums = [5,7,7,8,8,10], target = 6
class Solution {
public int[] searchRange(int[] nums, int target) {
int leftBorder = searchLeftBorder(nums, target);
int rightBorder = searchRightBorder(nums, target);
// 情况一
if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};
// 情况三
if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};
// 情况二
return new int[]{-1, -1};
}
public int searchLeftBorder(int[] nums,int target){
int left = 0;
int right = nums.length-1;
int leftBorder = -2;
while(left <= right){
int mid = left + (right - left)/2;
if(nums[mid] >= target){
right = mid - 1;
leftBorder = right;
}else{
left = mid + 1;
}
}
return leftBorder;
}
public int searchRightBorder(int[] nums,int target){
int left = 0;
int right = nums.length-1;
int rightBorder = -2;
while(left <= right){
int mid = left + (right - left)/2;
if(nums[mid] <= target){
left = mid + 1;
rightBorder = left;
}else{
right = mid - 1;
}
}
return rightBorder;
}
}
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2 示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1
class Solution{
public int mySqrt(int x){
int res = -1;
if(x == 0){
return 0;
}
if(x == 1){
return 1;
}
for(int i = 0; i <= x/2; i++){
if((long)i*i <= x){
res = i;
}else{
break;
}
}
return res;
}
}
class Solution{
public int mySqrt(int x){
int left = 0;
int right = x;
int res = -2;
while(left <= right){
int mid = left + (right - left)/2;
if( (long)mid*mid <= x){
res = mid;
left = mid + 1;
}else{
right = mid -1;
}
}
return res;
}
}
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16 输出：true 示例 2：
输入：num = 14 输出：false
提示：
1 <= num <= 2^31 - 1
与题目4思路是一致的，这里仅写二分法的代码
class Solution {
public boolean isPerfectSquare(int num) {
int left = 0;
int right = num;
while(left <= right){
int mid = left + (right - left)/2;
if((long)mid*mid == num){
return true;
}else if((long)mid*mid < num){
left = mid + 1;
}else{
right = mid -1;
}
}
return false;
}
}
符合下列属性的数组 arr 称为 山脉数组 ： arr.length >= 3 存在 i（0 < i < arr.length - 1）使得： arr[0] < arr[1] < ... arr[i-1] < arr[i] arr[i] > arr[i+1] > ... > arr[arr.length - 1] 给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
示例 1：
输入：arr = [0,1,0] 输出：1 示例 2：
输入：arr = [0,2,1,0] 输出：1 示例 3：
输入：arr = [0,10,5,2] 输出：1 示例 4：
输入：arr = [3,4,5,1] 输出：2 示例 5：
输入：arr = [24,69,100,99,79,78,67,36,26,19] 输出：2
提示：
3 <= arr.length <= 10^4 0 <= arr[i] <= 10^6 题目数据保证 arr 是一个山脉数组
进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？
分析题目： 使用二分法解决该问题，可知满足的条件为中间索引对应的值大于前一个索引对应的值同时大于后一个索引对应的值
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 0;
int right = arr.length -1 ;
while(left <= right){
int mid = left + (right - left)/2;
if(arr[mid] < arr[mid-1] && arr[mid] > arr[mid+1]){ //当前值小于前面的值而大于后面的值，峰顶在左边
right = mid;
}else if(arr[mid] > arr[mid-1] && arr[mid] < arr[mid+1]){ //当前值大于前面值而小于后面值，峰顶在右边
left = mid;
}else{ //比前、后值都大,即为峰顶
return mid;
}
}
return 0; //无意义，本题中必定能找到峰顶
}
}
给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时，字母是依序循环出现的。举个例子：
如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'
示例 1：
输入: letters = ["c", "f", "j"]，target = "a" 输出: "c" 示例 2:
输入: letters = ["c","f","j"], target = "c" 输出: "f" 示例 3:
输入: letters = ["c","f","j"], target = "d" 输出: "f"
提示：
2 <= letters.length <= 104 letters[i] 是一个小写字母 letters 按非递减顺序排序 letters 最少包含两个不同的字母 target 是一个小写字母
分析：
情况①：目标值在列表左边或者在列表的右边（可以等于最右的那个值），返回letters[0];
情况②：目标值在列表里，可以不等于列表的值。
思考：用二分法时，在终止条件是，左指针指向的值总是大于目标值，右指针指向的值总是小于目标值。利用该特性与本题结合，可知返回值为letters[left]
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
//情况①
if(letters[0] > target || letters[letters.length-1] <= target){
return letters[0];
}
//情况②
int left = 0;
int right = letters.length - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(letters[mid] > target){
right = mid - 1;
}else if(letters[mid] <= target){
left = mid + 1;
}
}
return letters[left];
}
}
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝 int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }
示例 1：
输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。 示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3] 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 100 0 <= nums[i] <= 50 0 <= val <= 100
须知：在数组内“移除”元素只能是覆盖。 移除所有等于val的元素，相当于用不等于val的元素去覆盖等于val的元素。 本题中使用双指针法，快指针fast指向不等于val的值就覆盖前一个值，慢指针指向的就是前一个值。
class Solution {
public int removeElement(int[] nums, int val) {
int fast = 0;
int slow;
for(slow = 0; fast < nums.length;fast++){
if(nums[fast] != val){ //快指针指向的值不等于val
nums[slow] = nums[fast]; //覆盖
slow++; //慢指针后移
}
}
return slow; //此时慢指针的值就是不等于val的数组新长度。
}
}
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组 int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; } 如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。 示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 10^4 -10^4 <= nums[i] <= 10^4 nums 已按 升序 排列
无
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 1;
for(int fast = 1;fast < nums.length;fast++){
if(nums[fast] != nums[fast-1]){
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
}
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2:
输入: nums = [0] 输出: [0]
提示:
1 <= nums.length <= 10^4 -2^31 <= nums[i] <= 2^31 - 1
无
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
int fast = 0;
while(fast < nums.length){
if(nums[fast] != 0){
swap(nums,slow,fast);
slow++;
}
fast++;
}
}
public void swap(int[] nums,int slow,int fast){
int flag = nums[slow];
nums[slow] = nums[fast];
nums[fast] = flag;
}
}
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c" 输出：true 解释：s 和 t 都会变成 "ac"。 示例 2：
输入：s = "ab##", t = "c#d#" 输出：true 解释：s 和 t 都会变成 ""。 示例 3：
输入：s = "a#c", t = "b" 输出：false 解释：s 会变成 "c"，但 t 仍然是 "b"。
提示：
1 <= s.length, t.length <= 200 s 和 t 只含有小写字母以及字符 '#'
进阶：
你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？
没理清
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0)
{
// 先找到 s 中第一个需要比较的字符（即去除 # 影响后的第一个待比较字符）
while (i >= 0)
{
if (s.charAt(i) == '#')
{
skipS ++;
i --;
}
else if (skipS > 0)
{
skipS --;
i --;
}
else
{
break;
}
}
// 再找到 t 中第一个需要比较的字符（即去除 # 影响后的第一个待比较字符）
while (j >= 0)
{
if (t.charAt(j) == '#')
{
skipT ++;
j --;
}
else if (skipT > 0)
{
skipT --;
j --;
}
else
{
break;
}
}
// 然后开始比较,注意有下面这个 if 条件的原因是：如果 index = 0 位置上为 '#'，则 i, j 会为 -1
// 而 index = -1 的情况应当处理。
if (i >= 0 && j >= 0)
{
// 如果待比较字符不同，return false
if (s.charAt(i) != t.charAt(j))
return false;
}
// (i >= 0 && j >= 0) 为 false 情况为
// 1. i < 0 && j >= 0
// 2. j < 0 && i >= 0
// 3. i < 0 && j < 0
// 其中，第 3 种情况为符合题意情况，因为这种情况下 s 和 t 都是 index = 0 的位置为 '#' 而这种情况下
// 退格空字符即为空字符，也符合题意，应当返回 True。
// 但是，情况 1 和 2 不符合题意，因为 s 和 t 其中一个是在 index >= 0 处找到了待比较字符，另一个没有找到
// 这种情况显然不符合题意，应当返回 False，下式便处理这种情况。
else if (i >= 0 || j >= 0)
return false;
i--;
j--;
}
return true;
}
}
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100] 示例 2：
输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]
提示：
1 <= nums.length <= 10^4 -10^4 <= nums[i] <= 10^4 nums 已按 非递减顺序 排序
进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题
题目中的数组是非递减顺序排序，可知数值平方后的最大值是在左右两边产生的。 需要双指针分别指向左，右。
class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length - 1;
int index = j;
int[] res = new int[nums.length];
while(left <= right){
if(nums[left] * nums[left] > nums[right] * nums[right]){
res[index] = nums[left] * nums[left];
left++;
}else{
res[index] = nums[right] * nums[right];
right--;
}
index--;
}
return res;
}
}
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例 1：
输入: s = "A man, a plan, a canal: Panama" 输出：true 解释："amanaplanacanalpanama" 是回文串。 示例 2：
输入：s = "race a car" 输出：false 解释："raceacar" 不是回文串。 示例 3：
输入：s = " " 输出：true 解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。 由于空字符串正着反着读都一样，所以是回文串。
提示：
1 <= s.length <= 2 * 10^5 s 仅由可打印的 ASCII 字符组成
class Solution {
public boolean isPalindrome(String s) {
char[] c = s.toLowerCase().toCharArray();
int i=0, j=c.length-1;
while(i <= j){
while(!isValid(c[i]) && i<j){ //非数字字母
i++;
}
while(!isValid(c[j]) && i<j){
j--;
}
if(c[i] != c[j]){ //数字字母，判断是否相等
return false;
}
i++;
j--;
}
return true;
}
//判断是否是小写字母或数字
private boolean isValid(char c){
return (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
}
}
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。 示例 2：
输入：target = 4, nums = [1,4,4] 输出：1 示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0
提示：
1 <= target <= 10^9 1 <= nums.length <= 10^5 1 <= nums[i] <= 10^5
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int i = 0;
int res = Integer.MAX_VALUE;
int sum = 0;
int subLength = 0;
for(int j = 0;j < nums.length;j++){
sum += nums[j]; //求和
while(sum >= target){
subLength = j - i + 1; //计算满足条件的数组子长度
res = res < subLength ? res : subLength;
sum -= nums[i++];
}
}
//若res为整型的最大值，说明数组的所有数加起来都比target小，返回0；
return res == Integer.MAX_VALUE ? 0 : res;
}
}
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
示例 1：
输入：fruits = [1,2,1] 输出：3 解释：可以采摘全部 3 棵树。 示例 2：
输入：fruits = [0,1,2,2] 输出：3 解释：可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。 示例 3：
输入：fruits = [1,2,3,2,2] 输出：4 解释：可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。 示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出：5 解释：可以采摘 [1,2,1,1,2] 这五棵树。
题目分析： 从某一棵树开始采摘，且必须连续采摘而不多于2种类型（值相同为同类型）的果树。如fruits = [1,2,3,2,2]，若从1开始采摘，则只能采摘到2，因为3与前面的都不是同一类型的果树。从2开始的话，能够采摘到2,3,2,2。题目中需要返回的是子数组的最大长度。 思考： 如果从头遍历数组，在遍历到该元素时，也就从该元素开始采摘。如何记录果树的类型不大于2 ?? 解决完果树类型不大于2时，同时记录子数组的长度，再返回即可。
现需要记录当前遍历的左右果树，分别用ln表示左果树类型、rn表示右果树类型。同时左（慢）指针，右（快）指针开始寻找能够装下篮子（果树类型）的水果，若右指针指向的果树类型与ln或者rn相同，记下此时能够装下的最大长度，右指针继续移动。若右指针指向的果树类型不同于ln、rn，即当前有3中类型的果树，因此需要左指针右移到右指针的前一个位置（不能是left++,参考示例4），再更新左、右果树类型。由于开始时左、右果树类型都是一样，此时需要进行判断，因为左指针移到右指针的前一个位置，但可能出现与左果树类型相同的情况。记录长度，返回即可。
class Solution {
public int totalFruit(int[] fruits) {
int left =0,right = 0; //左右指针
int ans = 0; //记录长度
int ln = fruits[left],rn = fruits[right]; //篮子一号和二号（左、右果树类型，此时果树类型相同）
while(right < fruits.length){
if(fruits[right] == rn || fruits[right] == ln){//属于篮子某个种类
ans = Math.max(ans,right - left + 1); //更新结果，每次取一个数就更新一下
right++;
}else{//如果遇到第三种，把慢指针移动到快指针前一步，该步的水果种类必然不同于快指针，此时慢指针慢慢回退齐所有的连续同类。
left = right - 1; //取到第三种则移动左标到right -1
ln = fruits[left]; //更新第一个篮子
while(left >= 1 && fruits[left - 1] == ln) { //左果树更新后回退至相同种类的开始位置
left--;
}
rn = fruits[right];
ans = Math.max(ans,right - left + 1);
}
}
return ans;
}
}
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1 输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7 输出：[]
提示：
列表中的节点数目在范围 [0, 10^4] 内 1 <= Node.val <= 50 0 <= val <= 50
/**
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode node = new ListNode(-1); //虚拟结点：仅仅是串起整条链，统一操作链表
node.next = head; //虚拟结点指向head
ListNode cur = node; //当前结点指向虚拟结点（node）
while(cur.next != null){
if(cur.next.val == val ){
cur.next = cur.next.next; //删除等于val的结点并后移
}else{
cur = cur.next; //后移
}
}
return node.next;
}
}
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。 addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。 addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。 addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。 deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
示例：
MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3 linkedList.get(1); //返回2 linkedList.deleteAtIndex(1); //现在链表是1-> 3 linkedList.get(1); //返回3
提示：
所有val值都在 [1, 1000] 之内。 操作次数将在 [1, 1000] 之内。 请不要使用内置的 LinkedList 库。
//单链表
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
// ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class MyLinkedList {
int size;
ListNode dummy; //虚拟头结点
public MyLinkedList() { //初始化
size = 0;
dummy = new ListNode(0);
}
public int get(int index) {
if(index < 0 || index >= size){ //超出索引位置
return -1;
}
ListNode cur = dummy;
for(int i = 0;i <= index;i++){
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0,val);
}
public void addAtTail(int val) {
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
if(index < 0){
index = 0;
}
if(index > size){
return;
}
size++;
ListNode pre = dummy;
for(int i = 0;i < index;i++){ //找 index-1 的结点
pre = pre.next;
}
ListNode add = new ListNode(val); //添加
add.next = pre.next;
pre.next = add;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
if (index == 0) {
dummy = dummy.next;
return;
}
ListNode pre = dummy;
for (int i = 0; i < index; i++) { //找 index-1 的结点
pre = pre.next;
}
pre.next = pre.next.next;
}
}
//双链表
public class ListNode {
int val;
ListNode next,prev;
ListNode() {}
ListNode(int val) { this.val = val; }
// ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class MyLinkedList {
int size;
ListNode head,tail;
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}
public int get(int index) {
if(index < 0 || index >= size){return -1;}
ListNode cur = head;
// 通过判断 index < (size - 1) / 2 来决定是从头结点还是尾节点遍历，提高效率
if(index < (size - 1) / 2){
for(int i = 0; i <= index; i++){ //从head开始
cur = cur.next;
}
}else{
cur = tail; //从tail开始
for(int i = 0; i <= size - index - 1; i++){
cur = cur.prev;
}
}
return cur.val;
}
public void addAtHead(int val) {
ListNode cur = head;
ListNode newNode = new ListNode(val);
newNode.next = cur.next;
cur.next.prev = newNode;
cur.next = newNode;
newNode.prev = cur;
size++;
}
public void addAtTail(int val) {
ListNode cur = tail;
ListNode newNode = new ListNode(val);
newNode.next = tail;
newNode.prev = cur.prev;
cur.prev.next = newNode;
cur.prev = newNode;
size++;
}
public void addAtIndex(int index, int val) {
if(index > size){return;}
if(index < 0){index = 0;}
ListNode cur = head;
for(int i = 0; i < index; i++){
cur = cur.next;
}
ListNode newNode = new ListNode(val);
newNode.next = cur.next;
newNode.prev = cur;
cur.next.prev = newNode;
cur.next = newNode;
size++;
}
public void deleteAtIndex(int index) {
if(index >= size || index < 0){return;}
ListNode cur = head;
for(int i = 0; i < index; i++){
cur = cur.next;
}
cur.next.next.prev = cur;
cur.next = cur.next.next;
size--;
}
}
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 示例 2：
输入：head = [1,2] 输出：[2,1] 示例 3：
输入：head = [] 输出：[]
提示：
链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
//双指针、迭代
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode prev = null;
ListNode temp = null; //保存下一个结点
while(cur != null){
temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
}
class Solution{
//递归
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
private ListNode reverse(ListNode prev, ListNode cur) {
if (cur == null) {
return prev;
}
ListNode temp = null;
temp = cur.next;// 先保存下一个节点
cur.next = prev;// 反转
// 更新prev、cur位置
// prev = cur;
// cur = temp;
return reverse(cur, temp);
}
}
//暴力，构建新链表
class Solution{
public ListNode reverseList(ListNode head){
ListNode ans = null;
for (ListNode x = head; x != null; x = x.next) {
ans = new ListNode(x.val,ans);
}
return ans;
}
}
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3] 示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100
//逻辑：
// 保存第二个节点，第一个节点指向第二层的返回值，再两两交换。
// 例子：1->2->3->4
// 第一层：
// 定义指针->2 1->??(第二层返回值) 1->4->3
// 当前层又进行交互：
// 2->1->4->3,返回定义的指针，即新的head
||
\/
// 进入第二层：
||
\/ /\
||
||
// 定义指针指向->4
// 3->??(进入第三层) 交换：4->3,返回
/\
||
// --> ----> 第三层为空，返回
class Solution {
public ListNode swapPairs(ListNode head) {
//递归的终止条件
if(head==null || head.next==null) {
return head;
}
//假设链表是 1->2->3->4
//这句就先保存节点2
ListNode tmp = head.next;
//继续递归，处理节点3->4
//当递归结束返回后，就变成了4->3
//于是head节点就指向了4，变成1->4->3
head.next = swapPairs(tmp.next);
//将2节点指向1
tmp.next = head;
return tmp;
}
}
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1] 提示：
链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
//法一：计算链表长度，找到要删除的前一个节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0,head);
ListNode cur = dummy;
int length = getLength(head); //获取链表长度
for(int i = 1;i < length -n +1;i++){ //要删除的前一个节点
cur = cur.next;
}
cur.next = cur.next.next; //删除倒数第n的节点
return dummy.next;
}
public int getLength(ListNode head){
int length = 0;
while(head != null){
length++;
head = head.next;
}
return length;
}
}
===================================================================
//法二：前后双指针（你走一步，我走一步）
class Solution{
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指针比second指针多n步
first = first.next;
}
while(first != null){ //你一步我一步，结束时second在要删除节点的前一个节点
first = first.next;
second = second.next;
}
second.next = second.next.next; //删除
return dummy.next;
}
}
===================================================================
//法三：递归
class Solution{
int cur = 0;
public ListNode removeNthFormEnd(ListNode head,int n){
if(head == null){ //递归终止条件
return null;
}
head.next = removeNthFormEnd(head.next,n);
cur++; //递归返回时都会执行，即寻找要删除的节点
if(n == cur){
return head.next; //直接抛弃要删除的节点，返回下一个节点
}
return head;
}
}
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。 提示：
listA 中节点数目为 m listB 中节点数目为 n 0 <= m, n <= 3 * 10^4 1 <= Node.val <= 10^5 0 <= skipA <= m 0 <= skipB <= n 如果 listA 和 listB 没有交点，intersectVal 为 0 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？
思考：两链表长度不一，如何进行遍历？ 可以计算出两链表的长度，进行差值，即有一个链表先移动（差值）步，再开始比较。分别用两指针指向当前该判断的位置。判断是否指针相等，若相等，则返回当前指针。若不等，则同时移动两个指针到下一个位置。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode cur1 = headA;
ListNode cur2 = headB;
int lengthA = 0;
int lengthB = 0;
while(cur1 != null){ //计算headA的长度
lengthA++;
cur1 = cur1.next;
}
while(cur2 != null){ //计算headB的长度
lengthB++;
cur2 = cur2.next;
}
cur1 = headA;
cur2 = headB;
if(lengthA > lengthB){ //判断长度的差值，使得指针在不同链表中的同一步
lengthA = lengthA - lengthB;
for(int i = 0;i < lengthA;i++){ //指针先移动lengthA步
cur1 = cur1.next;
}
}else{
lengthA = lengthB - lengthA;
for(int i = 0;i < lengthA;i++){
cur2 = cur2.next;
}
}
while(cur1 != null){ //判断当前指针是否相等
if(cur1 == cur2){ //相等
return cur1;
}
cur1 = cur1.next;
cur2 = cur2.next;
}
return null; //不相等
}
}
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。 提示：
链表中节点的数目范围在范围 [0, 10^4] 内 -10^5 <= Node.val <= 10^5 pos 的值为 -1 或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
//哈希
public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> temp = new HashSet<>();
ListNode a = head;
while(a != null){
temp.add(a);
a = a.next;
while(temp.contains(a)){
return a;
}
}
return null;
}
}
=========================================================
//快慢指针
public class Solution{
public ListNode detectCycle(ListNode head){
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {// 有环
ListNode index1 = fast;
ListNode index2 = head;
// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram" 输出: true
示例 2:
输入: s = "rat", t = "car" 输出: false 提示:
1 <= s.length, t.length <= 5 * 10^4 s 和 t 仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
//普通哈希,不符合unicode字符
class Solution {
public boolean isAnagram(String s, String t) {
int[] record = new int[26];
for(int i = 0;i < s.length();i++){
record[s.charAt(i) - 'a']++;
}
for(int i = 0;i < t.length();i++){
record[t.charAt(i) - 'a']--;
}
for(int var : record){
while(var != 0){
return false;
}
}
return true;
}
}
=========================================================
//进阶哈希
class Solution{
public boolean isAnagram(String s,String t){
if(s.length() != t.length()){
return false;
}
Map<Character,Integer> map = new HashMap<>();
for(int i = 0;i < s.length();i++){
char ch = s.charAt(i);
map.put(ch,map.getOrDefault(ch,0) +1);
}
for(int i = 0;i < t.length();i++){
char ch = t.charAt(i);
map.put(ch,map.getOrDefault(ch,0) -1);
if(map.get(ch) < 0){
return false;
}
}
return true;
}
}
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的 提示：
1 <= nums1.length, nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 1000 题目地址
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Set<Integer> res = new HashSet<>();
for(int var : nums1){
set.add(var);
}
for(int var : nums2){
if(set.contains(var)){
res.add(var);
}
}
int[] str = new int[res.size()];
int i = 0;
for(int var : res){
str[i++] = var;
}
return str;
// return res.stream().mapToInt(x -> x).toArray(); //流操作
}
}
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1，那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
示例 2：
输入：n = 2 输出：false 提示：
1 <= n <= 2^31 - 1
class Solution{
public boolean isHappy(int n){
Set<Integer> set = new HashSet<>();
if(n == 1){
return true;
}
while(n != 1 && !set.contains(n)){ //前一个条件用于循环，后一个条件用于判断不重复
set.add(n);
int total = 0;
while(n != 0){ //计算当前数的每一个位数的平方和，用total保存
int temp = n;
temp = temp%10;
n = n/10;
total += temp * temp;
}
if(total == 1){ //位数的平方和为1，符号条件
return true;
}
n = total; //赋值重新进入循环
}
return false;
}
}
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
提示：
2 <= nums.length <= 10^4 -109 <= nums[i] <= 10^9 -109 <= target <= 10^9 只会存在一个有效答案 进阶：你可以想出一个时间复杂度小于 O(n^2) 的算法吗？
class Solution{
public int[] twoSum(int[] nums,int target){
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
// Map<Integer,Integer> set = new HashMap<>();
// for(int i = 0; i < nums.length;i++){
// int n = target - nums[i];
// if(set.containsKey(n)){
// return new int[]{set.get(n),i};
// }
// set.put(nums[i],i);
// }
// return new int[0];
}
}
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] 输出：2 解释： 两个元组如下：
示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0] 输出：1
提示：
n == nums1.length n == nums2.length n == nums3.length n == nums4.length 1 <= n <= 200 -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
int temp;
int res = 0;
//统计两个数组中的元素之和，同时统计出现的次数，放入map
for (int i : nums1) {
for (int j : nums2) {
temp = i + j;
if (map.containsKey(temp)) {
map.put(temp, map.get(temp) + 1);
} else {
map.put(temp, 1);
}
}
}
//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
for (int i : nums3) {
for (int j : nums4) {
temp = i + j;
if (map.containsKey(0 - temp)) {
res += map.get(0 - temp);
}
}
}
return res;
}
}
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b" 输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab" 输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab" 输出：true 提示： 1 <= ransomNote.length, magazine.length <= 10^5 ransomNote 和 magazine 由小写英文字母组成
//Map
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int m = magazine.length();
int n = ransomNote.length();
Map<Character,Integer> map = new HashMap<>();
for(int i = 0; i < m;i++){
char c = magazine.charAt(i);
if(map.containsKey(c)){
map.put(c,map.get(c)+1);
}else{
map.put(c,1);
}
}
for(int i = 0; i < n;i++){
char c = ransomNote.charAt(i);
if(map.containsKey(c) && map.get(c) > 0){
map.put(c,map.get(c)-1);
}else{
return false;
}
}
return true;
}
}
============================================================
//数组
class Solution{
public boolean canConstruct(String ransomNote,String magazine){
//记录杂志字符串出现的次数
int[] arr = new int[26];
int temp;
for (int i = 0; i < magazine.length(); i++) {
temp = magazine.charAt(i) - 'a';
arr[temp]++;
}
for (int i = 0; i < ransomNote.length(); i++) {
temp = ransomNote.charAt(i) - 'a';
//对于金信中的每一个字符都在数组中查找
//找到相应位减一，否则找不到返回false
if (arr[temp] > 0) {
arr[temp]--;
} else {
return false;
}
}
return true;
}
}
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000 -10^5 <= nums[i] <= 10^5
大概懂
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
if (nums == null || nums.length <= 2) return ans;
Arrays.sort(nums); // O(nlogn)
for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
int target = -nums[i];
int left = i + 1, right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] == target) {
ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
// 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
left++; right--; // 首先无论如何先要进行加减操作
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (nums[left] + nums[right] < target) {
left++;
} else { // nums[left] + nums[right] > target
right--;
}
}
}
return ans;
}
}
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200 -10^9 <= nums[i] <= 10^9 -10^9 <= target <= 10^9
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0;i <= nums.length -4;i++){
if (nums[i] > 0 && nums[i] > target) { //排序后的数组第一个正数都比target大。
return res;
}
if (i > 0 && nums[i - 1] == nums[i]) { //排除前后数值相同
continue;
}
for(int j = i+1; j <= nums.length -3;j++){ //第二个指针j
if (j > i + 1 && nums[j - 1] == nums[j]) { //排除前后数值相同
continue;
}
int temp = nums[i] + nums[j]; //前2个指针的数值之和
int left = j + 1; //第三个指针
int right = nums.length -1; //第四个指针
while(left < right){
int total = temp + nums[left] + nums[right];
if(total > target){ //目标值小
right--;
}else if(total < target){ //目标值大
left++;
}else{ //相等
res.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));
while (right > left && nums[right] == nums[right - 1]){ //排除前后数值相同
right--;
}
while (right > left && nums[left] == nums[left + 1]){ //排除前后数值相同
left++;
}
left++; //继续看其他情况是否符合
right--;
}
}
}
}
return res;
}
}
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"] 示例 2：
输入：s = ["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
提示：
1 <= s.length <= 10^5 s[i] 都是 ASCII 码表中的可打印字符
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length -1;
while(left <= right){
if(s[left] != s[right]){
s[left] ^= s[right];
s[right] ^= s[left];
s[left] ^= s[right];
}
left++;
right--;
}
}
}
==============================================
//其他精简写法
int n = s.length;
for (int i = 0; i < n / 2; ++i) {
int j = n - 1 - i;
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
}
=================================================
int l = 0;
int r = s.length - 1;
while (l < r) {
s[l] ^= s[r]; //构造 a ^ b 的结果，并放在 a 中
s[r] ^= s[l]; //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
s[l] ^= s[r]; //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
l++;
r--;
}
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。 示例 1：
输入：s = "abcdefg", k = 2 输出："bacdfeg" 示例 2：
输入：s = "abcd", k = 2 输出："bacd"
提示：
1 <= s.length <= 10^4 s 仅由小写英文组成 1 <= k <= 10^4
题目理解：每隔2k个反转前k个，尾数不够k个时候全部反转
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0; i < ch.length; i += 2 * k){
int start = i;
//这里是判断尾数够不够k个来取决end指针的位置
int end = Math.min(ch.length - 1, start + k - 1);//字符串长度可能小于k，则尾指针使用总长度-1
//用异或运算反转
while(start < end){
ch[start] ^= ch[end];
ch[end] ^= ch[start];
ch[start] ^= ch[end];
start++;
end--;
}
}
return new String(ch);
}
}
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy." 输出："We%20are%20happy." 限制：
0 <= s 的长度 <= 10000
class Solution {
public String replaceSpace(String s) {
int length = s.length();
char[] array = new char[length * 3];
int size = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == ' ') {
array[size++] = '%';
array[size++] = '2';
array[size++] = '0';
} else {
array[size++] = c;
}
}
String newStr = new String(array, 0, size);
return newStr;
}
}
====================================================
class Solution{
public String replaceSpace(String s){
if (s == null) {
return null;
}
//选用 StringBuilder 单线程使用，比较快，选不选都行
StringBuilder sb = new StringBuilder();
//使用 sb 逐个复制 str ，碰到空格则替换，否则直接复制
for (int i = 0; i < s.length(); i++) {
//str.charAt(i) 为 char 类型，为了比较需要将其转为和 " " 相同的字符串类型
//if (" ".equals(String.valueOf(str.charAt(i)))){
if (s.charAt(i) == ' ') {
sb.append("%20");
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入：s = "the sky is blue" 输出："blue is sky the"
示例 2：
输入：s = " hello world " 输出："world hello" 解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = "a good example" 输出："example good a" 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
提示：
1 <= s.length <= 10^4 s 包含英文大小写字母、数字和空格 ' ' s 中 至少存在一个 单词
进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
class Solution {
public String reverseWords(String s) {
s = s.trim(); //去除前后空格
StringBuilder sb = new StringBuilder();
int end = s.length() - 1; //单词的尾指针
int start = end; //头指针
while(start >= 0){ //从后往前遍历
if(start == 0){ //当start为0时，直接加
sb.append(s,start,end + 1);
}
if(s.charAt(start) != ' '){ //当前字符不为' ',头指针找单词的头
start--;
}else{
// sb.append(s.substring(start + 1 , end+1)).append(' ');
sb.append(s,start + 1,end + 1).append(' '); //当前字符为' ',start指针此时在单词头的前一个索引位置，添加到sb中。
end = start - 1; //移动尾指针
while (s.charAt(end) == ' '){ //两单词之间多空格的情况，找尾指针不为空字符的时候，即尾指针指向第二个单词的尾部
end--;
}
start = end; //头指针与尾指针都指向第二个单词的尾部，重复如此
}
}
return sb.toString();
}
}
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2 输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6 输出: "umghlrlose" 限制：
1 <= k < s.length <= 10000
class Solution {
public String reverseLeftWords(String s, int n) {
// StringBuilder sb = new StringBuilder();
// sb.append(s,n,s.length());
// sb.append(s,0,n);
// return sb.toString();
return s.substring(n, s.length()) + s.substring(0, n);
}
}
============================================================
class Solution{
public String reverseLeftWords(String s, int n) {
int len=s.length();
StringBuilder sb=new StringBuilder(s);
reverseString(sb,0,n-1);
reverseString(sb,n,len-1);
return sb.reverse().toString();
}
public void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
}
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
提示：
1 <= haystack.length, needle.length <= 10^4 haystack 和 needle 仅由小写英文字符组成
未理清kmp
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
char[] s = haystack.toCharArray(), p = needle.toCharArray();
// 枚举原串的「发起点」
for (int i = 0; i <= n - m; i++) {
// 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
int a = i, b = 0;
while (b < m && s[a] == p[b]) {
a++;
b++;
}
// 如果能够完全匹配，返回原串的「发起点」下标
if (b == m) return i;
}
return -1;
}
}
==========================================================
//KMP
class Solution{
public int strStr(String haystack,String needle){
int n = haystack.length(), m = needle.length();
if (m == 0) {
return 0;
}
int[] pi = new int[m];
for (int i = 1, j = 0; i < m; i++) { //构造next数组（pi）
while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
j = pi[j - 1];
}
if (needle.charAt(i) == needle.charAt(j)) {
j++;
}
pi[i] = j;
}
for (int i = 0, j = 0; i < n; i++) { //匹配
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
j = pi[j - 1];
}
if (haystack.charAt(i) == needle.charAt(j)) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
}
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。 示例 2:
输入: s = "aba" 输出: false 示例 3:
输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。) 提示：
1 <= s.length <= 10^4 s 由小写英文字母组成
//枚举
class Solution {
public boolean repeatedSubstringPattern(String s) {
int m = s.length();
for(int i = 1;i <= m/2;i++){ //能够由子字符串构成的字符串，子字符串的长度必定是字符串长度的一半以内
if(m % i == 0){
boolean match = true;
for(int j = i ;j < m; j++){
if(s.charAt(j) != s.charAt(j - i)){
match = false;
break;
}
}
if(match){
return true;
}
}
}
return false;
}
}
===========================================================
//KMP
class Solution{
public boolean repeatedSubstringPattern(String s){
if (s.equals("")) return false;
int len = s.length();
// 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
s = " " + s;
char[] chars = s.toCharArray();
int[] next = new int[len + 1];
// 构造 next 数组过程，j从0开始(空格)，i从2开始
for (int i = 2, j = 0; i <= len; i++) {
// 匹配不成功，j回到前一位置 next 数组所对应的值
while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
// 匹配成功，j往后移
if (chars[i] == chars[j + 1]) j++;
// 更新 next 数组的值
next[i] = j;
}
// 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
if (next[len] > 0 && len % (len - next[len]) == 0) {
return true;
}
return false;
}
}
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false 说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 1, 1, false]
解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false 提示：
1 <= x <= 9 最多调用 100 次 push、pop、peek 和 empty 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作） 进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
根据队列FIFO的特性，用两个栈(LIFO特性)模拟。栈1负责元素进栈，栈2负责接收栈1的元素，并做出栈等操作。
class MyQueue {
//用栈模拟队列
Stack<Integer> stack1; //栈1(元素进栈)
Stack<Integer> stack2; //栈2(栈1的元素出栈，该栈负责元素出栈及获取栈顶元素)
public MyQueue() {
stack1=new Stack<>();
stack2=new Stack<>();
}
//进队
public void push(int x) {
stack1.push(x);
}
//出队
public int pop() {
if(stack2.isEmpty()){
// while(!stack1.isEmpty()){
// stack2.push(stack1.pop());
// }
outStack1_AndInStack2(); //将栈1的元素弹出并进栈2
}
return stack2.pop();
}
//队首元素
public int peek() {
if(stack2.isEmpty()){
// while(!stack1.isEmpty()){
// stack2.push(stack1.pop());
// }
outStack1_AndInStack2();
}
return stack2.peek();
}
//队空?
public boolean empty() {
return stack2.isEmpty()&&stack1.isEmpty();
}
//栈1元素出栈到栈2
private void outStack1_AndInStack2(){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
}
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。 注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false]
解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False 提示：
1 <= x <= 9 最多调用100 次 push、pop、top 和 empty 每次调用 pop 和 top 都保证栈不为空 进阶：你能否仅用一个队列来实现栈。
根据栈的特性LIFO，以及队列的特性FIFO,使用两个队列实现栈。首先队列1负责元素进出队，队列2负责临时存储元素。在元素进入队列1时，为达到LIFO的特性，用上临时存储队列2，先将队列2中所有的元素全部进队到队列1中，再交换队列，即交换存储空间（队列交换）达到队列1始终为空.
class MyStack {
//两个队列实现栈
private Queue<Integer> a;
private Queue<Integer> b;
public MyStack() {
a = new LinkedList<>();
b = new LinkedList<>();
}
public void push(int x) {
a.offer(x); //元素进入队列1
while(!b.isEmpty()){ //将队列2中的所有元素入队1
a.offer(b.poll());
}
//交换保证a始终为空
Queue temp = a;
a = b;
b = temp;
}
public int pop() {
return b.poll();
}
public int top() {
return b.peek();
}
public boolean empty() {
return b.isEmpty();
}
}
==========================================================
//一个队列实现栈
class MyStack{
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<Integer>();
}
public void push(int x) {
int n = queue.size();
queue.offer(x);
for (int i = 0; i < n; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}" 输出：true
示例 3：
输入：s = "(]" 输出：false
提示：
1 <= s.length <= 10^4 s 仅由括号 '()[]{}' 组成
该题不是那种穿插的括号，直接进行判断即可
//直接判断
class Solution {
public boolean isValid(String s) {
int n = s.length();
Stack<Character> stack = new Stack<>();
for(int i = 0;i < n;i++){
char ch = s.charAt(i);
if(ch == '(' || ch == '[' || ch == '{'){
stack.push(ch);
}else if(ch == ')' && (stack.isEmpty() == true || stack.pop() != '(')){
return false;
}else if(ch == ']' && (stack.isEmpty() == true || stack.pop() != '[')){
return false;
}else if(ch == '}' && (stack.isEmpty() == true || stack.pop() != '{')){
return false;
}
}
return stack.isEmpty();
}
}
=================================================================
//哈希快速匹配
class Solution{
public boolean isValid(String s){
int n = s.length();
if (n % 2 == 1) {
return false;
}
Stack<Character> stack = new Stack<>();
//右括号为键，左括号为值
Map<Character,Character> map = new HashMap<>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
for(int i = 0;i < s.length();i++){
char ch = s.charAt(i);
if(map.containsKey(ch)){ //右括号进行匹配
if(stack.isEmpty() || stack.pop() != map.get(ch)){
return false;
}
}else{ //左括号直接进栈
stack.push(ch);
}
}
//栈为空，即全部匹配完成
return stack.isEmpty();
}
}
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。 提示： 1 <= S.length <= 20000 S 仅由小写英文字母组成。
//栈思想实现
class Solution {
public String removeDuplicates(String s) {
StringBuilder stack = new StringBuilder();
int top = -1;
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
if (top >= 0 && stack.charAt(top) == ch) {
stack.deleteCharAt(top);
--top;
} else {
stack.append(ch);
++top;
}
}
return stack.toString();
}
}
=======================================================
//数组实现（还是栈的思想）
class Solution{
public String removeDuplicates(String s){
char[] ch = s.toCharArray();
int top = -1; //栈顶指针
for (int i = 0; i < s.length(); i++) {
if (top == -1 || ch[top] != ch[i]) { //当前元素与栈顶元素不一致就进栈
ch[++top] = ch[i];
} else {
top--; //删除栈顶元素
}
}
return String.valueOf(ch, 0, top + 1);
}
}
根据 逆波兰表示法，求表达式的值。 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"] 输出：22 解释：该算式转化为常见的中缀算术表达式为： ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
提示：
1 <= tokens.length <= 10^4 tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。 逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
是数字就进栈，是运算符则出栈2个数进行操作后再进栈。
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String item : tokens){
if(item.equals("+") || item.equals("-") || item.equals("*") || item.equals("/")){
int num1 = stack.pop();
int num2 = stack.pop();
if(item.equals("+")){
stack.push(num1+num2);
}else if(item.equals("-")){
stack.push(num2-num1);
}else if(item.equals("*")){
stack.push(num1*num2);
}else if(item.equals("/")){
stack.push(num2/num1);
}
}else{
stack.push(Integer.valueOf(item));
}
}
return stack.peek();
}
}
=====================================================================
class Solution{
public int evalRPN(String[] tokens){
Deque<Integer> stack = new LinkedList();
for (String s : tokens) {
if ("+".equals(s)) { // leetcode 内置jdk的问题，不能使用==判断字符串是否相等
stack.push(stack.pop() + stack.pop()); // 注意 - 和/ 需要特殊处理
} else if ("-".equals(s)) {
stack.push(-stack.pop() + stack.pop());
} else if ("*".equals(s)) {
stack.push(stack.pop() * stack.pop());
} else if ("/".equals(s)) {
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);
} else {
stack.push(Integer.valueOf(s));
}
}
return stack.peek();
}
}
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1 输出：[1] 提示：
1 <= nums.length <= 10^5 -104 <= nums[i] <= 10^4 1 <= k <= nums.length
难啊
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n - k + 1];
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < n; i++) {
// 添加元素时，如果要添加的元素大于队尾处的元素，就将队尾元素弹出（保证对首元素始终大于队尾元素）
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
// 如果队首存储的角标就是滑动窗口左边界数值，就移除队首（保证窗口大小为k）
if (!deque.isEmpty() && (i - k) == deque.peekFirst()) {
deque.pollFirst();
}
// 当i增长到第一个窗口右边界时，每滑动一步都将队首角标对应元素(窗口最大值)放入结果数组
if (i >= k - 1) {
res[i - k + 1] = nums[deque.peekFirst()];
}
}
return res;
}
}
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2:
输入: nums = [1], k = 1 输出: [1]
提示：
1 <= nums.length <= 10^5 k 的取值范围是 [1, 数组中不相同的元素的个数] 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
class Solution {
解法1：基于大顶堆实现
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
//出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]);
for(Map.Entry<Integer,Integer> entry:map.entrySet()){//大顶堆需要对所有元素进行排序
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
int[] ans = new int[k];
for(int i=0;i<k;i++){//依次从队头弹出k个,就是出现频率前k高的元素
ans[i] = pq.poll()[0];
}
return ans;
}
}
=======================================================================
class Solution{
//解法2：基于小顶堆实现
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
//出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
for(Map.Entry<Integer,Integer> entry:map.entrySet()){//小顶堆只需要维持k个元素有序
if(pq.size()<k){//小顶堆元素个数小于k个时直接加
pq.add(new int[]{entry.getKey(),entry.getValue()});
}else{
if(entry.getValue()>pq.peek()[1]){//当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
pq.poll();//弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
}
}
int[] ans = new int[k];
for(int i=k-1;i>=0;i--){//依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
ans[i] = pq.poll()[0];
}
return ans;
}
}
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1： 输入：root = [1,null,2,3] 输出：[1,2,3]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[1,2]
示例 5：
输入：root = [1,null,2] 输出：[1,2] 提示：
树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
/**
* 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 List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
pre(root,list);
return list;
}
public void pre(TreeNode root,List<Integer> list){
if(root == null){
return;
}
list.add(root.val);
pre(root.left,list);
pre(root.right,list);
}
}
=============================================================
//官方迭代
class Solution{
public List<Integer> preorderTraversal(TreeNode root){
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
res.add(root.val);
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;
}
return res;
}
}
==============================================================
//morris算法(二叉搜索树)
//实现原则
/*
1.如果cur无左孩子，cur向右移动（cur=cur.right）
2.如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
1.如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
2.如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）
*/
class Solution{
public List<Integer> preorderTraversal(TreeNode root){
List<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
TreeNode cur = root;
TreeNode mostRight = null;
while (cur != null){
// cur表示当前节点，mostRight表示cur的左孩子的最右节点
mostRight = cur.left;
if(mostRight != null){
// cur有左孩子，找到cur左子树最右节点
while (mostRight.right !=null && mostRight.right != cur){
mostRight = mostRight.right;
}
// mostRight的右孩子指向空，让其指向cur，cur向左移动
if(mostRight.right == null){
mostRight.right = cur;
res.add(cur.val);
cur = cur.left;
continue;
}else {
// mostRight的右孩子指向cur，让其指向空，cur向右移动
mostRight.right = null;
}
}else {
// System.out.print(cur.value + " ");
res.add(cur.val);
}
cur = cur.right;
}
return res;
}
}
===============================================================
//二叉树的初始化
class Node{
int value;
Node left;
Node right;
Node root; // 根节点
public Node(int[] data) {
createTree(data);
}
public void createTree(int[] data) {
List <Node> list = new ArrayList<>();//新建一个list集合，将数据变为各个节点
for (int temp : data) {
list.add(new Node(temp));
}
root=list.get(0);//将第一个元素设置为根节点
/**
* 利用构建完全二叉树的方式构建
*/
for(int i = 0;i < list.size()/2;i++){
if(( i*2 + 1) < list.size()){
list.get(i).setLeft(list.get(i*2 + 1));
}
if((i*2+2) < list.size()){
list.get(i).setRight(list.get(i*2+2));
}
}
}
public Node getRoot() { // 得到根节点
return root;
}
public Node(){};
public Node(int val){
this.value = val;
}
public Node(int value,Node left,Node right){
this.value = value;
this.left = left;
this.right = right;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
}
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
/**
* 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 List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
inorder(root,list);
return list;
}
public void inorder(TreeNode root,List<Integer> list){
if(root == null){
return;
}
inorder(root.left,list);
list.add(root.val);
inorder(root.right,list);
}
}
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[3,2,1]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1] 提示：
树中节点的数目在范围 [0, 100] 内 -100 <= Node.val <= 100 进阶：递归算法很简单，你可以通过迭代算法完成吗？
/**
* 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 List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
postorder(root,list);
return list;
}
public void postorder(TreeNode root,List<Integer> list){
if(root == null){
return;
}
postorder(root.left,list);
postorder(root.right,list);
list.add(root.val);
}
}
===========================================================
//迭代
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == prev) {
res.add(root.val);
prev = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return res;
}
}
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
树中节点数目在范围 [0, 2000] 内 -1000 <= Node.val <= 1000
//BFS（breadth first search：广度优先算法）
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>(); //存放结果集
Deque<TreeNode> que = new LinkedList<>(); //存放结点的队列
if (root == null){
return res;
}
que.offerLast(root);
while (!que.isEmpty()) {
int len = que.size();
List<Integer> list = new ArrayList<>();
while (len > 0) {
TreeNode node = que.pollFirst();
list.add(node.val);
if (node.left != null){
que.offerLast(node.left);
}
if (node.right != null){
que.offerLast(node.right);
}
len--;
}
res.add(list);
}
return res;
}
}
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[] 提示：
树中节点数目在范围 [0, 2000] 内 -1000 <= Node.val <= 1000
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Queue<TreeNode> que = new LinkedList<>();
if(root == null){
return res;
}
que.offer(root);
while(!que.isEmpty()){
int len = que.size(); //每一层的结点数量
List<Integer> ret = new ArrayList<>(); //存放第i层数组的值，i从1开始
while(len > 0){
TreeNode node = que.poll();
ret.add(node.val);
if(node.left != null){
que.offer(node.left);
}
if(node.right != null){
que.offer(node.right);
}
len--;
}
res.add(0,ret); //往结果集中的第0个位置存放，使得遍历完每一层的结果都在最前面，达到从下往上遍历的结果
}
return res;
}
}
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
示例 2:
输入: [1,null,3] 输出: [1,3]
示例 3:
输入: [] 输出: [] 提示:
二叉树的节点个数的范围是 [0,100] -100 <= Node.val <= 100
层序遍历，取最后一个节点的值即可
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int len = que.size(); //同一层的结点数量
while(len > 0){
TreeNode node = que.poll();
if(node.left != null){
que.offer(node.left);
}
if(node.right != null){
que.offer(node.right);
}
len--;
if(len == 0){
res.add(node.val);
}
}
}
return res;
}
}
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000] 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11] 。
示例 2:
输入：root = [3,9,20,15,7] 输出：[3.00000,14.50000,11.00000]
提示：
树中节点数量在 [1, 10^4] 范围内 -2^31 <= Node.val <= 2^31 - 1
层序遍历，遍历一层就计算出每一层的平均值。
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root == null){
return res;
}
que.offer(root);
while(!que.isEmpty()){
int len = que.size();
int count = len; //每层节点数量
double sum = 0;
while(len > 0){ //层序遍历每一层，得到每一层的总值
TreeNode node = que.poll();
sum += node.val;
if(node.left != null){
que.offer(node.left);
}
if(node.right != null){
que.offer(node.right);
}
len--;
}
res.add(sum/count);
}
return res;
}
}
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]] 提示：
树的高度不会超过 1000 树的节点总数在 [0, 10^4] 之间
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Queue<Node> que = new LinkedList<>();
if(root == null){
return res;
}
que.offer(root);
while(!que.isEmpty()){
int len = que.size();
List<Integer> ret = new ArrayList<>();
while(len > 0){
Node node = que.poll();
ret.add(node.val);
for(Node ch : node.children){
if(ch != null){
que.offer(ch);
}
}
// Iterator<Node> iter = node.children.iterator();
// while(iter.hasNext()){
// que.offer(iter.next());
// }
len--;
}
res.add(ret);
}
return res;
}
}
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]
示例2：
输入: root = [1,2,3] 输出: [1,3]
提示：
二叉树的节点个数的范围是 [0,10^4] -2^31 <= Node.val <= 2^31 - 1
层序遍历
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> res = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root == null){
return res;
}
que.offer(root);
while(!que.isEmpty()){
int len = que.size();
int max = Integer.MIN_VALUE;
while(len > 0){
TreeNode node = que.poll();
max = node.val > max ? node.val : max;
if(node.left != null){
que.offer(node.left);
}
if(node.right != null){
que.offer(node.right);
}
len--;
}
res.add(max);
}
return res;
}
}
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例 1：
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
示例 2:
输入：root = [] 输出：[] 提示：
树中节点的数量在 [0, 2^12 - 1] 范围内
-1000 <= node.val <= 1000 进阶：
你只能使用常量级额外空间。 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
=============================================================
//层序遍历
class Solution {
public Node connect(Node root) {
if(root == null){
return null;
}
Queue<Node> que = new LinkedList<>();
Node pre = null; //先前出队的节点
Node cur = null; //当前出队的节点
que.offer(root);
while(!que.isEmpty()){
int len = que.size(); //每层的节点数量
int len2 = len;
while(len > 0){
cur = que.poll();
if(len != len2){ //非最右侧节点指向先前出队的节点
cur.next = pre;
}
if(cur.right != null){ //每层的节点遵循从右往左入队
que.offer(cur.right);
}
if(cur.left != null){
que.offer(cur.left);
}
len--;
pre = cur;
}
}
return root;
}
}
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
提示：
树中的节点数小于 6000 -100 <= node.val <= 100
class Solution {
public Node connect(Node root) {
if(root == null){
return null;
}
Queue<Node> que = new LinkedList<>();
Node pre = null;
Node cur = null;
que.offer(root);
while(!que.isEmpty()){
int len = que.size();
int len2 = len;
while(len > 0){
cur = que.poll();
if(len != len2){
cur.next = pre;
}else{
cur.next = null;
}
if(cur.right != null){
que.offer(cur.right);
}
if(cur.left != null){
que.offer(cur.left);
}
len--;
pre = cur;
}
}
return root;
}
}
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。
//DFS(深度优先搜索)
class Solution{
public int maxDepth(TreeNode root){
//递归终止条件
if(root == null){
return 0;
}else{
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight,rightHeight)+1;
}
}
}
=================================================
//BFS(广度优先遍历)
class Solution{
public int maxDepth(TreeNode root){
int high = 0;
if(root == null){
return high;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int len = que.size();
while(len > 0){
TreeNode node = que.poll();
if(node.left != null){
que.offer(node.left);
}
if(node.right != null){
que.offer(node.right);
}
len--;
}
high++;
}
return high;
}
}
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5 提示：
树中节点数的范围在 [0, 10^5] 内 -1000 <= Node.val <= 1000
//bfs
class Solution{
public int minDepth(TreeNode root){
int res = 0;
if (root == null) {
return res;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while (!que.isEmpty()) {
int size = que.size();
res++;
for (int i = 0; i < size; i++) {
TreeNode node = que.poll();
if (node.left == null && node.right == null) { //该层的节点若没有左右节点即为最小的深度
return res;
}
if (node.left != null) {
que.offer(node.left);
}
if (node.right != null) {
que.offer(node.right);
}
}
}
return res;
}
}
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3] 输出：[2,3,1]
示例 3：
输入：root = [] 输出：[]
提示：
树中节点数目范围在 [0, 100] 内 -100 <= Node.val <= 100
class Solution {
public TreeNode invertTree(TreeNode root) {
//前序+递归
if(root == null){ //递归终止条件
return null;
}
TreeNode rightTree = root.right;
root.right = invertTree(root.left);
root.left = invertTree(rightTree);
return root;
}
}
===================================================
class Solution{
public TreeNode invertTree(TreeNode root){
//后序+递归
if(root == null){
return null;
}
TreeNode leftNode = invertTree(root.left);
TreeNode rightNode = invertTree(root.right);
root.right = leftNode;
root.left = rightNode;
return root;
}
}
=====================================================
class Solution{
public TreeNode invertNode(TreeNode root){
//层序
if(root == null){
return null;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
TreeNode node = que.poll();
TreeNode rightNode = node.right;
node.right = node.left;
node.left = rightNode;
if(node.left != null){
que.offer(node.left);
}
if(node.right != null){
que.offer(node.right);
}
}
return root;
}
}
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
提示：
树中节点数目在范围 [1, 1000] 内 -100 <= Node.val <= 100 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
class Solution {
//递归
public boolean isSymmetric(TreeNode root) {
return check(root,root);
}
public boolean check(TreeNode leftNode,TreeNode rightNode){
if(leftNode == null && rightNode == null){
return true;
}
if(leftNode == null || rightNode == null || leftNode.val != rightNode.val){
return false;
}
return check(leftNode.left,rightNode.right) && check(leftNode.right,rightNode.left);
}
}
=================================================================
class Solution{
public boolean isSymmetric(TreeNode root){
if(root == null){
return true;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root.left);
que.offer(root.right);
while(!que.isEmpty()){
TreeNode leftNode = que.poll();
TreeNode rightNode = que.poll();
if(leftNode == null && rightNode == null){
continue;
}
if(leftNode == null || rightNode == null || leftNode.val != rightNode.val){
return false;
}
que.offer(leftNode.left);
que.offer(rightNode.right);
que.offer(leftNode.right);
que.offer(rightNode.left);
}
return true;
}
}
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3] 输出：true
示例 2：
输入：p = [1,2], q = [1,null,2] 输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2] 输出：false 提示：
两棵树上的节点数目都在范围 [0, 100] 内 -10^4 <= Node.val <= 10^4
class Solution {
//递归
public boolean isSameTree(TreeNode p, TreeNode q) {
return check(p,q);
}
public boolean check(TreeNode p,TreeNode q){
if(p == null && q == null){
return true;
}
if(p == null || q == null || p.val != q.val ){
return false;
}
return check(p.left,q.left) && check(p.right,q.right);
}
}
==============================================================
class Solution{
public boolean isSameTree(TreeNode p,TreeNode q){
if(p == null && q == null){
return true;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(p);
que.offer(q);
while(!que.isEmpty()){
TreeNode node1 = que.poll();
TreeNode node2 = que.poll();
if(node1 == null && node2 == null){
continue;
}
if(node1 == null || node2 == null || node1.val != node2.val){
return false;
}
que.offer(node1.left);
que.offer(node2.left);
que.offer(node1.right);
que.offer(node2.right);
}
return true;
}
}
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2] 输出：true
示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输出：false 提示：
root 树上的节点数量范围是 [1, 2000] subRoot 树上的节点数量范围是 [1, 1000] -10^4 <= root.val <= 10^4 -10^4 <= subRoot.val <= 10^4
class Solution {
//树的子树的结果
//1.树相同
//2.是该树的左子树的子树
//3.是该树的右子树的子树
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//1.树相同
if(isSameTree(root,subRoot)){
return true;
}
if(root == null){
return false;
}
//子树
return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}
//相同树
public boolean isSameTree(TreeNode root,TreeNode subRoot){
if(root == null && subRoot == null){
return true;
}
if(root == null || subRoot == null || root.val != subRoot.val){
return false;
}
return isSameTree(root.left,subRoot.left) && isSameTree(root.right,subRoot.right);
}
}
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：3
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：5
提示：
树的深度不会超过 1000 。 树的节点数目位于 [0, 10^4] 之间。
class Solution {
//递归
public int maxDepth(Node root) {
if(root == null){
return 0;
}
int depth = 0;
for(Node node : root.children){
depth = Math.max(depth,maxDepth(node));
}
return depth+1;
}
}
==============================================
class Solution{
// 层序
public int maxDepth(Node root){
if(root == null){
return 0;
}
int res = 0;
Queue<Node> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int size = que.size();
while(size > 0){
Node node = que.poll();
for(Node n : node.children){
if(n != null){
que.offer(n);
}
}
size--;
}
res++;
}
return res;
}
}
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6] 输出：6
示例 2：
输入：root = [] 输出：0
示例 3：
输入：root = [1] 输出：1 提示：
树中节点的数目范围是[0, 5 * 10^4] 0 <= Node.val <= 5 * 1^04 题目数据保证输入的树是 完全二叉树
class Solution {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false
示例 3：
输入：root = [] 输出：true 提示：
树中的节点数在范围 [0, 5000] 内 -104 <= Node.val <= 10^4
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null){
return true;
}
return Math.abs(depth(root.left) - depth(root.right)) <= 1 &&
isBalanced(root.left) && isBalanced(root.right);
}
public int depth(TreeNode root) {
if (root == null) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
}
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。 示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
示例 2：
输入：root = [1] 输出：["1"]
提示：
树中节点的数目在范围 [1, 100] 内 -100 <= Node.val <= 100
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
dfs(root,new StringBuffer(),res);
return res;
}
public void dfs(TreeNode root,StringBuffer s,List<String> res){
if(root == null) return;
s.append(root.val); //根值
if(root.left==null && root.right==null){ //叶子节点
res.add(s.toString());
}
dfs(root.left,new StringBuffer(s).append("->"),res);
dfs(root.right,new StringBuffer(s).append("->"),res);
}
}
给定二叉树的根节点 root ，返回所有左叶子之和。
示例 1：
输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例 2:
输入: root = [1] 输出: 0
提示:
节点数在 [1, 1000] 范围内 -1000 <= Node.val <= 1000
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null){
return 0;
}
int res = 0;
if(root.left != null && root.left.left == null && root.left.right == null){ //当前遍历的左节点不为null时，且是叶子节点
res += root.left.val;
}
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right) + res;
}
}
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7 提示:
二叉树的节点个数的范围是 [1,10^4] -2^31 <= Node.val <= 2^31 - 1
class Solution {
//层序
public int findBottomLeftValue(TreeNode root) {
if(root == null){
return 0;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
root = que.poll();
if(root.right != null){
que.offer(root.right);
}
if(root.left != null){
que.offer(root.left);
}
}
return root.val;
}
}
本文章使用limfx的vscode插件快速发布