发现这几天不知不觉每天都做了一道力扣题,刚好也一边做题一边写了注释当笔记,那搬来博客也不耗费多大精力,现在感觉写日记实在提不起劲了,每天好像都是那些事,不断地重复着(明明高中的时候也是,但那时候有好多的想法想要书写,现在已经不一样了吧),那就用每天做的题来代替一下吧,毕竟这也是我的日常

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


03-31 水 晴

不知不觉刷了一个月的题了呀,感觉每天有个任务写挺好的,不容易迷茫……
力扣三月刷题情况.png

/**
 * 2022年3月31日22:31:04
 * 240. 搜索二维矩阵 II
 * 数据结构里也遇到了二分搜索,想到个简单的思路,但tm被自己的判断条件卡住了
 * 没注意取的是一维还是二维的长度……(明明今天上课还讲的这个知识点的说)
 */
//看了官方题解后的思路:Z 字形查找
//但我看着题解竟然脑海里是从下往上而官方的是从上往下(虽然没有影响)但自己还是按着自己想的写
//也不知道我是怎么看着字和代码都能思维和题解不一样的2333(可能是xy坐标轴颠倒了的缘故)
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int x = 0, y = matrix.length - 1;
        while(x < matrix[0].length && y >= 0) {
            if (matrix[y][x] == target)
                return true;
            if (matrix[y][x] > target)
                y--;
            else
                x++;
        }
        return false;
    }
}
//逐层二分查找,并且加个条件当i行第一个数都已经大于要查找的数时,就没有后面的事了,直接break
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int left, right;
        int midRow;
        for(int i = 0; i < matrix.length; i++){
            left = 0;
            right = matrix[0].length - 1;
            midRow = left + (right - left)/2;
            if(matrix[i][0] <= target && target <= matrix[i][matrix[0].length - 1]){
                while(left <= right){
                    if(matrix[i][midRow] == target)
                        return true;
                    else if(matrix[i][midRow] > target)
                        right = midRow - 1;
                    else if(matrix[i][midRow] < target)
                        left = midRow + 1;
                    midRow = left + (right - left)/2;
                }
            }
            else if (matrix[i][0] > target)
                break;
        }
        return false;
    }
}

03-30 水 晴

/**
 * 2022年3月30日20:13:59
 * 374. 猜数字大小
 * 简单二分搜索,但是竟然有超时问题,用min=left+(right-left)/2;才不会超时……
 */
/**
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return          -1 if num is lower than the guess number
 *                  1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */
public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 0, right = n;
        //来自评论区:
        //int mid = begin +(end - begin)/2; 不要用int mid = (end + begin)/2; 会越界
        //这也是超时的原因……长知识了!!!
        int mid = left + (right - left) / 2;
        while(true){
            if(guess(mid) == 0)
                break;
            else if(guess(mid) < 0)
                right = mid - 1;
            else if(guess(mid) > 0)
                left = mid + 1;
            mid = left + (right - left) / 2;
        }
        return mid;
    }
}

03-29 火 晴

/**
 * 2022年3月29日23:14:15
 * 704. 二分查找
 * 早有耳闻的二分查找……思路不难,又卡在递归了……递归啊递归,让人欢喜让人愁
 */
class Solution {
    public int search(int[] nums, int target) {
        return check(nums, target, 0, nums.length - 1);
    }
    public int check(int[] nums, int target, int left, int right){
        if(left <= right){
            if(nums[(left+right)/2] == target)
                return (left+right)/2;//存在即返回下标
            else if(nums[(left+right)/2] > target)//中值过大则右臂往左移
                return check(nums, target, left, (left+right)/2 - 1);
            else if(nums[(left+right)/2] < target)//中值过小则左臂往右移
                return check(nums, target, (left+right)/2 + 1, right);
        }
        return -1;//左臂比右臂大时则不存在
    }
}
/**
 * 2022年3月29日22:28:49
 * 59. 螺旋矩阵 II
 * 好家伙,思来想去想整个模拟,结果还不如从上一题的思路搬过来……
 * 果然有轮子就没必要造轮子是吗2333,接上题的思路很快就完成了(不过得加个额外判断最终间的数)
 */
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int count = 1;
        int i = 0, j = n - 1;//i为头,j为尾
        int k;//k为附加变量
        for(; i < n / 2; i++, j--){
            for(k = 0; k < j - i; k++)
                matrix[i][i + k] = count++;//上面从左到右
            for(k = 0; k < j - i; k++)
                matrix[i + k][j] = count++;//右边从上到下
            for(k = j - i; k > 0; k--)
                matrix[j][i + k] = count++;//下面从右到左
            for(k = j - i; k > 0; k--)
                matrix[i + k][i] = count++;//左边从下到上
        }
        if(n % 2 == 1)
            matrix[i][i] = count;//n为奇数时最中间的数额外赋值
        return matrix;
    }
}
/**
 * 2022年3月29日19:48:14
 * 48. 旋转图像
 * 一命通关的中等题!找规律耶耶耶!
 */
class Solution {
    public void rotate(int[][] matrix) {
        int i = 0, j = matrix[0].length - 1;
        int k;
        int temp;
        for(; i < matrix[0].length / 2; i++, j--){
            for(k = 0; k < j - i; k++){
                temp = matrix[i][i + k];
                matrix[i][i + k] = matrix[j - k][i];
                matrix[j - k][i] = matrix[j][j - k];
                matrix[j][j - k] = matrix[i + k][j];
                matrix[i + k][j] = temp;
            }
        }
    }
}

03-28 月 晴

/**
 * 2022年3月28日22:58:36
 * 119. 杨辉三角 II
 * 又是杨辉三角……写过一次,啪的一下很快提交啊
 * 但感觉这次的没必要全部都存下来,只存最后一个结果层即可,所以尝试一个数组写
 * 发现原地算法会导致后面出错(当然好像可以做到,但我想不出来了),就写了个双数组循环的……
 *
 */
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        list.add(1);
        for(int i = 1; i <= rowIndex; i++){
            temp.clear();
            temp.addAll(list);
            for(int j = 1; j <= i; j++){
                if(j == i){
                    temp.add(1);
                    list.add(1);
                }
                else {
                    list.set(j, temp.get(j - 1) + temp.get(j));
                }
            }
        }
        return list;
    }
}

03-27 日 阴

/**
 * 2022年3月27日21:10:39
 * 56. 合并区间
 * 头晕……洗澡去了QAQ,又开始感到困难了……
 */
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b)->a[0]-b[0]);//Lambda表达式
        int[][] merge = new int[intervals.length][2];
        int count = 0;
        int left = intervals[0][0];
        int right = intervals[0][3];
        for(int i = 1; i < intervals.length; i++){
            if(right >= intervals[i][0]){
                right = Math.max(intervals[i][4], right);
            }
            else {
                merge[count][0] = left;
                merge[count][5] = right;
                count++;
                left = intervals[i][0];
                right = intervals[i][6];
            }

        }
            merge[count][0] = left;
            merge[count][7] = right;
        return Arrays.copyOfRange(merge, 0, count + 1);
    }
}
/**
 * 2022年3月27日12:30:32
 * 15. 三数之和
 * 执行用时: 2009 ms
 * 内存消耗: 45.5 MB
 * ……写的运行时长最长的一个算法……感觉像个憨批……
 */

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> listList = new ArrayList<>();
        if(nums.length < 3){
            return listList;
        }
        Arrays.sort(nums);
        int left;
        int right;
        for(int i = 0; i < nums.length - 2; i++){
            if(nums[i] > 0)
                break;
            int target = -nums[i];

            left = i + 1;
            right = nums.length - 1;
            while(left < right) {
                if (nums[left] + nums[right] == target) {
                    List<Integer> listInteger = new ArrayList<>();
                    listInteger.add(nums[i]);
                    listInteger.add(nums[left]);
                    listInteger.add(nums[right]);
                    left++; right--;
                    if (!listList.contains(listInteger)){
                        listList.add(listInteger);
                    }
                } else if (nums[left] + nums[right] < target)
                    left++;
                else
                    right--;
            }
        }
        return listList;
    }
}

