11.二进制中1的个数
题目描述：输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
思路：
法1：位运算：使用位运算进行无符号右移>>>，注：符号右移>>，负数时高位补1。
法2：位运算技巧：直接统计1的个数，n & (n - 1)：去掉n从低位开始的第一个1。
代码：
public class Solution { // 法1：无符号右移`>>>` public int NumberOf1(int n) { int ans = 0; while (n != 0) { if ((n & 1) == 1) ans++; n >>>= 1; } return ans; } // 法2：技巧：`n & (n - 1)` public int NumberOf1_1(int n) { int ans = 0; while (n != 0) { n &= (n - 1); ++ans; } return ans; } }
12.数值的整数次方
题目描述：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方，base和exponent不同时为0。
思路：使用快速幂算法：递归和迭代两种实现。
法1：递归：递归出口指数为0，递归单层逻辑指数二分，注意：递归返回区分指数奇偶两种情况。
法2：迭代：关键是通过指数和底数的变换，找到对结果起贡献的值，并累乘。
代码：
public class Solution { // 法1：递归版本 public double Power(double base, int exponent) { return exponent >= 0 ? recur(base, exponent) : 1 / recur(base, -exponent); } public double recur(double base, int exponent) { if (exponent == 0) return 1.0; // 单层逻辑 double y = recur(base, exponent / 2); return exponent % 2 == 0 ? y * y : y * y * base; } // 法2：迭代版本 public double Power_1(double base, int exponent) { return exponent >= 0 ? iterate(base, exponent) : 1 / iterate(base, -exponent); } public double iterate(double base, int exponent) { // 初始贡献值 double ans = 1; while (exponent > 0) { if ((exponent & 1) == 1) { ans *= base; } base *= base; exponent >>= 1; } return ans; } }
13.调整数组顺序
题目描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路：本题关键是如何保证调整后的相对位置不改变。
法1：要保证相对位置，必须顺序移动，找到偶数区间的起始点，然后整体右移填充空格。使用双指针，但时间复杂度O(n^2)。
法2：空间换时间：开辟相同大小的数组，先统计奇数个数，然后遍历原数组，依次填入辅助数组。
代码：
public class Solution { // 法1：顺序双指针 public int[] reOrderArray (int[] array) { int n = array.length; if (n <= 1) return array; int l = 0, r; while (l < n) { while (l < n && !isEven(array[l])) { l++; } // 1.偶数区间的起始位置 r = l + 1; while (r < n && isEven(array[r])) { r++; } // 2.移动区间，填充数值 if (r < n) { // 3.记录偶数区间的下一个奇数 int tmp = array[r]; for (int i = r - 1; i >= l; --i) { array[i + 1] = array[i]; } // 4.填充偶数区间的前一个空格 array[l++] = tmp; } else { break; } } return array; } // 法2：空间换时间 public int[] reOrderArray (int[] array) { int n = array.length; if (array == null || n == 0) return array; int[] ans = new int[n]; int oddCount = 0; // 统计奇数个数 for (int num : array) { if (!isEven(num)) oddCount++; } // 复用oddCount作为偶数区间的起点 int oddBegin = 0; for (int i = 0; i < n; ++i) { if (!isEven(array[i])) { ans[oddBegin++] = array[i]; } else { ans[oddCount++] = array[i]; } } return ans; } // 判断i奇偶 public boolean isEven(int i) { return (i & 1) == 0 ? true : false; } }
14.链表中的倒数第k个点
题目描述：输入一个链表，输出该链表中倒数第k个结点。
思路：本题关键点：保证k之后的节点保持不变。若反转链表，找到节点后，必须再反转过来。这里我们采用先计算链表的长度n，遍历链表，找n - k + 1对应的节点。
代码：
public class Solution { // 求n - k + 1对应的节点 public ListNode FindKthToTail (ListNode pHead, int k) { int target = length(pHead) - k + 1; int i = 1; while (pHead != null) { if (i == target) return pHead; pHead = pHead.next; i++; } return null; } // 计算链表长度 public int length(ListNode pHead) { int len = 0; while (pHead != null) { len++; pHead = pHead.next; } return len; } }
15.反转链表
题目描述：输入一个链表，反转链表后，输出新链表的表头。
思路：通过递归和迭代实现。
法1：递归：返回值（反转后的表头）；终止条件（head == null || head.next == null）；递归逻辑：改变指针
法2：迭代：记录下一个节点；更改连接；改变指针。
代码：
public class Solution { // 法1：递归 public ListNode ReverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = ReverseList(head.next); // 递归逻辑：改变指针 head.next.next = head; head.next = null; return newHead; } // 法2：迭代实现 public ListNode ReverseList(ListNode head) { if (head == null) return head; ListNode pre = null, next; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } }
