• Java练习day3

    一、验证回文串

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {
    public boolean judge(char ch){
        if((ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')){
            return true;
        }
    return false;
    }

    public boolean judge1(char ch1, char ch2){
        if(ch1 == ch2){         
            return true;
        }
    return false;
    }

    public boolean isPalindrome(String s) {
        int left = 0;
        int n = s.length();
        int right = n - 1;
        s = s.toLowerCase();
        while(left <= right){
            while(left < n && (judge(s.charAt(left)) == false)){
                ++left;
            }
            while(right >= 0 && (judge(s.charAt(right)) == false)){
                --right;
            }
            if(left > right){
                break;
            }
            if(judge1(s.charAt(left), s.charAt(right)) == false){
                return false;
            } 
            ++left;
            --right;
        }
    return true;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    3.知识点

    (1) Java如何将字符串从小写转化为大写，从大鞋转化为小写。
    (2) 回文的基本概念。
    (3) 利用双指针来解决问题。

    二、环形链表

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode head1 = head;
        ListNode head2 = head;
        while(head1 != null && head1.next != null){
            head1 = head1.next;
            if(head1 == head2){
                return true;
            }
            head1 = head1.next;
            if(head1 == head2){
                return true;
            }
            head2 = head2.next;
        }
    return false;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    3.知识点

    (1) 链表方面的题目
    (2) 使用快慢指针来解决问题。

    三、二叉树的前序遍历

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * 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 void dfs(TreeNode root, List<Integer> res){
        if(root == null){
            return ;
        }
        res.add(root.val);
        dfs(root.left, res);
        dfs(root.right, res);
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        dfs(root, res);
    return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    3.知识点

    (1) 树的先序遍历，记住是根左右的顺序。
    (2) 利用递归直接解决。

    四、二叉树的后序遍历

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * 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 void dfs(TreeNode root, List<Integer> res){
        if(root == null){
            return; 
        }
        dfs(root.left, res);
        dfs(root.right, res);
        res.add(root.val);
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList();
        dfs(root, res);
    return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    3.知识点

    (1) 树的后序遍历，记住是左右根的顺序。
    (2) 利用递归直接解决。

    五、相交链表

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode head1 = headA;
        ListNode head2 = headB;
        int flag1 = 0;
        int flag2 = 0;
        while(head1 != null && head2 != null){
            if(head1 == head2){
                return head1;
            }
            if(head1.next == null && flag1 == 0){
                head1 = headB;
                flag1 = 1;
            } else{
                head1 = head1.next;
            } 
            if(head2.next == null && flag2 == 0){
                head2 = headA;
                flag2 = 1;
            } else{
                head2 = head2.next;
            }
        }
    return null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    3.知识点

    (1) 使用双指针从两个链表头开始形式，然后到达终点后再到达另一条链表的头，再到另一条链表的结尾。
    (2) 如果该过程两个指针相遇则代表有公共结点。

    六、Excel表列名称

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuffer res = new StringBuffer();
        while(columnNumber != 0){
            columnNumber--;
            int num = columnNumber % 26;
            columnNumber /= 26;
            res.append((char)(num  + 'A'));
        }
    return res.reverse().toString();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    3.知识点

    (1) 比较充满数学性的题目。

    七、多数元素

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3.知识点

    (1) 排序，取中位数即可。

    八、Excel 表列序号

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {
    public int titleToNumber(String columnTitle) {
        int res = 0;
        int n = columnTitle.length();
        for(int i = 0; i < n; ++i){
            res *= 26;
            res += (columnTitle.charAt(i) - 'A' + 1);
        }
    return res;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    3.知识点

    (1) 和第七条一样，反向推理。

    九、颠倒二进制位

    1、题目链接

    点击跳转到题目位置

    2、代码

    public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for(int i = 0; i < 32; ++i){
            if(((1 << (31 - i)) & n) != 0){
                res += (1 << i);
            }
        }
    return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    3、知识点

    (1) 考察了关于位运算相关知识。

    十、位1的个数

    1、题目链接

    点击跳转到题目位置

    2、代码

    public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ret = 0;
        while(n != 0){
            n &= (n - 1);
            ret++;
        }
    return ret;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    3、知识点

    (1) 关于汉明编码的一些优化。

    十一、快乐数

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {

    public int get_num(int n){
        int sum = 0;
        while(n != 0){
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
    return sum;
    }

    public boolean isHappy(int n) {
        Set<Integer> hash1 = new HashSet<>();
        while(n != 1 && !hash1.contains(n)){
            hash1.add(n);
            n = get_num(n);
        }
    return n == 1;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    3、知识点

    (1) 利用哈希表，每次模拟过程，如果模拟的过程中到达1或者到达过去已经到达过的数字就停止。

    十二、移除链表元素

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * Definition for singly-linked list.
 * 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) {
        if(head == null){
            return head;
        }
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        head = dummyHead;
        while(head.next != null){
            if(head.next.val == val){
                head.next = head.next.next;
            } else{
                head = head.next;
            }
        }
    return dummyHead.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    3、知识点

    (1) 链表中增删改查中删的操作。

    十三、同构字符串

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> hash1 = new HashMap<Character, Character>();
        Map<Character, Character> hash2 = new HashMap<Character, Character>();
        for(int i = 0; i < s.length(); ++i){
            char ch1 = s.charAt(i);
            char ch2 = t.charAt(i);
            if(hash1.containsKey(ch1) && hash1.get(ch1) != ch2 
            || hash2.containsKey(ch2) && hash2.get(ch2) != ch1){
                return false;
            }
            hash1.put(ch1, ch2);
            hash2.put(ch2, ch1);
        }
        return true;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    3、知识点

    (1) 实际上是利用两个哈希表来判断函数是否是双射关系。

    十四、反转链表

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * Definition for singly-linked list.
 * 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 reverseList(ListNode head) {
        ListNode dummyHead = new ListNode();
        while(head != null){
            ListNode temp = head.next;
            head.next = dummyHead.next;
            dummyHead.next = head;
            head = temp;
        }
    return dummyHead.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    3、知识点

    (1) 链表的头插法得到相反的序列。

    十五、存在重复元素

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> hash1 = new HashSet<>();
        for(int i = 0; i < nums.length; ++i){
            if(hash1.contains(nums[i])){
                return true;
            }
            hash1.add(nums[i]);
        }
    return false;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    3、知识点

    (1) 使用哈希表解决。

  • 相关阅读:
    SAP 采购订单行项目屏幕增强(BADI)
    jQuery系列之选择器
    如何添加判断账号为手机号且为11位数；密码且为6位数；且有姓名；和选择男女；和上传图片（如有错误请指点）
    封装一个滑块控制灯光组件
    Django笔记四十四之Nginx+uWSGI部署Django以及Nginx负载均衡操作
    应用程序转换工具Unite mac中文版软件特点
    集成学习方法之随机森林-入门
    leetcode：415. 字符串相加（模拟竖式计算）
    TCP/IP协议
    Appium混合页面点击方法tap的使用
  • 原文地址：https://blog.csdn.net/qq_56086076/article/details/133513410