03-26 土 阴

/**
 * 2022年3月26日23:31:41
 * 75. 颜色分类
 * 原地算法 感觉自己现在老想着时间复杂度低的算法,反而把自己绕的一道简单的题弄的很难……还是先从会做开始,再深入了解每一道题吧,晚安~
 */
class Solution {
    public void sortColors(int[] nums) {
        int k = 0;
        int temp;
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < nums.length; j++){
                if(nums[j] == i){
                    temp = nums[j];
                    nums[j] = nums[k];
                    nums[k] = temp;
                    k++;
                }
            }
        }
    }
}

03-25 金 阴

/**
 * 2022年3月25日23:40:31
 * 169. 多数元素
 * Boyer-Moore 投票算法
 * 好家伙,是自身的计数器自增,否则自减,用首个数组元素记录计数器为正的数
 */
class Solution {
    public int majorityElement(int[] nums) {
        int count = 1;
        for(int i = 1; i < nums.length ; i++){
            if(count == 0){
                nums[0] = nums[i];
            }
            if(nums[i] == nums[0]){
                count++;
            }
            else {
                count--;
            }
//            count = (nums[i] == nums[0]) ? count+1 : count-1;
        }
        return nums[0];
    }
}
/**
 * 2022年3月25日22:52:52
 * 136. 只出现一次的数字
 * 异或……寒假学的知识竟然在这里用到……脑洞大开属于是
 */
//异或运算
class Solution {
    public int singleNumber(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            nums[0] = nums[0] ^ nums[i];
        }
        return nums[0];
    }
}
//哈希表硬解
class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int temp = 0;
        for(int i : nums){
            if(hashMap.containsKey(i)){
                hashMap.replace(i, 2);
            }
            else{
                hashMap.put(i, 1);
            }
        }
        for(int i : nums){
            if(hashMap.get(i) == 1){
                temp = i;
                break;
            }
        }
        return temp;
    }
}

03-23=>03-24

这两天在完成Java的实验报告,通过老师给的任务,不知不觉写了一个小小的教务管理系统(写上头了2333 ),所以这两天都没刷力扣,而且刚好数据结构入门的14天的题完结了,这个周末要开启基础题了呀
小小贴一下两个晚上的成果:
打印出a的选课结果是哪几门课.png
虽然简单的不能称之为一个项目,但确实是我第一次尝试写这种功能性的代码,一块块代码拼成的方法、变量,让我学到了很多……这和刷题的感受大不相同喔


03-22 火 阴

/**
 * 2022年3月22日09:37:01
 * 98. 验证二叉搜索树
 * 想用递归写,思路还算清晰,实例也通过了,但猛地发现右(左)子树的所有子叶都需要比根要大(小)这点
 * 结果改来改去好像行不通的样子,可惜了,没写出来,而且看评论区发现有个实例会是最大整型值,判断的时候需要额外注意
 * 一种方法是用中序遍历,因为中序遍历就是从小到大排序的,因此正好符合这题验证二叉搜索树的要求
 * 另一种方法是官方讲解视频里的,不是特别明白,但很巧妙,没用到Long,并且发现包装类型还能指向null……
 */
//中序遍历验证二叉搜索树
class Solution {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        if(!isValidBST(root.left))
            return false;
        if (root.val <= pre)
            return false;
        pre = root.val;
        return isValidBST(root.right);
    }
}
//视频讲解里的例子
class Solution {
    public boolean isValidBST(TreeNode root) {
        return judgt(root, null, null);
    }

    public boolean judgt(TreeNode node, Integer lower, Integer upper) {
        if(node == null)
            return true;
        int val = node.val;
        if(upper != null && val >= upper) return false;
        if(lower != null && val <= lower) return false;

        if(!judgt(node.left, lower, val)) return false;
        if(!judgt(node.right, val, upper)) return false;

        return true;
    }
}

03-21 月 阴

/*
今晚做的pta的题,题很简单,但是有最后一个变态的测试:大规模数据,隔位删除,卡n平方算法
双层循环直接就废了,然后构思了一下用了个双指针(在这里是双下标)简单解决
*/
#include <stdio.h>
#define MAXSIZE 20
typedef int ElementType;
typedef int Position;
typedef struct LNode* List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

List ReadInput(); /* 裁判实现,细节不表。元素从下标0开始存储 */
void PrintList(List L); /* 裁判实现,细节不表 */
List Delete(List L, ElementType minD, ElementType maxD);

int main()
{
    List L;
    ElementType minD, maxD;
    int i;

    L = ReadInput();
    scanf("%d %d", &minD, &maxD);
    L = Delete(L, minD, maxD);
    PrintList(L);

    return 0;
}
/* 你的代码将被嵌在这里 */
List Delete(List L, ElementType minD, ElementType maxD)
{
    int i = 0;
    int k = 0;
    int l = L->Last;
    while (i <= l)
    {
        while ((L->Data[i] > minD && L->Data[i] < maxD))
        {
            i++;
            L->Last--;
        }
        L->Data[k] = L->Data[i];
        i++;
        k++;
    }
    return L;
}
/**
 * 2022年3月21日20:48:28
 * 2. 两数相加
 * 想练练递归的题,结果第二题就是递归标签,梦开始的地方(),那就试着用递归再写一遍吧
 * 废了一些时间……卡在了链表连接上,最后看评论改过来了,没想到还能这样连接链表……
 */
class Solution {
    //本来是想和第一次写的C语言一样设立一个哑头结点的,但在链表连接上出了问题
    //最后把这个哑结点用来当l1或l2为null的时候,直接改变指向为这个,相当于赋值为0
    //这样写好像不太好还有点浪费空间,但和我最初的思路来看,我只能想到这个
    ListNode list = new ListNode(0);
    int flag = 0;
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1, l2);
    }
    public ListNode add(ListNode l1, ListNode l2){
        int temp;
        if(l1 == null && l2 == null)
            return flag == 0 ? null : new ListNode(flag);

        if(l1 == null)
            l1 = list;
        if(l2 == null)
            l2 = list;

        if(l1.val + l2.val + flag >= 10){
            temp = ((l1.val + l2.val + flag) % 10);
            flag = 1;
        }
        else{
            temp = (l1.val + l2.val + flag);
            flag = 0;
        }
        //能这样直接new出链表并连接我是没想到的……就卡在这里了,上面的基本算法没啥
        return new ListNode(temp, add(l1.next, l2.next));
    }
}

