Home

public int pivotIndex(int[] nums) {
        int sum=0,sumLeft = 0,sumRight = 0;

        for (int n:nums){
            sum = sum + n;
        }

        for (int i=0;i<nums.length;i++){
            if (i==0){
                sumLeft = 0;
            }else {
                sumLeft = sumLeft + nums[i-1];
            }
            sumRight = sum - sumLeft - nums[i];
            if (sumLeft==sumRight){
                return i;
            }
        }
        return -1;
    }

class Solution {
    public int pivotIndex(int[] nums) {
        int length = nums.length;
        int sum = 0, leftSum = 0;

        // 获取数组元素总和
        for (int num: nums) sum += num;

        // 遍历自变量
        for (int i = 0; i < length; i++){
            if (leftSum*2 == sum - nums[i]) return i;
            leftSum += nums[i];
        }
        return -1;
    }
}

public int reverse(int x) {
        long n = 0;
        while (x != 0) {
            n = n * 10 + x % 10;
            x = x / 10;
        }
        return (int)n == n ? (int)n:0;
    }

ublic int reverse(int x) {
      String a = Integer.toString(x);
      int b = 1;
      if(a.charAt(0) == '-') {
          a = a.substring(1);
          b = -1;
      }
      char[] chars = a.toCharArray();
      char[] chars1 = new char[chars.length];
      for (int i = chars.length - 1; i >= 0; i--) {
          chars1[chars.length - 1 - i] = chars[i];
      }
      Long aLong = Long.valueOf(new String(chars1));
      if(aLong > Integer.MAX_VALUE || aLong < Integer.MIN_VALUE) {
          return 0;
      }
      return (int) (aLong * b);

  }

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }

        // 很妙的两个地方 carry 的设置 和 carry >0 的判断 🌟🌟🌟🌟🌟
        // 记录和大于10时 +1
        // carry >0 当大于10 则向前进 1
        int carry = 0;
        ListNode head = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
            int sum = carry;
            sum += stack1.isEmpty()? 0: stack1.pop();
            sum += stack2.isEmpty()? 0: stack2.pop();
            ListNode node = new ListNode(sum % 10);
            node.next = head;
            head = node;
            carry = sum / 10;
        }
        return head;
    }
}

public lass Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for(int i=0;i<prices.length;i++) {
            for(int j=i+1;j<prices.length;j++) {
                int subtract = prices[i]-prices[j];
                if(subtract<0&&subtract<res) {
                    res = subtract;
                }
            }
        }
        return -res;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        // 很巧妙的设计 设计最大值和最小值的比较
        int minprice = Integer.MAX_VALUE;
        int maxprice = 0;
        for(int price:prices){
            minprice = Math.min(minprice,price);
            maxprice = Math.max(maxprice,price-minprice);
        }
        return maxprice;
    }
}

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
        int[] res = new int[(r + 1) * (b + 1)];
        while(true) {
            for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right.
            if(++t > b) break;
            for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom.
            if(l > --r) break;
            for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left.
            if(t > --b) break;
            for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top.
            if(++l > r) break;
        }
        return res;
    }
}

public interface HandlerMethodArgumentResolver {
    boolean supportsParameter(MethodParameter var1);

    @Nullable
    Object resolveArgument(MethodParameter var1, @Nullable ModelAndViewContainer var2, NativeWebRequest var3, @Nullable WebDataBinderFactory var4) throws Exception;
}

import org.springframework.core.MethodParameter;
import org.springframework.web.bind.support.WebDataBinderFactory;
import org.springframework.web.context.request.NativeWebRequest;
import org.springframework.web.method.support.HandlerMethodArgumentResolver;
import org.springframework.web.method.support.ModelAndViewContainer;

/**
 * 用于绑定@CurrentUser的方法参数解析器
 *
 * @author lism
 */
public class CurrentUserMethodArgumentResolver implements HandlerMethodArgumentResolver {

    public CurrentUserMethodArgumentResolver() {
    }

    @Override
    public boolean supportsParameter(MethodParameter parameter) {
        if (parameter.getParameterType().isAssignableFrom(UserBean.class) && parameter.hasParameterAnnotation(CurrentUser.class)) {
            return true;
        }
        return false;
    }

    @Override
    public Object resolveArgument(MethodParameter parameter, ModelAndViewContainer mavContainer, NativeWebRequest webRequest, WebDataBinderFactory binderFactory) throws Exception {
        CurrentUser currentUserAnnotation = parameter.getParameterAnnotation(CurrentUser.class);
        //从Session 获取用户
        Object object = webRequest.getAttribute(currentUserAnnotation.value(), NativeWebRequest.SCOPE_SESSION);
//从  accessToken获得用户信息
       if (object == null) {
            String token = webRequest.getHeader("Authorization");
            if (token == null) {
                token = webRequest.getParameter("accessToken");
            }
            //为了测试先写死用户名
            //TODO: 取真实用户
            return new UserBean(1L,"admin");
        }
        return object;
    }
}

import java.lang.annotation.*;

/**
 * <p>绑定当前登录的用户</p>
 * <p>不同于@ModelAttribute</p>
 *
 * @author lism
 */
@Target({ElementType.PARAMETER})
@Retention(RetentionPolicy.RUNTIME)
@Documented
public @interface CurrentUser {

    /**
     * 当前用户在request中的名字
     *
     * @return
     */
    String value() default "user";

}

@RestController
@RequestMapping(value = "/test")
public class TestController  {

    /**
     * 根据name查询
     *
     * @param request
     * @return
     */
    @RequestMapping(value = "/testCurrentUser", method = RequestMethod.POST, produces = "application/json", consumes = "application/json")
    @ResponseBody
    public void test(@CurrentUser UserBean userBean, @RequestBody SubjectRequest request) {
        String createdBy = userBean.getUsername();
        log.info(createdBy);
    }
}

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.io.Serializable;

@Data
@NoArgsConstructor
@AllArgsConstructor
public class UserBean implements Serializable {
    private Long id;
    private String username;
}

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        if (len == 1) return nums[0];

        int[] dp = new int[len];

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[len - 1];
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

private void bubbleSort(int[] nums) {
    for (int i = nums.length - 1; i >= 1; i--) { // 冒泡得到n-1个最大值
        for (int j = 1; j <= i; j++) {
            if (nums[j-1]>nums[j])
                swap(nums, j, j-1);           // 交换得到较大值
        }
    }
}

private void selectionSort(int[] nums) {
    for (int i = nums.length - 1; i > 0; i--) {
        int maxIndex = 0;         // 最大元素的位置
        for (int j = 0; j <= i; j++) {
            if (nums[maxIndex]<nums[j]) {
                maxIndex = j;
            }
        }
        swap(nums, maxIndex, i);   // 把这个最大的元素移到最后
    }
}

private void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {   // 从第二个元素开始遍历
        int j = i;
        while (j>0&&nums[j]<nums[j-1]) {     // 将当前元素移动到合适的位置
            swap(nums, j, j-1);
            j--;
        }
    }
}

private void shellSor2(int[] nums) {
    int gap = nums.length >> 1;
    while (gap > 0) {
        for (int i = 0; i < gap; i++) {                        // 对每个子序列进行排序
            for (int j = i+gap; j < nums.length; j+=gap) {     // 插入排序的部分
                int temp = j;
                while (temp > i && nums[temp] < nums[temp-gap]) {
                    swap(nums, temp, temp-gap);
                    temp -= gap;
                }
            }
        }
        gap >>= 1;
    }
}

private void mergeSort(int[] nums, int left, int right) {  // 需要左右边界确定排序范围
    if (left >= right) return;
    int mid = (left+right) / 2;

    mergeSort(nums, left, mid);                           // 先对左右子数组进行排序
    mergeSort(nums, mid+1, right);

    int[] temp = new int[right-left+1];                   // 临时数组存放合并结果
    int i=left,j=mid+1;
    int cur = 0;
    while (i<=mid&&j<=right) {                            // 开始合并数组
        if (nums[i]<=nums[j]) temp[cur] = nums[i++];
        else temp[cur] = nums[j++];
        cur++;
    }
    while (i<=mid) temp[cur++] = nums[i++];
    while (j<=right) temp[cur++] = nums[j++];

    for (int k = 0; k < temp.length; k++) {             // 合并数组完成，拷贝到原来的数组中
        nums[left+k] = temp[k];
    }
}

private void quickSort(int[] nums, int left, int right) {
    if (left >= right) return;
    int lo = left+1;               // 小于分界点元素的最右侧的指针
    int hi = right;                // 大于分界点元素的最左侧的指针
    while (lo<=hi) {
        if (nums[lo]>nums[left]) { // 交换元素确保左侧指针指向元素小于分界点元素
            swap(nums, lo, hi);
            hi--;
        } else {
            lo++;
        }
    }
    lo--;                          // 回到小于分界点元素数组的最右侧
    swap(nums, left, lo);          // 将分界点元素移到左侧数组最右侧
    quickSort2(nums, left, lo-1);
    quickSort2(nums, lo+1, right);
}

private void quickSort(int[] nums, int left, int right) {
    if (left>=right) return;
    int cur = left + 1;                   // 从左侧第二个元素开始
    int lo = left;                        // 分界点为第一个元素
    while (cur <= right) {
        if (nums[cur] <= nums[left]) {    // 交换位置保证lo的左侧都是小于num[left]
            swap(nums, lo+1, cur);
            lo ++;
        }
        cur++;
    }
    swap(nums, left, lo);                 // 把分界点元素移动到新的分界位置
    quickSort(nums, left, lo-1);
    quickSort(nums, lo+1, right);
}

