发表于 | 分类于 ，

题目：

　　编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
　　不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

思路：

　　循环交换两端字符即可，注意可以使用异或运算交换增加运算效率，同时也可以使用递归实现。

代码：

循环：

1
2
3
4
5
6
7
8
9
public void reverseString(char[] s) {
       int l = 0;
       int r = s.length - 1;
       while(l < r) {
       	s[l] ^= s[r];
       	s[r] ^= s[l];
       	s[l++] ^= s[r--];
       }
   }

复杂度分析及总结：

循环：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

发表于 | 分类于 ，

题目：

　　给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路：

　　此题最开始无法想出思路。结合官方解答后做出。同时递归法难想到，比较巧妙，难理解。

代码：

递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode236 {
	private TreeNode LCA;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        recurseTree(root, p, q);
        return LCA;
    }
    public boolean recurseTree(TreeNode root, TreeNode p, TreeNode q) {
    	if (root == null) {
			return false;
		}
    	int left = recurseTree(root.left, p, q)?1:0;
    	int right = recurseTree(root.right, p, q)?1:0;
    	int mid = (root == p || root == q)?1:0;
    	if (left + right + mid >= 2) {
			this.LCA = root;
		}
    	return (left + right + mid) > 0;
    }
}

复杂度分析及总结：

递归：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

发表于 | 分类于 ，

题目：

　　给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

思路：

　　二叉树一般会用到递归或遍历。结合此题，由于该树是二叉搜索树，最近公共祖先节点的特点即其节点的值大于
等于p（左边）节点的值，小于等于q（右边）节点的值。由此可以写出递归或者循环代码。

代码：

1.递归：

1
2
3
4
5
6
7
8
9
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if (p.val > root.val && q.val > root.val) {
	return lowestCommonAncestor(root.right, p, q);
}else if (p.val < root.val && q.val < root.val) {
	return lowestCommonAncestor(root.left, p, q);
}else {
	return root;
}
  }

2.循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
 public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
 	TreeNode node = root;
 	while(node != null) {
 		if (p.val > node.val && q.val > node.val) {
	node = node.right;
}else if (p.val < node.val && q.val < node.val) {
	node = node.left;
}else {
	return node;
}
 	}
 	throw new RuntimeException("输入不合法");
 }

复杂度分析及总结：

1.递归：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

2.循环：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

发表于 | 分类于 ，

题目：

　　给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

思路：

　　与2相关的数字常常会用到位运算。2的幂转为2进制数后有一个特点，即仅有一位为1，故可利用此特点来判断一个数是否为2的幂。

代码：

位运算：

1
2
3
public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n-1))==0;
}

发表于 | 分类于 ，

题目：

　　给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

思路：

　　题目中二叉树为二叉搜索树，很容易想到将数中序遍历，得到的顺序即为排序顺序，从而很容易就得到第k小的元素。而实现中序遍历
有递归和循环两种写法。

代码：

1.递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private int count = 0;
private int res = 0;
// 递归
   public int kthSmallest(TreeNode root, int k) {
       count = k;
       inTraverse(root);
       return res;
   }
   public void inTraverse(TreeNode root) {
   	if (root != null) {
   		inTraverse(root.left);
   		count--;
   		if (count == 0) {
			res = root.val;
		}
   		inTraverse(root.right);
	}
}

2.排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 public int kthSmallest1(TreeNode root, int k) {
 	Deque<TreeNode> stack = new LinkedList<>();
 	int count = 0;
 	TreeNode node = root;
 	while(node != null || !stack.isEmpty()) {
 		while(node != null) {
 			stack.push(node);
 			node = node.left;
 		}
 		if (!stack.isEmpty()) {
	node = stack.pop();
	count++;
	if (count == k) {
		return node.val;
	}
	node = node.right;
}
 	}
 	throw new RuntimeException("参数错误");
 }

复杂度分析及总结：

1.递归：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

2.循环：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

总结：

　　注意递归写法中需要利用全局变量记录第k小的值。

发表于 | 分类于 ，

题目：

　　给定一个整数数组，判断是否存在重复元素。
　　如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

思路：

　　涉及数组中元素的次数，一般会想到利用哈希表记录元素个数。同时此题也可先排序，再比较相邻元素是否有相同。

代码：

1.哈希表：

1
2
3
4
5
6
7
8
9
10
 public boolean containsDuplicate(int[] nums) {
     Set<Integer> set = new HashSet<>();
     for(int num:nums) {
     	if (set.contains(num)) {
	return true;
}
     	set.add(num);
     }
     return false;
 }

2.排序：

1
2
3
4
5
6
7
8
9
 public boolean containsDuplicate1(int[] nums) {
 	Arrays.sort(nums);
 	for(int i = 0;i < nums.length-1;i++) {
 		if (nums[i] == nums[i+1]) {
	return true;
}
 	}
 	return false;
 }

复杂度分析及总结：

1.哈希表：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

2.排序：

　　时间复杂度：
　　　　O(nlogn)。
　　空间复杂度：
　　　　O(1)。

发表于 | 分类于 ，

题目：

　　在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

思路：

　　1.最直接的思路就是排序后取k-1索引处的值
　　2.利用快排中的partition函数，partition函数可以在O(n)时间复杂度内找出数组中第k大的数字
　　3.利用最小堆。设置最小堆的大小为k，循环将数组中的值加入最小堆，当超如k容量时取出最小值，这样完成循环后堆顶即为第k大的数。