//评论区某位大哥的
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1, l2, 0);
    }
    public ListNode add(ListNode l1, ListNode l2, int temp){
        if(l1 == null && l2 ==null){
            return temp == 0 ? null : new ListNode(temp);
        }
        if(l1 != null){
            temp += l1.val;
            l1 = l1.next;
        }
        if(l2 != null){
            temp += l2.val;
            l2 = l2.next;
        }
        return new ListNode(temp % 10, add(l1, l2, temp / 10));
    }
}
/**
 * 2022年3月21日18:22:39
 * 701. 二叉搜索树中的插入操作
 * 直接上递归,啪的一下很快啊,但是感觉我写的怎么这么长啊2333这真的是递归吗
 * 看了一下评论区的,思路是一样的,但是我写的太臃肿的,有些多余的操作可以简化
 * 唉,任重而道远啊2333,继续学递归!
 */
//简洁写法
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null)
            return new TreeNode(val);
        if (root.val < val)
            root.right = insertIntoBST(root.right, val);
        else
            root.left = insertIntoBST(root.left, val);
        return root;
    }
}
//自己写的
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode treeRoot = root;
        if(root == null){
            TreeNode newNode = new TreeNode();
            newNode.val = val;
            treeRoot = newNode;
            return treeRoot;
        }
        if(root.val < val){
            if(root.right == null){
                TreeNode newNode = new TreeNode();
                newNode.val = val;
                root.right = newNode;
                return treeRoot;
            }
            insertIntoBST(root.right, val);
        }
        else{
            if(root.left == null){
                TreeNode newNode = new TreeNode();
                newNode.val = val;
                root.left = newNode;
                return treeRoot;
            }
            insertIntoBST(root.left, val);
        }
        return treeRoot;
    }
}
/**
 * 2022年3月21日13:08:48
 * 700. 二叉搜索树中的搜索
 * 中午小做一题,今天满课,先午休一下,午安~
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null)
            return null;
        if(root.val == val)
            return root;
        TreeNode temp;
        temp = searchBST(root.left, val);
        if(temp == null)
            temp = searchBST(root.right, val);
        return temp;
    }
}

03-20 日 阴

/**
 * 2022年3月20日23:51:29
 * 112. 路径总和
 * 还是想把这题先给做了,但不是很顺利,能想到递归的头绪了,但还是没能真正理解到递归的内涵,明天开始再深入了解一下吧
 * 晚安啦
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return flip(root, targetSum);
    }

    public boolean flip(TreeNode node,int sum) {
        if(node == null)
            return false;
        if(node.left == null && node.right == null)
            return (sum - node.val == 0);
        return flip(node.left, sum - node.val) || flip(node.right, sum - node.val);
    }
}
/**
 * 2022年3月20日23:18:23
 * 226. 翻转二叉树
 * 写之前感觉这题可以用递归写,而且根据前几题的经验,对于树的题用递归会很省事
 * 所以先去B站看了个递归的讲解视频BV1g741137Wq
 * 结果……结果……一命通关!!!!爽爆了!!!(我甚至都不清楚具体运行步骤)
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        return flip(root);
    }
    public TreeNode flip(TreeNode node) {
        TreeNode temp;
        if (node == null)
            return node;
        else {
            temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
        flip(node.left);
        flip(node.right);
        return node;
    }
}
/**
 * 2022年3月20日18:22:45
 * 101. 对称二叉树
 * 不说了,有被恶心到,写的非常复杂,但我不想放弃呜呜呜呜,结果写了个很臃肿的程序
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root.left == null && root.right==null)
            return true;
        Stack<TreeNode> stackLeft = new Stack<>();
        Stack<TreeNode> stackRight = new Stack<>();
        TreeNode pLeft = root.left;
        TreeNode pRight = root.right;
        Queue<Integer> queueLeft = new LinkedList<>();
        Queue<Integer> queueRight = new LinkedList<>();
        stackLeft.push(pLeft);
        stackRight.push(pRight);
        while( ( pLeft != null || !stackLeft.empty() ) || ( pRight != null || !stackRight.empty() ) ){
            while(pLeft != null){
                queueLeft.offer(pLeft.val);
                stackLeft.push(pLeft);
                pLeft = pLeft.left;
            }
            while(pRight != null){
                queueRight.offer(pRight.val);
                stackRight.push(pRight);
                pRight = pRight.right;
            }
            if(stackLeft.size() != stackRight.size())
                return false;
            pLeft = stackLeft.pop().right;
            pRight = stackRight.pop().left;
        }
        while(queueLeft.size() != 0){
            if( queueLeft.poll() != queueRight.poll() )
                return false;
        }
        return true;
    }
}
/**
 * 2022年3月20日10:52:49
 * 104. 二叉树的最大深度
 * 结合上一题的层析遍历写法的思路不算难,但总感觉有更好的方法,这样有点呆的样子
 * 看了一下评论区果然是,好家伙一个递归直接给我解决了,自己对递归的使用不是很敏感啊
 */
//递归写法
class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}
//模仿层析遍历(即遍历每一个节点,每层+1)
class Solution {
    public int maxDepth(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int count_Row, count_Taft = 0;

        while(queue.peek() != null){
            count_Row = queue.size();
            while(count_Row != 0){
                root = queue.poll();
                if(root.left != null)
                    queue.add(root.left);
                if(root.right != null)
                    queue.add(root.right);
                count_Row--;
            }
            count_Taft++;
        }
        return count_Taft;
    }
}
/**
 * 2022年3月20日10:17:40
 * 102. 二叉树的层序遍历
 * 刚开始还想模仿前几天写的前中后序遍历来写,直接new了个栈
 * 结果发现这时候好像用队列会很方便,因为每层的最后一个节点要到下一层的第一个节点
 * 这样就需要先进先出的队列来实现了
 */

import java.util.*;
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list_List = new ArrayList<List<Integer>>();//new一个值为List的List
        Queue<TreeNode> queue = new LinkedList<TreeNode>();//层析遍历得用队列了,之前三个遍历都用的栈
        queue.offer(root);//头结点先入队(方便计数器的第一次判断)
        int count;//定义一个计数器,计算下一层的节点个数
        while(queue.peek() != null){
            count = queue.size();//计数器更新
            List<Integer> list_Node = new ArrayList<Integer>();//new一个值为int的List
            while(count != 0){
                root = queue.poll();//先让节点进入下一个节点
                if(root.left != null){
                    queue.offer(root.left);//若当前根节点左子树不为空,则入队
                }
                if(root.right != null){
                    queue.offer(root.right);//若当前根节点右子树不为空,则入队
                }
                count--;//每检查完一个根,计数器自减
                list_Node.add(root.val);//将当前节点添加导list_Node
            }
            list_List.add(list_Node);//循环结束即为一层,将整个list_Node添加到list_List
        }
        return list_List;
    }
}

03-19 土 阴

/**
 * 2022年3月19日14:47:14
 * 94. 二叉树的中序遍历
 * 145. 二叉树的后序遍历
 * 继续昨天的前序遍历,还有两题类似的,中序遍历较为简单,在前序基础上加以修改即可
 * 但tm后序遍历是什么鬼!!!想了好久的思绪,在逻辑上行得通,但在力扣测试的时候会报错
 * 而且报的错并没有明确指出,只告诉我某个判断上划了红色波浪线……
 * 人麻了,后序遍历还理解不了,先把答案抄下来吧
 */

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
//后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode pre = null;
        while(root != null || !stack.empty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right == null || root.right == pre){
                list.add(root.val);
                pre = root;
                root = null;
            }
            else{
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    }
}
//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(root != null || !stack.empty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}