private void heapSort(int[] nums) {
    heapify(nums);                                 // 新建一个最大堆
    for (int i = nums.length - 1; i >= 1; i--) {
        swap(nums, 0, i);                       // 弹出最大堆的堆顶放在最后
        rebuildHeap(nums, 0,i-1);          // 重建最大堆
    }
}

private void heapify(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int par = (i-1)>>1;                       // 找到父节点
        int child = i;                            // 定义子节点
        while (child>0&&nums[par]<nums[child]) {  // 从子节点到根节点构建最大堆
            swap(nums, par, child);
            child = par;
            par = (par-1) >> 1;
        }
    }
}

private void rebuildHeap(int[] nums, int par, int last) {
    int left = 2*par+1;                           // 左子节点
    int right = 2*par+2;                          // 右子节点
    int maxIndex = left;

    if (right<=last && nums[right]>nums[left]) {  // 找到最大子节点
        maxIndex = right;
    }

    if (left<=last && nums[par] < nums[maxIndex]) {// 和最大子节点比较
        swap(nums, par, maxIndex);                 // 互换到最大子节点
        rebuildHeap(nums, maxIndex, last);         // 重建最大子节点代表的子树
    }
}

private int[] bstSort(int[] nums) {
    TreeNode root = new TreeNode(nums[0]);   // 构建根节点
    for (int i = 1; i < nums.length; i++) {  // 将所有的元素插入到二叉搜索树中
        buildTree(root, nums[i]);
    }
    inorderTraversal(root, nums, new int[1]);// 中序遍历获取二叉树中的所有节点
    return nums;
}

private void inorderTraversal(TreeNode node, int[] nums, int[] pos) {
    if (node == null) return;
    inorderTraversal(node.left, nums, pos);
    nums[pos[0]++] = node.val;
    inorderTraversal(node.right, nums, pos);
}

private void buildTree(TreeNode node, int num) {
    if (node == null) return;
    if (num >= node.val) {                   // 插入到右子树中
        if (node.right == null) {
            node.right = new TreeNode(num);
        } else {
            buildTree(node.right, num);
        }
    } else {                                 // 插入到左子树中
        if (node.left == null) {
            node.left = new TreeNode(num);
        } else {
            buildTree(node.left, num);
        }
    }
}

static class TreeNode {   // 树节点的数据结构
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

private void countSort(int[] nums) {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int num : nums) {            // 找到最大最小值
        min = Math.min(min, num);
        max = Math.max(max, num);
    }
    int[] count = new int[max-min+1]; // 建立新数组
    for (int num : nums) {            // 统计每个元素出现频率
        count[num-min]++;
    }
    int cur = 0;
    for (int i = 0; i < count.length; i++) {  // 根据出现频率把计数数组中的元素放回到旧数组中
        while (count[i]>0) {
            nums[cur++] = i+min;
            count[i]--;
        }
    }
}

private void bucketSort(int[] nums) {
    int INTERVAL = 100;               // 定义桶的大小
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int num : nums) {            // 找到数组元素的范围
        min = Math.min(min, num);
        max = Math.max(max, num);
    }
    int count = (max - min + 1);      // 计算出桶的数量
    int bucketSize = (count % INTERVAL == 0) ?( count / INTERVAL) : (count / INTERVAL+1);
    List<Integer>[] buckets = new List[bucketSize];
    for (int num : nums) {            // 把所有元素放入对应的桶里面
        int quotient = (num-min) / INTERVAL;
        if (buckets[quotient] == null) buckets[quotient] = new ArrayList<>();
        buckets[quotient].add(num);
    }
    int cur = 0;
    for (List<Integer> bucket : buckets) {
        if (bucket != null) {
            bucket.sort(null);       // 对每个桶进行排序
            for (Integer integer : bucket) {  // 还原桶里面的元素到原数组
                nums[cur++] = integer;
            }
        }
    }
}

private void radixSort(int[] nums) {
    int max = -1;
    int min = 1;
    for (int num : nums) {         // 计算最大最小值
        max = Math.max(max, num);
        min = Math.min(min, num);
    }
    max = Math.max(max, -min);     // 求得绝对值最大的值
    int digits = 0;
    while (max > 0) {              // 计算绝对值最大的值的位数
        max /= 10;
        digits++;
    }
    List<Integer>[] buckets = new List[19]; // 建一个包含所有位数的数组
    for (int i = 0; i < buckets.length; i++) {
        buckets[i] = new ArrayList<>();
    }
    int pos;
    int cur;
    for (int i = 0, mod = 1; i < digits; i++, mod*=10) { // 对十进制每一位进行基数排序
        for (int num : nums) {                 // 扫描数组将值放入对应的桶
            pos = (num / mod) % 10;
            buckets[pos+9].add(num);
        }
        cur = 0;
        for (List<Integer> bucket : buckets) { // 将桶内元素放回到数组里面
            if (bucket!=null) {
                for (Integer integer : bucket) {
                    nums[cur++] = integer;
                }
                bucket.clear();                // 将桶清空
            }
        }
    }
}