代码：

2.partition函数：

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
   public int findKthLargest(int[] nums, int k) {
   	int low = 0;
   	int high = nums.length - 1;
       int index = partition(nums, low, high);
       while(index != nums.length-k) {
       	if (index > nums.length-k) {
			index = partition(nums, low, index-1);
		}else {
			index = partition(nums, index+1, high);
		}
       }
       return nums[index];
   }
    public static int partition(int[] nums,int low,int high) {
	int x = nums[low];
	int i = low;
	int j = high;
	while(i < j) {
		while(nums[j] >= x && i < j) {
			j--;
		}
		if (i < j) {
			nums[i] = nums[j];
			i++;
		}
		while(nums[i] <= x && i < j) {
			i++;
		}
		if (i < j) {
			nums[j] = nums[i];
			j--;
		}
	}
	nums[i] = x;
	return i;
}

2.最小堆

1
2
3
4
5
6
7
8
9
10
 public int findKthLargest1(int[] nums, int k) {
 	PriorityQueue<Integer> heap = new PriorityQueue<>();
 	for(int n:nums) {
 		heap.add(n);
 		if (heap.size() > k) {
	heap.poll();
}
 	}
 	return heap.poll();
 }

复杂度分析及总结：

1.partition函数：

　　时间复杂度：
　　　　O(n)。？？？
　　空间复杂度：
　　　　O(1)。

2.最小堆：

　　时间复杂度：
　　　　O(nlogk)。？？？
　　空间复杂度：
　　　　O(k)。
　　总结：
　　　　注意Java中堆可以用PriorityQueue实现。

发表于 | 分类于 ，

题目：

　　用循环和递归的方法实现反转链表

思路：

　　由于在反转链表的过程中链表会断开，所以需要定义多指针，以记录后续节点。

代码：

1.循环方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  public ListNode reverseList(ListNode head) {
      if (head == null || head.next == null) {
	return head;
}
      ListNode curNode = head;
      ListNode preNode = null;
      ListNode postNode = curNode.next;
      while(curNode != null) {
      	curNode.next = preNode;
      	preNode = curNode;
      	curNode = postNode;
      	if (postNode != null) {
      		postNode = postNode.next;
	}       	
      }
      return preNode;
  }

2.递归方法：

1
2
3
4
5
6
7
8
9
  public ListNode reverseList1(ListNode head) {
  	if (head == null || head.next == null) {
	return head;
}
  	ListNode p = reverseList1(head.next);
      head.next.next = head;
      head.next = null;
      return p;
  }

复杂度分析及总结：

1.循环方法：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

2.递归方法：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。由于递归栈可能会达到n。
　　总结：
　　　　递归方法较巧妙，它使反转链表从表尾开始，不需要多余指针防止链表断开。

发表于 | 分类于 ，

题目：

　　给定一个大小为n的数组，找到其中的众数。众数是指在数组中出现次数大于n/2的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。

思路：

　　此题解法众多。
1.数据出现次数问题想到可以使用哈希表
2.可先对数组排序，然后去n/2位置处的数据即为众数
3.利用

代码：

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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
			return null;
		}
        ListNode node1 = headA;
        ListNode node2 = headB;
        int countA = 0;
        int countB = 0;
        while(node1 != null) {
        	countA++;
        	node1 = node1.next;
        }
        while(node2 != null) {
        	countB++;
        	node2 = node2.next;
        }
        ListNode node3 = headA;
        ListNode node4 = headB;
        if (countA > countB) {
			for(int i = 0;i < countA - countB;i++) {
				node3 = node3.next;
			}
		}else {
			for(int i = 0;i < countB - countA;i++) {
				node4 = node4.next;
			}
		}
        while(node3 != null && node4 != null) {
        	if (node3 == node4) {
				return node3;
			}
        	node3 = node3.next;
        	node4 = node4.next;
        }
        return null;
    }

复杂度分析及总结：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

发表于 | 分类于 ，

题目：

　　编写一个程序，找到两个单链表相交的起始节点。

思路：

　　首先需要画出示例图，方便找思路。链表问题一般需要操作很多指针，该题可以使用双指针，
但需要保持两个链表上的指针距离尾指针的距离相同。因此想到需要首先统计出两链表的长度，然后
让长链表的指针先走到和短链表的指针相同的位置。

代码：

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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
			return null;
		}
        ListNode node1 = headA;
        ListNode node2 = headB;
        int countA = 0;
        int countB = 0;
        while(node1 != null) {
        	countA++;
        	node1 = node1.next;
        }
        while(node2 != null) {
        	countB++;
        	node2 = node2.next;
        }
        ListNode node3 = headA;
        ListNode node4 = headB;
        if (countA > countB) {
			for(int i = 0;i < countA - countB;i++) {
				node3 = node3.next;
			}
		}else {
			for(int i = 0;i < countB - countA;i++) {
				node4 = node4.next;
			}
		}
        while(node3 != null && node4 != null) {
        	if (node3 == node4) {
				return node3;
			}
        	node3 = node3.next;
        	node4 = node4.next;
        }
        return null;
    }

复杂度分析及总结：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。