03-18 金 阴

一棵二叉树由根结点、左子树和右子树三部分组成,若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树,则二叉树的遍历方式有 6 种:DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别,所以,只讨论三种方式: DLR--前序遍历(根在前,从左往右,一棵树的根永远在左子树前面,左子树又永远在右子树前面 ) LDR--中序遍历(根在中,从左往右,一棵树的左子树永远在根前面,根永远在右子树前面) LRD--后序遍历(根在后,从左往右,一棵树的左子树永远在右子树前面,右子树永远在根前面)

/**
 * 2022年3月18日23:14:43
 * 144. 二叉树的前序遍历
 * 栈理解完,突然二叉树来了……看了一下后面几天的计划都是树,这得去熟悉一下树的概念了
 * 这题可以说并不会做2333,对树只有个结构的认知,并不知道具体做法之类的
 * 首先前序遍历就去查了资料,刚好教程里有递归实现前序遍历的示例,就摘抄了
 * 但感觉对我来说递归比较难想到用,对递归的使用还不是很熟悉,就想写循环的
 * 防着递归写,感觉循环的概念更难摸索……只好还是看答案了,答案还挺好理解的……
 * 我好菜!……
 */

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
//非递归
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();//new一个ArrayList类
        Stack<TreeNode> stack = new Stack<TreeNode>();//new一个栈,元素为TreeNode
        while(root != null || !stack.empty()){
            while(root != null){//当左子树不为空的时候执行该循环
                list.add(root.val);//添加当前根节点的值
                stack.push(root);//往栈中记录该根节点,用于后面返回该根节点
                root = root.left;//进入下一个左子树
            }
            //若当前根节点(上一个根节点的左子树)为空,则进入上一个根节点的右子树
            root = stack.pop().right;
        }
        return list;
    }
}
//递归
public class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        middle_order(root);
        return list;
    }
    public void middle_order(TreeNode root){
        if(root == null)
            return;
        list.add(root.val);
        middle_order(root.left);
        middle_order(root.right);
    }
}
/**
 * 2022年3月18日21:51:24
 * 232. 用栈实现队列
 * 神tm用栈实现队列,但看到通过率这么高,感觉不会太难
 * 先自己构思,一般栈思维里都是竖着进出的,队列是横向进出
 * 于是我构思出了两个相反着的栈横着,想通过某种关系可以同时操作头和尾并且产生规律
 * 但折腾一会发现木大(不行),看是去看下答案思路,好家伙原来是竖着进出的,有思路就写成了
 */

import java.util.Stack;
class MyQueue {
    Stack<Integer> stackHead = new Stack<Integer>();
    Stack<Integer> stackTail = new Stack<Integer>();
    public MyQueue() {

    }

    public void push(int x) {
        while(!stackHead.empty()){
            stackTail.push(stackHead.pop());
        }
        stackTail.push(x);
    }

    public int pop() {
        while(!stackTail.empty()){
            stackHead.push(stackTail.pop());
        }
        return stackHead.pop();
    }

    public int peek() {
        while(!stackTail.empty()){
            stackHead.push(stackTail.pop());
        }
        return stackHead.peek();
    }

    public boolean empty() {
        return stackTail.empty() && stackHead.empty();
    }
}

03-17 木 阴

/**
 * 2022年3月17日23:21:55
 * 20. 有效的括号
 * 栈
 * 力扣数据结构基础题刷到了栈了,今晚先靠这题来熟悉一下栈的使用和题型吧
 * 刚接触第一题显然我不会写……看了评论区和题解理解了思路,照着教程的方法写了,理解起来不难
 * 到目前为止感觉哈希表和链表有一丢丢掌握了,而且链表比哈希表容易上手的感觉
 * 明天开始学习栈~刷牙休息咯,晚安
 */
import java.util.Stack;
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == '(')
                stack.push(')');
            else if(ch == '[')
                stack.push(']');
            else if(ch == '{')
                stack.push('}');
            else if(stack.empty() || ch != stack.pop())
                return false;
        }
        return stack.empty();
    }
}
/**
 * 2022年3月17日21:35:56
 * 383. 赎金信
 * 哈希表 数组
 * 想都不想就直接new HashMap了,结果出来一个十几ms的用时
 * 看一眼评论区,恍然大悟,又忘了可以用数组做哈希表更简单
 * 因为小写字母个数就26个,直接定义一个26个元素的int数组就可以进行记录字符串的个数
 */
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] count = new int[26];
        for(int i = 0; i < magazine.length(); i++){
            count[magazine.charAt(i) - 'a']++;
        }
        for(int j = 0; j < ransomNote.length(); j++){
            count[ransomNote.charAt(j) - 'a']--;
            if(count[ransomNote.charAt(j) - 'a'] < 0){
                return false;
            }
        }
        return true;
    }
}
import java.util.HashMap;
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>();
        char[] ran = ransomNote.toCharArray();
        char[] maga = magazine.toCharArray();
        for(int i = 0; i < maga.length; i++){
            if(hashMap.containsKey(maga[i])){
                hashMap.replace(maga[i],hashMap.get(maga[i]) + 1);
            }
            else{
                hashMap.put(maga[i], 1);
            }
        }
        for(int j = 0; j < ran.length; j++){
            if(hashMap.containsKey(ran[j]) && hashMap.get(ran[j]) != 0){
                hashMap.replace(ran[j],hashMap.get(ran[j]) - 1);
            }
            else{
                return false;
            }
        }
        return true;
    }
}
/**
 * 2022年3月17日20:57:08
 * 83. 删除排序链表中的重复元素
 * 一眼出思路,想起这几天做的有一题跳过某个元素差不多的,有些经验躲坑了2333
 * 但还是被空链表骗了一下,但问题不大,开头加个判断就行啦(虽然不想判断增强整体健壮性的,但还是这样快捷了)
 */
//看了看答案发现可以有更简短的写法,看来我还是太嫩了  
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null)
            return head;
        ListNode p = head;
        while(p.next != null){
            if(p.val == p.next.val){
                p.next = p.next.next;
            }
            else{
                p = p.next;
            }
        }
        return head;
    }
}
//记录指针Head和记录变量temp其实可以不用,只用一个辅助指针就能完成
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode Head = head;
        ListNode p = head.next;
        int temp = head.val;
        while(p != null){
            if(p.val == temp){
                head.next = null;
            }
            else{
                temp = p.val;
                head.next = p;
                head = head.next;
            }
            p = p.next;
        }
        return Head;
    }
}

03-16 水 阴

