一、验证回文串
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;}
}
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;}
}
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;}
}
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;}
}
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;}
}
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();}
}
3.知识点
(1) 比较充满数学性的题目。
七、多数元素
1、题目链接
点击跳转到题目位置
2、代码
class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}
}
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;}
}3.知识点
(1) 和第七条一样，反向推理。
九、颠倒二进制位
1、题目链接
点击跳转到题目位置
2、代码
public class Solution {// you need treat n as an unsigned valuepublic 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;}
}
3、知识点
(1) 考察了关于位运算相关知识。
十、位1的个数
1、题目链接
点击跳转到题目位置
2、代码
public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int ret = 0;while(n != 0){n &= (n - 1);ret++;}return ret;}
}
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;}
}
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;}
}
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;}
}
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;}
}
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;}
}
3、知识点
(1) 使用哈希表解决。
