LeetCode算法题(一)
一、237. 删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
输入: head = [4,5,1,9], node = 5输出: [4,1,9]解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}自评：这个是基础链表题，修改节点指向即可。
二、104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。 示例：给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
if(root.left == null && root.right != null){
return 1 + maxDepth(root.right);
}
if(root.right == null && root.left != null){
return 1 + maxDepth(root.left);
}else{
int maxRight = maxDepth(root.right) + 1;
int maxLeft = maxDepth(root.left) + 1;
if(maxRight > maxLeft){
return maxRight;
}else{
return maxLeft;
}
}
}
}自评：关于和二叉树相关的使用递归解题比较容易，先设置退出条件，就是两边子树为空的情况下，递归体就是一直往下遍历，到最后为空的节点，返回最大深度，然后两者相互比较，得出最大深度。
三、344. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。 示例 1： 输入：["h","e","l","l","o"]输出：["o","l","l","e","h"] 示例 2： 输入：["H","a","n","n","a","h"]输出：["h","a","n","n","a","H"]
class Solution {
public void reverseString(char[] s) {
char temp;
int len = s.length-1;
for(int i = 0; i < len; i++, len--){
temp = s[i];
s[i] = s[len];
s[len] = temp;
}
}
}自评：设置两个指针，从头和尾来回交换，不断网中间靠近，知道两者相等。
四、171. Excel表列序号
给定一个Excel表格中的列名称，返回其相应的列序号。
例如：
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...示例 1: 输入: "A"输出: 1示例 2: 输入: "AB"输出: 28示例 3: 输入: "ZY"输出: 701
class Solution {
public int titleToNumber(String s) {
int len = s.length() - 1;
int n = len;
int num = 0;
for(int i = 0; i < len + 1; i++){
num += Math.pow(26, n) * (s.charAt(i) - 'A' + 1);
n--;
}
return num;
}
}自评：这是26尽进制转换为10进制问题，有两点：1.就是进制转换的时候，最高位代表的是26的几次方以及其他的位 2.谁乘这个26的几次方，这个通过A-B算出该为的数值。
五、108. 将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return toBST(nums, 0, nums.length-1);
}
public TreeNode toBST(int[] nums, int left, int right){
//结束条件，left==right时则为一个最后一个节点，也需要设置
if(left >right){
return null;
}
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = toBST(nums, left, mid - 1);
root.right = toBST(nums, mid + 1,right);
return root;
}
}自评：通过新建一个方法，进行遍历。每次遍历都需要将该数组的中间一个当做父节点，把该数组两边分开，左边继续遍历，右边继续遍历。
六、118.杨辉三角
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例: 输入: 5输出:[ [1], [1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
class Solution {
public List<List<Integer>> generate(int numRows) {
if(numRows == 0){
List<List<Integer>> bigList = new ArrayList();
return bigList;
}
List<List<Integer>> bigList = new ArrayList();
List<Integer> smallList1 = new ArrayList();
if(numRows == 1){
smallList1.add(1);
bigList.add(smallList1);
return bigList;
}
if(numRows == 2){
smallList1.add(1);
List<Integer> smallList2 = new ArrayList();
smallList2.add(1);
smallList2.add(1);
bigList.add(smallList1);
bigList.add(smallList2);
return bigList;
}
if(numRows >= 3){
smallList1.add(1);
List<Integer> smallList2 = new ArrayList();
smallList2.add(1);
smallList2.add(1);
bigList.add(smallList1);
bigList.add(smallList2);
for(int i = 3; i <= numRows; i++){
List<Integer> smallList = new ArrayList();
smallList.add(1);
for(int j = 2; j <= i-1; j++){
smallList.add(bigList.get(i-2).get(j-1) + bigList.get(i-2).get(j-2));
}
smallList.add(1);
bigList.add(smallList);
}
return bigList;
}
return null;
}
}自评：从第三行开始循环添加包括以后行的list
七、206.反转链表
反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL进阶:你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
}自评：通过递归一直到该链表的最后，在最后往前改变链表指向。
八、136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明： 你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？ 示例 1: 输入: [2,2,1]输出: 1示例 2: 输入: [4,1,2,1,2]输出: 4
class Solution {
public int singleNumber(int[] nums) {
int n = 0;
for(int i = 0; i < nums.length; i++){
n ^= nums[i];
}
return n;
}
}自评：需要异或运算，以及交换律，类似 4^2^3^2^3 这样的异或运算，换一下位置(2^2)^(3^3)^4。
九、412. Fizz Buzz
写一个程序，输出从 1 到 n 数字的字符串表示。
- 如果 n 是3的倍数，输出“Fizz”；
- 如果 n 是5的倍数，输出“Buzz”； 如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
示例： n = 15, 返回:[ "1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz"]
class Solution {
public List<String> fizzBuzz(int n) {
List<String> list = new ArrayList();
for(int i = 1; i <= n; i++){
if(i % 15 == 0){
list.add("FizzBuzz");
}else if(i % 3 == 0){
list.add("Fizz");
}else if(i % 5 == 0){
list.add("Buzz");
}else{
list.add(String.valueOf(i));
}
}
return list;
}
}自评：就是一般逻辑题，眼拙没看出有什么隐含知识。
十、169. 求众数
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1: 输入: [3,2,3]输出: 3示例 2: 输入: [2,2,1,1,1,2,2]输出: 2
class Solution {
public int majorityElement(int[] nums) {
int z = nums.length / 2;
for(int i = 0; i < nums.length; i++){
int count = 0;
for(int j = 0; j < nums.length; j++){
if(nums[i] == nums[j]){
count++;
}
}
if(count > z){
return nums[i];
}
}
return -1;
}
}力扣题解：
public int majorityElement(int[] nums) {
Stack<Integer> stack = new Stack<>();
for(int i:nums){
if(stack. empty()||i==stack.peek()){
stack.push(i);
}else{
stack.pop();
}
}
return stack.peek();
}
作者：linxinfu
链接：https://leetcode-cn.com/problems/two-sum/solution/shi-yong-zhan-lai-ji-yi-by-linxinfu/
需要一个栈，遍历数组时处理两种情况：
① 当数组元素等于栈顶元素或栈为空时入栈；
② 当元素不等于栈顶元素时则出栈。
最后的栈顶元素即为众数。自评：通过记录每一个出现的数量值来和n/2做比较，大于则直接返回。
腾讯云开发者