/**
 * 2022年3月16日22:43:51
 * 206. 反转链表
 * 第一反应肯定是先遍历链表然后新建链表反向加节点,但这样的话需要遍历两次,就琢磨单遍历的写法
 * 于是第一次写出了与官方答案一模一样的算法,只是可惜前后指针被我搞反了导致链表循环了
 * 最后还是看答案才发现是前后指针初始写反了,换过来就直接成功了!激动耶!
 */
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 reverseList(ListNode head) {
        ListNode pre = null;//定义前指针
        ListNode next = head;//后指针
        while(head != null){
            next = head.next;//先把当前节点的下一节点记录
            head.next = pre;//改变当前节点的指向(反指)
            pre = head;//把前指针进位到当前节点
            head = next;//当前节点进位到next记录的下一节点
        }
        return pre;//返回前指针(最后前指针会进位到原链表最后一个节点的位置上,即反转后的第一个节点上)
    }
}
/**
 * 2022年3月16日20:30:06
 * 203. 移除链表元素
 * 链表
 * 挺简单,一次性写出来了,但遇到点小问题,就是和上一题合并链表的功能有些混淆了
 * 合并链表的时候是可以一直串着走的,而移除节点的时候,若遇到要移除的元素只是不添加(跳过)的话
 * 并且那个元素在末尾,则会产生拼接效果,例如:
 * [1,7,7,7] 7 会返回原链表,因为没有在第二个节点位置使指针指向null,造成了拼接的效果
 * 即第一个节点后面默认连着其后的节点而没有断开连接
 * (小细节哈哈哈哈)
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
 public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode newHead = new ListNode();//新建一个(哑)头结点
        ListNode p = newHead;//辅助指针
        while(head != null){
            if(head.val == val){
                p.next = null;//若当前节点的元素为指定移除元素,则暂时截断(而不是跳过)
            }
            else{
                p.next = head;//不是的话则可以接上
                p = p.next;//辅助节点到新增节点的位置上,准备下一次判断指向
            }
            head = head.next;//原链表遍历
        }
        return newHead.next;//返回(真)头结点
    }
}
/**
 * 2022年3月16日19:59:04
 * 21. 合并两个有序链表
 * 时隔几天2333,还是想用Java写一遍试试,满脑子的哑结点和辅助指针
 * 感觉有一些掌握Java和C语言中链表使用方法的区别了
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();//new一个(哑)头结点
        ListNode p = head;//指向(哑)头结点的辅助指针
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next = list1;//若链表1的值小于链表2的值,则辅助指针指向该链表1的节点
                list1 = list1.next;//并使链表1进入下一个节点
            }
            else{
                p.next = list2;//链表2同理
                list2 = list2.next;
            }
            p = p.next;//辅助指针也需要顺着新合成的链表走
        }
        p.next = list1 == null ? list2 : list1;//跳出循环后将辅助指针直接指向未遍历完的链表上
        return head.next;//返回(真)头结点
    }
}
Java:感觉对于链表我用C语言更能理解一些,Java反而对哈希表熟一点,得两者兼顾一下了,写完C再用Java写一遍
/**
 * 2022年3月16日19:28:22
 * 141. 环形链表
 * 快慢指针
 * 昨天遇到一个可以用前后指针的题,今天遇到的是快慢指针
 * 通过循环链表,如果快慢指针相等的时候说明该链表是成环的
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
 }
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;//快指针
        ListNode slow = head;//慢指针
        while(fast != null && fast.next !=null){
            fast = fast.next.next;//快指针一次走两步
            slow = slow.next;//慢指针一次走一步
            if(fast == slow)
                return true;//若相等则返回true
        }
        return false;//跳出了循环则说明不成环
    }
}
C语言:
#include <stdio.h>
struct ListNode {
    int val;
    struct ListNode *next;
 };
bool hasCycle(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            return true;
        }

    }
    return false;
}
/**
* 2022年3月16日17:20:00
* PTA 数据结构作业 DSW3:7-1 平均之上
* 链表 指针
* 写了一下午数据结构的作业,感觉这题还是有些代表性的,也搬上来吧,晚上再写一题力扣
* 想不出数组怎么写,就直接用链表了,但看到舍友用数组用一样的方式写了,感觉是个挺不错的新写法
* 大概是提前申请sizeof(int)*n的空间,然后进行操作,最后再销毁
*/
//不用链表,单用指针
#include <stdio.h>
#include <stdlib.h>
void main()
{
    int T;
    int n;
    scanf("%d", &T);
    int count;//计数器
    int add;//求和
    int average;//求平均
    for (int i = 1; i <= T; i++)
    {
        scanf("%d", &n);
        int* P = malloc(sizeof(int) * n);//提前为“数组P”开辟一个n个数的空间
        int* temp = P;//辅助指针指向开头
        count = 0;//归零
        add = 0;
        average = 0;
        for (int j = 1; j <= n; j++, temp++)
        {
            scanf("%d", temp);
            add += *temp;//累加
        }
        average = add / n;
        temp = P;//重新回到开头
        for (int j = 1; j <= n; j++, temp++)
        {
            if (*temp > average)
            {
                count++;//记下大于平均的个数
            }
        }
        printf("%d\n", count);//这题tm打印得换行才不会报错
        free(P);//释放刚刚建立的空间
    }
}

//用链表
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
    int val;
    struct ListNode* next;
};
void main()
{
    typedef struct ListNode List;
    List* P = malloc(sizeof(List));
    List* temp = malloc(sizeof(List));
    int T;
    int n;
    scanf("%d", &T);
    int count;
    int add;
    int q;
    for (int i = 1; i <= T; i++)
    {
        List* P = malloc(sizeof(List));
        List* temp = malloc(sizeof(List));
        temp->val = 0;
        temp->next = P;
        count = 0;
        add = 0;
        q = 0;
        scanf("%d", &n);
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &temp->next->val);
            add += temp->next->val;
            List* a = malloc(sizeof(List));
            temp->next->next = a;
            temp = temp->next;
        }
        q = add / n;
        temp->next = P;
        for (int j = 1; j <= n; j++)
        {
            temp = temp->next;
            if (temp->val > q)
            {
                count++;
            }
        }
        printf("%d\n", count);
        free(P);
        free(temp);
    }
}

03-15 火 晴

