LeeCode题库数据结构
Solution136只出现一次的数字、Solution137只出现一次的数字Ⅱ、Solution20有效括号、Solution83删除排序链表中重复的元素、Solution203移除指定相同元素、Solution206反转链表、Solution232栈实现队列.
Solution136只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
要求不使用额外空间
不使用额外空间就考虑位运算
class Solution {
public int singleNumber(int[] nums) {
int n = 0;
for (int num : nums) {
n ^= num;
}
return n;
}
}
Solution137只出现一次的数字Ⅱ
给你一个整数数组 nums
解题思路：
如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 33 的倍数。
因此，统计所有数字的各二进制位中 11 的出现次数，并对 33 求余，结果则为只出现一次的数字。
class Solution {
public int singleNumber(int[] nums) {
int one = 0, two = 0, three;
for (int num : nums) {
// two的相应的位等于1，表示该位出现2次
two |= (one & num);
// one的相应的位等于1，表示该位出现1次
one ^= num;
// three的相应的位等于1，表示该位出现3次
three = (one & two);
// 如果相应的位出现3次，则该位重置为0
two &= ~three;
one &= ~three;
}
return one;
}
}
Solution20有效括号
判断有效括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。 public class S20有效括号 {
//异或 只要最后输出是空 即有效 不过没有考虑复杂度及特殊情况的出现
public boolean isValid(String s) {
int length = s.length() / 2;
for (int i = 0; i < length; i++) {
s = s.replace("()", "").replace("{}", "").replace("[]", "");
}
return s.length() == 0;
}
}
建立一个新的栈，然后遍历字符串的字符，进行比较 时间复杂度低
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for(char c: s.toCharArray()){
if(c=='(')stack.push(')');
else if(c=='[')stack.push(']');
else if(c=='{')stack.push('}');
else if(stack.isEmpty()||c!=stack.pop())return false;
}
return stack.isEmpty();
}
}
Solution83删除排序链表中重复的元素
给定一个已排序的链表的头
head
， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
两种思路
public class Solution83移除重复元素 {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode left = head;
ListNode right = left.next;
while (right != null) {
if (left.val == right.val) {
left.next = right.next;
right.next = null;
right = left.next;
} else {
left = left.next;
right = left.next;
}
}
return head;
}
public ListNode deleteDuplicates01(ListNode head) {
if (head == null) return head;
ListNode cur = new ListNode(Integer.MIN_VALUE);
cur.next = head;
ListNode resNode = cur;
while (cur.next != null) {
if (cur.val != cur.next.val) {
cur = cur.next;
} else
cur.next = cur.next.next;
}
return resNode.next;
}
}
Solution203移除指定相同元素
两种方式
//删除指定相同元素
public class Solution83删除重复元素 {
//设虚拟头结点避免头结点就是要删的
public ListNode removeElements(ListNode head, int val) {
ListNode header = new ListNode(0);
header.next = head;
ListNode cur = header;
while(cur.next != null){
if(cur.next.val == val ){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return header.next;
}
//递归
class Solution
{
public ListNode removeElements(ListNode head, int val)
{
if (head == null)
return head;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}
}
Solution206反转链表
本质思想移动头结点过去就是反转了
//反转链表
public class Solution206反转 {
//递归方法 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
public ListNode reverseList(ListNode head) {
if (head == null)
return head;
if (head.next == null)
return head;
ListNode last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
}
//迭代
public ListNode reverseList01(ListNode head) {
if (head == null)
return head;
ListNode b, c;
c = head;
head = null;
while (c != null) {
b = c.next;//先在前面占个位置
c.next = head;//回头看看
head = c;//自已变成头
c = b;//继续向前
}
return head;
}
}
Solution232栈实现队列
//请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
//
//实现 MyQueue 类：
//
//void push(int x) 将元素 x 推到队列的末尾
//int pop() 从队列的开头移除并返回元素
//int peek() 返回队列开头的元素
//boolean empty() 如果队列为空，返回 true ；否则，返回 false
public class S232栈实现队列 {
private Stack<Integer> a;// 输入栈
private Stack<Integer> b;// 输出栈
public S232栈实现队列() {
a = new Stack<>();
b = new Stack<>();
}
public void push(int x) {
a.push(x);
}
public int pop() {
// 如果b栈为空，则将a栈全部弹出并压入b栈中，然后b.pop()
if (b.isEmpty()) {
while (!a.isEmpty()) {
b.push(a.pop());
}
}
return b.pop();
}
public int peek() {
if (b.isEmpty()) {
while (!a.isEmpty()) {
b.push(a.pop());
}
}
return b.peek();
}
public boolean empty() {
return a.isEmpty() && b.isEmpty();
}
}