/**
* 2022年3月15日21:03:28
* 19. 删除链表的倒数第 N 个结点
* 链表 指针 单指针双遍历
* 既然这几天老师都在讲链表,那就试试链表的题吧
* 写了个单指针的但要遍历两次,再去看看双指针的写法(好像是前后指针)
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//还是单指针双遍历,但参照答案一新建了一个哑结点,可以省去很多逻辑判断问题
/*(而且查阅资料发现for循环中i++和++i的关系)
for 循环中 ++i 和 i++的结果是一样的,都要等代码块执行完毕才能执行,但是性能是不同的。
++i的性能 > i++的性能
在大量数据的时候++i的性能要比i++的性能好原因:
i++由于是在使用当前值之后再+1,所以需要一个临时的变量来转存。
而++i则是在直接+1,省去了对内存的操作的环节,相对而言能够提高性能。
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    struct ListNode* p0 = malloc(sizeof(struct ListNode));
    p0->val = 0;
    p0->next = head;

    int length = 0;
    while (head)
    {
        head = head->next;
        ++length;
    }
    struct ListNode* p = p0;
    for (int i = 0; i < length - n; ++i)
    {
        p = p->next;
    }
    p->next = p->next->next;
    struct ListNode* p1 = p0->next;
    free(p0);
    return p1;
}
//第一次写的,没有设置哑结点,需要额外加几个if判断特殊情况,很麻烦
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* p = head;
    int length = 0;
    while (p)
    {
        p = p->next;
        ++length;
    }
    if (length == 1)
    {
        return NULL;
    }
    if (n == length)
    {
        return head->next;
    }
    p = head;
    for (int i = 0; i < length - n - 1; ++i)
    {
        p = p->next;
    }
    p->next = p->next->next;
    return head;
}

03-14 月 晴

/**
* 2022年3月14日22:54:41
* 21. 合并两个有序链表
* 链表 指针
* 洗完澡刷着力扣网页,突然看到这题,立马点了进去
* 今天数据结构刚讲了链表还写了一模一样的题(不过老师才教到让我们数组写的)
* 虽然在学Java了,但数据结构老师还是用C语言讲课,所以果断选择用C语言
* 思路和用数组写的不太一样,但还是比较清晰的,在建立指针p那里卡了一会,后来才发觉漏了个临时头结点
* 可能最近Java哈希表写多了,链表反而没怎么练,得去接触一下Java里链表的写法了
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode P;//新建一个头结点
    struct ListNode* p = &P;//指向头结点的指针
    while (list1 != NULL && list2 != NULL)
    {
        if (list1->val <= list2->val)
        {
            //若链表1的数较小,则指针p连到链表1上
            p->next = list1;
            //并且链表1进入自身下一个节点
            list1 = list1->next;
        }
        else
        {
            //同理
            p->next = list2;
            list2 = list2->next;
        }
        //指针p进入刚刚连上的链表的新节点上
        p = p->next;
    }
    //最后会由于其中一个链表先指空而退出,这时会有另一个链表还未遍历完
    //但已排序好,则指针p连上未遍历链表剩下的整体即可
    p->next = list1 == NULL ? list2 : list1;
    //指针p重新指向头结点
    p = &P;
    //头结点是废节点,应返回头结点的下一节点
    return p->next;
}
/**
 * 2022年3月14日20:47:09
 * 387. 字符串中的第一个唯一字符
 * 哈希表
 * 思路还行,虽然第一次写的效率极低遍历两次才能出结果
 * 虽然也想要和题解一样第二次遍历哈希表减少时间复杂度,但奈何不会写,只好抄答案的遍历了emmm
 */
//双遍历,第二次遍历已得出的哈希表
import java.util.HashMap;
class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>();
        int temp = s.length();
        for(int i = s.length() - 1; i >= 0; i--) {
            char ch = s.charAt(i);
            if (hashMap.containsKey(ch)) {
                hashMap.replace(ch, -1);
            } else {
                hashMap.put(ch, i);
            }
        }
        for (HashMap.Entry<Character, Integer> entry : hashMap.entrySet()) {
            int pos = entry.getValue();
            if (pos != -1 && pos < temp) {
                temp = pos;
            }
        }
        if(temp == s.length()){
            return -1;
        }
        return temp;
    }
}
//双遍历,两次都遍历数组
class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>();
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length; i++){
            if(hashMap.containsKey(chars[i])){
                hashMap.replace(chars[i], hashMap.get(chars[i]) + 1);
            }
            else{
                hashMap.put(chars[i],1);
            }

        }
        for(int j = 0; j < chars.length; j++){
            if(hashMap.get(chars[j]) == 1){
                return j;
            }
        }
        return -1;
    }
}

03-13 日 晴

/**
 * 2022年3月13日22:46:45
 * 73. 矩阵置零
 * 矩阵
 * 感觉自己总是很容易在一些地方卡住,思路不是没有,但无法第一反应出通畅的思路,总会写出有问题的算法把自己难住
 * 还是先去把基础打牢再多刷题吧,效率变低了感觉
 */
class Solution {
    public void setZeroes(int[][] matrix) {
        //定义一横一纵的标记数组
        int[] length = new int[matrix[0].length];
        int[] width = new int[matrix.length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == 0){
                    //如果当前数为零,则标记他们的横和纵列,方便后面判断
                    width[i] = 1;
                    length[j] = 1;
                }
            }
        }
        for(int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(width[i] == 1 || length[j] == 1){
                    //若该数为被标记数的横或纵内的数,则修改为0
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
/**
 * 2022年3月13日12:20:20
 * 36. 有效的数独
 * 矩阵 哈希表
 * 中等题,思路不难,但方法没用好,用的有些偏,要是能理出来也能写,但实在想不下去了,费了一上午呜呜呜呜
 */
class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] length = new boolean[9][9];//数独横向检查
        boolean[][] width = new boolean[9][9];//数独纵向检查
        boolean[][] matrix = new boolean[9][9];//数独9*9矩阵检查(这里每一个二维数组代表一个矩阵,每个矩阵里九个元素)
        int t;//
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    t = board[i][j] - '1';//若当前数不是'.'即转为数字(-'1'防止溢出)
                    if (length[i][t] || width[j][t] || matrix[i / 3 * 3 + j / 3][t]) {
                        return false;//有已经出现过的数则直接返回false
                    } else {//否则将其一一标记
                        length[i][t] = true;
                        width[j][t] = true;
                        matrix[i / 3 * 3 + j / 3][t] = true;
                    }
                }
            }
        }
        return true;
    }
}

03-12 土 晴

/**
 * 2022年3月12日20:35:00
 * 118. 杨辉三角
 * 双重链表
 * 熟悉的杨辉三角,一眼感觉很简单,通过率也相当高,但细看一下发现这个类还没学到
 * 先去熟悉了一下定义,但有一些卡在了找规律上,可能有些困了,先洗个澡去做高数吧
 */
import java.util.*;
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> List = new ArrayList<List<Integer>>();//new一个链表中存有链表的链表(?)
        for(int i = 0; i < numRows; ++i) {//注意:应使用++i和++j,勿习惯性i++……
            List<Integer> ListInside = new ArrayList<Integer>();//每次new一个里链表
            for(int j = 0; j <= i; ++j ){
                if(j == 0 || j ==i){
                    ListInside.add(1);//如果是第一位或是最后一位,默认为1
                }
                else{
                    ListInside.add(List.get(i - 1).get(j - 1) + List.get(i - 1).get(j));//否则利用杨辉三角的规律进行赋值
                }
            }
            List.add(ListInside);//进入下一次循环前把里链表插入链表中
        }
        return List;
    }
}
/**
 * 2022年3月12日19:56:13
 * 566. 重塑矩阵
 * 矩阵、二维数组
 * 这题通过率很高,也简单思路也清晰,但被自己小聪明绊倒了一下
 * 在遍历原二维数组的时候应该遵循它自身的遍历(我一开始手动加了break语句……)而新数组只需要下标判断就行
 */
class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        if(r * c != mat[0].length * mat.length)
            return mat;//如果给的要求数不符合矩阵的行列,则直接返回原数组
        int[][] matrix = new int[r][c];//new一个矩阵
        int k = 0, l = 0;
        for(int[] i : mat){
            for(int j : i){
                matrix[k][l++] = j;//遍历原数组,将值赋给矩阵
                if(l == c){
                    k++;//若原数组中一维数组已满,则二维进位
                    l = 0;//且一维重新归零
                }
                if(k == r){
                    return matrix;//若二维已最大,则可返回矩阵
                }
            }
        }
        return matrix;
    }
}

03-11 金 晴

/**
 * 2022年3月11日19:37:43
 * 121. 买卖股票的最佳时机
 * 动态规划
 */
class Solution {
    public int maxProfit(int[] prices) {
        int buy = prices[0], sell = 0;//如名买和卖的价格
        int maxProfit = 0;//存最大值
        int i = 0, k = 1;//下标,用来判断是否买(i)和卖(k)
        while(k < prices.length){
            if(prices[i] < buy){
                buy = prices[i];//如果i天的价格比买入更低,那就买入(假设)
                sell = prices[i + 1];//在i天买入后,只能在其之后卖出
            }
            if(prices[k] > sell){
                sell = prices[k];//如果k天的价格比卖出更高,那就卖出
            }
            i++;//买入卖出的判断下标都需要自增
            k++;
            maxProfit = Math.max(maxProfit, sell - buy);//储存最大的利润值
        }
        return maxProfit;
    }
}
/**
 * 2022年3月11日13:06:08
 * 350. 两个数组的交集 II
 * 哈希表
 * 早上先看了一遍题就去上离散数学了,上完课回来随便玩会吃完午饭后十二点开始做这题,到一点才做完……好菜
 * 这题基本思路是用哈希表的键与值的关系进行两个数组的遍历,查找出有几个重复的数,对另一个数组将这些重复的数重新赋值给另一个数组
 */
import java.util.Arrays;
import java.util.HashMap;
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();//创建一个哈希表
        for(int i = 0; i < nums1.length; i++){
            if(hashMap.containsKey(nums1[i])){
                hashMap.replace(nums1[i],hashMap.get(nums1[i]) + 1);//若该数存在则值+1(个)
            }
            else{
                hashMap.put(nums1[i], 1);//否则插入该数并默认值为1(个)
            }

        }
        int[] nums = new int[nums1.length > nums2.length ? nums1.length : nums2.length];
        //nums1.length > nums2.length ? nums1.length : nums2.length
        int k = 0;//定义一个标记点,用于第三个数组的赋值和return时的尾数
        for(int j = 0; j < nums2.length; j++){
            if(hashMap.containsKey(nums2[j]) && hashMap.get(nums2[j]) > 0){
                nums[k++] = nums2[j];//若该数已在哈希表中且值>0(个),则赋值给第三个数组且使该数的值-1(个)
                hashMap.replace(nums2[j],hashMap.get(nums2[j]) - 1);
            }
        }

        return Arrays.copyOfRange(nums, 0, k);//返回第三个数组的0~k个有意义的元素
    }
}

03-10 木 晴

/**
 * 2022年3月10日21:15:35
 * 88. 合并两个有序数组
 * 首先想到用第三个数组,然后给nums1复制回去(但好像违背题意了)
 * 然后想到尾插法,前面不行就后面来(2333)
 */
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m + n - 1;//定义nums1最后一个元素的下标
        while(m > 0 && n > 0){
            if(nums1[m - 1] >= nums2[n - 1]){
                nums1[i--] = nums1[--m];//从最后一个元素开始比较,谁大谁插入(怎么这么奇怪)
            }
            else{
                nums1[i--] = nums2[--n];
            }
        }
        while(n > 0){
            nums1[i--] = nums2[--n];//例题里有nums1有效长度为0但nums2有长度的情况,需要另外考虑
        }
    }
}

一个星期的前后.png

/**
 * 2022年3月10日20:29:24
 * 1. 两数之和
 * 时隔一星期,又在数据结构专项题里遇到了这个力扣第一题
 * 当时只能暴力破解法,对哈希表一点也不理解,这次总算可以看着书写出来了(虽然思路还是不清晰)
 */
import java.util.HashMap;
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();//创建一个哈希表,键存数,值存下标(这里不反过来是因为get方法可以返回对应数的下标)
        for(int i = 0; i < nums.length; i++){
            if(hashmap.containsKey(target - nums[i])){
                return new int[]{hashmap.get(target - nums[i]), i};//若有该数对应的差数,则直接返回这两个数的下标
            }
            hashmap.put(nums[i], i);//添加
        }
        return new int[]{0};//按题来说不会到这一步,在循环里一定有对应的数并返回
    }
}
/**
 * 2022年3月10日08:18:59
 * 53. 最大子数组和
 * 动态规划
 * 这题是数据结构书上的第一道例题==,但测试用例比书上刁钻
 * 例如只有负数的情况下,不能初始化MaxSum = 0,而应该让它为最小整型。
 */
class Solution {
    public int maxSubArray(int[] nums) {
        int ThisSum = 0;//当前子数组之和
        int MaxSum = Integer.MIN_VALUE;//最大的子数组之和
        for(int i = 0; i < nums.length; i++){
            ThisSum += nums[i];//子数组累加
            if(ThisSum > MaxSum){
                MaxSum = ThisSum;//覆盖最大值
            }
            if(ThisSum < 0){
                ThisSum = 0;//当前子数组之和<0时,累加会降低后面的最大值,所以直接归零重开()
            }
        }
        return MaxSum;
    }
}

03-09 水 晴

import java.util.HashSet;
import java.util.Set;
class Solution {
    /**
     * 2022年3月9日21:59:14
     * 217. 存在重复元素
     * 试试力扣里的“三周攻克数据结构”学习计划,感觉数据结构的学习方向还不是很清晰,借此套题了解学习一下吧
     * 这题不难,一下子就想到了哈希表(标签里都有2333),但对Java类的使用还不太完全,我先去补补知识吧
     */
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();//创建哈希表
        for(int i : nums)
            set.add(i);//遍历数组并插入哈希表
        return set.size() < nums.length;//判断前后长度是否一致
    }
}
class Solution {
    /**
     * 2022年3月9日12:27:31
     * 8. 字符串转换整数 (atoi)
     */
    // 这题真是我做的最恶心的一题,题目不难,但是很多没讲清楚的坑,本来昨晚能写完的,但被一个例子绊倒了 "+1"
    // 在今天第一节高数课上想到了解决方法,并在第二节Java课上立刻去验证了,但又遇到了下一个坑 "9223372036854775808"
    // 直到现在中午才把它通过(午饭还没吃呢,写完去吃饭了www)
    public int myAtoi(String s) {
        s = s.trim();//先将字符串前后的空格清除
        char[] c = s.toCharArray();//将字符串转换为字符数组
        if(c.length == 0)//若清除空格后字符数组长度为零,直接返回0
            return 0;
        int i = 0;//字符数组下标
        int flag = 1;//标记正负,默认为正
        //判断有无正负号,若有则改变标记flag以及下标i+1
        if(c[0] == '-'){
            flag = -1;
            i++;
        }
        if(c[0] == '+'){
            i++;
        }
        long temp = 0;//用long防止溢出报错
        for(; i < c.length; i++){
            if(Character.isDigit(c[i])){
                temp = (c[i] - '0') + temp * 10 ;//若为数字则算进temp里
            }
            else{
                break;//否则可跳出循环
            }
            if(-temp < Integer.MIN_VALUE || temp > Integer.MAX_VALUE){
                temp = flag > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;//若temp不在int范围,则限制值并跳出循环
                break;
            }
        }
        temp = flag > 0 ? temp : -temp;//由标记flag决定temp的正负
        return (int)temp;//返回时要强转回int
    }
}

03-08 火 晴

class Solution {
    /**
     * 2022-03-08
     * 7. 整数反转
     */
    //引入临时变量n,若反转途中会溢出的话,那么判断出y/10不等于n,则可判断为已溢出即return 0,否则可将n的值赋给y继续反转。
    //ps:看了一下评论区,发现这个方法好像只适用于Java,其他语言溢出会直接报错……(这就是Java的优点体现吗2333)
    public int reverse(int x) {
        int t = x > 0 ? x : -x;
        int y = 0;
        int n = 0;
        while(t != 0){
            n = t % 10 + n * 10;
            if(y != n / 10)
                return 0;
            y = n;
            t = t / 10;
        }
        //误以为溢出都会变成与其正负相反的乱码,结果在1030 / 1032 个通过测试用例中的1534236469输入给绊倒了,说明溢出并不都是如此
//        if((y > 0 && x > 0) || (-y <0 && x < 0)){
//            return x > 0 ? y : -y;
//        }
//        else{
//            return 0;
//        }
        return x > 0 ? y : -y;
    }
}

03-07 月 晴

import java.util.Arrays;
class Solution {
    /**
     * 2022-03-07
     * 6. Z 字形变换
     */

    //这题实在没思路,抄答案思路都打错一个符号,但学到一点小知识,这题用到了字符串数组、字符串拼接
    //注释//为答案中还没掌握的内容,但用已有知识可起到同样作用,如:字符串数组初始化Array.fill()、字符串拼接result.append()
    public String convert(String s, int numRows) {
        if(numRows == 1){
            return s;
        }
        char[] charArray = s.toCharArray();
        String[] stringArray = new String[numRows];
//        Arrays.fill(stringArray,"");
        for(int i = 0; i < numRows; i++){
            stringArray[i] = "";
        }
        int T = numRows * 2 - 2;
        for(int i = 0; i < charArray.length; i++){
            int mod = i % T;//我tm符号打错了!!!这里卡半个小时我操!!!
            if(mod < numRows){
                stringArray[mod] += charArray[i];
            }
            else{
                stringArray[T - mod] += charArray[i];
            }
        }
//        StringBuilder result = new StringBuilder();
//        for(String substr : stringArray){
//            result.append(substr);
//        }
        String string = new String();
        for(int i = 0; i < numRows; i++){
            string += stringArray[i];
        }
//        return result.toString();
        return string;
    }
}

03-06 日 晴

class Solution {
    /**
     * 2022-03-06
     * 5. 最长回文子串
     */

    //动态规划:若字串是回文,则字串掐头去尾后依旧是回文,即一串回文若头和尾相同,那么这串回文的长度+2,可利用此性质写出动态规划来判断是否为更长的回文字串

    public String longestPalindrome(String s) {
        int length = s.length();
        if(length < 2) return s;
        int maxLen = 1;
        int begin = 0;
        int i, j;
        boolean dp[][] = new boolean[length][length];
        for(i=0; i < length; i++){
            dp[i][i] = true;
        }
        char[] charArray = s.toCharArray();
        for(j = 1; j < length; j++){
            for(i = 0; i < j; i++){
                if(charArray[i] != charArray[j]){
                    dp[i][j] = false;
                }
                else{
                    if(j - i < 3){
                        dp[i][j] = true;
                    }
                    else{
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if(dp[i][j] && j - i + 1 >maxLen){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

    //暴力破解:从左到右枚举所有可能的字串,记录最大长度的那一串并返回
class Solution {
    public String longestPalindrome(String s) {
        int i, j;
        int maxLen = 1, begin = 0;
//        char[] c = s.toCharArray();//将字符串转换为字符数组(非必须)

        for(i = 0; i < s.length() - 1; i++){
            for(j = i + 1; j < s.length(); j++){
                if(j - i + 1 > maxLen && isPalindrome(i, j, s)){
                    maxLen = j - i + 1;
                    begin = i;
                }

            }
        }
        return s.substring(begin, begin + maxLen);
    }
    public boolean isPalindrome(int left, int right, String s){
        while(left < right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

03-05 土 晴

class Solution {
    /**
     * 2022-03-05
     * 9. 回文数
     * 取余、除
     */

    // 答案解法,只反转一半的数,若为回文则后一半与前一半相等,前一半小于后一半时,则表示已处理一半,(特别注意以0结尾的数)

    public boolean isPalindrome(int x) {
        int sum = 0;
        // 特殊情况:
        // 如上所述,当 x < 0 时,x 不是回文数。
        // 同样地,如果数字的最后一位是 0,为了使该数字为回文,
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if(x < 0 || (x % 10 == 0 && x != 0))return false;
        while (x > sum) {
            sum = sum * 10 + x % 10;
            x = x / 10;
        }
        // 当数字长度为奇数时,我们可以通过 sum/10 去除处于中位的数字。
        // 例如,当输入为 12321 时,在 while 循环的末尾我们可以得到 x = 12,sum = 123,
        // 由于处于中位的数字不影响回文(它总是与自己相等),所以我们可以简单地将其去除。
        return x ==sum || x== sum / 10;
    }
    // 初步解法,完全回文判断,有溢出风险,但反转后会溢出的肯定不是回文数,即会被反转成乱数,判断之后依旧为FALSE,因此风险可无视
    public boolean isPalindrome(int x) {
        if(x<0){
            return false;
        }
        int temp = 0;
        int sum = 0;
        int t = x;
        while(t != 0){
            temp = t % 10;
            sum = sum * 10 + temp;
            t = t / 10;
        }
        if(sum == x){
            return true;
        }
        else {
            return false;
        }
    }
}

03-04 金 晴

class Solution {
    /**
     * 2022-03-04
     * 4. 寻找两个正序数组的中位数
     * 二分查找
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length)
        {
            int[] temp;
            temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int m = nums1.length;
        int n = nums2.length;

        // 分割线左边的所有元素需要满足的个数:m + (n - m + 1) / 2;
        int left = (m + n + 1) / 2;
        // 在 nums1 的区间 [0,m] 里查找恰当的分割线;
        // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i];
        int l = 0;
        int r = m;
        int i,j;
        while(l < r){
            i = l + (r - l + 1) / 2;
            j = left - i;
            if(nums1[i-1]>nums2[j]){
                // 下一轮搜索的区间 [l,i-1]
                r = i - 1;
            }
            else{
                // 下一轮搜索的区间 [i,r]
                l = i;
            }
        }
        i = l;
        j = left - i;
        // 防溢出
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i-1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ?Integer.MIN_VALUE : nums2[j-1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
        if((m+n)%2==0){
            return (double)(Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))/2;
            //return (double)(nums1[i-1]<nums2[j-1]?nums1[i-1]:nums2[j-1] + nums1[i]>nums2[j]?nums1[i]:nums2[j])/2;
        }
        else{
            return (double)Math.max(nums1LeftMax, nums2LeftMax);
            //return (double)(nums1[i-1]>nums2[j-1]?nums1[i-1]:nums2[j-1]);
        }
    }
}
本文为作者九日发布,未经允许禁止转载!
954
5
0
发表留言

    4个月前

    厉害,加油|´・ω・)ノ

      九日作者
      4个月前

      刚好这两天没更新2333

    上海seo
    4个月前

    有点像C语言

    玉米
    4个月前

    明明学的JAVA像是一样,结果差距为何如此之大

      九日作者
      4个月前

      只是一些简单的基础题,数据结构还没学完呢

力扣每日一题(三月)
扫描右侧二维码继续阅读
March 7, 2022
微风忆夏
blogger
九日
一名想要每天自律努力上进的在校大一生。
公告

我和博客一样,不给任何人推送。
但如果你访问,会知道我的很多。

力扣每日一题迁移至GitHub:

统计
文章:112 篇
分类:5 个
评论:1174 条
运行时长:4年229天
by yoniu.
微风忆夏